프로세스 상태, CPU 스케줄러

프로세스 상태

running state : 현재 cpu에서 실행 상태

ready state : cpu에서 실행 가능한 상태(실행 대기 상태)

block state : 특정 이벤트 발생 대기 상태( ex : 프린팅 완료)

 

스케줄러란

스케줄러는 레디 큐에 존재하는 프로세스들을 특정한 우선순위 기반으로 CPU를 할당받게 해주는 역할을 함

링크드 리스트, 해쉬 리스트, 비트 맵, 레드 블랙 트리(리눅스)로 구현

 

스케줄링 목적

• 처리량 최대화 - 스케줄링 규칙은 단위 시간당 가능하면 많은 프로세스가 서비스를 받을 수 있도록 해야 함
• 자원 활용도 최대화 - 시스템 자원을 부지런히 사용 해야 함
• 무기한 연기 회피 - 프로세스들이 서비스를 받으려고 한 없이 대기하면 안됨
• 우선순위 강화 - 시스템이 프로세스에 우선순위를 부여할 경우 스케줄링 메커니즘은 우선순위가 더 높은 프로세스를 선호 해야 한다
• 오버헤드(처리를 하기 위해 들어가는 간접적인 처리 시간, 메모리) 최소화 - 오버헤드는 자원 낭비
• 예측 가능성 보장 - 프로세스 반응 시간에 대한 통계적인 변량을 최소화함으로써 시스템은 프로세스가 예측 가능한 수준으로 서비스함을 보장

 

스케줄링 수준

• 고수준 스케줄링 : 어떤 작업이 시스템에 들어갈 것인지 결정
• 중간 수준 스케줄링 : 어떤 프로세스가 프로세서를 얻으려고 경쟁할 수 있는지 결정
• 저수준 스케줄링 : 정책은 활성화된 프로세스 중 어떤 프로세스에 프로세스를 할당할지 결정

 

선점형/비선점형 스케줄링

• 비선점형 스케줄링 : 
  • 시스템이 일단 프로세스를 어떤 프로세스에 할당한 경우 프로세스로부터 프로세서를 강제로 빼앗지 않는다
  • 비선점형 스케줄링 규칙에서는 각 프로세스가 프로세서를 할당받으면 작업을 완료할 때까지 혹은 프로세스가 자발적으로 프로세서를 반납할때까지 프로세서에서 실행 할 수 있다
• 선점형 스케줄링
  • 프로세서에서 프로세스가 실행 중일 때 시스템이 해당 프로세서를 빼앗을 수 없다
  • 문맥전환을 일으킬 수 있다

 

스케줄링 알고리즘

비선점 스케줄링

• FCFS(First Come, First Served)
  • CPU를 처음 요구한 프로세스가 CPU를 처음 사용
  • FIFO(First in First Out) 큐 자료 구조 사용해 구현
  • CPU를 사용하고 있는 프로세스 자기 자신이 CPU를 놓아줄 때까지 CPU를 다른 프로세스에게 양보하지 않음
  • 콘보이 효과 불러 일으킬수 있음
    • 콘보이 효과란 CPU를 매우 오래 사용하는 프로세스가 도착하게 되면 다른 프로세스가 CPU를 사용하는 시간이 매우 커지는 현상을 말함
    • 비선점 스케줄링을 사용할 때만 발생
  • 장점 : FCFS는 모든 프로세스가 공평한 조건으로 CPU를 사용할 수 있게 해주면 반응시간 예측 가능
  • 단점 : 대기 시간이 매우 긴 스케줄링 알고리즘

 

선점 스케줄링

• SJF(Shortest Job First)
  • 가장 시간이 적게 걸리는 작업을 먼저 함
  • CPU 업데이트 될 때 가장 시간이 적게 걸리는 프로세스가 선택되어 실행
  • SJF는 비선점 스케줄링, 선점 스케줄링 2가지 종류가 있음
  • 선점형 SJF는 SRTF(Shortest Remaining Time First)라고도 한다
  • 장점 : 평균 대기시간을 가장 적게 가지는 스케줄링 알고리즘
  • 단점 :
    • 최소의 오버헤드로 최적의 성능 보장하도록 구현하는 것이 힘듬
    • 선점형 SJF에서는 프로세스끼리 끼어들기 때문에 CPU가 점유 시간을 예측하는것이 힘듬
• Priority Scheduling
  • 높은 우선순위를 가진 프로세스가 항상 먼저 CPU를 사용할 수 있도록 구현
  • 우선순위가 낮은 프로세스는 영원히 작동하지 않을 수 있음
  • 해결책 : Aging-method(레디 큐에서 오랜 시간을 기다린 프로세스의 우선 순위를 높히는 방법)
• Round Robin(RR)
  • Round Robin 스케줄링은 각각의 프로세스가 공평하게 시간 간격 동안 CPU를 활용할 수 있도록 하는 알고리즘
  • 정해진 시간 간격이 끝나면 CPU를 사용하고 있던 프로세스는 선점적으로 추방(레디 큐에 다시 들어가게 된다.)
  • Round Robin은 SJF 스케줄링 보다 반응 시간 최적화에 있어서 탁월 하지만 대기 시간 최적화가 떨어짐