STCF(PSJF)는 turnaround time 측면에서는 좋지만 response time이 좋지 않았다.
또한 STCF는 process의 실행시간에 대한 선행지식이 필요하다는 한계점이 있었다.

RR은 각 process가 얼마나 실행되는지와 관계없이 공평하게 process를 실행하기 때문에 response time면에서 좋았지만 turnaround time이 좋지 않았다.
하지만 RR은 아무런 선행지식 없이도 적용할 수 있다는 장점이 있었다.

어떻게 선행지식이 아예 없이 process를 schedule할 수 있을까?

Multi-Level Feedback Queue (MLFQ)

scheduler는 과거를 통해 배워 미래를 예측한다!

프로세스의 과거 동작으로부터 미래를 예측하는 것이다.
예를 들면, 이 프로세스가 그동안 얼마나 오래 CPU를 소모했는지. 만약에 CPU를 지금까지 충분히 오래 사용했다면 이 프로세스는 long job length를 가지고 있는 프로세스라고 판단할 수 있다.
새로 들어오는 프로세스는 그 프로세스에 대한 지식이 아예 없고 새로 들어온 프로세스는 다른 프로세스들에 비해 적은 시간동안 실행됐으므로 높은 priority를 준다.

Key objective는 다음과 같다:

1. turnaround time을 optimize하기 : shorter job을 먼저 실행한다. 정확히 그 프로세스가 얼마나 running될지 알 수는 없지만 지금까지 얼마나 running됐는지는 알 수 있으니 그것을 이용한다.
2. job length에 대한 선행지식 없이 response time을 최소화하기 : RR scheduling을 이용한다.

MLFQ : Basic Rules

MLFQ는 여러 개의 distinct queue로 이루어져 있다.
이는 priority를 구분하기 위한 것이다. 새로 들어온 프로세스는 CPU에서 running된 시간이 없으므로 높은 우선순위를 부여하고 CPU에서의 실행시간이 늘어날수록 long job length를 가지고 있을 것이라고 생각해 우선순위를 낮춘다.

higher priority queue에 있는 job이 실행된다.
높은 priority queue의 프로세스를 RR 방식으로 실행한다.

MLFQ는 프로세스의 observed behavior로 priority를 결정한다. observed behavior은 지금까지 얼마나 CPU time을 소모했는가이다.
예를 들면, I/O를 기다리며 반복적으로 CPU를 yield하는 경우 그 프로세스가 CPU time을 충분히 소모하지 않았다고 판단하기 때문에 높은 우선순위를 유지한다 (사실 이건 잘못됨).
또한 job이 CPU time을 긴 시간동안 소모하면 오래 실행되는 job으로 간주해서 우선순위가 내려간다.

Rule 1 : 만약 Priority(A) > Priority(B)라면, A 가 실행된다 (B 는 실행되지 않는다).
Rule 2 : 만약 Priority(A) = Priority(B)라면, A와 B가 RR로 실행된다.

MLFQ : How to Change Priority

MLFQ의 priority adjustment algorithm은 다음과 같다:

Rule 3 : job이 system에 들어오면 그 job은 가장 높은 우선순위에 위치한다.
Rule 4a : job이 실행 도중 모든 time slice를 사용하면 그 job의 우선순위는 낮아진다.
Rule 4b : job이 time slice를 다 실행하기 전에 CPU를 give up하면 같은 우선순위를 유지한다.

이 방법을 통해 MLFQ가 SJF에 근사한다.
미래를 알 수는 없지만 과거가 probability와 priority를 결정한다. 모든 것이 past behavior를 통해 결정됨.

Example 1 : A Single Long-Running Job

time slice가 10ms이고 3개의 queue를 가진 scheduler이면 다음과 같이 동작한다.

Example 2 : Along Came a Short Job

다음과 같이 가정한다:

Job A : 오랫동안 실행되는 CPU-intensive job
Job B : runtime이 20ms인 짧게 실행되는 interactive job

A가 실행되고 있는 도중 B가 T=100에 도착하였다.

Example 3 : What About I/O?

다음과 같이 가정한다:

Job A : 오랫동안 실행되는 CPU-intensive job
Job B : I/O를 수행하기 전 1ms만 CPU를 필요로 하는 interactive job

B는 그저 CPU time을 소모하는 것이 아니라 user와 반복적으로 interactive하며 I/O를 위해 CPU를 yield한다.
MLFQ는 interactive job을 가장 높은 우선순위에 유지한다.
정해진 time slice를 다 사용하지 않고 계속적으로 CPU를 yield하기 때문이다.

Problems with the Basic MLFQ

• Starvation : 만약 시스템에 interactive job이 너무 많다면 long-running job은 CPU time을 받지 못하게 된다.
  많은 interactive job들이 계속해서 CPU를 yield하면서 높은 우선순위를 유지하니까 낮은 우선순위의 long-running job이 CPU를 사용할 수 없는 것.
• Game the scheduler : job이 고의적으로 주어진 time slice의 99%를 실행하고 I/O operation을 발생시켜 CPU를 yield한다.
  job이 충분한 시간동안 실행되었음에도 time slice를 다 사용하기 전에 CPU를 yield했으므로 높은 우선순위를 유지하게 된다. 그럼 job이 전체 CPU time의 많은 비율동안 실행된다.
• A program may change its behavior over time : CPU bound process -> I/O bound process
  MLFQ principle에 의해 I/O bound process가 CPU bound process를 dominate할 수 있다. CPU bound process가 CPU time을 획득할 chance를 얻지 못하기 때문이다.

Priority Boost

priority boost는 starvation을 막을 수 있는 방법이다.

Rule 5 : 어떤 period S 이후에 시스템의 모든 job을 topmost queue로 옮긴다.

이전의 모든 past behavior를 잊고 모든 job을 가장 우선순위가 높은 queue로 옮기는 것이다.
record reset을 통해 starving process를 구제할 수 있다.

long running job A와 2개의 short-running interactive job B, C가 있다면 다음과 같이 실행한다.이전에는 한 번 우선순위가 내려갔을 때 이를 유지했지만 이제부터는 일정 time interval마다 전체 job을 가장 우선순위가 높은 queue로 넣어서 각 interval당 최소 한 번씩은 CPU에서 실행될 수 있는 기회를 준다.

Better Accounting

우리의 scheduler를 gaming하는 것을 어떻게 막을 수 있을까?

기존의 rule을 다음과 같이 수정한다:

Rule 4a : job이 실행 도중 모든 time slice를 사용하면 그 job의 우선순위는 낮아진다.
Rule 4b : job이 time slice를 다 실행하기 전에 CPU를 give up하면 같은 우선순위를 유지한다.
-> Rule 4 : job이 얼마나 CPU를 yield했는지와 관계 없이 자신의 우선순위 level에 맞는 time allotment를 다 사용한다면, 그 job의 우선순위는 낮아진다.

CPU에서 동작한 총 시간을 가지고 특정 시간 이상 CPU를 점유했다면 priority를 내리는 것이다. 예전에는 yield만 하면 '와 너 좋은 애구나!'하고 CPU를 얼마나 점유했는지 신경쓰지 않았지만 이제는 CPU를 사용한 총 시간을 기억하겠다는 의미이다.

Tuning MLFQ And Other Issues

Lower Priority, Longer Quanta

• 우선순위가 높은 queue -> short time slices
• 우선순위가 낮은 queue -> longer time slices

MLFQ : Summary

Rule 1 : If Priority(A) > Priority(B), A runs (B doesn't).
Rule 2 : If Priority(A) = Priority(B), A & B run in RR.
Rule 3 : When a job enters the system, it is placed at the highest priority.
Rule 4 : Once a job uses up its time allotment at a given level(regardless of how many times it has given up the CPU, its priority is reduced). game the scheduler 방지
Rule 5 : After some time period S, move all the jobs in the system to the topmost queue. starvation 방지