1. MLFQ의 목적
스케줄러 설계 시 두 가지 상충되는 목표가 있습니다.
- 반환 시간 (Turnaround Time) 최적화: 짧은 작업을 먼저 실행 (SJF 방식)
- 응답 시간 (Response Time) 최적화: 대화형 사용자에게 빠른 응답 (RR 방식)
SJF는 작업의 총 실행 시간을 미리 알아야 하는 문제가 있고, RR은 반환 시간에 불리합니다.
MLFQ의 핵심 질문은 이것입니다: "작업의 실행 시간에 대한 사전 정보 없이, 대화형 작업의 응답 시간을 최소화하고 동시에 반환 시간을 최소화하는 스케줄러를 어떻게 설계할 수 있을까?"
2. MLFQ의 기본 동작 규칙
MLFQ는 여러 개의 큐로 구성되며, 각 큐는 서로 다른 우선순위를 갖습니다. 스케줄러는 작업의 특성에 따라 우선순위를 동적으로 조정합니다.
- 규칙 1:
Priority(A) > Priority(B)이면, A가 실행됩니다. (B는 실행되지 않음) - 규칙 2:
Priority(A) = Priority(B)이면, A와 B는 라운드 로빈(RR) 방식으로 실행됩니다.
작업의 우선순위를 결정하는 규칙은 다음과 같습니다.
- 규칙 3: 작업이 시스템에 진입하면, 가장 높은 우선순위 큐에 배치됩니다.
- 규칙 4: 작업이 주어진 타임 슬라이스를 모두 사용하면, 우선순위가 낮아집니다. (즉, 한 단계 아래 큐로 이동)
- 규칙 5: 작업이 타임 슬라이스를 소진하기 전에 CPU를 양도하면 (예: I/O 작업), 같은 우선순위를 유지합니다.
이 규칙들은 다음과 같은 효과를 가집니다.
- SJF 근사: CPU를 오래 사용하는 작업(CPU-bound)은 타임 슬라이스를 계속 소진하여 낮은 우선순위 큐로 빠르게 강등됩니다. (규칙 4)
- 응답 시간 최적화: 입출력 위주의 대화형 작업(I/O-bound)은 CPU를 양도하므로 높은 우선순위를 유지하며 빠른 응답을 받습니다. (규칙 5)
3. 기본 규칙의 문제점
하지만 위의 기본 규칙만으로는 심각한 결점 세 가지가 발생합니다.
-
기아 상태 (Starvation)
- 항상 더 높은 우선순위의 작업들만 시스템에 계속 도착한다면, 낮은 우선순위 큐에 있는 작업들은 CPU 시간을 전혀 할당받지 못할 수 있습니다.
-
얌체 프로세스 (Gaming the Scheduler)
- 악의적인 프로세스가 타임 슬라이스가 끝나기 직전, 고의로 I/O 작업을 요청하여 CPU를 양도할 수 있습니다.
- 이 경우, 규칙 5에 따라 높은 우선순위를 계속 유지하며 CPU를 불공평하게 독점하게 됩니다.
-
특성 변화 대응 불가
- 처음에는 CPU 위주 작업이라 낮은 큐로 강등되었으나, 나중에 대화형 작업으로 성격이 바뀐다 해도 시스템은 과거 기록만 보고 해당 작업을 계속 낮은 우선순위로 취급합니다.
4. 문제 해결 방안
이러한 문제들을 해결하기 위해 MLFQ에 두 가지 핵심 규칙이 추가됩니다.
해결책 1: 우선순위 상향 조정 (Priority Boost)
규칙 6 (수정): 일정 기간 S가 지나면, 시스템의 모든 작업을 최상위 큐로 이동시킨다.
이 '우선순위 상향 조정'은 두 가지 문제를 한 번에 해결합니다.
- 기아 상태 해결: 아무리 낮은 우선순위에 있던 작업이라도, 주기적으로 최상위 큐로 올라가 실행될 기회를 얻습니다.
- 특성 변화 대응: CPU 위주 작업에서 대화형 작업으로 성격이 바뀐 프로세스도, 최상위 큐로 이동하여 스케줄러가 자신의 변경된 특성을 파악할 기회를 갖게 됩니다.
해결책 2: 얌체 프로세스 방지 (Accounting)
규칙 4와 5를 'CPU 양도 횟수'가 아닌 'CPU 총 사용 시간'을 기준으로 변경하여 얌체 프로세스를 방지합니다.
규칙 4/5 (수정): 주어진 단계(큐)에서 작업의 CPU 총 사용 시간을 측정한다. 작업이 해당 큐의 시간 할당량(Time Allotment)을 모두 소진하면 (CPU를 한 번에 썼든, 여러 번 나눠 썼든 상관없이), 우선순위는 낮아진다. (아래 큐로 이동)
이렇게 하면 얌체 프로세스가 I/O를 아무리 짧게 자주 발생시켜도, 결국 해당 큐의 총 CPU 사용 시간을 채우게 되면 아래 큐로 강등됩니다.
