Multi-level Feedback Queue, MLFQ

해결하고자 한 문제

• 짧은 작업 먼저 실행시켜 반환시간 최적화
• 대화형 사용자에게 응답시간 최소화 제공

기본 구성

• 여러개의 큐로 구성되어있다
• 큐마다 각각 다른 priority level(우선순위) 배정됨
• 각 작업의 특성에 따라 큐에게 동적으로 우선순위 부여
  ex) CPU를 잘 양보하는 작업은 우선순위 높게, 양보하지 않는 작업은 우선순위 낮게 부여

기본 규칙

1. Priority(A) > Priority(B)이면 A 실행
2. Priority(A) = Priority(B)이면 RR 방식 실행
3. 작업이 처음으로 시스템에 들어오면 가장 높은 우선순위 부여
4. 주어진 time slice를 다 소진하면 우선순위 내림
5. time slice를 소진하기 전에 CPU를 양도하면 같은 우선순위 유지 (CPU를 잘 양보하므로)

MLFQ 예

높음

Q5 -> A -> B
Q4
Q3 -> C
Q2
Q1 -> D
Q0

낮음

예시

1. 한개의 긴 실행시간 가진 작업

   맨 처음 들어오면 우선순위가 가장 높은 위치에 놓임
   매 단계마다 CPU를 다 쓰고 한단계씩 낮은 큐로 내려옴
   -> Q0에 계속 머무르게 된다

2. 긴 실행시간 가진 작업을 짧은 작업과 함께

   충분히 짧은 작업이라면 우선순위가 가장 낮은 큐에 도달하기 전에 작업이 끝남, 이후에 가장 밑바닥에 있는 긴 실행시간을 가진 작업 시행

따라서 MLFQ는 SJF와 근사하다고 할 수 있다!

문제점

1. starvation
   너무 많은 대화형 작업 발생시 긴 실행시간 작업이 CPU를 할당받지 못함

   해결책

   주기적 시간 S가 지나면 모든 작업을 최상위 큐로 이동한다면?
   -> starvation 해결
   -> CPU 위주의 작업의 변경된 특성 반영 가능

2. 사용자가 스케줄러를 자신에게 유리하게 동작하도록 프로그램 작성 가능
   타임 슬라이스가 끝나기 전에 아무 파일 입출력 요청을 내려 CPU를 양도한다면 같은 큐에 머무르기가 가능함

   해결책

   주어진 큐에서 시간 할당량을 소진하면 무조건 우선순위를 낮춘다
   -> 입출력 행동과 무관하게 아래단계 큐로 천천히 이동하게 됨

3. 프로그램은 시간 흐름에 따라 특성이 변함