CPU 스케줄링 - 2

스케줄링 알고리즘

---

FCFS(First-Come First-Served)

FCFS 스케줄링은 프로세스가 준비 큐에 도착한 시간 순서대로 CPU를 할당하는 방식을 말한다. CPU를 먼저 요청한 프로세스에게 먼저 CPU를 할당하고 작업을 완료할 때까지 강제로 빼앗을 수 없다.
단점: 적은 CPU burst을 가진 프로세스는 CPU burst이 긴 프로세스를 오랫동안 기다려야 하기 때문에, 평균 대기 시간이 커지게 된다.

예제

프로세스	CPU 버스트
$P_1$	24
$P_2$	3
$P_3$	3

프로세스가 $P_1$, $P_2$, $P_3$ 순으로 도착하고 각각의 CPU 버스트가 위와 같다고할 때, FCFS 스케줄링에 의한 순서를 나타낸 간트 차트는 아래와 같다.

• 대기 시간: $P_1= 0$, $P_2=24$, $P_3=27$
• 평균 대기 시간: $\frac{0 + 24 + 27}{3} = 17$

도착 순서가 $P_2$, $P_3$, $P_1$일 경우는

• 대기 시간: $P_1= 6$, $P_2=0$, $P_3=3$
• 평균 대기 시간: $\frac{6 + 0 + 3}{3} = 3$

이전의 도착 순서와 비교하면 평균 대기 시간이 약 5배정도 줄어들었다.

Convoy Effect: CPU 버스트가 짧은 프로세스가 CPU 버스트가 긴 프로세스보다 나중에 도착해 오랜 시간 기다려야 하는 현상을 말한다. FCFS의 대표적 단점

SJF(Shortest-Job First)

SJF 알고리즘은 CPU 버스트가 가장 짧은 프로세스에게 제일 먼저 CPU를 할당하는 방식이다. 비선점형과 선점형 두 가지 방식이 있다.

• 비선점형: 일단 CPU를 획득하면 그 프로세스가 일을 끝마칠 때까지 강제로 빼앗지 않는 방식
• 선점형: 레디 큐에서 CPU 버스트가 더 짧은 프로세스가 도착할 경우 CPU를 빼앗아 더 짧은 프로세스에게 부여하는 방식(= SRTF(Shortest Remaining Time First))

단점: 나중에 들어올 프로세스의 CPU 버스트의 크기를 알기 어렵다. 기아 현상이 일어날 수 있다.

예시(Non-preemptive)

프로세스	도착 시간	CPU 버스트
$P_1$	0	7
$P_2$	2	4
$P_3$	4	1
$P_4$	5	4

간트 차트

• 평균 대기 시간: $\frac{0 + 6 + 3 + 7}{4}$ = 4

예시(Preemptive)

프로세스	도착 시간	CPU 버스트
$P_1$	0	7
$P_2$	2	4
$P_3$	4	1
$P_4$	5	4

간트 차트

• 평균 대기 시간: $\frac{9 + 1 + 0 + 2}{4} = 3$

다음 CPU 버스트 길이 예측

프로세스의 CPU 버스트 길이는 미리 알 수는 없으나 과거의 CPU 버스트 길이를 통해 예측은 할 수 있다.
1. $t_n=$ $n^{th}$ CPU 버스트의 실제 길이
2. $τ_{n+1} =$ 다음 CPU 버스트 예측 길이
3. $\alpha, 0\le\alpha\le1$
4. $τ_{n+1} =\alpha t_n+(1-\alpha)τ_n$