MLFQ(Multi-Level Feedback Queue) 스케줄링

0 / 11

MLFQ(Multi-Level Feedback Queue) 스케줄링

다단계 피드백 큐(MLFQ) 스케줄링도 MLQ처럼 준비 큐를 여러 개로 나누지만, 프로세스가 큐 사이를 옮겨 다닌다. 새 프로세스는 가장 위 큐에서 시작하고, 그 큐의 할당량 안에 끝내지 못하면 운영체제가 실행을 멈추고(선점) 한 단계 아래 큐로 내린다. 아래 큐일수록 늦게 실행되는 대신 할당량이 크고, 가장 아래 큐는 RR 방식으로 실행한다. 아래 큐 프로세스가 실행 중이어도 위 큐에 새 프로세스가 오면 운영체제가 실행을 멈춘다.

은행으로 치면: 창구는 하나이고 줄이 셋 있다. 모든 손님은 먼저 '1분 줄'에 서고, 1분 안에 못 끝내면 '2분 줄'로, 거기서도 못 끝내면 '4분 줄'로 옮긴다. 위 줄이 비어야 아래 줄 손님 차례가 온다.

1 / 11

0ms: P1이 큐 0에서 실행

새 프로세스는 모두 가장 위 큐 0에 선다. 큐 0에서는 한 번에 1ms까지만 실행할 수 있다.

2 / 11

1ms: P1이 큐 1로 내려감

P1은 할당량 1ms를 다 쓰고도 끝나지 않아(4ms 남음) 한 단계 아래 큐 1로 내려간다. 1ms에 온 P2가 큐 0에서 실행된다.

3 / 11

2ms: P2도 큐 1로 내려감

P2도 1ms 실행하고 2ms가 남은 채로 큐 1에 선다. 2ms에 온 P3가 큐 0에서 실행된다.

4 / 11

3ms: P3도 큐 1로 내려감

P3는 7ms가 남은 채로 큐 1에 선다. 3ms에 온 P4가 큐 0에서 실행된다.

5 / 11

4ms: 큐 0이 비어서 큐 1 차례

P4도 1ms가 남은 채로 큐 1에 선다. 큐 0이 비었으니 큐 1의 맨 앞 P1이 실행된다. 큐 1에서는 한 번에 2ms까지 실행할 수 있다.

6 / 11

6ms: P1이 큐 2로 내려감

P1은 할당량 2ms를 다 쓰고도 2ms가 남아 가장 아래 큐 2로 내려간다. 큐 1의 P2가 실행된다.

7 / 11

8ms: P2가 끝남

P2는 남은 2ms를 할당량 2ms 안에 끝냈다. P3가 실행된다.

8 / 11

10ms: P3가 큐 2로 내려감

P3는 5ms가 남은 채로 큐 2에 선다. 큐 1의 P4가 실행된다.

9 / 11

11ms: P4가 끝나고 큐 2 차례

P4는 1ms만 남아 금방 끝났다. 큐 0과 큐 1이 모두 비어서 큐 2의 P1이 실행된다. 큐 2에서는 한 번에 4ms까지 실행할 수 있다.

10 / 11

13ms: P1이 끝나고 P3 실행

P1은 남은 2ms라 할당량 안에 끝났다. P3는 17ms에 할당량을 다 써도 기다리는 프로세스가 없으니 계속 실행된다.

11 / 11

18ms: 모두 끝남

기다린 시간은 P1 8ms, P2 4ms, P3 8ms, P4 6ms로 평균 6.5ms다. 실행 시간을 미리 몰라도, 짧은 P2·P4는 큐 1에서 끝났고 긴 P1·P3는 큐 2까지 내려갔다. 아래 큐에서 너무 오래 기다린 프로세스는 위 큐로 올려 주기도 한다(에이징).