作業系統筆記之 CPU排程(CPU Scheduling)

最後更新於 2021 年 6 月 2 日

排程簡介

對於單處理系統每次只允許一個程序執行，其他程序必須等待，直到CPU空閒能被排程為止，因此如何保證CPU有最大利用率就需要CPU排程。

CPU排程必須要依賴行程(Process)的CPU-I/O週期，指的是行程執行從 CPU 區間開始，在這之後是 I/O 區間，直到最後一個CPU區間呼叫一個終止行程執行的系統呼叫(system call)作為行程結束。由此我們可以知道，CPU區間的執行依賴於上一個I/O區間的完成，但在I/O區間進行時能否也使得其他行程的CPU區間使用CPU呢？CPU排程就是為了完成這種轉換。

那麼，CPU該由誰來排程？

由短期排程程式（short-term scheduler）執行。每當CPU空閒時，排程程式就從就緒佇列中選擇一個行程並為之分配CPU使用權。排程程序選擇了行程之後，將CPU使用權傳遞給被選擇的行程此一過程是由 分派程序(dispatcher)來進行的。

分派程序需要做的事情包括：

切換內容
切換到用戶模式
跳轉到用戶程序合適的位置，以重新啟動程序

而完成上述工作所需的時間稱為 分派延遲(dispatch latency)。

排程標準

用於評價排程演算法適不適合的基準

CPU使用率
吞吐量(Throughput)：單位時間內完成的工作數
周轉時間(Turnaround time)：從行程提交到完成行程所用的時間
等待時間(Waiting time)：行程在就緒隊列中花費的時間
響應時間(Response time)：從提交請求到返回響應所花的時間
*分時系統(Time-sharing System)與使用者交互系統(User-Interactive) 特別重視

可搶佔vs.不可搶佔

CPU Scheduler的所有演算法大致可以分為兩大類：

不可搶佔式(Non-preemptive)

當Process取得CPU在執行時，除非這個Process自願將CPU釋放出去(如：Process 結束工作、Wait for I/O complete)，其它Process才有機會取得CPU，否則其它的Process無法取得CPU的使用權。

可搶佔式(Preemptive)

當一個Process取得CPU在執行時，有可能被迫放棄CPU (如：Highest Priority Process進入系統、中斷發生、CPU time slice expires)，將CPU交給其它的Process執行。

image 5 作業系統筆記之 CPU排程(CPU Scheduling) — 可搶佔與不可搶佔式排班的比較表

排程演算法

排程演算法包含下列幾種：

First-Come First-Served Scheduling (先到先排班)
shortest-job-first scheduling (最短作業優先排程)
Round Robin (RR) Scheduling (依序循環排班)
Priority Scheduling (優先權排班)
Multilevel Queue Scheduling (多級佇列排程)
Multilevel Feedback-Queue Scheduling (多級反饋佇列排程)

先到先處理排程(FCFS)

顧名思義就是先請求CPU的程序最先分配到CPU，通常來說，使用此方法排程平均等待時間較長。

假設有三個程序要執行：

行程	CPU處理時間	往返時間	等待時間
P1	10	10	0
P2	4	14	10
P3	7	21	14

image 10 作業系統筆記之 CPU排程(CPU Scheduling) — gantt圖

按照P1,P2,P3的順序到達，則平均等待時間為 (0 + 10 + 14)/3 = 8

優點

較公平
不會發生飢餓(Starvation)

缺點

排班效益最差(∵Avg. Waiting Time 或Avg. Turnaround Time最長)
易產生護航效果(convoy effect)
- 很多Processes均在等待一個需要很長CPU Time來完成工作的Process，造成平均等待時間(Avg. Waiting Time) 大幅增加的不良現象。

最短作業優先排程(SJF)

當CPU空閒時，它會從就緒佇列中找到下一個具有最短CPU區間的程序先執行，若是有兩個程序具有相同長度，則可以使用FCFS排程處理。SJF演算法可能是可搶佔(SRTF)的或不可搶佔(SJF)的。

舉個例子

行程	CPU處理時間	往返時間	等待時間
P1	9	23	14
P2	3	3	0
P3	4	7	3
P4	7	14	7

image 11 作業系統筆記之 CPU排程(CPU Scheduling) — SJF gantt圖

最短優先排程(SJF)平均等待時間為 (0+3+7+14)/4 = 6

image 12 作業系統筆記之 CPU排程(CPU Scheduling) — FCFS gantt圖

先到先處理排程(FCFS)則是 (0+9+12+16)/4 = 9.25

由此例子能看出SJF演算法平均等待時間是最短的，只以平均等待時間來看，SJF演算法可稱為最佳演算法，但程序尚未處理前無法預估其處理時間，也因此無法得知下一個CPU區間的長度，導致SJF在實務上不可行。

接著舉一個 可搶佔最短作業優先(SRTF) 的例子：

行程	到達時間	CPU處理時間	往返時間	等待時間
P1	0	3	4	1
P2	1	1	2	0
P3	2	3	7	2

image 13 作業系統筆記之 CPU排程(CPU Scheduling) — SRTF gantt圖

平均等待時間為 (1+0+2)/3 = 1

*注：等待時間還需要減去到達時間。

優點

排班效益最佳(最理想) Avg. Turnaround Time與Avg. Waiting Time最小
不會有Convoy Effect

缺點

不公平
無法得知下一個CPU區間長度
需要很長時間來執行的行程一直被無限推遲，這種情況稱為飢餓(starvation)，對長作業不利。
解決辦法：Aging

優先權排程

每一個程序都會有自己的優先權，高優先權的程序會最先被分配到CPU，相同優先權則是按照FCFS(先來先服務)排程，SJF(最短優先排程)是優先權排程的一個特例，算是前兩種演算法的中和，權衡了短作業與長作業。

優先權可通過內部以及外部方式來定義，內部定義會使用一些測量資料以計算優先權；外部則是通過作業系統之外的準則來定義，如程序重要性…等。

分為非搶佔式以及搶佔式，若是非搶佔式即使高優先權的來也不會讓CPU，而是先將自己執行完畢，反之則是搶佔式。

但這樣的排程方式容易造成低優先權的程序一直處於等待CPU的狀態(indefinite blocking / starvation)，解決的方法之一是Aging(老化)，隨著行程的等待會將其優先權緩緩提高，直至能夠執行。

舉個例子：

行程	CPU處理時間	優先權
P1	10	3
P2	1	1
P3	2	4
P4	1	5
P5	5	2

優先權值越小代表優先權越高

image 14 作業系統筆記之 CPU排程(CPU Scheduling) — Priority gantt圖

平均等待時間為：(6+0+16+18+1)/5 = 41/5 = 8.2

缺點

不公平
可能會發生飢餓情況

依序循環排程(RR)

使用最廣且最公平的演算法，專門為分時系統(Time-Sharing)設計，類似於FCFS排程(先到先處理)。

定義了一個較小的時間單元為Time Quantum/Slice(時間片)，每個程序分配一個時間片，允許程序在時間段中執行，時間一到就分配給另外一個程序。

舉個使用4 ms 時間片的例子：

行程	CPU處理時間	等待時間
P1	24	0 , (10-4)
P2	3	4
P3	3	7

image 15 作業系統筆記之 CPU排程(CPU Scheduling) — RR gantt圖

平均等待時間為 (0+4+7+(10-4)) /3 = 5.66

接著可能會發生兩種情況：

1.程序可能只需要小於時間片的CPU區間

對於這種情況，程序本身會自動釋放CPU，排程程式接著處理就緒佇列的下一個程序。

2.程序執行的CPU區間比時間片要長

定時器會中斷產生作業系統中斷，然後進行內容轉換(Context Switching)，將程序加入到就緒佇列的尾部，接著CPU排程程式會選擇就緒佇列的下一個程序。

RR演算法效能很大程度依賴於時間片的大小，如果時間片非常大，那麼RR演算法和FCFS演算法一樣；如果時間片很小，那麼RR演算法稱為處理器共享，n個程序對於使用者都有它自己的處理器，速度為真正處理器速度的1/n。

小的時間片會增加內容轉換(Context Switch)的次數，因此希望時間片比內容交換(Context Switch)時間長，絕大多數現代作業系統內容轉換的時間僅佔時間片的一小部分，迴轉時間也依賴於時間片的大小。

優點

公平的
不會發生飢餓情況

RR的排班效益取決於CPU Time Slice之定義：

CPU Time Slice 越大 ⇒ FCFS
CPU Time Slice 越小 ⇒ Context switch太頻繁，CPU Time未真正用在process execution上，導致throughput低。

通常80%的工作可以在Time Slice內完成，效果較好。

多級佇列排程

將就緒佇列分成多個獨立的佇列，例如：Foreground(交談)、Background(批次)，每個佇列有各自使用的演算法。在排程時，這些佇列之間要先做優先順序的排程、CPU時間的分配。

例如：

Foreground：RR演算法、高優先、80%的CPU時間。
Background：FCFS演算法、低優先、20％的CPU時間。

根據Process的不同特性，將主記憶體中所形成的單一Ready Queue分成不同優先等級的Ready Queues。

每個Queue可有自已的Scheduling Algorithm。
Queue與Queue之間採取“Preemptive Priority”之排班方式。
不允許Process在各個Queue之間移動。

缺點

不公平
會有Starvation

多級反饋佇列排程

是 依序循環排程(RR) 以及 優先權排程 的綜合，比起多級佇列排程演算法更為動態，行程可以在不同的佇列之間移動。

「多級」表示有多個佇列，每個佇列優先權從高到低，同時優先權越高時間片越短。
「反饋」表示如果有新的程式加入優先權高的佇列時，立刻停止當前正在執行的程式，轉而去執行優先權高的佇列；

舉個例子，假設有三個佇列：

Q0 – RR 時間量= 8毫秒
Q1 – RR 時間量= 16毫秒
Q2 – FCFS

新的程式會被放入到Q0的末尾，按先來先服務(FCFS)的原則排隊等待被排程，如果在Q0規定的時間片內沒執行完成，則將其轉入到Q1的末尾，以此類推，直至完成。

當較高優先權的佇列為空，才排程較低優先權的佇列中的程式執行。如果程式執行時，有新程式進入較高優先權的佇列，則停止當前執行的程式並將其移入到原佇列末尾，接著讓較高優先權的程式執行。

優點

排班設計/調整之Flexibility高
不會有飢餓(Starvation)
- 採取類似“Aging”技術，每隔一段時間就將Process往上提升到上一層Queue中。∴在經過有限時間後，在Lower Priority Queue中的Process會被置於Highest Priority Queue中。故無Starvation。
- 亦可配合降級之動作。當上層Queue中的Process取得CPU後，若未能在Quantum內完成工作，則此Process在放棄CPU後，會被置於較下層的Queue中。

缺點