
정답
45ms 후 1 레벨 큐에는 왼쪽에서 오른쪽 순서로 \(P5, P3, P2\) 가 저장되어 있다.
프로세스 \(P6\) 이 작업을 종료할 때까지 걸리는 시간은 \(55\text{ ms}\) 이다.
프로세스들이 종료하는 순서는 \(P4 \rightarrow P6 \rightarrow P2 \rightarrow P5 \rightarrow P1 \rightarrow P3\) 이다.
출제 의도
멀티레벨 피드백 큐 스케줄링에서 각 레벨의 우선순위, FCFS와 라운드 로빈 방식, 시간 할당량(타임 퀀텀)에 따른 프로세스 이동과 실행 순서를 이해하고, 이를 바탕으로 시간 경과에 따른 각 큐의 상태와 프로세스 종료 시점 및 종료 순서를 계산할 수 있는지를 평가하는 문제이다.
풀이 과정
조건을 정리한다.
- 0 & 1 레벨 큐 : FCFS 방식, 한 번 선택되면 \(20\text{ ms}\) 씩 CPU를 사용한다.
- 2 레벨 큐 : 라운드 로빈, 타임 퀀텀 \(20\text{ ms}\).
- 최하위(2 레벨)를 제외하고, 자신의 큐에서 할당 시간 \(20\text{ ms}\) 를 모두 쓰고도 끝나지 않으면 한 단계 낮은 큐로 이동한다.
- 항상 높은 레벨 큐가 모두 비어야만 그보다 낮은 레벨 큐의 프로세스가 실행된다.
- 현재 이후에는 새로운 프로세스가 진입하지 않는다.
그림에서 큐는 왼쪽이 진입(rear), 오른쪽이 종료(front) 방향이므로, 오른쪽에 있는 프로세스가 먼저 실행된다.
현재 시점에서 각 큐의 상태는 다음과 같다.
- 0 레벨 큐 : 왼쪽에서 \(P6(15), P5(40), P4(20)\) ⇒ 가장 오른쪽 \(P4\) 가 먼저 실행
- 1 레벨 큐 : 왼쪽에서 \(P3(60), P2(15)\)
- 2 레벨 큐 : \(P1(10)\)
시간 경과를 따라 CPU 실행을 추적한다.
1) \(t = 0 \sim 20\text{ ms}\) 0 레벨의 \(P4\) 가 \(20\text{ ms}\) 동안 실행되고, 잔여 버스트가 \(20\text{ ms}\) 이므로 바로 종료된다. 이때까지의 종료 프로세스 : \(P4\).
2) \(t = 20 \sim 40\text{ ms}\) 0 레벨에서 다음으로 오른쪽에 있는 \(P5(40)\) 가 선택된다. \(20\text{ ms}\) 를 모두 사용하지만 끝나지 않으므로 잔여 \(20\text{ ms}\) 를 가진 채 1 레벨 큐로 강등된다. → \(t = 40\text{ ms}\) 에 1 레벨 큐는 왼쪽에서 \(P5(20), P3(60), P2(15)\) 가 된다.
3) \(t = 40 \sim 55\text{ ms}\) 0 레벨에는 \(P6(15)\) 만 남으므로 이 프로세스가 실행된다. 필요 시간이 \(15\text{ ms}\) 이므로 \(t = 55\text{ ms}\) 에 종료된다. 이때까지의 종료 프로세스 순서 : \(P4 \rightarrow P6\).
따라서 \(t = 45\text{ ms}\) 시점에는 아직 0 레벨에서 \(P6\) 이 실행 중이고, 1 레벨 큐에는 아무도 실행되지 않은 채 왼쪽부터 \(P5, P3, P2\) 가 저장되어 있다. 즉, 45ms 후 1 레벨 큐의 프로세스 ID는 \(P5, P3, P2\) 이다.
\(P6\) 은 \(t = 40\) 부터 \(15\text{ ms}\) 를 사용하여 \(t = 55\) 에 종료되므로, 현재 시점에서 종료까지 걸리는 시간은 \(55\text{ ms}\) 이다.
이제 0 레벨 큐가 비었으므로 그 다음부터는 1 레벨, 그 후 2 레벨을 사용한다.
4) \(t = 55 \sim 70\text{ ms}\) (1 레벨) 1 레벨 큐 오른쪽의 \(P2(15)\) 가 먼저 실행되어 \(15\text{ ms}\) 만에 종료된다. 종료 순서 : \(P4 \rightarrow P6 \rightarrow P2\).
5) \(t = 70 \sim 90\text{ ms}\) (1 레벨) 다음으로 오른쪽의 \(P3(60)\) 이 실행된다. \(20\text{ ms}\) 를 모두 사용하지만 끝나지 않아 잔여 \(40\text{ ms}\) 를 가진 채 2 레벨 큐로 강등된다.
6) \(t = 90 \sim 110\text{ ms}\) (1 레벨) 1 레벨에 남은 \(P5(20)\) 가 \(20\text{ ms}\) 동안 실행되어 \(t = 110\) 에 종료된다. 종료 순서 : \(P4 \rightarrow P6 \rightarrow P2 \rightarrow P5\).
이제 0, 1 레벨 큐가 비었으므로 2 레벨 큐를 사용한다. 2 레벨 큐에는 처음부터 있던 \(P1(10)\) 과, 강등된 \(P3(40)\) 가 있다. 진입 방향을 고려하면 오른쪽에 \(P1\), 왼쪽에 \(P3\) 이므로 \(P1\) 이 먼저 실행된다.
7) \(t = 110 \sim 120\text{ ms}\) (2 레벨, RR) \(P1(10)\) 이 실행되어 \(10\text{ ms}\) 만에 종료된다. 종료 순서 : \(P4 \rightarrow P6 \rightarrow P2 \rightarrow P5 \rightarrow P1\).
8) \(t = 120 \sim 140\text{ ms}\), \(t = 140 \sim 160\text{ ms}\) (2 레벨, RR) 마지막으로 \(P3(40)\) 가 라운드 로빈 방식으로 두 번의 퀀텀을 사용한다. 첫 번째 \(20\text{ ms}\) 실행 후 잔여 \(20\text{ ms}\) 로 다시 선택되어 \(t = 160\) 에 최종 종료된다.
따라서 전체 종료 순서는
$$ P4 \;\rightarrow\; P6 \;\rightarrow\; P2 \;\rightarrow\; P5 \;\rightarrow\; P1 \;\rightarrow\; P3 $$
이다.
<풀이가 부정확할 수 있으니 반드시 교차검증 확인 바랍니다.>