상태나 종료상태로 전이될 때까지 계속 실행상태에 있게 된다. 이러한 비선점 방식은 강제적인 문맥 교환이 없어 오버헤드가 발생하지 않는다. 그러나 오랜 시간이 걸리는 프로세스가 실행 중이라면 실행시간이 짧은 프로세스가 오래 기다리게 되는 상황이 발생할 수 있다.
SJF(Shortest Job First) 스케줄링은 준비 큐에서 기다리는 프로세스 중 실행시 간이 가장 짧다고 예상되는 것을 먼저 디스패치하여 실행하는 비선점 방식의 스케줄링 알고리즘이다. SJF 스케줄링은 실행할 프로세스의 CPU 사이클이 미 리 주어져야만 적용 가능하다.
처음에는 프로세스 A만 준비 큐에 있으므로 A를 디스패치하여 실행시킨다. A가 실행되는 동안 준비 큐에는 프로세스 B(2), C(3), D(5)가 순차적으로 도착한다. 시각 6에 A의 수행이 완료된 후, 준비 큐에 있는 프로세스 중 실행시간이 가장 짧은 것은 cpu 사이클이 1인 C, cpu 사이클이 2인 D, cpu 사이클이 3인 B 순이다. 따라서 A 수행 완료 후에는 C가 디스패치된다. C가 시각 7에 완료된 후 준비 큐에는 E가 새롭게 들어오고 이후 새롭게 도착할 프로세스는 없다. 이때 준비 큐에 있는 프로세스 중에서 실행시간이 가장 짧은 것은 D, B, E 순서이다. 따라서 C 완료 후에는 D, B, E 순서로 프로세스가 수행된다.
위 과정에 따라 SJF 스케줄링 알고리즘의 결과는 다음과 같다.
0
6
7
9
12
16
A
C
D
B
E
프로세스의 반환시간 = 프로세스 수행완료 시각 - 프로세스 생성 시작 시각(준비큐에 들어온 시간으로 가정)
위 식으로 각 프로세스의 반환시간을 구하면 다음과 같다.
A = 6 - 0 = 6
B = 12 - 2 = 10
C = 7 - 3 = 4
D = 9 - 5 = 4
E = 16 - 7 = 9
따라서 평균반환시간은 = (6 + 10 + 4 + 4 + 9) / 5 = 6.6
참고로 “프로세스의 대기시간 = 프로세스 디스패치 시각 - 프로세스 도착시간”으로 계산한다. 따라서 각 프로세스의 대기시간은 다음과 같다.
A = 0
B = 9 - 2 = 7
C = 6 - 3 = 3
D = 7 - 5 = 2
E = 12 - 7 = 5
따라서 평균대기시간 = (0 + 7 + 3 + 2 + 5) / 5 = 3.4
3. 참고문헌
김진욱, 이인복(2023). 운영체제. 한국방송통신대학교출판문화원.
조성호(2018). 쉽게 배우는 운영체제. 한빛아카데미.