CPU 스케줄링 - 3

Priority scheduling

우선순위 스케줄링은 레디 큐에서 기다리는 프로세스들 중 우선순위(priority number, integer)가 가장 높은 프로세스에게 제일 먼저 CPU를 할당하는 알고리즘을 말한다.

• 선점형: 현재 CPU에서 수행 중인 프로세스보다 우선순위가 높은 프로세스가 도착해 CPU를 선점해 새롭게 도착한 프로세스에게 할당하는 방식
• 비선점형: 일단 CPU를 얻었으면 우선순위가 높은 프로세스가 도착하더라도 자진해서 반납하기 전까지는 빼앗지 않는 방식

단점: 기아 현상이 발생할 수 있다. 우선순위가 낮은 프로세스는 계속해서 높은 프로세스가 도착하게 될 때, 계속 기다려야할 수 있기 때문이다.
이러한 문제점을 해결하기 위해 $\color{cadetblue}Aging$을 적용할 수 있다.

Aging: 기다리는 시간이 길어지면 우선순위를 조금씩 높여 언젠가는 가장 높은 우선순위가 되어 CPU를 할당받을 수 있게 해주는 방법

• multiple “priority queues”
  

Round Robin(RR)

라운드 로빈 스케줄링은 각 프로세스마다 CPU를 연속적으로 사용할 수 있는 최대 시간인 time quantum 둬 제한을 시킨다.

• time quantum이 너무 짧으면 CPU를 사용하는 프로세스가 빈번하게 교체되어 문맥교환 오버헤드가 커지게 된다.
• time quantum이 너무 길면 FCFS와 같게 된다.

만약 $n$개의 프로세스가 레디 큐에 있고 time quantum이 $q$라고 하면, 모든 프로세스는 $(n-1)q$ 시간 내에 적어도 한번은 CPU 할당을 받을 수 있게 된다.

예시($q = 20$)

도착 시간은 0에 동시에 도착

프로세스	CPU 버스트
$P_1$	53
$P_2$	17
$P_3$	68
$P_4$	24

간트 차트

프로세스	반환 시간	대기 시간
$P_1$	121	121 - 40 = 81
$P_2$	37	20
$P_3$	162	134 - 40 = 94
$P_4$	121	117 - 20 = 97

• Average waiting time: $\frac{81 + 20 + 94 + 97}{4} = 73$

SJF 알고리즘보다 평균 대기 시간은 길지만 응답 시간은 더 짧다.
라운드 로빈의 목적은 CPU 버스트 시간이 짧은 프로세스가 빨리 CPU를 얻을 수 있도록하는 동시에, CPU 버스트 시간이 긴 프로세스가 불이익을 당하지 않도록 하는 것이다.

time quantum과 문맥 교환

• q = 12: 문맥 교환이 발생하지 않는다.
• q = 6: 문맥교환이 1회 발생
• q = 1: 문맥교환이 9회 발생

라운드 로빈의 문제점

time quantum이 너무 커지면 FCFS 스케줄링과 다를 바가 없고 응답시간도 떨어지게 되며 너무 작아진다면 문맥교환으로 인한 오버헤드가 발생한다.

• A rule of thumb: CPU 버스트의 80%는 time quantum보다 작아야 한다.