作業系統筆記 之 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)

排程標準

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

  1. CPU使用率
  2. 吞吐量(Throughput):單位時間內完成的工作數
  3. 周轉時間(Turnaround time):從行程提交到完成行程所用的時間
  4. 等待時間(Waiting time):行程在就緒隊列中花費的時間
  5. 響應時間(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處理時間往返時間等待時間
P110100
P241410
P372114
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處理時間往返時間等待時間
P192314
P2330
P3473
P47147
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處理時間往返時間等待時間
P10341
P21120
P32372
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處理時間優先權
P1103
P211
P324
P415
P552
優先權值越小代表優先權越高
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處理時間等待時間
P1240 , (10-4)
P234
P337
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時間。
image 7 作業系統筆記 之 CPU排程(CPU Scheduling)

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

image 8 作業系統筆記 之 CPU排程(CPU Scheduling)
  • 每個Queue可有自已的Scheduling Algorithm。
  • Queue與Queue之間採取“Preemptive Priority”之排班方式。
  • 不允許Process在各個Queue之間移動。

缺點

  • 不公平
  • 會有Starvation

多級反饋佇列排程

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

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

舉個例子,假設有三個佇列:

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

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

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

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

優點

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

缺點

  • 不公平 => 佇列有可能用到不公平演算法

總結

為上述幾個排班演算法做分類:

可搶佔的

  • SRTF
  • Preemptive Priority
  • RR
  • Multilevel Queue
  • Multilevel Feedback Queue

不可搶佔的

  • FCFS
  • SJF
  • Non-Preemptive Priority

No Starvation

  • FCFS
  • RR
  • Multilevel Feedback Queue

公平的

  • FCFS
  • RR

參考資料

4e52d54f6bc42abb41d26eb5b0df6517?s=250&d=wavatar&r=g 作業系統筆記 之 CPU排程(CPU Scheduling)
2.7 3 評分數
Article Rating
訂閱
通知
guest
1 Comment
在線反饋
查看所有評論
brian
brian
2 月 前

RR的方法,P2等待時間應該是6吧