8. Scheduling : The Multi-Level Feedback Queue

chapter 7에서는

1. turnaround time과 response time 간의 trade-off 문제

2. 실제 OS는 하나의 job이 어느 정도의 수행 시간을 가지게 될 것인지 사전에 알 수 없다는 문제

위 두 가지 문제점을 내재하고 있는 스케줄링 기법에 대해 공부했다.

 

다단계 피드백 큐는 실제로 OS가 process에 대해 알 수 있는 것이 많지 않음에도 불구하고 가장 이상적인 스케줄링을 어떻게 해나갈 수 있는지에 대한 최선의 해결책인 것 같다.

---

8.1 MLFQ : Basic Rules

a Multi Level Feedback Queue

 - 여러 개의 큐가 있음

 - 각각의 큐는 서로 다른 priority를 가짐

 - 가장 우선순위가 높은 큐에 있는 작업이 가장 먼저 실행됨

Rule 1	If Priority(A) > Priority(B), A runs (B doesn't)
Rule 2	If Priority(A) = Priority(B), A&B run in RR

출처 : Operating Systems_Three Easy Pieces

 - A와 B는 RR로 실행됨. 그러는 동안 C와 D는 우선순위에 밀려 실행되지 않음

 - 그렇다면 시간이 지남에 따라 우선순위를 어떻게 바꾸어 주어야 할까?

 

8.2 Attempt #1 : How to Change Priority

Rule 3	When a job enters the system, it is placed at the highest priority(the topmost queue).
Rule 4a	If a job uses up an entire time slice while running, its priority is reduced(i.e., it moves down one queue).
Rule 4b	If a job gives up the CPU before the time slice is up, it stays at the smae priority level.

(- Rule 4a는 주로 CPU bound job에, Rule 4b는 주로 i/o intensive job 같은 interactive job에 대해 적용되는 것 같다.)

 

Example 1 : A Single Long-Running Job

출처 : Operating Systems_Three Easy Pieces

 - Single Long-Running Job은 수행되면서 점점 우선순위가 낮은 큐에 배정됨(time slice 안에 작업을 끝내지 못하므로 rule 4a 적용)

 

Example 2 : Along Came A Short Job

출처 : Operating Systems_Three Easy Pieces

 - How MLFQ approximates SJF?

  : 처음엔 특정 작업에 대한 전체 수행시간을 알 수 없기 때문에 해당 작업에 가장 높은 우선순위를 부여하고, 점점 길어질수록 우선순위를 낮추는 방식을 통해 SJF에 근접해간다. (짧은 작업은 높은 우선순위에서 끝나고 길어지는 작업은 점점 우선순위가 낮아지게 되므로)

 

Problems With Our Current MLFQ

1. starvation	I/O intensive job이나 short job들이 계속해서 들어오면, 우선순위가 낮은 long-running job은 수행되지 못한다.
2. game the scheduler	우선순위를 계속 높게 유지하기 위해서 time slice가 다 되기 직전에 I/O와 같은 작업을 발생시킴으로써 tricky한 방법으로 우선순위를 유지하는 일이 생길 경우에 대처하지 못한다. --> 결과적으로 CPU bound job이 interactive job으로 변질된다.

 

8.3 Attempt #2 : The Priority Boost

 - 위와 같은 문제점을 해결하기 위해서 주기적으로 우선순위를 다 높여주는 작업을 시행(boost)

Rule 5

After some time period S, move all the jobs in the system to the topmost queue

출처 : Operating Systerms_Three Easy Pieces

 - 왼쪽 : CPU bound job이 계속해서 우선순위에 밀리고 있음

 - 오른쪽 : boost를 해줌으로써 Q0에 있던 job도 위로 올라가 수행될 수 있게 됨

 

8.4 Attempt #3 : Better Accounting

 - How to prevent gaming of the scheduler?

  : The scheduler should keep track; once a process has used its allotment, it is demoted to the next priority queue.

  : 즉, 아무리 time slice를 이용해 우선순위를 조작한다고 할지라도, 전체 할당량을 다 사용한 경우, 강등

 

Rule 4

Once a job uses up its time allotment at a given levle(regradless of how many times it has given up CPU), its priority is reduced(i.e., it moves down one queue)

 

---

• Rule 1 : 높은 우선순위에 있는 작업이 먼저 실행된다.
• Rule 2 : 우선순위가 같은 두 작업은 RR로 실행된다.
• Rule 3 : 각 작업은 맨 처음에는 가장 높은 우선순위 큐로 들어간다.
• Rule 4 : 각 작업은 time slice와 상관 없이, 전체 시간 할당량 만큼의 수행을 하면 우선순위가 낮아진다.
• Rule 5 : S라는 time period 후에는 모든 작업이 다 가장 높은 우선순위 큐로 들어간다.

---

 

-출처-

<OPERATING SYSTEMS three easy pieces>

 

REMZI H. ARPACI-DUSSEAU

ANDREA C. ARPACI-DUSSEAU

UNIVERSITY OF WISCONSIN-MADISON