2-5. Virtualization: Multi-Level Feedback Queue

스케줄링(Scheduling)은 CPU를 어떤 프로세스에 할당할지 결정하는 중요한 기술이다.
그중에서도 Multi-Level Feedback Queue(MLFQ)는 현대 운영체제에서 널리 사용되는 스케줄링 방식이다. "모두를 만족시키는 스케줄러를 만들 수는 없을까?"라는 물음에서 시작된, MLFQ의 여정을 함께 살펴보자.

---

간단한 스케줄러들, 그리고 그들의 한계 🤔

FIFO (First In, First Out)

• 장점: 단순하다!
• 단점: "convoy effect"가 발생.
  예를 들어, 앞에 있는 작업이 엄청 느리면 뒤의 작업이 전부 대기 상태로 전환된다.
  → 결과적으로 CPU와 I/O 자원 이용률이 낮아짐.

SJF (Shortest Job First)

• 장점: 평균 대기 시간, 평균 완료 시간이 줄어든다.
• 단점: "작업 길이를 예측할 수 있느냐?"가 문제.
  현실에서는 대부분의 작업 길이를 정확히 알 수 없다.

RR (Round Robin)

• 장점: 응답 시간(response time)을 줄이는 데 탁월하다.
• 단점: turnaround time(처리 완료 시간)은 오히려 길어진다.

---

그래서 나온 해결책: MLFQ의 철학

MLFQ는 위 스케줄링 방식들의 장점을 결합해 다음과 같은 목표를 세웠다.

1. 짧은 작업을 먼저 실행해 turnaround time을 최적화하자.
2. RR 방식을 사용해 응답이 빠른 시스템처럼 느껴지게 만들자.
3. 과거의 실행 정보를 바탕으로 미래를 예측하자.

---

MLFQ의 기본 동작 원리 🛠️

MLFQ는 여러 개의 큐(queue)로 구성된다. 각 큐는 우선순위(priority level)가 다르다.
최상위 큐는 가장 높은 우선순위를 가지며, 가장 먼저 실행된다.

MLFQ의 기본 규칙

1. 규칙 1: $Priority(A) > Priority(B)$이면, A를 실행한다.
2. 규칙 2: $Priority(A) = Priority(B)$이면, RR 방식으로 실행한다.
3. 규칙 3: 새로 들어온 작업은 맨 위 큐에 배정한다.
4. 규칙 4a: 주어진 time slice를 모두 소진하면 아래 큐로 이동한다.
5. 규칙 4b: time slice를 다 쓰기 전에 양보하면 우선순위를 유지한다.

---

MLFQ의 작동 과정 👇

1. 새 작업이 시스템에 들어오면, 맨 위 큐(최상위 우선순위)로 배정된다.
2. 작업이 time slice를 소진하면 한 단계 아래 큐로 이동한다.
   • → 짧은 작업은 상위 큐에서 빨리 처리되도록 설계.
3. 주기적으로 I/O 작업을 양보하는 interactive job은 높은 우선순위를 유지한다.

---

문제점? 완벽한 건 없다!

MLFQ는 똑똑한 스케줄러지만, 몇 가지 문제가 있다.

1. Starvation(기아 현상)
   너무 많은 상위 우선순위 작업이 들어오면, 긴 작업이 영원히 대기 상태에 머물 수 있다.
2. Scheduler 악용
   프로세스가 time slice의 99% 동안 실행 후 1%만 I/O 작업을 반복한다면,
   상위 큐를 독점할 수 있다.
3. 성격 변환 미대응
   CPU-bound(연산 위주) 작업이 I/O-bound(입출력 위주)로 바뀌거나 그 반대일 때, 기존 규칙만으로는 대처하기 어렵다.

[!NOTE]

위 문제들을 막기 위하여, 규칙 5를 새롭게 정의하고, 규칙 4를 재정의한다.

문제 해결! 수정된 MLFQ 규칙 🌟

규칙 5 (New)

S시간이 지나면 모든 작업을 최상위 큐로 올린다.

• Starvation 방지: 대기 중인 긴 작업도 언젠가 실행 기회를 얻는다.

---

규칙 4 (Modified)

주어진 단계에서 정해진 최대 시간을 초과하면, 우선순위를 낮춘다.

• 한 단계에서 무제한으로 실행되는 걸 방지.

---

최종 MLFQ 규칙 정리 📝

1. 규칙 1: $Priority(A) > Priority(B)$이면, A 실행.
2. 규칙 2: $Priority(A) = Priority(B)$이면, RR로 실행.
3. 규칙 3: 새로 들어온 작업은 맨 위 큐에 배정.
4. 규칙 4: 한 단계에서의 최대 시간을 초과하면 우선순위 낮춤.
5. 규칙 5: S시간이 지나면 모든 작업을 최상위 큐로 올림.

---

핵심 튜닝 포인트 🎯

1. 상위 큐 → 짧은 time slice
   → 빠른 작업은 상위 큐에서 빠르게 처리.
2. 하위 큐 → 긴 time slice
   → 무거운 작업에서 context switching 비용을 줄임.

---

마무리하며 🎉

MLFQ는 다양한 유형의 작업을 효율적으로 스케줄링하는 데 최적화된 방식이다.
짧은 작업은 빠르게 처리하고, 무거운 작업은 최대한 효율적으로 실행할 수 있는 구조를 제공한다.

다음 글에서는 CPU 스케줄링의 실제 구현과 시뮬레이션에 대해 다룰 예정이다.
궁금한 점은 댓글로 남겨 주세요! 🚀