최단 작업 우선 스케줄링(Shortest Job First Scheduling)은 평균 대기 시간을 최소화하기 위해 CPU 점유 시간이 가장 짧은 프로세스에 CPU를 먼저 할당하는 방식의 CPU 스케줄링 알고리즘으로 평균 대기시간을 최소로 만드는 걸 최적으로 두고 있는 알고리즘이다.
FIFO 스케줄링과 SJF 스케줄링의 차이점은
장점
- 항상 실행 시간이 짧은 작업을 신속하게 실행하므로 평균 대기 시간이 가장 짧다.
단점
- 초기의 긴 작업을 짧은 작업을 종료 할 때까지 대기시켜 기아가 발생한다.
- 기본적으로 짧은 작업이 항상 실행되도록 설정하므로 불공정한 작업을 실행한다.
- 실행 시간을 예측하기 어려워 실용적이지 못하다.
스케줄링 실행
반환시간 = 마지막 작업 시작시간 - 이미 처리한 시간 - 도착시간
SJF 스케줄링은 프로세스 작업을 시작하면 해당 프로세스 작업완료까지 다른 프로세스의 작업을 시작하지 않는다.
그러므로 반환시간 계산식의 이미 처리한 시간이 존재 할 수가 없으니
반환시간 = 마지막 작업 시작시간 - 도착시간이 된다.
예제)
| 도착시간 | 0 | 1 | 3 | 5 | 9 |
| 프로세스 | A | B | C | D | E |
| CPU사이클 | 8 | 5 | 2 | 4 | 3 |
프로세스별 도착시간과 필요한 CPU사이클(작업시간) 이 위와 같을 때 프로세스의 실행 순서는 다음과 같다.
| 시간(초) | 실행중인 프로세스 (괄호는 남은시간) |
실행대기 (괄호는 CPU 사이클(초)) |
설명 |
| 0 | A(8) | 가장먼저 도착한 A실행 | |
| 1 | A(7) | B(5) | B도착 |
| 2 | A(6) | B(5) | |
| 3 | A(5) | B(5), C(2) | C도착 |
| 4 | A(4) | B(5), C(2) | |
| 5 | A(3) | B(5), C(2) ,D(4) | D도착 |
| 6 | A(2) | B(5), C(2) ,D(4) | |
| 7 | A(1) | B(5), C(2) ,D(4) | |
| 8 | C(2) | B(5) | A종료, 사이클이 가장짧은 C실행 |
| 9 | C(1) | B(5),E(3) | E도착 |
| 10 | D(4) | B(5),E(3) | C종료, 사이클이 가장짧은 D실행 |
| 11 | D(3) | B(5),E(3) | |
| 12 | D(2) | B(5),E(3) | |
| 13 | D(1) | B(5),E(3) | |
| 14 | E(3) | B(5) | D종료, 사이클이 가장짧은 E실행 |
| 15 | E(2) | B(5) | |
| 16 | E(1) | B(5) | |
| 17 | B(5) |
:
| 22 | B(0) | 모든작업 완료. |
실행순서 = A(0초) -> C(8초) -> D(4초) -> E(14초) ->B(17초)
대기시간
| A | B | C | D | E | 평균 |
| 0 | 17 - 1 = 16 | 8 - 3 = 5 | 10 - 5 = 5 | 14 - 9 = 5 | (0+16+5+5+5) / 5 = 6.2 |