行程管理『任務排班』

單核CPU使用率的提升一切從排班說起

前言

主題以『任務排班』“任務”這個詞來代表，而不是以行程或執行緒，這完全是由作業系統來決定，如果說支持執行緒，那執行緒將是CPU排班基本單位，否則行程就是CPU排班的基本單位，所以我們將行程及執行緒以“任務”這個詞來統稱，並且來討論CPU排班演算法。

為什麼要對任務進行排班？

在開始討論“為何要對任務進行排班？”之前，我們先介紹交互式與非交互式任務及重提CPU及I／O傾向行程，如下：

交互式任務：特別著重於響應時間（Response Time），例如：在編輯文章的時候，每次按下鍵盤都能夠迅速地反應，讓使用者可以有良好的使用者體驗。交互式任務其實也就是屬於I／O傾向任務。

非交互式任務：特別著重回復時間（Turnaround Time），例如：程式的編譯任務，也就是從進入系統到離開系統的時間。非交互式任務其實也就是屬於CPU傾向任務。

I／O傾向任務（I／O-bound）：CPU執行時間短，I／O執行時間長。（優先權重較CPU傾向任務高）

CPU傾向任務（CPU-bound ）：CPU執行時間長，I／O執行時間短。

在不同場合下的計算機系統，它們皆有各自的CPU排班演算法，在這裡我們針對個人電腦（PC）下的作業系統CPU排班進行討論。交互式任務與非交互式任務常常是同時存在的，它們彼此間存在一定的矛盾，沒辦法同時對它們進行完美地優化，所以只能折中給出方案對其優化，以處理這兩種不同種類的任務，這成為實現CPU排班演算法時要分析的核心問題。然而在『行程與執行緒概念』這篇文章當中，我們有提過“一個簡單CPU的工作原理”，當一個行程遇上IO要求時，此刻CPU必須等到該行程IO處理完才能繼續執行，CPU在這段期間處於閒置狀態，其CPU的使用率非常的差，為了改善這樣的情況，我們必須有個解決方案，以提高CPU使用率。

§ 再重提一次CPU排班程式

短程排班程式（short-term scheduler），又稱CPU排班程式，主要就是負責選擇一個合適的行程，接著將CPU配置給它使用。

§ 那什麼時機會進行排班決策呢？

在討論“什麼時機會進行排班決策”之前，我們先介紹可搶先及不可搶先排班，如下：

可搶先（preemptive）：當任務正在運行時，可以隨時被打斷，將CPU讓給其它任務使用。若在共用資料下，必須注意競爭情況（race condition）。

不可搶先（nonpreemptive）：當任務正在運行時，只有等到它運行結束或者發生某事件而被阻塞，才會將CPU讓給其他任務使用。

通常進行排班決策有以下情況：

1. 當任務從執行狀態轉到等待狀態
2. 當任務從執行狀態轉到就緒狀態
3. 當任務從等待狀態轉到就緒狀態
4. 當任務從執行狀態轉到終止狀態

§ 排班原則

任務的回復時間（turnaround time）：該任務進入到作業系統到該任務離開作業系統所經歷的全部時間。

任務的響應時間（response time）：使用者向某個程式發起一個操作，到該任務有所反應的這段時間。

任務的等候時間（waiting time）：任務在就緒佇列中等待的時間。

產量（throughput）：每單位時間所完成的任務數量。

CPU使用率：讓CPU盡可能的忙碌，以提升CPU的使用率。

排班演算法

先來先服務（first come first served, FCFS）

最簡單的CPU排班演算法，屬於不可搶先。在就緒佇列中先進去的任務會被先服務，也就是說每個任務依序被執行，一旦任務被分配CPU執行，該任務就會一直佔著此CPU，除非等到該任務執行完畢或者發出IO要求，才會放棄CPU讓下一個任務被執行。這個演算法非常適合CPU傾向任務系統，而不適合I／O傾向任務系統。

§ 甘特圖描述執行結果

考慮如下表格，其抵達時間忽略不計，CPU執行時間以毫秒為單位：

在這裡忽略不計抵達時間，上圖任務相關資訊的抵達時間是為了要凸顯哪一個任務先抵達而已。

A的等待時間為0毫秒

B的等待時間是15毫秒

C的等待時間為20毫秒

D的等待時間為24毫秒

因此平均等待時間為（0+15+20+24）/4 ≒ 15毫秒

如果說，任務抵達順序是D → C → B → A呢？讓我們來討論一下這與上面的差別在哪裡吧！

D的等待時間為0毫秒

C的等待時間為3毫秒

B的等待時間為7毫秒

A的等待時間為12毫秒

因此平均等待時間為（0+3+7+12）/4 = 5.5毫秒

在這裡其實大家可以發現，根據任務的執行時間及抵達時間的不同，會造成其等待時間及平均等待時間的不同，如果像A → B → C → D這樣的順序，可以發現其CPU使用率會比D → C → B → A這樣的順序還要差，也就是其單位時間內所執行的任務數比較少。A → B → C → D這樣的順序在15毫秒內只能完成一個任務，但是D → C → B → A這樣的順序卻可以在15毫秒內完成3個任務然後正在執行第四個任務，所以可以發現短時間的任務先執行，那麼該就緒佇列中的任務就可以被更早一點開始執行，將這個思考問題提出之後，我們可以對其進行改善，也就是這個問題會是我們等等會討論的短工作先做。

§ FCFS演算法產生的護送現象（convoy effect）

因為屬於不可搶先，也正是因為這樣，如果就緒佇列當中的所有任務都在等待一個執行時間很長的大任務離開CPU，那會造成其他任務的等待，好比大家目送著它離開，所以稱這個現象為護送現象，如下圖：

最短的工作先做（shortest job first, SJF）

在先來先服務中我們有先探討過最短的工作先做，這種演算法可以大大地降低平均等待時間，使CPU產量上升，此種演算法有兩種模式，一種是不可搶先，另一種是可搶先，在FCFS介紹的最短工作先做是屬於不可搶先，所以在這將討論可搶先，通常稱其為剩餘時間最短的先做（shortest-remaining-time-first, SRTF）。

這裡必須先說，這個演算法看似非常理想，但是任務的執行時間不可能事前就知道，我們只能回測過去，來預估任務執行時間。

§ 甘特圖描述執行結果

考慮如下表格，CPU執行時間以毫秒為單位：

在t為0的時候，任務A抵達進入就緒佇列當中，此時被排班，然後被分配CPU使用。

在t為2的時候，任務B抵達進入就緒佇列當中，此時任務B執行時間比任務A執行時間還要短，所以被排班然後搶走CPU的使用權。

在t為4的時候，任務C抵達進入就緒佇列當中，此時任務C執行時間比任務B執行時間還要短，所以被排班然後搶走CPU的使用權。

在t為5的時候，任務D抵達進入就緒佇列當中，並且任務C也剛好執行完畢，所以比較就緒佇列中哪個任務的執行時間比較短就執行哪一個，此時發現任務B的執行時間較短，所以任務B被排班分配CPU使用。

在t為7的時候，就緒佇列中剩下任務A及任務D，但是任務D的執行時間比較短，所以被排班分配CPU使用。

平均等待時間為[(16-0-7)+(7-2-4)+(5-4-1)+(11-5-4)]/4 = 3

A的響應時間為0

B的響應時間為0

C的響應時間為0

D的響應時間為2

依序循環（round-robin, RR）排班

為最簡單、最公平且使用最廣的排班演算法，專為分時系統（time-sharing）所設計，其基本思想就是在一段時間內，讓所有任務都有機會向前執行。

§ 特性

• 每個任務被分配一個時間區間，我們稱此時間區間為時間量（time quantum）或稱為時間片段（time slice）。
• 就緒佇列為環狀佇列，在時間片段內沒執行完的任務會回到佇列尾部，等待下一次的執行。
• 一個任務執行一個時間片段卻還沒執行完，計時器將停止並對作業系統產生一個中斷，執行上下文切換。
• 一個任務執行不到一個時間片段就執行完畢，那將會主動歸還CPU使用權。
• 通常時間片段被設置為10～100毫秒，如果過短會造成過多的上下文切換，降低CPU的使用率，又或者過長會造成任務的響應時間變長。

§ 甘特圖描述執行結果

考慮如下表格，其抵達時間忽略不計，CPU執行時間以毫秒為單位：

如果時間片段為4毫秒，則以下為其執行結果

§ 過多的上下文切換

以上面RR甘特圖任務A為例

從上圖可以看出時間片段比較小時，會造成任務過多的上下文切換，進而導致了CPU使用率下降，但是過長的時間片段又會造成任務響應時間過長的情形，基於以上所以我們通常會規範時間片段的大小，在現代電腦中時間量範圍為10到100毫秒。

多層佇列（multilevel queue）排班

在作業系統中有交互式與非交互式任務，經常我們需要一起處理這兩種不同類型的任務，於是該排班演算法就是將其分成前景佇列（foreground queue）與背景佇列（background queue），前景佇列對應的是交互式任務，而背景佇列對應的則是非交互式任務，然而前景佇列優先級總是比背景佇列還要高，也就是說前景佇列的任務會先被執行，等到前景佇列空了才會執行背景佇列的任務，如下圖所示：

§ 特性

• 每個獨立的佇列都有自己的排班演算法，比如：前景佇列可能是使用RR演算法排班，而背景佇列則可能使用FCFS演算法排班。
• 前景佇列優先級比背景佇列高。
• 如果採用不可搶先，一旦背景佇列任務得到CPU使用權，那只能等到執行完後才會釋放CPU，這段時間裡抵達的前景佇列任務必須等待，也造成了其前景佇列的任務響應時間變長，與使用者的交互變差。
• 如果採用可搶先，一旦前景佇列有任務，就必須等到前景佇列沒有任務才能執行背景佇列的任務，這非常有可能會造成飢餓的狀態。

多層回饋佇列（multilevel feedback queue）排班

多層“回饋”佇列排班演算法，這個詞回饋凸顯出了這個排班演算法的核心，也就是動態調整任務，通常我們按執行時間長度來動態調整任務應該位於哪個佇列當中。下圖為一個三層回饋佇列，如果說現在我們有一個任務A執行完一個時間片段，但是該任務A還沒有被執行完，說明了這個任務A沒有發生IO的操作，所以認定該任務A為非交互式任務，於是將其優先權降級，然後放入了就緒佇列2當中，如果說該任務A在就緒佇列2中依然沒有被執行完，該任務A就會繼續被降級，然後放到就緒佇列3當中，我們可以發現這個有點類似SRTF排班演算法，而且我們不需要有任務執行時間的這個參數，完美地解決了SRTF排班演算法的任務時間長度的預測問題。

§ 特性

• 有效地解決了交互式與非交互式任務的排班。
• 任務的平均等待時間下降了。
• 任務的響應時間很明顯地在一個可被使用者接受的範圍。
• 為最通的一種CPU排班演算法，但是也是為最複雜的排班演算法之一。

參考來源

1. B站，操作系統（哈工大李治軍老師）
2. YT，作業系統（周志遠教授）
3. Abraham Silberschatz, Peter B. Galvin, Greg Gagne。《作業系統概念》。駱詩軒譯。台北。台灣東華書局。