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會是

$\frac{10+20+30}{3}=20$
此時我們鬆綁第一個assumption, 也就是每個job的run-time可以不相同, 這會造成什麼影響？有可能導致FIFO給出非常糟糕的average turnaround time嗎？
假設task A現在需要100個time unit來完成, 並且我們還讓task A在第一個執行
則average turnaround time會變成

$\frac{100+110+120}{3}=110$ , 瞬間變得非常糟糕
以上就是著名的convoy effect, 也就是相對短的workload被一個超重型的workload給霸佔CPU而不能執行的情況, 那我們該如何避免這樣的事情發生?

Shortest Job First (SJF)

因為執行時間短的workload被卡住才造成convoy effect, 我們可以規定執行時間越短的task應該先被執行, 如此一來剛剛的情況會變成
先執行B, C才執行A, average turnaround time會變成

$\frac{10+20+120}{3}=50$
可以看到turnaround time有顯著的改進
事實上如果維持所有job都在相同時間抵達的假設, 那SJF是一個optimal scheduling algorithm

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

如同上圖所示, 可以看到average turnaround time變成

$\frac{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會變成

$\frac{(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