在進入正題之前，大家可以想像一下一個情境，現在有A、B、C 三人走進麥噹噹，他們分別點了這些食物：
（依照「點餐的先後時間」排序，越前面代表越早點餐）

A: 100 份麥香魚（所需時間：60分鐘）
B: 一包大薯 （所需時間：2分鐘）
C: 一個冰炫風（所需時間：1分鐘）

我們要以這個情境去揣摩各個排班演算法

排班演算法大致可以區分為兩大屬性

1. 可以搶先（Preemptive）
   每分每秒都在比較各程序的狀態，當有程序進入就緒狀態時，就會把它跟目前正在使用的程序比較優先順序，優先順序較高者就會把較低者踢去排隊

2. 不可以搶先 (Nonpreemptive)
   不論其他程序的狀態為何，擁有 CPU 使用權的程序能夠一直使用，直到它跳到其他非執行的狀態才會進行排班

▋名詞報你知

等待時間（Wating Time）

行程在就緒佇列中等待執行的總時間

行程所需時間（Turnaround Time）

行程交付到執行完畢的時間（回覆時間）

▋先到先處理（First Come First Serve, FIFO）

圖片來源

套用麥噹噹情境：A、B、C 三人中，A 先點了 100 份麥香魚，需要耗費 60 分鐘，那就要等 A 的餐做完，才會做 B 的餐，即便 B 只要 2 分鐘就可以完成，也還是會等A的做完，以此類推 C 也是如此！

平均等待時間為 (60 + 2) /3 = 20.6分鐘 （交換一下來的先後順序又會有不一樣的結果喔

每當有一個新的程序需要使用 CPU 的資源時，它就會被串接到就緒佇列的末端，當 CPU 完成了一個程序，就會處理排在就緒佇列中的第一個程序，並且把執行完的踢除。這種排班方式是「不可搶先」的。一旦 CPU 被分配給某個程序，那就要等它進入等待或是結束狀態時，才會執行下一個程序，這就是「先到先處理」

▋最短工作先處理（Short Job First, SJF）

「所需時間」最短的程序會優先得到 CPU 的使用權，如果有兩個以上的程序所需時間相同，就會依照先到先服務的方式挑選，套用麥當當的例子，執行順序就會如下：

B（所需時間: 2 分鐘） => C（所需時間: 1 分鐘） => A（所需時間: 60 分鐘）

平均等待時間為：(2 + 1) / 3 = 1分鐘

「最短工作先處理」可以分為「可搶先」和「不可搶先」兩種方式：
如果是「可搶先」的情況，在 CPU 執行某一程序的同時，突然有新的程序產生，就要比較新程序的所需時間，如果比較短，新的程序就會搶走 CPU 的使用權; 如果是「不可搶先」的情況，新的程序就要等待目前的程序執行完畢，然後 CPU 就會檢視在這些等待被執行的程序中各會花多少時間，來安排其優先順序

▋優先權排班（Priority Scheduling）

「優先權排班」就比較特別一點了，它會把程序階級化，標上各自的順序
那階級化的依據是什麼呢？
廣義來看會從各面向下去評估，像是計算所需時間、記憶體需求、程序大小、程序的重要性等

套用麥噹噹情境：不只是考量 A、B、C 的所需時間，還會考量其他面向，剛好 B 是米其林派來的評審，就會給他較高的優先權(誒？

「優先權排班」也可以分為「可搶先」和「不可搶先」兩種方式：
跟「最短工作先處理」一樣，在「可搶先」的情況下，如果突然有一個新的程序產生，而且它的優先順序又比目前正在執行的程序來得前面時，就可以搶走 CPU; 而在「不可搶先」的情況下，就得等待當前程序執行完畢

「優先權排班」有可能會有的潛在問題就是，有些程序因始終得不到資源而變成「飢餓」(starvation）的狀態，因為 CPU 就是不斷地去分配給優先序較高的程序，而優先權較低的程序就一直在就緒佇列中癡癡等待～等到天荒地老～
那可以怎麼解決呢？
就是也把「等待時間」也納入優先權設定的考量範圍，這樣一來，總會有等到的一天吧！

▋依序循環排班（Round Robin Scheduling）

「依序循環排班」可說是為了「分時系統」所設計的！分時系統在昨天的文章有講到，這裡就不細說了。它的主要任務是要在時間一到就讓下一個程序使用 CPU，以「時間觸發」（Time Driven）為首要。
「依序循環排班」的方式，會預先設定好間隔時間（Time Slice）， 過了間隔時間，CPU 就會切換到下一個程序。也就是所有的程序都會先放到「先進先處理」的就緒佇列中，CPU 會挑選第一個要執行的程序，然後開始倒數，時間一到，就會處理下一個程序，這種排班方式會有兩種情境：

1. 程序所需時間 < 間隔時間：
   在這個情況下，程序一執行完畢，就得返還 CPU 的使用權，讓 CPU 執行下一個程序

2. 程序所需時間 > 間隔時間
   CPU 在倒數完畢時，還會有尚未完成的部分，但我們必須堅守時間一到就要讓出 CPU 給下一個程序的原則呀，那這時候沒有執行完的部分要怎麼辦呢？
   作業系統就會把目前沒有執行完的程序記錄到程序控制表（Process Control Block, PCB）中，然後把程序放到就緒佇列的尾巴
   PS 「程序控制表」是作業系統核心中一種資料結構，表示「行程狀態」

以下舉個圖例：

圖片來源

上圖中可以拆成以下幾部分來看：

1. 首先是 p2 實際只需要 3 豪秒就可以執行完成，不需要到 5 毫秒的時間，所以 p2 執行完後就可以讓 CPU 執行下一個程序

2. 18 毫秒時：p2 已執行完成，所以把他從佇列中移出，佇列中的第一個程序就變成 p3 ，就變成執行 p3 並把 p1 放到佇列的尾巴

3. 21 毫秒時：p3 執行完成，佇列中只剩下 p1 ，所以就會繼續執行直到 p1 完成

執行次數越多代表 CPU 切換的頻率越頻繁，就要花比較多時間在讀取和寫入程序控制表。如果「間隔時間」設定的太短也會造成執行次數越多; 間隔時間設定太長就會變成「先進先處理」的排班方式
那這樣要怎麼辦？？怎麼做都不太對勁
這時候通常會使用「二八法則」，讓 20% 的程序所需時間 > 間隔時間; 80% 的程序所需時間 < 間隔時間

▋所以，為什麼需要 CPU 排班？

為了避免程序被比較耗費時間的任務卡住，資源被佔用，根據演算法必須在某個時間先暫時被踢出去，讓別的程序先被執行。

值得注意的是，排班法並不會加快 CPU 處理的速度，像是麥當當在做 A + B + C 的餐點時，所需要的總時間永遠都是 63 分鐘呀 ，但會依照不同的排班方式而有不同的等待時間，執行效率也不一樣

▋總結

不論採用哪種排班方式，都會依照「請求」、「使用」、「釋放」資源的方式執行。在「多元程式規劃」系統中，程序之間要彼此競爭取得有限的資源，然而搶不到的程序就會進入「等待」狀態，直到所需要的資源被釋放。但當所請求的資源也被其他正在「等待」中的程序所佔用，也有可能無法跳脫「等待」的狀態，產生「死節」（Deadlock）。程序都在等待另一個程序觸發事件，但遲遲沒等到，最終呈現「飢餓」（starvation）的狀態

• 「先到先處理」的方式實作上簡單，但是會受來的先後順序影響平均等待時間，有時甚至會相差很大，並不是最理想的排班方式
• 「最短工作先處理」的方式，如果只考慮把平均等待的時間降到最低，那麼它應是首選，不過也會遇到些問題，像是實際在執行時，很難精準的預測每一個程序會花多少時間來完成工作
• 「優先權排班」會把程序階級化，會把所需時間、記憶體需求、程序大小、重要性等納入考量，評估各自的順序
• 「依序循環排班」也是「可搶先」排班，每個程序時間一到，CPU 使用權就會被搶走，不能繼續罷佔下去

▋參考資源

1. 全華 - 計算機概論 資訊素養大補帖
2. CPU Seducling
3. 排程介紹