0. 원리
MLFQS(Multi-Level Feedback Queue Scheduling)은 이름 그대로 여러 개의 큐를 활용한 스케줄링 기법이다. 각 작업(프로세스)들은 큐에 담겨 스케줄링되는데, 이 때 각각의 큐에 작업이 들어가거나 이동하는 과정에서 여러 가지 피드백에 기초한 움직임이 일어난다.
1. 정책
MLFS의 정책은 다음과 같다.
- 스케줄링을 위한 프로세스 큐 $N$개가 있을 때, 각 큐들은 서로 다른 우선순위를 가진다.
- 우선순위가 높은 큐의 작업들부터 먼저 수행된다.
- 임의의 두 작업 $A$와 $B$가 있을 때, 우선순위가 $A > B$ 라면(즉, $A$가 $B$보다 우선순위가 높은 큐에 들어있다면) $A$가 수행된다.
- 두 작업 $A$, $B$의 우선순위가 $A == B$ 라면(즉, $A$, $B$가 같은 큐에 있다면) 둘은 RR(Round-Robin)방식으로 수행된다.
- 임의의 큐에 들어있는 작업이 해당 큐에서 배정해 준 시간을 모두 사용한 경우 작업은 그 다음 우선순위를 가진 큐로 이동한다.
- 임의의 시간 $S$마다 모든 작업은 최상위 큐로 이동한다.
2. 설명
MLFQS는 SJF, STCF같은 스케줄링 기법과 Round-Robin 스케줄링 기법의 각 단점을 보완하는 방식이다. SJF로 대표되는 스케줄링 기법들은 각 작업이 어느 정도의 작업 시간을 가질 지를 파악하고 있어야 한다는 단점이 존재하며(운영체제는 그것을 일반적으로 알 수 없다), RR방식은 빠른 반응성을 보이지만 최악의 반환 시간을 가질 수 있다는 단점이 존재한다.
MLFQS는 각기 다른 우선순위의 큐들을 이용해 스케줄링함으로써 빠른 반응이 필요한 대화형 프로그램들은 높은 우선순위의 큐에, 긴 CPU점유를 필요로 하는 작업들은 낮은 우선순위의 큐에 자동으로 위치하도록 함으로써 효율적인 반환 시간과 반응성을 가질 수 있다.
다만 이 경우 낮은 우선순위의 큐에 작업들이 존재하는 상황에서 빠른 응답이 필요한 프로그램들이 끊임없이 진입하는 경우, 낮은 우선순위 큐의 작업들이 영영 수행되지 못하는 기아 현상이 발생할 수 있는데, 이를 방지하기 위한 정책이 6번 정책이다. 어차피 작업들은 각 큐마다 작업들에게 제공하는 타임 슬라이스를 모두 소진하면 다음 큐로 점차 내려가게 되므로, 가장 간단하게 모든 작업을 일괄적으로 최우선순위 큐로 올림으로써 기아 현상을 해결할 수 있는 것이다.
참고로 MLFQ에서 큐의 개수나 작업들을 부스팅하는 시간 $S$를 어떠한 값으로 주어야 하는지는 정확히 알 수 없다. 단지 워크로드를 충분히 경험해 보고 그에 맞는 값을 찾아가야 한다.