Multi-level Feedback Queue

MLFQ 

 

1.Goal

-turnaround time 최적화

-response time 최소화 : RR는 responsetime은 최소화할 수 있지만 turnaroundtime은 안좋았음

 

2.정보없이 스케쥴링 할 수 있는 방법이 무엇인가 해서 개발하게됨

과거 데이터를 기반으로 미래를 예측하는 것을 어떻게 할지 ?

 

3.프로세스는 다양한 큐사이에서 움직일 수 있음 (다른큐로 이동가능 각각의 큐에서는 독립적으로 실행가능)

 

4. 서로 다른 큐를 가짐 

-각각의 큐는 서로 다른 우선순위를 가짐

-더 높은 우선순위가 먼저 실행 

 

5. Rule 1: if Priority(A) > Prioriy(B), A runs (B doesn't)

    Rule 2: if Priority(A) = Prioriy(B), A&B run in RR

 

6. 각 작업의 특성에 따라 동적으로 부여

• Interactive job(I/O-intensive jobs)

      -fast response time, short-running

      -우선순위를 높게 줌

• CPU-intensive job

     -긴 시간 cpu를 집중적으로 사용

     -response time을 상관안함

     -우선순위를 낮게 줌

 

7. Rule 3: 프로세스가 들어오면 가장 높은 우선순위로 둠

   Rule 4a: time slice가 다 되면 우선순위를 낮춤(큐를 내린다)

   Rule 4b:  cpu를 타임슬라이스 다 되기 이전에 cpu를 반환하면 ( 해당 프로세스가 cpu intensive한 job이 아니기 때문에 낮추지않고) 동일한 priority level을 갖도록 함.

그림설명:

job B: 입출력 전에 1ms만 사용하는 interactive job

1ms사용하다가 입출력 요청이 왔을 때 cpu 해제됐을 경우 우선순위 유지 

=>SJF와 유사하게 구사가능

 

8. MLFQ 의 문제점

1)Starvation 기아상태

interactive job이 많게 되면, 우선순위가 낮은 long-running jobs은 cpu를 할당받지 못하게 됨

2)Game the scheduler

입출력 요청이 왔을 때 우선순위 유지 

time slice 100ms 일 때 우선순위가 낮아지는데 입출력 요청이 왔을 때 우선순위가 유지되기 때문에 

99ms정도 지났을 때 실제 i/o요청이 아닌데 가하면 우선순위를 갖게 됨

3)프로그램이 시간에 지남에 따라 변함

cpu intensive -> i/o interactive process가 될 수 있다.  이 점을 반영하지 못하는 문제점!

 

9. Priority Boost

문제점 1,3 해결

Rule 5: 일정시간이 지나고 나서 모든 프로세스잡에 대해 가장 높은 큐로 이동

b c가 계속 번갈아서 할당하기 때문에 a가 할당x starvation문제가 생김

-> s가 지났을 때 우선순위가 높은 q2로 올려서 a도 실행할 수 있게 됨 

-> 특성이 바뀐 케이스도 반영됨 100ms 이후 (cpu intensive -> interactive process) 도 해결

 

10. gaming the scheduler 막는 방법

Rule 4를 변경: 

만약 각각 cpu를 프로세스마다 할당량을 준다. 각 단계에서 cpu사용 총 시간을 측정하고 저장했다가 그 시간을 다 소진하면 우선순위를 낮춤

입출력 요청을 와서 cpu를 몇번이나 해제(포기)를 했는지 여부와 상관없이 실제 cpu를 사용한 시간을 저장하다가 설정된 값을 다 사용하면 우선순위를 낮춤(일정부분 cpu를 가지고 실행하면 우선순위를 낮추게 됨)

한쪽 프로세스가 cpu를 가지고있는 것을 막을 수 있음.

 

cpu를 얼만큼 사용했는지 정보를 저장함으로써 방지

 

11. 

우선순위가 높은 큐 => 낮은 time slice  ex)interactive 

우서순위가 낮은 큐 => 큰 time slice

 

12. Solaris MLFQ 구현

-60개 큐 가짐

-item slice길이를 우선순위가 낮을 곳으로 갈수록 조금씩 증가시키는 형태

우선순위가 높은 부분:20msec

낮은 우선순위: 수백 milliseconds

-우선순위 boot는 1초간격