# Multi-Level Feedback Queue

## MLFQ 規則

1. 若任務 A 的優先度大於任務 B，則任務 A 先執行
2. 若任務 A 和 B 具備相同優先度，使用 RR 策略
3. 新加入的任務有最高優先度
4. 若任務在目前的優先度已經使用完所有的時間，則降低優先度
a. 若任務為 I/O 密集任務，通常會維持優先度
b. 把分配時間執行完的 CPU 密集任務會被降低優先度
5. 每過時間 $S$ 所有的任務都會被提昇 (Boost) 到最高優先度

## 範例

### CPU 密集任務

任務把分配時間完全用完代表為 CPU 密集任務，因為不是 I/O 密集任務，所以較不影響使用者體驗（螢幕輸出延遲等...），因此被降低優先度


### I/O 密集任務

灰色的線段是 I/O 密集任務，只需要很短的時間去發起 I/O 請求，剩下的時間就給 CPU 密集任務用，這樣可以保證 CPU 和 I/O 利用率都很高


### Starvation

如果有太多的 I/O 密集任務，I/O 密集任務彼此 RR 就輪不到 CPU 密集任務，因此透過定時提昇 (Boost) 所有任務到最高優先度可以避免 CPU 密集任務無法執行 (Starvation) 的狀況


### Gaming Tolerance

為避免有惡意程式利用 I/O 密集任務可以保留優先級，排程器會紀錄 (Accouting) 任務時間，以下面的範例，發起 I/O 請求之後又馬上繼續執行同一個任務，在作業中有提到時間配額的定義，如果一個任務在某一個優先級當中執行的時間超過配額時間時就會被將低優先級，而會用 Time Slice 的原因是同一個優先級的任務是使用 RR 策略，通常高優先級隊列 (Queue) 的 Time Slice 較短
> Note that while the chapter talks about allotments in terms of time, here it is done in terms of number of time slices, i.e., if the time slice length for a given queue is 10 ms, and the allotment is 2, the job can run for 2 time slices (20 ms) at that queue level before moving down in priority.


### Lower Priority, Longer Quanta

因為低優先級的任務大多是 CPU 密集任務，所以給低優先級的時間長度較長讓它們可以一次用處理器久一點


## 課後問題

1. Run a few randomly-generated problems with just two jobs and two queues; compute the MLFQ execution trace for each. Make your life easier by limiting the length of each job and turning off I/Os.
> 兩個任務在同一個優先級的 Queue 使用 RR 策略排程，並且同時降低優先級

    ./mlfq.py -l 0,30,0:0,30,0 -c
    Here is the list of inputs:
    OPTIONS jobs 2
    OPTIONS queues 3
    OPTIONS allotments for queue  2 is   1
    OPTIONS quantum length for queue  2 is  10
    OPTIONS allotments for queue  1 is   1
    OPTIONS quantum length for queue  1 is  10
    OPTIONS allotments for queue  0 is   1
    OPTIONS quantum length for queue  0 is  10
    OPTIONS boost 0
    OPTIONS ioTime 5
    OPTIONS stayAfterIO False
    OPTIONS iobump False
    ......
    Final statistics:
      Job  0: startTime   0 - response   0 - turnaround  50
      Job  1: startTime   0 - response  10 - turnaround  60

      Avg  1: startTime n/a - response 5.00 - turnaround 55.00

3. How would you run the scheduler to reproduce each of the examples in the chapter?
> Fig 8.2 `./mlfq.py -l 0,200,0 -q 10 -n 3`
> Fig 8.3 `./mlfq.py -l 0,180,0:100,20,0 -q 10`
> Fig 8.4 `./mlfq.py -n 3 -q 10 -l 0,175,0:50,25,1 -i 5 -S`
> Fig 8.5(1) `./mlfq.py -n 3 -q 10 -l 0,120,0:100,50,5:100,50,5 -i 5 -S`
> Fig 8.5(2) `./mlfq.py -n 3 -q 10 -l 0,120,0:100,50,5:100,50,5 -i 5 -S -B 50`
> Fig 8.6(1) `./mlfq.py -n 3 -q 10 -l 0,200,0:80,100,9 -i 1 -S`
> Fig 8.6(2) `./mlfq.py -n 3 -q 10 -l 0,200,0:80,100,9 -i 1`
> Fig 8.7 `./mlfq.py -n 3 -q 10 -A 2,2,2 -Q 10,20,40 -l 0,150,0:0,150,0`
5. How would you configure the scheduler parameters to behave just like a round-robin scheduler?
> 把 Time Slice 設為最大的任務時間除以任務的數量，並且 Allotment 設為 1
7. Craft a workload with two jobs and scheduler parameters so that one job takes advantage of the older Rules 4a and 4b (turned on with the `-S` flag) to game the scheduler and obtain 99% of the CPU over a particular time interval.
> By Fig 8.5(1) `./mlfq.py -n 3 -q 10 -l 0,120,0:100,50,5:100,50,5 -i 5 -S`
9. Given a system with a quantum length of `10` ms in its highest queue, how often would you have to boost jobs back to the highest priority level (with the `-B` flag) in order to guarantee that a single longrunning (and potentially-starving) job gets at least 5% of the CPU?
> `200` ms -> $\frac{10}{200} = 0.05 =$ 5%
11. One question that arises in scheduling is which end of a queue to add a job that just finished I/O; the `-I` flag changes this behavior for this scheduling simulator. Play around with some workloads and see if you can see the effect of this flag.
> 在第二個狀況中當第二個任務執行到第 11 個時間單位時，會發起一個 I/O 請求，此時下一個時間會變成第一個任務執行，然後再下一個時間因為第二個任務的 I/O 執行完畢，所以又變成第二個任務執行，因為選項 `-I` 開啟 IO Bump 讓剛結束 I/O 請求的任務在同一個優先級有最高優先權

    ./mlfq.py -n 2 -q 10 -l 0,50,0:0,50,11 -i 1 -S -c
    ./mlfq.py -n 2 -q 10 -l 0,50,0:0,50,11 -i 1 -S -I -c