하다. 실시간 시스템에서 선점 스케줄링 정책을 이용하면 필요한 프로세스가 CPU를 선점할 수 있도록 하므로 결과 예측이 가능하다. 또한 시분할 시스템에서도 빠른 응답시간을 유지하기 위해 선점 스케줄링 정책이 필요하다.
선점 스케줄링 정책에는 RR(Round Robin) 스케줄링, SRT 등이 있는데, 여기서는 SRT에 대해서 설명한다. SRT(Shortest Remaining Time) 스케줄링은 SJF 알고리즘의 선점 방식 버전으로, 준비 큐에서 기다리는 프로세스 중 남은 실행시간이 가장 짧다고 예상되는 것을 먼저 디스패치하여 실행하는 알고리즘이다. 선점 방식이기 때문에 준비 큐에 새로 도착한 프로세스의 예상실행시간이 실행 중인 프로세스의 남은 실행시간보다 짧다면, 새로 도착한 프로세스가 즉시 디스패치된다. SJF 스케줄링처럼 실행할 프로세스의 CPU 사이클이 미리 주어져야만 적용 가능하다.
SJF는 비선점 방식이므로 한 프로세스가 일단 실행을 시작하면 그 프로세스는 완료될 때까지 계속 실행된다. 그러나 SRT는 남은 실행시간 추정치가 더 작은 프로세스가 생기면 실행 중인 프로세스로부터 CPU를 선점할 수 있다. 이런 의미에서 SRT 스케줄링이 SJF 스케줄링보다 평균대기시간이나 평균반환시간에서 효율적일 수 있다. 그러나 SRT 스케줄링은 실행되는 각 프로세스의 실행시간을 추적하여 각 프로세스가 서비스를 받은 시간을 기록해야 하며, 때로는 선점을 위한 문맥 교환도 해야 하므로 SJF 보다 오버헤드가 더 크다는 단점이 있다.
이상의 설명을 바탕으로 SRT 스케줄링을 해보면 다음과 같다.
프로세스 A가 가장 먼저 도착하므로 A부터 실행한다. A 실행 중 시각 2에 B가 도착한다. 이때 A의 남아 있는 실행시간 추정치는 2(=4-2)이고, B는 3이다. 따라서 B를 준비상태로 두고, A를 계속 실행시킨다. 시각 4에 A는 종료되고 이때 B만 준비 상태이므로 B를 실행한다. 시각 5에 C가 도착한다. 이때 B의 남아 있는 실행시간 추정치는 2(=3-1), C는 1이므로, B는 준비 상태로 전이하고 C를 실행한다. C가 종료되는 시각 6에 D가 도착한다. 이때 B의 실행시간 추정치는 2이고, D는 5이므로 B를 실행시키고 D는 준비 상태로 한다. B가 실행 중인 시각 7에 E가 도착한다. 이때 B의 실행시간 추정치는 1(=2-1)이고, E의 실행시간 추정치는 2이다. 따라서 B는 계속 실행시키고, E는 준비상태에 둔다. 시각 8에 B가 종료되면 남아 있는 프로세스는 D와 E이므로, CPU 사이클이 가장 적은 E를 먼저 실행시켜 시각 10에 E가 종료된다. 시각 10에 최종적으로 D를 실행하면 시각 15에 D가 종료된다.
따라서 프로세스들의 수행순서는 다음 그림과 같다.
0
2
4
5
6
7
8
10
14
15
A
B
C
B
B
E
D
평균대기시간이란 각 프로세스가 수행이 완료될 때까지 준비 큐에서 기다리는 시간의 합의 평균값이며, 평균반환시간이란 각 프로세스가 생성된 시점(여기서는 준비 큐에 들어온 시점과 동일한 것으로 가정) 부터 수행이 완료된 시점까지의 소요시간의 평균값이다.
프로세스의 반환시간 = 프로세스 수행완료 시각 - 프로세스 생성 시작 시각(준비큐에 들어온 시각으로 가정)
A = 4 - 0 = 4
B = 8 - 2 = 6
C = 6 - 5 = 1
D = 15 - 6 = 9
E = 10 - 7 = 3
따라서 평균반환시간은 다음과 같이 계산된다.
평균반환시간 = (4 + 6 + 1 + 9 + 3) / 5 = 4.6
3. 참고문헌
김진욱, 이인복(2023). 운영체제. 한국방송통신대학교출판문화원.
조성호(2018). 쉽게 배우는 운영체제. 한빛아카데미