[C언어 알고리즘] 7.2 SJF(Shortest Job First) 알고리즘

[C언어 알고리즘] 7.2 SJF(Shortest Job First) 알고리즘

---

여러 개의 작업을 하나의 CPU에서 수행하는 순서를 결정하는 스케쥴링 알고리즘은 여러가지 방법이 있습니다. 그 중에서 작업을 수행 요청하고 실제 수행이 끝날 때까지 대기하는 평균 시간을 최소로 하는 알고리즘은 SJF(Shortest Job First)알고리즘입니다.

 

SJF 알고리즘은 작업량이 작은 작업을 먼저 수행하는 알고리즘입니다. 동시에 n개의 작업을 수행 요청이 왔다가 가정합시다.

 

n번째 수행할 작업의 길이를 An이라고 한다면 모든 작업을 수행하는데 걸리는 비용은 다음과 같습니다.

A1 + (A1 + A2) + (A1 + A2 + A3) + ... + (A1+A2+A3+...+An) = nA1 + (n-1)A2 + (n-2)A3 + ... +An

 

그리고 대기 시간의 합은 다음과 같습니다.

A2 + (A1 + A2) + ... + (A1+A2+A3+...+An-1) = (n-1)A1 + (n-2)A2 + (n-3)A3 + ... +An-1

 

첫 번째 작업은 작업 요청한 후에 대기 시간은 0, 수행을 완료할 때까지 걸린 시간이 A1입니다.

두 번째 작업이 작업 요청한 후에 대기 시간은 A1, 수행을 완료할 땨까지 걸린 시간은 A1 + A2입니다.

따라서 수행 완료까지 걸린 시간의 합은 Sa = A1 + (A1 + A2) + (A1+A2+A3)+...+(A1+A2+...+An)입니다.

Sa = A1 + (A1 + A2) + (A1+A2+A3)+...+(A1+A2+...+An) = nA1+(n-1)A2+(n-2)A3+...(n-i-1)Ai+...An

 

i>j>0이고 Ai<Aj 인 부분이 있을 때 수행 완료까지 걸린 시간의 평균 비용이 최소라고 가정합시다.

Sa에서 Ai와 Aj의 순서를 바꾼 것이 전체 시간의 합입니다.

Sb = nA1 + (n-1)A2 + ... + (n-(j-1))Ai + ... + (n-(i-1))Aj+...+An

 

Sa - Sb = (i-j)Aj + (j-i)Ai = (i-j)(Aj - Ai)<0 이므로 가정은 거짓입니다.

 

따라서 SJF 알고리즘이 작업 수행 완료까지 걸린 평균 시간을 최소로 할 수 있다는 것을 알 수 있습니다.

평균 대기 시간 = 작업 수행 완료까지 걸린 평균 시간 – 평균 작업 량

따라서 평균 대기시간도 최소라고 말할 수 있습니다.  SJF 알고리즘의 소스 구현은 여기에서는 하지 않습니다. 디디딤돌 자료구조와 알고리즘 with C++을 참고하세요.

---

12.2 SJF 알고리즘 [디딤돌 자료구조와 알고리즘 with C++]