MLFQ(Multilevel Feedback Queue, 다중 레벨 피드백 큐)는 우선순위와 시간 할당량(time quantum)이 서로 다른 여러 개의 준비 큐를 운영하는 CPU 스케줄링 알고리즘입니다. 새로 생성된 프로세스는 항상 최상위 우선순위 큐에서 시작하며, 실행 중 나타나는 행동 패턴에 따라 더 높은 큐로 승격되거나 낮은 큐로 강등됩니다. 이러한 적응형 구조 덕분에 대화형(interactive) 프로세스와 CPU 집약적 프로세스의 요구를 효과적으로 균형 있게 조율할 수 있습니다.
MLFQ의 기본 구조
- 큐 0 (최고 우선순위) — 시간 할당량: 1
- 큐 1 (중간 우선순위) — 시간 할당량: 2
- 큐 2 (최저 우선순위) — FCFS(선입선처리) 방식
프로세스 이동 규칙
- 새로운 프로세스는 항상 큐 0에서 시작합니다.
- 시간 할당량이 모두 소진되면 다음 하위 큐로 강등됩니다.
- 에이징(Aging) 메커니즘이 장기 대기 프로세스를 승격시켜 기아 상태를 방지합니다.
MLFQ의 작동 원리
MLFQ는 다음과 같은 핵심 원칙에 따라 동작합니다.
- 우선순위 기반 스케줄링: 우선순위가 높은 큐부터 먼저 처리됩니다.
- 가변 시간 할당량: 우선순위가 높은 큐일수록 더 짧은 시간 조각(time slice)을 부여받습니다.
- 동적 우선순위 조정: 프로세스의 행동에 따라 큐 사이를 자유롭게 이동합니다.
- 에이징 메커니즘: 오랫동안 대기한 프로세스를 승격시켜 기아(starvation) 현상을 예방합니다.
예제
다음과 같은 특성을 가진 세 개의 프로세스를 살펴보겠습니다.
| 프로세스 | 도착 시간 | CPU 버스트 시간 | 초기 큐 |
|---|---|---|---|
| P1 | 0 | 8 | 큐 0 |
| P2 | 1 | 4 | 큐 0 |
| P3 | 2 | 2 | 큐 0 |
큐 0의 시간 할당량은 1, 큐 1의 시간 할당량은 2이며, 큐 2는 FCFS 방식으로 동작한다고 가정합니다.
MLFQ 실행 타임라인
| 실행 구간 | 실행 프로세스 | 소속 큐 |
|---|---|---|
| 0 ~ 1 | P1 | 큐 0 |
| 1 ~ 2 | P2 | 큐 0 |
| 2 ~ 3 | P3 | 큐 0 |
| 3 ~ 4 | P2 | 큐 1 |
| 4 ~ 6 | P1 | 큐 1 |
| 6 ~ 8 | P2 | 큐 1 |
| 8 ~ 14 | P1 | 큐 2 (FCFS) |
P1과 P2는 시간 할당량을 초과하여 하위 큐로 강등되는 반면, P3는 큐 0에서 단 한 번의 실행만으로 작업을 마무리합니다. 이처럼 MLFQ는 짧은 작업에 빠르게 응답하고 긴 작업은 점차 낮은 우선순위에서 처리함으로써 전체적인 시스템 효율을 높입니다.
활용 사례
MLFQ는 다음과 같은 환경에서 특히 효과적입니다.
- 대화형 애플리케이션: 웹 브라우저, 텍스트 편집기, GUI 애플리케이션은 사용자 입력에 대한 빠른 응답 시간의 혜택을 받습니다.
- 시분할(Time-sharing) 시스템: 대화형 작업과 배치 작업이 공존하는 다중 사용자 시스템에 적합합니다.
- 실시간 시스템: 중요 작업과 비중요 작업에 서로 다른 우선순위 수준이 필요한 시스템에 활용됩니다.
- 게임 애플리케이션: 오디오·네트워킹 같은 백그라운드 작업을 관리하면서도 즉각적인 입력 처리가 필요한 게임 환경에 적합합니다.
장점
- 향상된 응답 시간: 짧은 프로세스가 높은 우선순위 큐에서 신속하게 처리됩니다.
- 동적 우선순위 조정: 프로세스의 행동 패턴에 자동으로 적응합니다.
- 기아 방지: 에이징 메커니즘 덕분에 오래 대기한 프로세스도 결국 CPU 시간을 할당받습니다.
- 우수한 처리량: 대화형 작업과 배치 처리의 요구를 효과적으로 균형 있게 조율합니다.
- 유연한 설정: 시간 할당량과 큐의 개수를 워크로드 특성에 맞게 자유롭게 조정할 수 있습니다.
단점
- 구현 복잡성: 서로 다른 정책을 가진 여러 큐를 관리해야 하므로 시스템 복잡도가 높아집니다.
- 높은 오버헤드: 큐 간 잦은 문맥 전환(context switch)과 우선순위 재조정으로 인해 스케줄링 비용이 증가할 수 있습니다.
- 매개변수 튜닝의 어려움: 큐의 개수, 시간 할당량, 승격·강등 기준을 최적값으로 맞추기가 쉽지 않습니다.
- 스케줄러 게이밍 가능성: 일부 프로세스가 시간 할당량이 끝나기 직전 의도적으로 I/O를 발생시켜 높은 우선순위를 계속 유지하려 할 수 있습니다.
