스케줄링 정책 중에 Multi Level Feedback Queue(MLFQ)가 있다.

앞서 살펴봤던 SJF/STCF 등의 정책은 반환시간을 최적화시키지만 응답시간에는 문제가 있으며, RR은 응답시간은 빠르지만 반환시간이 나빠지기 때문에 두 지표는 트레이드오프 관계에 있다고 볼 수 있다.

그러나 MLFQ는 이 두 지표의 최적화된 값을 모두 따라잡는 것을 목표로 한다.

또한 SJF는 실행을 해보기 전에 잡들의 실행시간을 알아야 한다는 비현실적인 가정을 필요로 하지만, MLFQ는 이러한 가정 없이도 동작한다.

MLFQ는 이름에서 알 수 있듯이, 잡들을 담는 큐를 여러개(Multi Level) 관리하는데, 각 레벨은 잡들의 우선순위를 나타낸다.

즉 여러 계층의 큐가 있을때, 개념적으로 가장 위에 존재하는 큐를 우선순위가 높은 잡들이 담기는 큐, 가장 아래에 존재하는 큐는 우선순위가 낮은 잡들이 담기는 큐가 되는 것이다.

이러한 상황에서 스케줄러는 아래의 규칙대로 스케줄링을 진행한다.

1. 높은 우선순위를 갖는 큐에 담긴 잡들을 더 우선적으로 스케줄링한다.

2. 같은 우선순위를 갖는(같은 큐에 담긴) 잡들에 대해서는 라운드로빈으로 스케줄링한다.

3. 새로운 잡이 추가될 경우에는, 처음엔 반드시 가장 높은 우선순위를 갖는 큐에 담는다.

4. 만약 해당 잡이 타이머 인터럽트에 걸릴 경우(너무 긴 잡이라는 뜻), 한 단계 낮은 우선순위를 갖는 큐로 강등된다.
   그러나 타임 슬라이스를 다 사용하기 이전에 IO 발생 등으로 인해 스스로 cpu를 반납할 경우에는 강등시키지 않고 그대로 유지한다.

5. 일정한 주기마다 모든 잡들을 우선순위가 가장 높은 큐로 전부 이동시킨다.

사실 1,2번 규칙의 경우에는 굉장히 상식적으로 들린다.

여러 잡들의 우선순위가 다를 경우에 더 높은 우선순위를 갖는 잡들을 먼저 스케줄링한다는 점은 그냥 생각해도 말이 되며, 같은 우선순위일 경우에는 공정하게 라운드로빈 방식으로 스케줄링되기 때문이다.

그렇다면 우선순위가 정해지는 방식이 중요해지는데, 이를 위해 3,4,5번 규칙이 존재한다.

3번 규칙에 따라, 시스템에 잡이 처음 들어왔을 때는 이 잡이 짧은지 긴지 알 수 없으므로 일단은 우선순위가 가장 높은 큐에 배치하게 된다.

스케줄러는 반환시간을 줄이려는 목표를 갖고 있기 때문에, 우선순위가 높다는 것은 실행시간이 짧다는 뜻과 같은데, 실행 시간이 짧은 잡들을 먼저 처리함으로써 반환시간을 최적화하는 것이 SJF, STCF 정책의 기본 개념이기 때문이다.

전체 실행시간을 모르는 상태에서 이를 파악하기 위해서 타임아웃을 기준으로 잡을 수 있다.

라운드로빈을 활용하기 위해서 특정 주기의 타임슬라이스마다 타임아웃을 걸어서 잡들을 나눠 실행하는데, 타임아웃이 많이 걸리는 잡을 실행시간이 긴 잡, 적게 걸리는 잡을 짧은 잡이라고 볼 수 있기 때문이다.

그렇기 때문에 타임아웃이 한번 걸릴 때 마다 우선순위가 한단계씩 낮아지는 4번 규칙이 존재한다.

처음에는 최상위 큐에 들어왔다가, 한번 cpu를 할당 받았다가 주어진 시간을 다 써나갈수록 점점 우선순위가 낮아지며 빨리 끝나는 다른 숏잡들보다 늦게 스케줄링되면서 결과적으로 전체 실행시간이 짧은 잡들이 빨리 처리되는 것이다.

결과적으로 롱잡이 늦게, 숏잡이 빨리 처리되면서 반환시간이 줄어든다.

그러나 실행시간이 짧은 잡들, 대화형 작업 등이 계속해서 추가되거나, 타임아웃이 걸리기 전에 계속 cpu를 반납함으로써 우선순위를 높게 가져가는 잡들이 계속 있다고 생각해보자.

이러한 경우에는 우선순위가 낮아진 잡들은 최악의 경우 평생 실행되지 않는 starvation 상태에 놓이게 되는 문제가 발생한다.

높은 우선순위를 갖는 잡들만 cpu를 계속해서 점유하기 때문에, 어떤 프로그래머가 이를 악의적으로 이용하여 자신의 프로그램이 계속해서 cpu를 사용하도록 코드를 설계할 수도 있기 때문이다.

이러한 문제점들을 해결하기 위해 규칙 5번을 추가함으로써, 일정시간마다 모든 잡들을 맨 위로 옮겨버리는 것이다.

그렇기 때문에 지정해둔 일정 기간인 S마다 롱잡들도 규칙2번에 의해 최상위 큐에서 한번씩 실행됨이 보장된다.

즉 MLFQ는 같은 우선순위의 잡은 라운드로빈으로 나눠줌으로써 응답시간이 빨라지는 효과를 가지며, 우선순위에 의해 실제로 빨리 끝나는 잡들이 먼저 스케줄링되면서 반환시간도 빨라지게 된다.