CPU Scheduling - Scheduling Algorithm_2

Shortest-Job-First(이하 SJF) Algorithm

 

SJF 알고리즘의 경우 더 정확히 말한다면 Shortest-Next CPU Burst가 더 적절한 표현이다.

 

왜냐하면 SJF 알고리즘은 다음에 수행될 Process들 중에서 CPU Burst Time이 짧은 것부터 수행하기 때문이다.

 

예를 들어보자. Process P1, P2, P3, P4가 있고 각각의 CPU-Burst Time이 아래와 같다고 가정하자.

 

 

 

 

이 Process들을 SJF에 따라 스케쥴링 한걸 Grandtt Chart로 나타내면 아래와 같다.

 

 

 

 

이때 Average Waiting Time은 (0+3+9+16)/4 = 7 milliseconds이다. 만일 이 Process들을 FCFS 알고리즘에 따라서

 

스케쥴링 한다면 Average Waiting Time은 (0+6+14+21)/4 = 10.25 milliseconds가 된다.

 

SJF 알고리즘 경우 Minimum Average Waiting Time면에서만 볼때면 최적의 알고리즘이다. 왜냐하면

 

적은 Process를 긴 Process에 앞서 수행시킬 경우 긴 Process의 대기 시간이 증가하는 것보다

 

적은 Process의 대기 시간의 감소효과가 더욱 크기 때문이다.

 

SJF알고리즘에 가장 큰 문제점은 다음에 올 Process의 CPU-Burst Time을 어떻게 알 수 있는가 하는 점이다.

 

이는 이전의 CPU-Burst Time의 지수 평균값을 이용해서 예측한다.  예측 공식에 사용하는 미지수는 아래와 같다.

 

   T_n : length of the n-th CPU burst (가장 최근의 CPU burst 값)

   t_n+1 : 다음 CPU burst의 예측값
   t_n : 이전의 CPU burst에 대한 history
   a : 최근 값과 과거의 값에 대한 가중치

 

다음 예측값 t_n+1 을 구하는 공식은 아래와 같다.

 

t_n+1 = aT_n + (1 - a)t_n이다.

 

만일 a = 0 이면 t_n+1= t_n으로 과거 기록에만 전적으로 의지하며 a = 1이면 t_n+1= T_n으로 최근 CPU-Burst값에만 의존하는 방식이다.

 

예를 들어 a = 1/2일 경우의 CPU-Burst Time의 예측도를 살펴보면 아래와 같다.

 

SJF의 경우 Preemptive방식과 Non-Preemptive방식으로 나뉘는데 Preemptive방식의 경우

 

Process가 수행중일때 새로운 Process가 Ready상태가 될 때 수행중인 Process와 새로운 Process를 비교하여

 

그 결과에 따라서 Process Scheduling하는 방식이고 Non-Preemptive방식의 경우에는 수행 중인 Process가

 

끝날때까지 유지하는 방식이다. 예를 들어서 P1, P2, P3, P4가 있을때 CPU-Burst Time이 아래와 같다고 하자.

 

 

이를 Preemptive SJF 방식으로 스케쥴링하면

 

위와 같이 되며 Average Waiting Time은 ((10 - 1) + (1 - 1) + (17 - 2) + (5 - 3))/4 = 6.5 milliseconds 가 된다.

 

만일 이를 Non-Preemptive SJF 방식으로 스케쥴링 할 경우의 Average Waiting Time은 7.75 milliseconds가 된다.