[운영체제] 스케줄링 알고리즘

CPU 스케줄링은 준비 큐에 있는 어느 프로세스에 CPU 코어를 할당한 것인지를 결정한다.

이번에는 여러 가지 다른 CPU스케줄링 알고리즘들에 대하여 알아보자.

 

[선입 선처리 스케줄링]

CPU를 먼저 요청하는 프로세스가 CPU를 먼저 할당 받는 구조이다.

이 구조의 문제점은 평균 대기 시간이 대단히 길 수 있다는 점이다.

 

아래와 같은 경우를 생각해보자

프로세스	버스트 시간
P1	24
P2	3
P3	3

 

프로세스들이 P1,P2,P3순서로 도착하고 선입선출의 구조로 일처리가 된다고 하면 다음과 같은 결과를 얻는다.

 

프로세스 P1의 대기 시간은 0밀리초이며, 프로세스 P2는 24, P3는 27밀리초가 된다.

따라서 평균 대기 시간은 (0 + 24 + 27) / 3 = 17밀리초이다.

 

보통 CPU의 처리 속도는 빠르고, I/O처리를 기다리는 시간이 많다. 

모든 다른 프로세스들이 하나의 긴 프로세스가 CPU를 양도하기를 기다리는 것을 호위 효과라고 한다.

이는 짧은 프로세스들이 먼저 처리되도록 허용될 때보다 CPU 장치의 이용률이 저하되는 결과를 낳는다.

 

---

[최단 작업 우선 스케줄링(SJF)]

선입 선처리의 경우 처리 시간이 길 프로세스가 오면 다른 프로세스들이 오랫동안 기다려야하는 문제점이 있다.

따라서 최단 작업 우선 스케줄링에서는 최단 시간이 걸리는 작업을 먼저 처리한다.

 

아래와 같은 경우를 생각해보자

프로세스	버스트 시간
P1	6
P2	8
P3	7
P4	3

SJF 스케줄링을 이용하면 다음과 같다.

 

P1의 대기 시간은 3, P2는 16, P3는 9, P4는 0밀리 초이다.

따라서 평균대기 시간은 (3+16+9+0)/4 = 7밀리초이다.

 

선입 선처리 스케줄링과 비교해봤을 때 평균 대기 시간이 줄어든 것으로 확인할 수 있다.

 

하지만 이 경우 CPU 버스트의 길이를 알 방법이 없다는 문제점이 있다.

따라서 CPU버스트의 길이를 예측하는 방법을 이용한다.

 

우리는 다음 CPU 버스트가 이전의 버스트와 길이가 비슷하다고 기대하고 이 점을 이용한다. 

측정된 이전의 CPU버스트들의 길이를 지수평균한 것으로 예측하는데 수식은 다음과 같다.

 

 

아래의 경우로 평균 대기 시간을 계산해보자

Process	Arrival Time	Burst Time
P1	0	8
P2	1	4
P3	2	9
P4	3	5

P1은 큐의 유일한 프로세스이므로 시간 0에 바로 시작됨. 하지만 P2가 시간1에 도착하면 프로세스 처리 시간에 의해 P2가 선점되고 2초에 P3가 도착하지만 처리 시간이 P2보다 길기 때문에 대기함. P4도 마찬가지.

P2가 처리가 완료되면 P1,P3,P4중에 처리 시간이 가장 낮은 순부터 처리가 됨.

 

이를 계산해보면

[(10-1) + (1-1) + (17-2) + (5-3)] / 4 = 6.5밀리초