# Overview of Scheduling Problem
## Introduction
Scheduling Problem (排程問題)是CS領域當中一直存在的重要議題
從作業系統層級乃至到大型分散式系統層級, 甚至data center當中都存在需要做排程的需求, 在了解排程演算法之前應該先思考, 為什麼要排程?

排程的概念可以用以下的方式想像
你是一個manager, 老闆交給你一大堆工作(可能有相依性也可能沒有), 並且給你一個或多個工作人員, 給你各種要求希望你在滿足要求的情況下完成全部工作(最短時間/最少花費/最快完成第一個工作)
你該**怎麼分配工作給每個工作人員**, 才能在**滿足要求的情況下完成全部工作**？

**分配工作給工作人員**的動作就稱為scheduling, **滿足所有要求的情況完成所有工作**就稱為這個scheduling problem的objectives

至於在電腦中的排程問題, 我們通常有以下術語對應關係
工作 : workload
工作人員 : processor
要求 : metrics

由於現實當中的scheduling problem非常複雜, 我們在此處先套用幾個基本假設, 可能很不實際, 不過讓我們先從這個角度出發來簡化並了解我們在處理的問題, 接著再一步一步把這些假設拿掉

## Basic Assumptions
* Each job runs for the same amount of time
* Each job has no dependency with others
* All jobs arrive at the same time
* All jobs only use the CPU (perform no I/O)
* The run-time of each job is known

## Scheduling Metrics
* **Turnaround time**
$T_{turnaround} = T_{completion} - T_{arrival}$
* **Fairness**

## Basic Scheduling Algorithms
### FIFO
如同名字所說, FIFO演算法就是先到的Task先執行
優點顯而易見是實作非常簡單, 並且處理也很簡單
有一個簡單的例子如下, A, B, C三個job同時幾乎同時抵達(依照assumption)
假設三個job都需要10個time unit來處理(根據assumption, 我們事先知道每個job的執行時間), 則這一批工作的average turnaround time會是
$(T_A + T_B + T_C) / 3$
$T_A = 10 - 0 = 0, T_B = 20 - 0 = 20, T_C = 30 - 0 = 30$

所以average turnaround time會是$\cfrac{10 + 20 + 30}{3} = 20$
此時我們鬆綁第一個assumption, 也就是每個job的run-time可以不相同, 這會造成什麼影響？有可能導致FIFO給出非常糟糕的average turnaround time嗎？
假設task A現在需要100個time unit來完成, 並且我們還讓task A在第一個執行
則average turnaround time會變成$\cfrac{100 + 110 + 120}{3} = 110$ , 瞬間變得非常糟糕
以上就是著名的**convoy effect**, 也就是相對短的workload被一個超重型的workload給霸佔CPU而不能執行的情況, 那我們該如何避免這樣的事情發生?

### Shortest Job First (SJF)
因為執行時間短的workload被卡住才造成convoy effect, 我們可以規定執行時間越短的task應該先被執行, 如此一來剛剛的情況會變成
先執行B, C才執行A, average turnaround time會變成$\cfrac{10 + 20 + 120}{3} = 50$
可以看到turnaround time有顯著的改進
事實上如果維持所有job都在相同時間抵達的假設, 那SJF是一個optimal scheduling algorithm

那我們就嘗試鬆綁這個假設看看會發生什麼事, 現在task A在t = 0時後抵達, task B, C都在t=10才抵達, 會發生什麼事？


如同上圖所示, 可以看到average turnaround time變成$\cfrac{100 + (110 - 10) + (120 - 10)}{3}$

### Shortest Time-to-Completion First (STCF)
如果我們在這時候引進context switch跟interrupt的機制
允許job在執行期間被scheduler給**preempt**, 則我們就有機會改進上述情況
SJF因為non-preemptive的特性所以可能在task的arrival time不同的時候表現不好, 在原本的SJF上加上preemptive性質就可以得到Shortest Time-to-Completion First或稱為Preemptive Shortest Job First

演算法如下, 每次有一個新的job抵達的時候, scheduler就會判斷這個job還有剩下所有還沒完成的jobs當中誰剩下需要的執行時間最短, 把該job拿給CPU執行
原本的情境就會變為以下


在B, C抵達系統的時候,A還剩下90 time units才能完成, 而B, C都只需要10 time units, 因此先執行B或C
如此一來average turnaround time會變成$\cfrac{(20 - 10) + (30 - 10) + 120}{3}$
而STCF在目前的情況來說也可以被證明是optimal的

在過往的電腦當中STCF這樣的演算法是非常有效也被大量使用的
不過自從**time-shared machine**出現後情況就改變了, 使用者變得可以和電腦互動, 因此**response time**變得極為重要
$T_{response} = T_{firstrun} - T_{arrival}$

而前述幾個演算法對於response time並不會表現的特別好

### Round Robin
Round Robin的原則非常簡單, 不是將每個job一口氣執行到結束, 而是每次只執行一個**time slice** (or scheduling quantum)然後就切換到下一個job
如此一來可以有效的優化response time, 不過也存在一個隱憂, 如果time slice太長, 則Round Robin和SJF沒什麼兩樣, 但如果time slice太短, 則context switch的時間可能會造成巨大影響

事實上就優化turnaround time來說, RR是最不適合的演算法之一
更廣泛地說, 任何**fair**的排程演算法, 對於turnaround time都不友善, 只有當你願意用**unfair**的方式對待每個job, 才有可能讓turnaround time變短變好

### Incorporating I/O
現在我們再將一個假設鬆綁, 也就是task不執行I/O
事實上所有的programs都會執行I/O, 那我們該如何在有I/O的情況處理scheduling呢？
很明顯的如果一個process在執行I/O, 則它不會也不應該佔用CPU, 所以這時候CPU會被blocked住, 沒有做任何事也沒辦法執行其他task
情況會長得像以下圖示


但如果我們把每個CPU burst視為一個獨立的job, 則我們有5個各自需要10 time units的task A(不過submission time不同), 還有一個需要50 time units的task B
在第一個task A的sub job完成後(代表task A去做I/O), 此時CPU就可以把task B拿進來執行, 當task A的I/O完成後, task A的第二個sub job也進入了系統, 這時候STCF scheduler會把CPU交給task A的第二個sub job(因為completion time較短)

上述行為稱為**overlap**, 可以最大化系統的使用率

到這裡為止我們已經解除了三個assumption, 分別是
* task execute for the same amount of time
* task arrive at the same time
* task perform no I/O

那還有一點是我們目前都預設我們已經知道task的runtime, 但這在真實系統中是幾乎不可能的, 我們很難事先知道task會花多久時間來完成, 為了解決這個問題, 我們需要一個可以依靠recent past來預測未來的scheduler, 稱為multi-level feedback queue, 我們會在下一篇文章中介紹

## Reference
[Operating System: 3 easy pieces](https://techiefood4u.files.wordpress.com/2020/02/operating_systems_three_easy_pieces.pdf)