[운영체제] CPU 스케줄링

CPU 스케줄링

• 다중 프로그래밍에서 CPU의 효율성을 높이고 작업 응답 시간을 최소화하기 위하여 적절하게 프로세스들에게 CPU를 할당하는 기법

 

프로세스 상태 변화

 

1. 선점형 스케줄링 (Preemptive Scheduling)

• 한 프로세스가 CPU를 할당 받았을 때, 우선순위가 높은 다른 프로세스가 CPU를 강제로 빼앗을 수 있는 스케줄링

종류	설명
라운드 로빈 (Round-Robin)	- 모든 프로세스들은 같은 크기의 CPU 시간을 할당받는다. - 시간 내에 작업을 처리하지 못하면 준비 큐 리스트의 맨 뒤로 보내진다.
SRT (Shortest Remaining Time First)	- 준비 큐에 남은 처리 시간이 더 짧은 프로세스가 있다면 CPU를 선점받을 수 있다.
다단계 큐 (Multi-level Queue)	- 여러 개의 큐를 이용하여 작업들이 독립적인 스케줄링을 가지게 한다. - 상위단계 큐가 더 높은 우선순위를 가진다.
다단계 피드백 큐 (Multi-level feedback Queue)	- 다단계 큐의 형태를 가지지만 작업이 큐 사이를 이동할 수 있다. - 작업 시간이 너무 길면 작업을 낮은 단계 큐로 옮기게 된다. - 입출력 작업, 전면작업을 높은 우선순위 큐에 놓고 프로세서 중심 프로세스는 낮은 우선순위 큐에 놓는다.

 

 

2. 비선점형 스케줄링 (Non-preemptive Scheduling)

• 우선순위가 높은 프로세스가 있어도 CPU를 강제로 빼앗을 수 없는 스케줄링

종류	설명
우선순위 (Priority)	- 프로세스 별로 우선순위를 가지고, 우선순위가 높은 프로세스부터 CPU를 할당받는다.
FCFS (First Come First Service)	- 먼저 준비 큐에 도착한 프로세스부터 먼저 처리한다. - FIFO 알고리즘과 동일하다.
SJF (Shortest Job First)	- 준비 큐에 있는 작업 중 가장 작업 시간이 짧은 작업부터 CPU를 할당받는다. - 단점 : CPU 요구시간이 긴 프로세스는 CPU를 할당받지 못해 '기아현상'이 발생할 수 있다.
HRN (High Response Ratio Next)	- SJF의 단점인 기아현상을 보완한 기법이다. - 현재 대기 큐의 작업 중 '응답률'이 가장 높은 프로세스부터 CPU를 할당한다. - 우선순위 = (대기시간 + 서비스 시간) / 서비스 시간