[스케쥴링] 2. 선점 스케쥴링 알고리즘

1. Round Robin 

: 프로세스를 먼저 들어온 순서대로 일정 시간씩 실행하는 스케쥴링 기법

시간 할당량(time quantum)이라고 하는 작은 단위의 시간을 정의하고, 준비 완료 큐에 있는 프로세스에 대해서 한번에 한 시간 할당량 동안 CPU를 할당

 

2. 선점 우선순위 

: 준비 큐에 프로세스가 도착하면, 도착한 프로세스의 우선순위와 현재 실행중인 프로세스의 우선순위를 비교하여 우선순위가 가장 높은 프로세스에 프로세서를 할당하는 방식

- 우선순위가 동일할 경우 FIFO 순서로 스케쥴링 실행

 

3. SRT 스케쥴링(Shortest Remaining Time Scheduling)

: 잔여 시간이 가장 적은 순서대로 실행

- 선점형 SJF(Shortest Job First)라고 불린다.

 

4. 다단계 큐 스케쥴링

: 다단계 큐 스케줄링 알고리즘은 준비 완료 큐를 다수의 별도의 큐로 분류하여 수행하는 방식

• 우선순위마다 준비 큐 형성
• 항상 가장 높은 우선순위 큐의 프로세스에 CPU를 할당
• 우선순위가 낮은 큐에서 작업 실행 중이더라도 상위 단계의 큐에 프로세스가 도착하면 CPU를 빼앗는 선점형 스케줄링

(단점)

• 한번 큐에 할당되면 다른 큐로 이동 불가능
• 적은 스케쥴링 오버헤드가 단점이지만 융퉁성이 적다

5. 다단계 피드백 큐 스케쥴링

• 다단계 피드백 큐 스케줄링 알고리즘에서는 프로세스가 큐들 사이로 이동하는 것을 허용
• CPU 시간을 너무 많이 사용하면, 낮은 우선순위 큐로 이동
• 입/출력 중심의 프로세스와 대화형 프로세스들은 높은 우선순위의 큐로 이동
• 이러한 Aging(노화) 형태는 기아 상태를 예방
• 다단계 큐 스케쥴링의 단점 극복