📌 MLFQ?
멀티 레벨 피드백 큐(Multi-level Feedback Queue, MLFQ)란 프로세스의 스케쥴링하는 하나의 방법이 아니다.
핵심만 짚고 넘어가자면, 프로세스에 고정된 우선순위를 부여하는 것이 아니라 각 작업의 특성에 따라 동적으로 우선순위를 부여하는 것을 일컫는다.
MLFQ가 해결하려는 2가지 문제
MLFQ가 해결하려는 2가지 문제는 다음과 같다.
- 짧은 작업을 먼저 실행시켜 반환 시간을 최적화
- SJF나 STCF 같은 알고리즘은 작업의 실행 시간 정보를 필요로 하지만, 불행히도 운영체제는 이 실행 시간을 미리 알 수 없다.
- 대화형 사용자에게 빠른 응답을 해주기 위해 반환 시간을 최적화
- RR과 같은 알고리즘은 응답 시간을 단축시키지만 반환 시간은 거의 최악이다.
MLFQ의 기본 규칙
현재 구현되어 있는 여러 MLFQ들은 각각 마다 미묘한 차이가 있지만, 기본적으로 비슷한 알고리즘을 제시하고 있다.
MLFQ는 여러 개의 큐로 구성되며, 각각 다른 우선순위가 배정된다. 실행 준비가 된 프로세스는 이 중 하나의 큐에 존재한다.
큐에는 둘 이상의 작업이 존재할 수 있으며, 이들은 모두 같은 우선순위를 가진다. 또한, 모두 라운드 로빈 (Round-Robin, RR)이라는 같은 스케줄링 알고리즘이 적용된다.
다시 한 번 MLFQ의 핵심에 대해 생각해 보자.
MLFQ는 어떻게 각 작업의 특성을 파악하고 동적으로 우선순위를 부여하는 것일까?
예를 들어 설명하자면 다음과 같다.
어떤 작업이 키보드 입력을 기다리며 반복적으로 CPU를 양보하면 MLFQ는 해당 작업의 우선순위를 높게 유지한다. (이러한 패턴은 대화형 프로세스가 나타내는 패턴이다)
대신에 한 작업이 긴 시간 동안 CPU를 집중적으로 사용하면 MLFQ는 해당 작업의 우선순위를 낮춘다.
이렇게 MLFQ는 작업이 진행되는 동안 해당 작업의 정보를 얻고, 이 정보를 이용하여 미래 행동을 예측한다.
MLFQ의 규칙은 다음과 같다.
- Priority(A > Priority(B) 이면, A가 실행된다 (B는 실행되지 않는다)
- Priority(A) = Priority(B) 이면, A와 B는 RR 방식으로 실행된다.
- 작업이 시스템에 진입하면, 가장 높은 우선순위, 즉 맨 위의 큐에 놓여진다.
- 주어진 타임 슬라이스를 모두 사용하면 우선순위는 낮아진다. 즉, 한 단계 아래 큐로 이동한다.
- 타임 슬라이스를 소진하기 전에 CPU를 양도하면 같은 우선순위를 유지한다
- MLFQ의 예
- 그림에서 A와 B는 가장 높은 우선순위에 존재하고, C는 중간, D는 가장 낮은 우선순위 큐에 존재한다.
- MLFQ의 동작을 고려하면 스케줄러는 가장 높은 우선순위 큐의 A와 B를 번갈아 실행할 것이다.
그림만으로는 MLFQ가 정확히 어떻게 동작하는지도 모르고, C와 D는 실행되지 않을 수도 있다는 생각을 할 수가 있다.
작업 우선순위가 시간에 따라 어떻게 변화하는지 알아보자.
📖 MLFQ 요약
알고리즘은 멀티 레벨 큐를 가지고 있으며, 지정된 작업의 우선순위를 정하기 위하여 피드백을 사용한다. 과거에 보여준 행동이 우선순위 지정의 지침이 된다.
즉, 프로세스가 시간이 지남에 따라 어떻게 행동하고 그에 맞게 어떻게 처리하는지에 대해 주의를 기울여야 한다.
MLFQ에 대해 요약하자면,
- MLFQ는 작업의 특성에 대한 정보 없이, 작업의 실행을 관찰한 후 그에 따라 우선순위를 지정한다.
- MLFQ는 반환 시간과 응답 시간을 모두 최적화한다.
짧게 실행되는 대화형 작업에 대해서는 우수한 전반적인 성능을 제공한다 (SJF / STCF와 유사) - 오래 실행되는 CPU-집중 워크로드에 대해서는 공정하게 실행하고 조금이라도 진행되도록 한다.
이러한 이유로 BSD UNIX와 여기서 파생된 다양한 운영체제 ([LEF+89; Bac86], Solaris [McD06], Windows NT 및 이후 Windows 운영체제 [CS97] 등)를 포함한 많은 시스템이 기본 스케줄러로 MLFQ를 사용한다.
