OSTEP 08. Multi-level Feedback

이번 장의 주제는 Multi-level Feedback Queue(MLFQ)입니다. 이전 장의 FIFO, SJF, STCF, RR은 작업의 실행 시간이나 스케줄링 목표를 비교적 단순하게 놓고 봤습니다. 하지만 실제 운영체제는 작업이 얼마나 오래 실행될지 미리 알 수 없습니다. MLFQ는 이 현실적인 조건에서 작업의 과거 실행 행동을 피드백으로 삼아 우선순위를 계속 조정하는 CPU 스케줄링 방식입니다.

한 문장 요약

MLFQ는 모든 작업을 처음에는 높은 우선순위에서 시작시키고, CPU를 오래 쓰는 작업은 낮은 큐로 내리며, 짧게 실행하고 자주 양보하는 작업은 높은 우선순위에 더 오래 머물게 하는 동적 스케줄러입니다.

핵심 질문

이 장의 핵심 질문은 다음과 같습니다.

질문	핵심 답변
작업의 실행 시간을 모를 때 어떻게 스케줄링할 수 있는가?	처음에는 짧은 작업일 가능성이 있다고 보고 높은 우선순위에 둔 뒤, 실제 CPU 사용 패턴을 관찰해 우선순위를 조정합니다.
MLFQ의 목표는 무엇인가?	짧은 작업에는 좋은 반환 시간을, 대화형 작업에는 빠른 응답 시간을 제공하는 것입니다.
여러 큐는 무엇을 의미하는가?	각 큐는 서로 다른 우선순위입니다. 높은 큐가 먼저 실행되고, 같은 큐 안에서는 RR 방식으로 CPU를 나눕니다.
기아 상태는 어떻게 막는가?	일정 주기마다 모든 작업을 최상위 큐로 올리는 priority boost를 사용합니다.
스케줄러를 속이는 작업은 어떻게 막는가?	한 번의 연속 실행 시간이 아니라 해당 큐에서 누적 사용한 CPU 시간을 기준으로 강등합니다.

MLFQ의 기본 구조

MLFQ는 여러 개의 준비 큐를 둡니다. 위쪽 큐일수록 우선순위가 높고, 운영체제는 항상 비어 있지 않은 가장 높은 우선순위 큐에서 실행할 작업을 고릅니다.

기본 선택 규칙은 단순합니다.

규칙	내용
규칙 1	Priority(A) > Priority(B)이면 A를 실행합니다.
규칙 2	Priority(A) = Priority(B)이면 A와 B를 RR 방식으로 실행합니다.

이 두 규칙만 보면 정적 우선순위 스케줄링과 비슷해 보입니다. MLFQ의 핵심은 우선순위가 고정되어 있지 않다는 점입니다. 작업이 CPU를 오래 쓰는지, 짧게 쓰고 자주 I/O를 기다리는지를 관찰한 뒤 큐 위치를 바꿉니다.

우선순위 피드백

MLFQ는 처음부터 어떤 작업이 짧은 작업인지 알 수 없으므로, 새 작업을 일단 최상위 큐에 넣습니다. 짧은 작업이라면 높은 우선순위에서 빨리 끝날 것이고, 긴 작업이라면 CPU를 계속 사용하면서 점차 낮은 큐로 내려갑니다.

규칙	내용	의도
규칙 3	새 작업은 최상위 큐에 배치됩니다.	짧은 작업일 가능성을 먼저 인정합니다.
초기 규칙 4a	타임 슬라이스를 모두 사용하면 한 단계 낮은 큐로 이동합니다.	CPU 중심 작업을 아래 큐로 보냅니다.
초기 규칙 4b	타임 슬라이스를 다 쓰기 전에 CPU를 양보하면 같은 우선순위를 유지합니다.	대화형/I/O 중심 작업의 응답성을 높입니다.

이 방식은 짧은 작업을 빠르게 처리한다는 점에서 SJF에 가까운 효과를 냅니다. 동시에 키보드 입력, 마우스 이벤트, 디스크 I/O 등을 기다리는 대화형 작업은 CPU를 짧게 쓰고 자주 양보하므로 높은 우선순위에 머무를 가능성이 큽니다.

문제 1: 기아 상태

단순한 MLFQ는 대화형 작업이 많을 때 문제가 생깁니다. 높은 우선순위의 작업이 계속 들어오면 낮은 큐의 CPU 중심 작업은 거의 실행되지 못합니다. 이것이 기아 상태(starvation)입니다.

해결책은 일정 주기 S마다 모든 작업을 최상위 큐로 올리는 priority boost입니다.

priority boost는 두 가지 역할을 합니다. 첫째, 낮은 큐에 오래 머문 작업도 언젠가는 CPU를 받을 수 있게 합니다. 둘째, 처음에는 CPU 중심 작업이었지만 나중에 대화형 작업처럼 행동이 바뀐 프로세스를 다시 평가할 기회를 줍니다.

문제 2: 스케줄러 조작

초기 규칙 4b에는 허점이 있습니다. 어떤 작업이 타임 슬라이스가 끝나기 직전에 일부러 I/O를 요청하면, CPU를 거의 다 쓰고도 같은 우선순위에 남을 수 있습니다. 이렇게 하면 높은 우선순위 큐를 사실상 독점할 수 있습니다.

따라서 최종 규칙에서는 연속 실행 시간이 아니라 해당 큐에서 누적 사용한 CPU 시간을 기준으로 강등합니다. CPU를 한 번에 다 쓰든, 여러 번 나눠 쓰든, 배정받은 시간 할당량을 모두 쓰면 아래 큐로 내려갑니다.

큐별 타임 슬라이스

실제 MLFQ 구현에서는 큐마다 타임 슬라이스를 다르게 줄 수 있습니다. 높은 우선순위 큐는 대화형 작업을 빠르게 번갈아 실행해야 하므로 짧은 타임 슬라이스가 어울립니다. 낮은 우선순위 큐는 CPU 중심 작업이 많으므로 더 긴 타임 슬라이스를 주어 문맥 교환 비용을 줄일 수 있습니다.

큐	일반적인 타임 슬라이스	이유
높은 큐	짧음	대화형 작업을 빠르게 교체해 응답 시간을 줄입니다.
낮은 큐	김	CPU 중심 작업의 문맥 교환 비용을 줄입니다.

예를 들어 Q2=10ms, Q1=20ms, Q0=40ms처럼 설정할 수 있습니다. 다만 큐 개수, 큐별 타임 슬라이스, priority boost 주기 S는 정답이 있는 값이 아니라 워크로드에 맞춰 조정해야 하는 정책 변수입니다.

최종 규칙

책에서 정리한 MLFQ의 최종 규칙은 다음과 같습니다.

규칙	최종 형태
규칙 1	Priority(A) > Priority(B)이면 A가 실행됩니다.
규칙 2	Priority(A) = Priority(B)이면 A와 B는 RR 방식으로 실행됩니다.
규칙 3	새 작업은 최상위 큐에 배치됩니다.
규칙 4	작업이 현재 큐에서 배정받은 CPU 시간을 누적해서 모두 사용하면, CPU를 몇 번 양보했는지와 무관하게 한 단계 낮은 큐로 이동합니다.
규칙 5	일정 주기 S가 지나면 모든 작업을 최상위 큐로 이동합니다.

실습 코드

OSTEP homework의 mlfq.py를 사용하면 우선순위 하락, 짧은 작업 선호, priority boost를 직접 확인할 수 있습니다.

작업 형식은 다음과 같습니다.

예를 들어 20,80,5는 t=20에 도착하고, 총 80ms의 CPU 시간이 필요하며, CPU를 5ms 사용할 때마다 I/O를 요청하는 작업입니다.

정리

MLFQ는 작업 길이를 미리 알 수 없는 현실적인 상황에서 응답 시간과 반환 시간을 함께 개선하려는 스케줄러입니다. 새 작업은 최상위 큐에서 시작하고, CPU를 오래 쓰는 작업은 점차 낮은 큐로 내려가며, 같은 우선순위 안에서는 RR로 공정성을 제공합니다.

단순한 MLFQ는 기아 상태와 스케줄러 조작에 취약합니다. 그래서 최종 형태에서는 주기적인 priority boost와 누적 CPU 사용량 기반 강등을 사용합니다. 결국 MLFQ의 핵심은 작업의 과거 행동을 피드백으로 사용해 우선순위를 계속 재평가하는 것입니다.