第二章　排班程式 2-1　排班程式之類型 2-2　排班程式

2-1 排班程式之類型 1. 排班程式依其處理之功能與時機可歸類成下列三大類型 － (1) 長程排班 (Long - Term Scheduling) (或 Job Scheduling)： 決定那些工作 (Job) 可以載入主記憶體中準備執行。必須使主記憶體中的以 CPU - Bound 工作與以 I/O - Bound 工作維持均衡，還有必須考慮系統內多程式 (Multiprogramming) 的程度。

(2) 中程排班 (Mediun - Term Scheduling)： 降低系統內多程式的程度 (Degree of Multiprogramming)，改善 CPU 與 I/O 間的負載平衡。 (3) 短程排班 (Short - Term Scheduling) (或 CPU Scheduling)： 自主記憶體中挑選一個等待執行的處理單元，將之交付給 CPU 執行。

2. 三類型排班程式間的關係圖如下 －

(1) CPU 使用率 (CPU Utilzation)： CPU 的使用程度。即 (2) 生產量 (Throughput)： 單位時間內完成處理單元之個數。

(3) 返轉時間 (Turnaround Time)： 一個處理單元自開始進入系統中到執行完畢所耗費的時間。 (4) 回應時間 (Response Time)： 一個處理單元自開始進入系統中到第一次產生輸出所耗費的時間。 (5) 等待時間 (Waiting Time)： 一個處理單元在預備佇列 (Ready Queue) 中等待執行所耗費的時間。

2. CPU 排班程式之種類 － (1) 先來先服務 FCFS (First Come First Serve)： 分配 CPU 給處理單元的次序是依它們到達預備佇列的時間先後而定。一旦處理單元獲得 CPU 便可一直執行至結束，是一種不可搶用的 (Non - preemptive) 排班法。

 範例： 有三個處理單元，A，B 與 C，其進入預備佇列之順序為 A，B，C，其執行時間 (Burst Time) 分別為 20，5 與 2。則經 FCFS 排班結果如下：

<註>：護航效應 (Convey Effect) 是指有許多的處理單元在等候一個需佔用較長 CPU 時間的處理單元，導致在其後進入預備佇列的處理單元皆在等候它的完成。FCFS 排班程式的缺點便是當發生護航效應時，會造成CPU 與輸出／輸入設備在某些時段的使用率極低。

(2) 巡迴服務 (Round Robin，RR)：CPU 分配給處理單元的方式仍以先到者先服務，但處理單元並非一直執行到結束，而是配置一固定的時間配額在CPU上執行，在配額時間用完後，若仍未完成工作，則時間計時器 (Timer) 會發出一個中斷來中止處理單元繼續執行，並由分配程式 (Dispatcher) 將CPU使用權移給下一個處理單元，被中斷的處理單元必須回預備佇列 中排隊。故它是一種可搶用的排班法，且適合於分時系統。

 範例： 有三個處理單元 A，B 與 C ，其執行時間 (Burst Time) 分別為 20，5 與 2。設時間配額 (Time Quantum) 為 4，則經 RR 排班結果如下：

(3) 最短工作先服務 (Shortest - Job - First，SJF)： 在所有等待之工作或處理單元中，估計從開始至結束其工作所需執行時間最少者優先。故 SJF 較偏好較短的工作或處理單元，此法為不可搶用 (Non - preemptive)。 <註>：對於同樣一組處理單元(考慮所有處理單元進入預備佇列時間相同時)，若採用 SJF 則其平均等待時間會是所有排班方法中最小的。

 範例： 有三個處理單元，A，B 與 C，其執行時間分別為 20，5 與 2。則經 SJF 排班結果下：

(4) 剩餘最短的工作先服務 (Shortest - Remaining - Time，SRT) 挑選距離工作完成所需時間最少者為最優先 (包括新到達的工作)，此法在分時 (Time - Sharing) 系統中的效能頗佳，屬於可搶用 (Preemptive)。此法或稱為可搶用 SJF (Preemptive SJF)。

 範例： 有三個處理單元，A，B 與 C，其到達時間 (Arrival Time) 分別為 0，2 與 3；執行時間分別為 20，5 與 2。則經 SRT 排班結果下：

(5) 優先次序法 (Priority Scheduling) 如採優先次序法排班，則每個處理單元會給予一個優先次序值 (Priority)，優先次序值愈大其擁有 CPU 使用權的權限愈高。此排班法可以設計成可搶用或不可搶用，如果設計成可搶用，則當有處理單元進入預備佇列且其優先次序值較目前正在執行的處理單元高，則原先執行的處理單元會被中斷，而新進的處理單元會佔用 CPU 執行﹔反之，若設計成不可搶用，則即使剛進入預備佇列的處理單元之優先次序值較高，仍需等待目前正在CPU 中執行之處理單元執行完畢後，才能使用 CPU。

 範例： 有三個處理單元A、B與C，約同時進入預備佇列且其執行時間分別為20 , 5 與 2 , 優先次序值分別為 3 , 7 與 5，則經優先次序法排班之結果如下：

(6) 高反應率的工作先服務 (Highest - Response - Ratio – Next Scheduling，HRN) 此法是屬於優先次序排班程式的一種，它是針對 SJF 偏好短工作而忽略長工作之缺點而改進的方法，每個工作的優先權不再僅由所需服務時間決定，尚須考慮已等候時間的長短。 由優先等級的公式中可以看出此法對於短工作或等待時間較長者會給予較高的優先等級。 <註>：以等待時間來提昇優先次序值的方法稱之為增長 (Aging)，即等待愈久者，其優先等級會愈高 。

 範例： 有三個處理單元，A、B與C，其到達預備佇列的時間分別為0 , 1與0﹔執行時間分別為20 , 5與2。則經HRN排班結果如下：

<註>：此法因屬於優先次序法，故可以設計成可搶用或不可搶用之形式，但如果設計成可搶用將會使系統效能較設計成不可搶用時低。試想有幾個等長的工作t1 , t2,……與tn 幾乎是同時進入預備佇列中，若 t1 先執行1個單位的時間候，則t2 , t3,……與tn 因已等後１個單位時間，其優先等即已提昇，此時 t1 將被中斷，而再由t2 , t3,……與tn 中挑選一個執行，在此情況下將會退化成RR。

(7)多層佇列法 (Multilevel Queue Scheduling) 由於每個處理單元的性質不一定完全一致，如何將它們做適當的區分，並依其特性給適當的排班演算法。例如：將隸屬於系統層級的處理單元 (System-Process) 置於高優先等級的預備佇列中,將交談式的處理單元 (Interattive Process) 置於中等優先等級的預備佇列中，而屬於批次式的處理單元 (Batch Process) 則置於較低優先等級的預備佇列中。

多層佇列排班，其特性如下： 將單一個預備佇列再分割數個預備佇列 (預備佇列的數量依各系統的特性與需求決定)。 每個處理單元依其特性，由處理單元性質區分程式將之放至於適當的預備佇列等待執行。 每個預備佇列各自擁有一個優先等級，預備佇列的優先等級愈高，則該佇列擁有 CPU 使用權的權限愈高。

由於高優先等級佇列內的處理單元擁有CPU 使用權的機率較高，可能導致低優先等級佇列內的處理單元永遠無法使用被 CPU 所執行，造成所謂的飢餓現象 (Starvation)。為了避免上述情況的發生，可將CPU的服務時間切割，並依各預備佇列的重要程度分配適當比例的CPU時間 (例如：高優先等級預備佇列分配60% 的 CPU 服務時間；中優先等級預備佇列分配30% 的 CPU 服務時間；低優先等級預備佇列分配10% 的 CPU 服務時間)

(8) 多層回饋佇列 (Multilevel Feedback Queues Scheduling，MFQ) 由於多層佇列排班法方式不夠彈性，一旦決定處理單元進入某一佇列後，便無法再更動且使用該佇列之排班方式至處理完畢，為了改善多層佇列的缺失，多層回饋佇列允許處理單元在不同的預備佇列中轉移，所以在設計此種排班演算法時必須考慮如下兩點因素： 1. 預備佇列的數量及各預備佇列所採用之排班演算法。 2. 定義各種預備佇列的優先等級，及如何由高優先等級的預備佇列降級至低優先等級預備佇列的方法或如何由低優先等級的預備佇列升級 至高優先等級的預備佇列的方法。

當處理單元第一次獲得 CPU 時，排班程式 無法知道其型態，因以輸出入為主 (I/O - Bound) 的處理單元只會使用少許的 CPU 時間就去處理 I/O，而以 CPU 為主 (CPU - Bound) 的處理單元大部分時間是用在 CPU 上，若在不可搶用下，可能會使用 CPU 長達數個小時之久，故多層回饋佇列為達成 a. 選擇較短的工作。 b. 偏好以 I/O 為主的工作，以便獲取較高 I/O 使用率。 c. 儘快決定工作之特性，以做為排班的根據。

其操作方式如下：  系統分成n個層次(Level) 的預備佇列。從第一層 (Level 1) 到第 (n-1) 層的佇列皆為先進先出 (FIFO) 佇列，其排班方式是每個處理單元在該佇列上執行一固定的時間配額，若順利執行完則離開該佇列，否則移至下一佇列中，至於第 n 層的佇列則以巡迴服務 (RR)方式排班。從第一層到第 (n-1) 層中，每個層次的 CPU 時間配額愈往下愈多，即第一層最少，第 (n-1) 層最多。

 一個新的處理單元進入系統後會被加入在第一層的佇列的最後面。  當此處理單元獲取 CPU 時，若在時間配額 未用盡時就變成暫止或完成狀態，則此處理單元離開佇列。  若時間用盡，則置於第二層的佇列的後端，再等候機會使用 CUP。  只要一處理單元因時間配額用盡且未完成工作，則置於下一個層級佇列的最後面。

 第二層內的處理單元只有在第一層預備佇列沒有任何的處理單元時，才有機會獲得 CPU，其餘層次的佇列則依此類推。 在最低層 (Level n) 佇列內的處理單元，則視此層佇列所使用之排列方式 (如：以巡迴服務 (RR)、最短工作先服務 (SJF) 或先來先服務 (FCFS)的方式排班)，一直到處理完成或發生 I/O 為止。

 範例： 有五個處理單元，A、B、C、D與E約同時依序到達預備佇列中，其執行時間分別為20, 12, 8, 4與2。假設多層饋佇列之架構與排班的服務方式如下：

則其經MFQ排班之結果如下：

3. 排班程式特性匯整 －