OSTEP: 8. Scheduling:The Multi-Level Feedback Queue

이 글은 OSTEP(Operating Systems: Three Easy Pieces)의 ‘Scheduling: MLFQ’ 문서를 직접 읽고 정리한 내용이다.
이론적 알고리즘의 원리와 실제 운영체제에서의 변형·적용 사례를 비교해 이해하는 데 초점을 맞췄다.

---

1. MLFQ의 기본 아이디어

스케줄링의 궁극적 목표는 두 가지다.

• 대화형(interactive) 환경 → 사용자 응답성을 높이는 것
• 배치(batch) 환경 → 전체 처리율을 높이는 것

하지만 현실의 작업(job)은 CPU 사용 패턴이 제각각이라, 미리 “짧은 작업인지 긴 작업인지” 알 수 없다.
MLFQ(Multi-Level Feedback Queue)는 바로 이 문제를 해결하기 위해 등장했다.

핵심은 다음과 같다.

• 여러 개의 우선순위 큐를 둔다.
• CPU 사용 패턴을 관찰하며 프로세스를 큐 사이에서 이동시킨다.
• 짧게 실행되는 대화형 작업은 위쪽 큐에서 빠르게 처리하고,
  CPU를 오래 잡아먹는 작업은 아래쪽 큐로 내려간다.

즉, 응답성과 공정성의 균형을 맞추려는 접근이다.

---

2. MLFQ 규칙 (Rules)

OSTEP에서는 MLFQ의 동작 원리를 다섯 가지 규칙으로 설명한다.

1. Rule 1 – 높은 우선순위 큐 먼저
   항상 우선순위가 높은 큐의 작업부터 실행한다. 같은 큐 안에서는 Round Robin 방식.
2. Rule 2 – CPU 사용 패턴 기반 승격/강등
   • CPU를 오래 쓰면 → 낮은 큐로 강등
   • CPU를 짧게 쓰고 I/O로 빠지면 → 높은 큐 유지
3. Rule 3 – 새 작업은 최상위 큐에서 시작
   새로 들어온 job은 CPU burst 특성을 모르므로 우선 대화형처럼 취급한다.
4. Rule 4 – Aging 적용
   낮은 큐에서 오랫동안 대기한 job은 점차 높은 큐로 승격시켜 starvation을 방지한다.
5. Rule 5 – 정책 유연성
   큐 개수, 타임 퀀텀, 승격·강등 기준은 운영체제마다 다르게 조정할 수 있다.

---

3. 핵심 개념 정리

• Priority (우선순위):
  짧은 CPU burst → 높은 우선순위 유지, 긴 job → 낮은 큐로 이동.
• Starvation (기아):
  상위 큐에 job이 몰리면, 하위 큐 job은 실행 기회를 잃을 수 있다.
• Aging (에이징):
  오래 대기한 job을 승격시켜 기아 현상을 해소한다.

즉, MLFQ는 priority 기반 스케줄링의 문제를 aging 기법으로 보완한 모델이다.

---

4. 현실 운영체제에서의 활용

MLFQ는 교과서적 모델이지만, 실제 운영체제와 시스템에서도 변형된 형태로 널리 활용된다.

• Windows Scheduler
  MLFQ 변형을 채택.
  I/O-bound 프로세스에 높은 우선순위를 주고, CPU-bound 프로세스는 낮은 큐로 이동.
  장시간 대기한 job에는 priority boost를 적용해 aging 구현.
• BSD / macOS
  Time-sharing 클래스에서 MLFQ 유사 정책을 사용.
  UI와 같은 대화형 앱이 CPU를 빠르게 받을 수 있도록 설계됨.
• Linux (CFS: Completely Fair Scheduler)
  MLFQ를 그대로 쓰지 않고, 공정성(fairness) 을 수학적으로 정의한 CFS를 도입.
  하지만 본질적으로 짧은 작업에는 빠른 응답, 긴 작업은 CPU 독점 방지라는 철학은 MLFQ와 유사하다.
• 기업 시스템 (DBMS, 클러스터 스케줄러)
  • SQL Server, Oracle DB 등 DBMS는 쿼리 실행에서도 짧은 쿼리를 우선 처리하는 MLFQ-like 전략을 채택.
  • 구글 Borg, Kubernetes와 같은 대규모 클러스터 스케줄러도 “작은 job 우선, 큰 job 후순위”라는 원칙에서 MLFQ 철학을 계승.

---

5. 요약 및 맺음말

MLFQ는 단순 우선순위 스케줄링이 가진 기아 문제를 해결하고,
대화형 시스템의 응답성과 배치 시스템의 처리율을 동시에 고려하는 알고리즘이다.

• Rules: 우선순위, 승격/강등, 새 job 처리, aging, 정책 유연성
• 현실 적용: Windows와 macOS는 MLFQ 변형, Linux는 CFS로 발전, 기업 시스템에서도 원칙을 계승

결국 MLFQ는 그대로 쓰이지 않더라도,
현대 스케줄러 설계의 근본적 뿌리라고 할 수 있다.