Multi-Level Feedback Queue (MLFQ)

• 과거를 바탕으로 미래를 예측하는 Scheduler
  • Turnaround Time 최적화 → 짧은 작업을 우선 수행
  • Response Time을 최소화 → Runtime에 대한 사전 정보 없이

Basic Rules

• MLFQ는 여러 개의 고유 Queue를 유지한다.
  • 이때, 각 Queue는 서로 다른 우선 순위를 가진다.
    ⠀⠀
• 실행 준비가 완료된 작업은 하나의 Queue에만 존재한다.
  • 우선 순위가 높은 Queue에 존재하는 작업이 실행된다.
  • 하나의 Queue에 여러 작업이 존재한다면 Round-Robin 방식을 통해 진행된다.
    ⠀⠀
• MLFQ가 우선 순위를 결정하는 방법은 다음과 같다.
  • 입출력을 기다리기 위해 빈번하게 CPU 권한을 포기하는 작업
    ⠀▪ Interactive 작업으로 간주 → 상위 우선 순위를 부여 → 짧은 Time Slice → 짧은 Response Time
  • CPU에 대한 권한을 오래 유지하는 작업
    ⠀▪ Batch 작업으로 간주 → 하위 우선 순위를 부여 → 긴 Time Slice → 짧은 Turnaround Time
    ⠀⠀
• MLFQ는 이러한 방식을 통해 실행되는 프로세스에 대해 학습하고 작업 기록을 사용하여 향후 동작을 예측한다.

How to Change Priority

• MLFQ의 문제 - 소속 Queue를 옮길 수 없다.
  ⠀⠀
• MLFQ의 우선 순위 결정 알고리즘
  • Rule 1: 우선 순위가 높은 Queue의 작업을 우선 수행
  • Rule 2: 같은 Queue 내에서는 Round-Robin 방식으로 작업 순서 결정
  • Rule 3: 최근 들어온 작업은 Interactive 작업으로 가정하여 최우선 순위
  • Rule 4-1: 작업이 전체 Time Slice를 소모하고도 완료되지 않으면 하위 우선 순위의 Queue로 이동
  • Rule 4-2: Time Slice가 끝나기 전에 작업이 끝나면 현재 Queue의 우선 순위를 유지

Example 1: A single Long-Running Job

200ms의 Runtime을 가진 작업은 10ms 단위의 Time Slice에서 끝나지 않아 계속해서 하위 우선 순위의 Queue로 내려와서 수행 완료된다.

Example 2: Along Came a Short Job

작업 A가 진행되는 도중에 작업 B가 수행된다. Runtime이 20ms로 비교적 짧은 B는 두 번째 우선 순위에서 수행 완료된다. 그 후 중단되었던 A가 재개된다.

Example 3: What About I/O?

작업 A는 CPU 권한이 오래 필요한 작업, 작업 B는 Interactive 작업으로, 입출력 작업을 위해 1ms동안의 CPU 권한이 필요하다. 작업 B에서 입출력이 요청되면 CPU에서는 작업이 끝났다고 판단하여 작업 A을 수행한다.

Problems With The Basic MLFQ

Starvation

상위 우선 순위 Queue에 많은 작업이 존재하는 경우, 하위 우선 순위 Queue에 존재하는 작업은 실행되지 못하는 Starvation이 발생한다.

Fixed Priority

상위 우선 순위 Queue에서 하위 우선 순위 Queue로 이동하는 것은 가능하지만, 그 반대는 불가능해서 발생하는 문제이다. 상위 우선 순위 Queue에서 입출력이 발생하는 경우에도 하위 우선 순위 Queue의 작업은 올라올 수 없다.

Malicious CPU Using

Time Slice의 99%를 사용한 후, 의도적으로 입출력 작업을 발생시켜 계속 상위 우선 순위를 확보하는 경우이다.

The Priority Boost

• Rule 5: 일정 시간 이후, 모든 작업을 최상위 우선 순위 Queue로 이동 → Starvation, Fixed Priority 문제 해결 방안
  ⠀⠀
• Example
  Runtime이 긴 작업 A, Runtime이 비교적 짧은 작업 B, C

너무 큰 S값 → A와 같은 작업들의 Starvation 문제 발생
너무 작은 S값 → B, C와 같은 작업들이 CPU 권한을 얻기 어려움

Better Accounting

• Rule 4 (수정): 작업의 남은 시간과 Time Slice를 비교하여 우선 순위를 결정하지 않고, 작업이 총 소모한 시간과 Time Slice를 비교하여 우선 순위를 결정

Time Slice가 10ms라고 가정하겠다. 원래대로 라면 그림의 좌측과 같이 9.9ms동안 수행되고, 악의적으로 입출력 작업을 진행한다. 개선된 방법에서는 9.9ms 진행된 이후, 입출력 작업을 진행하는 것은 동일하다. 하지만 다시 CPU 권한을 얻은 이후에 9.9ms 진행되지 않고, 9.9 + $α$(=0.1) = 10이 되는 순간에 하위 우선 순위 Queue로 내려가게 된다.

Tuning MLFQ and Other Issues

• 고려해야할 사항
  • Queue의 개수
  • 각 Queue에서 사용할 Scheduling Algorithm
  • Queue마다의 Time Slice 길이
  • Priority Boost에서 필요한 S의 크기

Summary

• Rule 1: 우선 순위가 높은 Queue의 작업을 우선 수행
  ⠀⠀
• Rule 2: 같은 Queue 내에서는 Round-Robin 방식으로 작업 순서 결정
  ⠀⠀
• Rule 3: 최근 들어온 작업은 Interactive 작업으로 가정하여 최우선 순위
  ⠀⠀
• Rule 4: 작업의 남은 시간과 Time Slice를 비교하여 우선 순위를 결정하지 않고, 작업이 총 소모한 시간과 Time Slice를 비교하여 우선 순위를 결정한다.
  ⠀⠀
• Rule 5: 일정 시간 이후, 모든 작업을 최상위 우선 순위 Queue로 이동 → Starvation, Fixed Priority 문제 해결 방안