MLFQ

---

앞서 살펴본 SJF나 STCF는 turnaround time을 최적화하는데 있어서는 좋았지만,
수행시간을 미리 알고 있어야 한다는 제한점이 있고,
RR은 수행시간을 몰라도 되지만, turnaround time이 좋지 않다는 단점이 있었다.
위의 한계점들을 극복하기 위해 나온 것이 바로 MLFQ이다.

MLFQ - Basic Rules

• MLFQ는 여러개의 priority queue를 가지고 있다
  • 각각의 priority queue들은 우선순위가 서로 다르다
  • 우선순위가 높은 큐에 있는 job이 먼저 실행된다
  • 우선순위가 동일한 큐에 여러 job들이 있다면, RR(Round Robin) 형식으로 실행된다
• MLFQ에서 job의 우선순위는 기존에 동작했었던 것을 바탕으로 우선순위를 정한다
  • Interactive jobs
    • 사용자와 정보를 계속 주고 받는 job
    • 짧게 동작하여 response time이 짧아야 하는 job
    • 우선순위를 높게 유지해주어야 한다
  • CPU-intensive jobs
    • CPU가 오랜시간동안 연산을 해야하는 job
    • response time에 별로 상관이 없다
    • 우선순위를 낮춰도 된다

MLFQ - How to Change Priority

MLFQ는 다음과 같은 알고리즘으로 우선순위를 결정한다.

• 시스템에 처음 들어온 job의 경우, 가장 높은 우선순위를 부여해준다
• 만약 그 job이 time-slice 한번만에 동작을 끝내지 못하면, 우선순위를 한 단계 낮춰준다
• 그 job이 time-slice안에 모든 동작을 끝내고 CPU를 반환한다면, 우선순위를 그대로 둔다

3개의 priority queue가 있는 스케줄러의 예시

CPU-intensive job인 A가 돌아가고 있는 도중에 Interactive job인 B가 들어온 경우

MLFQ - 문제점

• Starvation
  • 너무 많은 Interactive job들이 있으면 우선순위가 낮은 CPU-intensive job이 CPU를 할당받지 못할 수도 있다
• Game the scheduler
  • 몇몇 프로세스가 99%의 time-slice를 사용한 뒤 CPU를 반환해버리면, 긴 작업이라도 계속 같은 우선순위에서 CPU를 할당 받을 수 있다
• 시간에 따른 process의 변화
  • 처음에는 CPU-intensive job이었지만, 나중에는 Interactive job으로 바뀌는 경우 우선순위를 올려줄 수 없다

Priority Boost(시간에 따른 process의 변화 해결)

일정 주기마다 모든 job들을 최고 우선순위로 올려준다.

Better Accounting(Game the scheduler 해결)

해당 우선순위에서 사용한 시간의 총 양이 time-slice보다 큰 경우 우선순위를 낮춰준다.

Game the scheduler의 악용 사례

같은 프로세스들이지만, Better Accounting을 한 뒤 빗금친 process가 강등당했다.

Tuning MLFQ And Other Issues

높은 우선순위 큐의 경우에는 짧은 time-slice를 주고, 낮은 우선순위 큐의 경우에는 긴 time-slice를 주는 방식이다