[Operating System] MLFQ Multi-level Feedback Queue Scheduling

Multi-level Feedback Queue Scheduling

• RR은 응답시간은 단축시키나 반환 시간은 최악(너무 자주 잘라서)
• MLFQ는 이러한 RR의 한계점을 극복하기 위해 고안해낸 방법이다
• RR의 장점인 짧은 평균 응답 시간은 유지하면서, RR의 단점인 짧은 task의 불리함을 해결하자는 것이다.
• RR에서는 Queue를 1개만 운용했다면, MLFQ는 다양한 Time Quantum을 가지는 여러 Queue를 동시에 운용한다.
• Turn around time의 최적화 → 짧은 작업 우선
• MLFQ 는 대화식 사용자에게 응답시간을 최소화 → 빠르시스템인것처럼 느끼게

여러 개의 Queue는 상단에서 하단으로 내려갈수록 Time Quantum은 길어지고, 이는 당연히 process가 CPU를 점유했을 시 한 번에 실행되는 시간이 길어짐을 뜻한다. 반면 상단에서 하단 Queue로 내려갈수록 우선 순위는 떨어져 점유 가능성은 낮아진다. 더 정확히는, 하단에 있는 Queue가 Pop되려면 해당 Queue의 상단에 있는 모든 Queue가 empty 상태여야만 한다.

MLFQ

• 여러개의 큐
  • 각 큐는 다른 우선순위 부여
  • 실행 준비 된 프로세스는 여러 프로세스가 있을 수 있다.
  • 하나의 큐에있는 프로세스들의 우선순위는 동일
  • 높은 우선순위에 있는 큐에 있는 프로세스가 높은 우선순위

상위 큐 : CPU 차지 확률 높음

하위 큐 : CPU차지 시간 높음

MLFQ RULE

1. 우선순위가 더 높은 (더 상단의 Queue에 위치한) task를 먼저 수행한다.
2. 우선순위가 같은 (같은 Queue에 위치한) task 중에서는 먼저 들어온 task를 수행한다.
3. 처음 실행되는 task에 대해서는 가장 높은 우선순위를 부여한다(최상단 Queue에 push한다).
4. TQ를 모두 소모하면, 우선순위가 낮아진다(아래의 Queue에 push한다).
5. TQ를 모두 소모하기 전에 CPU 점유를 해제하면, 같은 우선순위를 유지한다(같은 Queue에 push한다).

MLFQ 문제점

1. Starvation(기아) 상태 발생 가능성
   1. 실행 시간이 길어 우선순위가 낮아진 task 는 계속 신규 task가 들어오게 될경우 기아 상태에 빠짐
2. 프로그램 재작성하여 스케줄러를 자신에 유리하게 동작 할 가능성
   • 지정된 할당 시간보다 더 많은 시간을 할당 받도록..
3. 시간에 따라 프로그램 특성이 변할경우 우선순위 조정이 불가능할 가능성
   1. cpu 위주의 작업이 대화형 작업으로 바뀌어도 우선순위는 낮음

MLFQ 개선

Gaming Tolerance

• mlfq의 각 큐 레벨에서 cpu사용시간 측정하고 저장
• 주어진 큐 레벨에서 cpu 다 쓰면 우선순위를 낮춘다.

일정 시간

• 일정시간 s가 지나면 모든 task들의 우선순위를 초기화한다.이러한 작업을 Boosting이라고 부른다. MLFQ의 1, 3번 문제를 해결할 수 있다.