CPU 스케줄링

CPU 스케줄링이란?

레디 큐 내의 프로세스 중에서, 어떤 녀석에게 CPU를 할당할 것인지 결정하는 것 혹은 그 방식(Policy)

---

CPU 스케줄링에서 고려될 수 있는 것들

• CPU Utilization(CPU 이용률)
• Throughput - 얼마나 많은 프로세스를 처리할 수 있는가
• Turnaround Time(반환 시간) - 프로세스가 도착한 시점부터 해당 프로세스가 완료될 때까지 걸리는 시간
• Waiting Time(대기 시간)- 어떤 프로세스가 레디 큐에서 대기하는 시간의 총 합

---

CPU 스케줄링 방식

FCFS

• 먼저 CPU를 요청한 프로세스(= 먼저 온 프로세스)에게 CPU를 할당한다.
• FIFO Queue를 이용한 간단한 구현 가능
• 프로세스가 도착한 순서 혹은 CPU를 요청한 순서에 따라서 Average Waiting Time이 달라진다.(Average Turnaround Time은 변함 없다.)
• 앞선 프로세스의 CPU Burst time이 너무 길 경우, 다른 프로세스들이 CPU를 할당 받지 못한 채 장시간 대기하게 되는 Convoy Effect가 발생할 수 있다.
• 한 번 할당된 CPU는 해당 프로세스의 CPU Burst time 동안 다른 프로세스가 선점할 수 없는, 비선점형 스케줄링 방식이다.

SJF(Shortest-Job-First)

• CPU burst time이 적은 프로세스부터 처리한다.(일종의 priority 스케줄링)
• 동일한 CPU burst time의 프로세스가 여러개 있다면 FCFS 순서 적용
• 선점형, 비선점형 스케줄링 방식 모두 가능
• average waiting time 측면에서는 최적이라고 할 수 있으나, 어떤 프로세스의 CPU burst time을 미리 알 수 없기에 SRTF의 등장
• Starvation 문제 발생 가능 - CPU burst time이 긴 프로세스는 영원히 선택받지 못하는 일이 발생 가능하다.

SRTF(Shortest-Remaining-Time-First)

• 선점형 스케줄링 방식
• 어떤 프로세스의 지난 CPU burst time의 기하 평균을 이용하여 다음 CPU burst time을 예측
• Starvation 문제 발생 가능

RR(Round-Robin)

• 할당 시간(time quantum)이 도입된 선점형 FCFS라고 할 수 있다.
• 어떤 프로세스가 레디 큐에서 나와서 할당 시간 동안 CPU를 사용하고 나면, 다시 레디 큐의 뒤로 들어가서 다음 CPU 할당을 대기하게 된다.
• 각 프로세스는 CPU 사용 시간만큼 대기 시간이 증가하게 되므로 공평한 스케줄링 방법이라고 할 수 있다.
• 할당 시간이 너무 길어진다면 FCFS와 동일하게 되어 Convoy Effect 등이 발생할 수 있고, 할당 시간이 너무 짧다면 해당 시간 동안 instruction 하나 조차 수행하지 못하는 등의 일이 발생할 수 있고 잦은 context switch로 인한 오버 헤드 발생 가능성이 있다. --> 할당 시간의 길이에 의해 성능이 크게 좌지우지되므로 합리적인 선택이 필요하다.

Priority 스케줄링

• 레디 큐 내의 프로세스 별로 우선 순위를 부여한다.
• 우선순위는 정수로 표현되며, 숫자가 작을수록 우선순위는 높다.
• 우선순위가 높은 프로세스가 레디 큐에서 선택되고 CPU를 사용하게 된다.
• 선점형, 비선점형 모두 가능
• 우선순위가 낮은 프로세스는 영영 선택되지 못하는 Starvation 문제 발생 가능(Indefinite blocking)
• Starvation 해결을 위해, Aging 기법을 통해 오래 기다린 프로세스의 우선순위는 점차 증가된다.
• 일반적으로 RR과 함께 이용된다. Priority based 스케줄링 방식을 이용하되 동일한 우선 순위의 프로세스에 대해서는 Time Quantum을 적용하여 Context Switching을 해가며 프로세스 처리