Scheduling:The Multi-Level Feedback Queue

Multi-Level Feedback Queue(MLFQ)

MLFQ의 목적은 turnaround time을 optimize하고 프로그램의 실행시간을 모르는 상태에서 response time을 minimize하는 것이다.

MLFQ를 배우기 전에 알아야 할 개념이 있는데 short job은 반복적으로 CPU권한을 포기하는 job이고(ex : repeat I/O), long job은 CPU를 굉장히 intense하게 사용하는 job이다.

MLFQ 예시

fork(A,B,C,D)를 했다고 가정하자. A와 C는 프로그램이 완료 또는 interrupt가 2ms 정도에 이루어지고, B는 16ms, C는 64ms 정도에 이루어진다고 하자. 처음 들어온 A,B,C,D 모두 Q4에 들어가 순서대로 2ms씩 실행되게 된다. A와 C는 실행이 완료되었지만 B와 D는 완료되지 않아 Q3로 넘어가게 된다. Q3에서도 B와 C는 완료되지 않아 Q2로 내려간다. B는 Q2까지 내려가서 비로소 완료가 되고 C는 완료되지 않기 때문에 Q1으로 넘어가고 Q1에서 실행되면서 끝난다.

MLFQ는 위와 같은 방식으로 response time과 turnaround time을 모두 잡은 것 같지만 Qi는 Qi-1이 비어있을 때 실행되기 때문에 Qi-1에 계속 파일이 input된다면 Qi에 있는 파일, 즉 long time job은 계속 실행되지 못할 것이고 우리는 이를 starvation이라고 한다.

long time job을 실행하는 도중 short time job이 올 경우

long time job과 interactive job이 실행되는 경우

starvation을 피하는 법

Starvation을 피하기 위해서 Q0에 어느 정도 job이 머물러 있으면 다시 q2로 올려주면 된다. Period S(어느 정도의 시간)을 정하는 것은 매우 어렵다.

 

 

gaming of scheduler를 피하는 법

---

gaming of scheduler를 피하기 위해 CPU 포기한 횟수와 상관없이 해당 queue에 얼마나 오래있었는지를 계산하여 우선순위를 내려주는 방식을 사용하면 된다.

 

 

Queue의 priority에 따라 time slice의 길이를 늘려주면 휠씬 더 효율적으로 프로그램이 돌아간다.

---