[OS] Priority Inversion부터 MLFQ까지: 스케줄링 문제와 해결책

 

핵심 가정 

1. 모든 작업의 실행 시간이 동일하다.
2. 모든 작업이 동시에 도착한다.
3. 한번 시작된 작업은 완료될 때까지 실행된다.
4. 모든 작업은 CPU만 사용하며 I/O는 수행하지 않는다.
5. 각 작업의 실행 시간을 미리 알고 있다.

지난번 FIFO부터 STCF 스케줄링 알고리즘을 공부하며 4가지 가정 중 1~4번까지의 가정을 완화하며 그에 따라 최적의 알고리즘에 대해서 알아봤습니다. 오늘은 마지막 5번 가정인 '각 작업의 실행 시간을 미리 알고 있다'는 가정을 완화해보겠습니다.. 즉, 미리 작업 길이를 알 수 없는 상황에 대한 스케줄링 방법에 대해서 알아보겠습니다. 
 
 

---

 

Priority Scheduling의 개념

• 원리: 각 프로세스에 숫자로 된 우선순위(priority)를 부여합니다.
  • 예를 들어, Unix/BSD 시스템에서는 숫자가 작을수록 우선순위가 높습니다. (반대로 Pintos에서는 숫자가 작을수록 우선순위가 낮습니다.)
• 작동 방식: 항상 우선순위가 가장 높은 프로세스에게 CPU를 할당합니다. 마치 항공사 체크인 시 퍼스트 클래스 승객을 먼저 처리하는 것과 유사합니다.
• 구현: 선점형(preemptive) 또는 비선점형(non-preemptive)으로 구현될 수 있습니다.
• 활용: 최단 작업 우선(SJF, Shortest Job First) 스케줄링을 구현하는 데 활용될 수 있습니다. 이 경우, 우선순위를 '1 / 예상 실행 시간'으로 설정하여 예상 실행 시간이 짧은 작업에 더 높은 우선순위를 줄 수 있습니다.

 

Priority Scheduling의 문제점과 해결책

• 문제점: Starvation
  • 우선순위가 낮은 작업은 우선순위가 높은 작업들이 계속해서 도착하면 무한정 대기하게 될 수 있습니다.
• 해결책: Aging
  • 작업이 대기하는 시간이 길어질수록 우선순위를 점진적으로 높여주는 방식입니다.
  • 또는 CPU를 많이 사용한 작업의 우선순위를 낮추는 방식도 있습니다.

 

Priority Inversion 문제

• 문제 상황: 우선순위 스케줄링을 동기화 기본 요소(Synch Primitives)와 함께 사용할 때 발생할 수 있는 문제입니다.
  • 스케줄링 규칙:
    1. 항상 가장 높은 우선순위의 스레드를 선택합니다.
    2. 예외: 낮은 우선순위의 스레드가 높은 우선순위 스레드가 필요로 하는 자원(resource)을 점유하고 있다면, 낮은 우선순위 스레드가 자원을 해제할 때까지 실행되어야 합니다.
• 우선순위 역전(Priority Inversion) 현상: 우선순위가 높은 스레드(H)가 우선순위가 낮은 스레드(L)가 점유하고 있는 락을 기다려야 하는 상황이 발생합니다. 즉, 우선순위가 높은 작업이 우선순위가 낮은 작업 때문에 실행되지 못하는 현상입니다.
• 발생 과정:
  1. 낮은 우선순위 작업 (L)이 공유 자원(R)에 대한 락(lock) k를 획득합니다.
  2. 높은 우선순위 작업 (H)이 락 k를 얻으려 하지만, L이 락을 해제할 때까지 대기(block)해야 합니다.
  3. 이때, 중간 우선순위 작업 (M)이 시스템에 들어와 L을 선점(preempt)합니다.
  4. 결과적으로, M이 실행되는 동안 L은 락을 해제할 수 없게 되고, H는 M보다 우선순위가 높음에도 불구하고 실행되지 못하는 문제가 발생합니다.

 

Lock의 역할

• 개념: Lock은 동시성 프로그래밍에서 공유 자원에 대한 접근을 제어하는 동기화 기본 요소입니다.
• 목적: 한 번에 하나의 스레드만 자원에 접근하도록 보장하여, 경쟁 상태(race conditions)와 데이터 손상(data corruption) 같은 문제를 방지합니다.

 
 
 

Solution: Priority Donation

• 개념: 우선순위 역전(Priority Inversion) 문제를 해결하기 위한 기술입니다.
• 원리:
  1. 높은 우선순위의 스레드가 낮은 우선순위의 스레드 때문에 대기 상태가 될 때, 자신의 우선순위를 낮은 우선순위의 스레드에게 "기부"합니다.
  2. Lock을 점유하고 있는 낮은 우선순위의 스레드는 일시적으로 대기 중인 가장 높은 우선순위 스레드의 우선순위를 상속받습니다.
  3. 이렇게 높아진 우선순위는 해당 스레드가 락을 해제할 때까지 유지됩니다.
• 장점:
  • 중간 우선순위 작업이 락을 점유하고 있는 낮은 우선순위 작업을 선점(preempting)하는 것을 방지합니다.
  • 이를 통해 낮은 우선순위 작업이 빠르게 실행되어 락을 해제하고, 높은 우선순위 작업이 대기 상태에서 벗어나 실행될 수 있게 됩니다.
  • 락이 해제되면, 낮은 우선순위 작업은 원래의 우선순위로 돌아갑니다.

 

Priority Donation 예시

가정: 숫자가 높을수록 우선순위가 높다고 가정합니다 (예: Pintos).

• 예시 1 (Single Lock):
  • 작업 우선순위: L (2), M (4), H (8)
  • L이 락 k를 점유합니다.
  • M이 락 k를 기다립니다. L은 M의 우선순위를 기부받아 자신의 우선순위가 max(M, L) = 4가 됩니다.
  • 이후 H가 락 k를 기다립니다. L은 H의 우선순위를 기부받아 자신의 우선순위가 max(H, 4) = 8로 다시 높아집니다. 이제 L은 H와 동일한 높은 우선순위로 실행되어 락을 빠르게 해제할 수 있습니다.
• 예시 2 (Multiple Locks):
  • 작업 우선순위: L (2), M (4), H (8)
  • L이 락 k를 점유하고, M이 락 k2를 점유합니다.
  • M이 락 k를 기다립니다. L은 M의 우선순위를 기부받아 자신의 우선순위가 max(M, L) = 4가 됩니다.
  • 이후 H가 락 k2를 기다립니다. M은 H의 우선순위를 기부받아 자신의 우선순위가 max(H, M) = 8이 됩니다.
  • 그런데 M은 L이 점유한 락 k를 기다리고 있으므로, M이 L에게 우선순위를 기부합니다. 결과적으로 L의 최종 우선순위는 max(M의 새로운 우선순위, L의 현재 우선순위) = max(8, 4) = 8이 됩니다.

 
 

---

 
 

알고리즘 결합

다양한 목표를 동시에 최적화하기 위해 여러 스케줄링 알고리즘을 결합할 수 있습니다.

1. 여러 개의 큐(Queue)를 둡니다: 각기 다른 특성의 작업을 담을 수 있도록 여러 개의 대기열을 만듭니다.
2. 각 큐에 다른 알고리즘을 적용합니다: 각 큐의 작업 특성에 맞춰 적절한 스케줄링 알고즘(예: Round Robin, Priority 등)을 사용합니다.
3. 프로세스를 큐 간에 이동시킵니다: 작업의 행동 변화에 따라 프로세스를 더 적합한 큐로 옮깁니다.

 

예시: 다중레벨 피드백 큐(MLFQ)

이러한 결합의 대표적인 예시가 바로 다중레벨 피드백 큐(MLFQ)입니다. MLFQ는 여러 개의 큐를 사용하고, 각 큐마다 다른 스케줄링 정책을 적용하며, 작업의 과거 행동을 바탕으로 프로세스를 큐 간에 이동시켜 최적의 성능을 끌어내는 복합적인 스케줄링 알고리즘입니다. 
 
 
 

MLFQ의 핵심 아이디어

• 여러 개의 큐 사용: MLFQ는 다양한 종류의 작업을 처리하기 위해 여러 개의 큐를 사용합니다. 각 큐는 서로 다른 우선순위를 가집니다.
• 우선순위 기반 선점: 우선순위가 높은 큐에 있는 작업은 우선순위가 낮은 큐에 있는 작업을 선점(preempt)할 수 있습니다.
• 동일 큐 내 스케줄링: 동일한 큐에 있는 작업들은 보통 라운드 로빈(Round Robin)과 같은 동일한 스케줄링 알고리즘을 사용합니다.

 
 

MLFQ가 해결하려는 근본적인 문제

MLFQ는 CPU 스케줄링에서 가장 중요한 두 가지 목표를 동시에 달성하려고 합니다.

1. Turnaround time 최적화: 짧은 작업을 우선 처리하여 turnaround time을 줄입니다. 하지만 운영체제는 작업의 실행 시간을 미리 알지 못합니다.
2. Response time 최소화: 시스템이 대화형 사용자에게 빠르게 반응하도록 응답 시간을 줄입니다. 라운드 로빈은 Response time에는 좋지만, turnaround time에는 최악의 성능을 보일 수 있습니다.

따라서, "운영체제가 프로세스의 실행 시간을 미리 알지 못하는 상황에서, 두 가지 목표(turnaround time과 response time)를 모두 균형 있게 달성할 수 있는 스케줄러를 어떻게 설계할 것인가?"라는 문제가 발생합니다.
 

 

MLFQ의 해결책: 과거 행동 기반 학습

• 핵심 아이디어: MLFQ는 과거 행동에 기반한 피드백을 사용합니다. 프로세스의 과거 행동을 바탕으로 우선순위를 동적으로 조절합니다.
• 결론: MLFQ는 과거로부터 학습하여 미래를 예측하는 스케줄러라고 할 수 있습니다. 이를 통해 시스템은 CPU 집중형 작업과 대화형 작업을 구분하고, 각 작업에 적합한 우선순위를 부여할 수 있습니다.

 

MLFQ의 기본 규칙

MLFQ 스케줄러를 만들기 위해 알아야 할 기본적인 규칙은 다음과 같습니다.

• 다수의 큐(Queue) 사용: MLFQ는 여러 개의 뚜렷이 구분된 큐를 가지고 있습니다. 각 큐에는 서로 다른 우선순위(priority level)가 할당됩니다.
• 작업의 배치: 실행 준비가 된 작업은 한 번에 하나의 큐에만 배치됩니다.
• 우선순위 기반 스케줄링:
  • 규칙 1: 만약 작업 A의 우선순위(Priority)가 작업 B보다 높다면(), A가 실행되고 B는 실행되지 않습니다.
    • Priority(A)>Priority(B)
  • 규칙 2: 만약 작업 A와 B의 우선순위가 같다면(), 두 작업은 라운드 로빈(Round Robin) 방식으로 번갈아 실행됩니다.
    • Priority(A)=Priority(B)

 

 

MLFQ: 관찰된 행동에 따른 우선순위 변화

MLFQ의 핵심은 관찰된 작업의 행동에 따라 작업의 우선순위를 동적으로 변경하는 것입니다.

• 예시:
  • 입출력(I/O) 작업을 자주 수행하는 작업: CPU를 자주 양보하고 I/O를 기다리는 작업은 interactive 작업으로 간주됩니다. 이러한 작업의 우선순위를 높게 유지하여 빠른 응답 시간을 보장합니다.
  • CPU를 집중적으로 오래 사용하는 작업: 할당된 시간을 모두 소모하는 작업은 CPU 집중형(CPU-bound) 작업으로 간주됩니다. 이러한 작업의 우선순위를 낮추어 다른 작업에게 CPU를 양보하도록 합니다.

결론적으로, MLFQ는 시간이 지남에 따라 작업의 우선순위가 어떻게 변하는지를 이해하는 것이 중요합니다. 이 메커니즘을 통해 스케줄러는 실행 시간을 미리 알지 못하는 상황에서도 다양한 작업의 요구를 효율적으로 충족시킬 수 있습니다.
 
 
 

Attempt #1: MLFQ - Priority 변경 규칙

MLFQ 스케줄러는 다음 규칙에 따라 작업의 우선순위를 동적으로 조정합니다.

• 규칙 3: 새로운 작업이 시스템에 들어오면, 가장 높은 우선순위 큐에 배치됩니다.
• 규칙 4a: 작업이 할당된 time slice를 모두 소모하며 실행을 마치면, 그 작업의 우선순위는 낮아집니다(즉, 다음 우선순위 큐로 이동합니다).
• 규칙 4b: 작업이 시간 할당량이 끝나기 전에 자발적으로 CPU를 양보하면(예: 입출력(I/O) 작업을 수행하기 위해), 해당 작업은 원래의 우선순위 수준에 머무릅니다.

이러한 방식으로 MLFQ는 실행 시간을 미리 알지 못하면서도, 최단 작업 우선(SJF, Shortest Job First) 스케줄링을 근사하게 모방합니다.

 

예시 1: 하나의 긴 작업

세 개의 큐(Q0, Q1, Q2)가 있고, 시간 할당량이 10ms인 스케줄러를 가정해 보겠습니다.

• 초기 상태: 긴 작업을 나타내는 'Long-running Job'이 시스템에 진입하면, 가장 높은 우선순위 큐인 Q2에 배치됩니다.
• 1단계 (Q2): 이 작업은 Q2에서 할당된 10ms의 시간 할당량을 모두 사용합니다.
• 2단계 (Q1): 규칙 4a에 따라, 작업의 우선순위가 하나 낮아져 Q1으로 이동합니다.
• 3단계 (Q0): Q1에서도 할당된 10ms를 모두 사용한 후, 최종적으로 시스템에서 가장 낮은 우선순위인 Q0으로 이동하여 그곳에 머무릅니다.

 
이 그래프는 시간이 지남에 따라 긴 작업의 우선순위가 점진적으로 낮아지는 과정을 보여줍니다.
 
 

예시 2: 짧은 작업의 도착

이 예시는 긴 작업(Job A)이 실행 중일 때, 짧은 작업(Job B)이 도착하는 상황을 다룹니다.

• 가정:
  • 작업 A (검정색): CPU를 오래 사용하는 긴 작업(CPU-intensive job)입니다.
  • 작업 B (회색): 실행 시간이 20ms인 짧은 대화형 작업(interactive job)입니다.
• 상황:
  • 긴 작업 A는 이미 실행 중이며 우선순위가 낮은 큐로 이동했을 것입니다.
  • 시간 T=100에 짧은 작업 B가 도착합니다.
• MLFQ의 작동:
  • 규칙 3에 따라, 새로 도착한 B는 가장 높은 우선순위 큐(예: Q2)에 배치됩니다.
  • MLFQ의 규칙 1에 의해, B는 A보다 높은 우선순위를 가지므로, A를 선점(preempt)하고 즉시 실행됩니다.
  • B는 실행 시간이 짧기 때문에(20ms), 할당된 시간 내에 완료되고 시스템을 떠납니다.
  • B가 완료된 후, A는 다시 실행을 재개합니다.

 

 
이 예시를 통해 MLFQ는 짧은 작업에 즉각적인 우선순위를 부여하여, 응답 시간을 최소화하고 SJF(최단 작업 우선)와 유사한 효과를 얻는 것을 볼 수 있습니다.

 

예시 3: I/O 작업의 처리

 
이 예시는 I/O를 자주 사용하는 interactive job이 어떻게 높은 우선순위를 유지하는지 보여줍니다.

• 가정:
  • 작업 A (검정색): CPU를 오래 사용하는 긴 작업입니다.
  • 작업 B (회색): 1ms의 짧은 CPU 사용 후 I/O 작업을 수행하는 대화형 작업입니다.
• MLFQ의 작동:
  • B가 시스템에 들어오면 가장 높은 우선순위 큐(Q2)에 배치됩니다.
  • B는 1ms만 CPU를 사용하고 자발적으로 CPU를 양보하여 I/O를 수행합니다.
  • 규칙 4b에 따라, B는 시간 할당량을 모두 사용하지 않았기 때문에 Q2에 그대로 머무릅니다.
  • I/O가 완료된 후 B는 다시 실행 준비 상태가 되고, Q2의 가장 높은 우선순위로 다시 CPU를 할당받습니다.

 

 
MLFQ 접근 방식은 I/O를 자주 수행하는 interactive 작업을 가장 높은 우선순위에 계속 유지시킵니다. 이 덕분에 interactive 작업은 항상 빠르게 응답할 수 있으며, CPU-intensive 작업은 우선순위가 낮아져 뒤로 밀려나게 됩니다.
 
 
 

현재 MLFQ의 문제점

지금까지 설명된 MLFQ는 몇 가지 중요한 한계점을 가지고 있습니다.

• Starvation:
  • 만약 시스템에 너무 많은 interactive 작업이 있다면, CPU를 집중적으로 사용하는 긴 작업들은 우선순위가 계속 밀려 CPU 시간을 전혀 얻지 못할 수도 있습니다.
  • 이러한 긴 작업들은 가장 낮은 우선순위 큐에 머무르게 되고, 높은 우선순위의 짧은 작업들이 계속 도착하면 사실상 무한정 대기하게 됩니다.
• Gaming(스케줄러 속이기):
  • MLFQ의 규칙 4b는 작업이 시간 할당량이 끝나기 전에 자발적으로 CPU를 양보하면 우선순위를 유지하도록 합니다.
  • 이를 악용하여, 어떤 악의적인 작업이 할당량의 99%를 사용한 후 의도적으로 I/O를 수행하는 척 CPU를 양보할 수 있습니다.
  • 이러한 방식으로 작업은 우선순위 강등을 피하면서, 다른 작업에 비해 불공평하게 더 많은 CPU 시간을 점유할 수 있게 됩니다.
• 작업 행동의 변화:
  • 프로그램의 행동은 시간에 따라 변할 수 있습니다. 예를 들어, 처음에는 CPU-intensive 작업이 나중에는 I/O를 집중적으로 사용하는 작업으로 바뀔 수 있습니다.
  • 현재의 MLFQ는 이러한 변화에 유연하게 대처하기 어렵습니다. 한번 우선순위가 낮아진 작업은 다시 높은 우선순위로 올라가기 어렵기 때문입니다.

 
 

Attempt #2: Priority Boost를 통한 문제 해결

starvation문제를 해결하는 간단한 아이디어는 주기적으로 모든 작업의 우선순위를 높여주는 것입니다.

• 규칙 5: 일정 시간 S가 지나면, 시스템에 있는 모든 작업을 가장 높은 우선순위 큐로 이동시킵니다.

예시: Priority Boost적용

• 상황: 하나의 긴 작업(A)과 두 개의 짧은 대화형 작업(B, C)이 있습니다.

• 부스트 없을 때 (왼쪽 그래프):
  • 짧은 작업 B와 C는 높은 우선순위 큐(Q2)에 머물면서 CPU를 계속 사용합니다.
  • 긴 작업 A는 우선순위가 낮아져 가장 낮은 우선순위 큐(Q0)에 머무르게 되며, B와 C에 의해 선점되어 거의 CPU 시간을 얻지 못하고 starvation 상태에 빠집니다.
• 부스트 적용할 때 (오른쪽 그래프):
  • 마찬가지로 A는 Q0으로 내려가고 B와 C는 Q2에 머뭅니다.
  • 하지만, 일정 시간마다(예: T = 100) 모든 작업의 우선순위가 Q2로 부스트됩니다.
  • 이때 A는 다시 Q2로 올라가서 B, C와 함께 Round Robin 방식으로 CPU를 사용할 기회를 얻게 됩니다.
  • A는 할당량을 모두 사용한 후 다시 Q0으로 내려가지만, 다음 부스트 주기까지 CPU 시간을 조금이라도 확보할 수 있습니다.

이처럼 우선순위 부스트는 시스템의 모든 작업이 최소한의 CPU 시간을 보장받을 수 있도록 하여, starvation 문제를 효과적으로 해결합니다.

 

Attempt #3: Better Accounting

기존 MLFQ의 문제점 중 하나인 스케줄러 속이기(gaming)를 어떻게 방지할 수 있을까요?

• 문제: 기존 규칙(Rule 4b)에 따르면, 작업이 할당된 시간(time slice)을 모두 사용하지 않고 I/O 등으로 자발적으로 CPU를 양보하면 우선순위가 유지되었습니다. 이를 악용하여, 작업이 할당량 직전에 CPU를 양보하는 방식으로 우선순위 강등을 피할 수 있었습니다.
• 해결책 (규칙 4 재정의):
  • 새로운 규칙 4: 한 작업이 주어진 우선순위 레벨에서 할당된 총 시간 할당량(time allotment)을 모두 사용하면, 그 작업이 CPU를 몇 번 양보했는지와 상관없이 우선순위가 낮아집니다(즉, 다음 큐로 이동합니다).

이 새로운 규칙은 다음과 같이 작동합니다.

• 좌측 그래프 (기존 규칙): I/O를 자주 사용하는 작업(B)이 할당량 직전에 CPU를 양보하는 속임수를 사용하면, 우선순위가 계속 높은 Q2에 머무릅니다. 긴 작업(A)은 Q0에 머물러 기아 상태에 빠집니다.
• 우측 그래프 (새 규칙 적용): 이제 B가 Q2에서 총 20ms의 할당량을 소진했다고 가정해 봅시다. B가 1ms씩 20번을 사용하든, 10ms씩 2번을 사용하든, 총 20ms를 사용하면 우선순위가 낮아져 Q1으로 이동합니다. 이 방식은 작업이 할당된 시간 내에 완료되지 않으면 우선순위를 낮추어, 스케줄러를 속이는 것을 방지합니다.

이러한 개선을 통해, MLFQ는 작업의 행동을 더 정확하게 파악하고 불공정한 CPU 시간 점유를 막을 수 있게 됩니다.
 
 

MLFQ 튜닝 및 기타 문제점

MLFQ 스케줄러를 실제 시스템에 적용하려면 몇 가지 중요한 매개변수를 조정해야 합니다.

• 큐의 개수: 큐를 몇 개나 두어야 할까요?
• 큐별 시간 할당량 크기: 각 큐에 할당되는 time slice는 얼마나 길어야 할까요?
• 우선순위 부스트 주기: starvation 문제를 피하기 위해 우선순위 부스트는 얼마나 자주 발생해야 할까요?

MLFQ의 튜닝 방법

대부분의 MLFQ는 큐별로 가변적인 time slice 길이를 허용합니다.

• 높은 우선순위 큐: 빠른 전환(fast switching)을 위해 짧은 time slice를 가집니다. 이는 대화형 작업의 응답 시간을 최적화하는 데 유리합니다.
• 낮은 우선순위 큐: CPU를 집중적으로 사용하는 긴 작업에 적합하도록 더 긴 time slice를 가집니다. 이는 context switch 비용을 줄여 시스템의 효율을 높입니다.

실제 시스템에서는 이러한 매개변수들을 표 형식으로 관리하여 쉽게 설정할 수 있도록 합니다. 예를 들어, Solaris의 MLFQ는 60개의 큐를 사용하고, 1초마다 우선순위 부스트를 수행하도록 설정되어 있습니다
 
 
 

BSD 시스템의 Priority 계산 방식

Solaris가 미리 정의된 테이블을 사용하는 것과 달리, BSD는 고정된 규칙이나 테이블 대신 공식(formula)을 사용해 프로세스의 우선순위를 동적으로 계산합니다.
BSD의 우선순위는 다음 세 가지 요소를 기반으로 결정됩니다.

• CPU 사용량 (CPU usage): 프로세스가 CPU를 더 많이 사용할수록 우선순위가 낮아집니다. 이는 특정 프로세스가 CPU를 독점하는 것을 방지하기 위한 것입니다.
• Priority decay: 시간이 지남에 따라 우선순위가 점진적으로 높아집니다. 이는 starvation 문제를 해결하고, 오래 기다린 프로세스에게 기회를 주기 위한 것입니다.
• 사용자 입력 (nice value): 사용자가 직접 프로세스의 우선순위에 영향을 줄 수 있도록 합니다. nice 값을 통해 사용자는 특정 작업의 우선순위를 높이거나 낮출 수 있습니다.

이러한 동적 계산 방식은 시스템의 현재 상태와 작업의 행동을 종합적으로 고려하여 더욱 유연한 스케줄링을 가능하게 합니다.
 
 
 

정리

MLFQ 스케줄러의 핵심을 이루는 최종적인 규칙들은 다음과 같습니다.

• 규칙 1 (우선순위 기반 실행): 만약 작업 A의 우선순위가 B보다 높으면(), A가 실행되고 B는 실행되지 않습니다.
  • Priority(A)>Priority(B)
• 규칙 2 (동일 우선순위 큐): 만약 작업 A와 B의 우선순위가 같다면(), 두 작업은 라운드 로빈(Round Robin) 방식으로 번갈아 실행됩니다.
  • Priority(A)=Priority(B)
• 규칙 3 (초기 배치): 새로운 작업이 시스템에 들어오면, 가장 높은 우선순위 큐에 배치됩니다.
• 규칙 4 (우선순위 강등): 한 작업이 특정 우선순위 레벨에서 할당된 총 시간 할당량을 모두 사용하면(CPU를 몇 번 양보했는지와 관계없이), 해당 작업의 우선순위는 낮아집니다(즉, 아래 큐로 이동합니다).
• 규칙 5 (우선순위 부스트): 일정 시간(S)이 지나면, 시스템에 있는 모든 작업을 가장 높은 우선순위 큐로 이동시킵니다.

 

사례 연구: Solaris, BSD, Pintos

이러한 MLFQ의 기본 원리는 다양한 운영체제에서 다르게 구현됩니다.

• Solaris: 스케줄링을 위해 미리 정의된 테이블을 사용합니다.
• BSD: 동적인 공식을 사용해 우선순위를 계산합니다.
• Pintos: MLFQ의 기본 개념을 구현하여 스케줄링을 수행합니다.

 

MLFQ의 장점

MLFQ의 가장 큰 장점은 바로 프로세스의 CPU 사용량에 대한 사전 지식이 필요 없다는 점입니다. MLFQ는 작업의 과거 행동을 관찰하고 학습하여, 짧은 대화형 작업과 긴 CPU 집중형 작업을 효율적으로 구분하고 처리할 수 있습니다. 이를 통해 Response time과 Turnaround time을 모두 최적화하는 균형 잡힌 스케줄링을 제공합니다.

 

 

 

 

 
 
 

출처: 경북대학교 한명균 교수님, “운영체제” 강의 자료