【文章內(nèi)容簡介】 處理器的進程 ： 進程調(diào)度的主要功能是按照一定的策略選擇一個處于就緒狀態(tài)的進程 ， 使其獲得處理器運行 。 根據(jù)不同的系統(tǒng)設計目標 ， 有各種各樣的選擇策略 。 ?進行進程上下文的切換 ： 進程的上下文是進程執(zhí)行活動全過程的靜態(tài)描述 。 一個進程的上下文包括進程的狀態(tài) 、 有關變量和數(shù)據(jù)結構的值 、 機器寄存器的值和 PCB以及有關程序 、 數(shù)據(jù)等 。 一個進程的執(zhí)行是在進程的上下文中執(zhí)行的 。 當正在運行的進程由于某種原因要讓出處理器時 ， 系統(tǒng)要做進程上下文切換 ， 以使另一個進程得以運行 。 5． 3 ． 2 進程調(diào)度方式 ?非剝奪調(diào)度方式 ： 調(diào)度程序一旦把處理器分配給某進程 ， 該進程就將一直運行下去 ， 只有當進程完成或發(fā)生其事件而阻塞時 ， 系統(tǒng)才把處理器分配給另一進程的調(diào)度方式稱為非剝奪調(diào)度 ， 也稱非搶占方式 （ nonpreemptive scheduling） 方式 。 在此調(diào)度方式下 ， 系統(tǒng)不得以任何理由剝奪現(xiàn)行進程所占用的處理器 。 該調(diào)度方式的優(yōu)點是簡單 、 系統(tǒng)開銷小 ，但卻可能導致系統(tǒng)性能的惡化 ， 表現(xiàn)為： ?當一個緊急任務到達時，不能立即投入運行，以至于延誤時機； ?若干個后到的短作業(yè)，需要等待先到的長作業(yè)運行完畢后才能運行，致使短作業(yè)的周轉(zhuǎn)時間較長。 5． 3 ． 2 進程調(diào)度方式 ?剝奪調(diào)度方式 ： 進程的另一種調(diào)度方式是剝奪調(diào)度方式 ， 或稱搶占方式 （ preemptive scheduling） ， 這是指進程正在運行時 ， 系統(tǒng)可根據(jù)某種原則 ， 剝奪已分配給它的處理器 ， 并將處理器再分配給其他進程的一種調(diào)度方式 。 剝奪的原則有： ?優(yōu)先權原則。優(yōu)先權高的進程可以剝奪優(yōu)先權低的進程的運行； ?短進程優(yōu)先原則。短進程到達后可以剝奪長進程的運行； ?時間片原則。一個時間片運行完后重新調(diào)度。 5． 3 ． 3 進程調(diào)度的時機 進程調(diào)度發(fā)生的時機，與引起進程調(diào)度的原因以及進程調(diào)度的方式有關。引起進程調(diào)度的原因有以下幾類： ?正在執(zhí)行的進程執(zhí)行完畢或由于某種錯誤而異常中止。 ?執(zhí)行中的進程自己調(diào)用阻塞原語將自己阻塞起來而進入等待狀態(tài)（如等待某一事件而事件未發(fā)生或調(diào)用了 wait原語而資源不足等）。 ?分時系統(tǒng)中的時間片用完。 ?在執(zhí)行完系統(tǒng)調(diào)用等系統(tǒng)程序后返回用戶進程時，這時可看作系統(tǒng)進程運行完畢，從而可選擇一新的用戶進程執(zhí)行。 5． 3 ． 3 進程調(diào)度的時機 ?在基于優(yōu)先級調(diào)度的策略時，就緒隊列中的某進程的優(yōu)先級變得高于當前運行進程的優(yōu)先級，從而也將引發(fā)進程調(diào)度。 以上 1～ 4條是在剝奪和不可剝奪情況下引起進程調(diào)度的原因，而第 5條是在剝奪情況下引起調(diào)度的原因。 5． 4 常用的調(diào)度算法 調(diào)度算法是指：根據(jù)系統(tǒng)的資源分配策略所規(guī)定的資源分配算法 。 對于不同的系統(tǒng)和系統(tǒng)目標 ，通常采用不同的調(diào)度算法 。 目前存在著多種調(diào)度算法 ， 有的算法適用于作業(yè)調(diào)度 ， 有的算法適用于進程調(diào)度 ， 但也有些調(diào)度算法 ， 既可用于作業(yè)調(diào)度 ，也可用于進程調(diào)度 。 5． 4 ． 1 先來先服務調(diào)度算法 ?實現(xiàn)方法： 先來先服務 FCFS（ First Come First Serve， FCFS）調(diào)度算法是一種最簡單的調(diào)度算法。其基本思想是：將用戶作業(yè)或就緒進程按提交或變?yōu)榫途w狀態(tài)的先后次序排成隊列，調(diào)度時總是選擇隊首作業(yè)或進程投入運行。該算法既可用于作業(yè)調(diào)度，也可用于進程調(diào)度。 ?優(yōu)缺點： 雖然 FCFS調(diào)度算法易于實現(xiàn)，表面上也公平，但服務質(zhì)量不佳，對短作業(yè)用戶不公平 。 ?使用場合： FCFS算法很少作為進程調(diào)度的主調(diào)度算法，但常作為一種輔助調(diào)度算法。 5． 4 ． 1 先來先服務調(diào)度算法 【 例 51】 假設有五道作業(yè)，它們的進入時間和運行時間由下表給出： 作業(yè)號 進入時間 運行時間 1 0 4 2 1 3 3 2 6 4 3 2 5 4 4 在不剝奪方式的單道環(huán)境下，采用 FCFS調(diào)度算法，試說明它們的調(diào)度順序，并計算在該種調(diào)度算法下的平均周轉(zhuǎn)時間和平均帶權周轉(zhuǎn)時間。 5． 4 ． 1 先來先服務調(diào)度算法 解：采用 FCFS調(diào)度算法，調(diào)度順序是 1， 2， 3， 4， 5 五道作業(yè)的執(zhí)行時間、完成時間和周轉(zhuǎn)時間如下表所示： 作業(yè) 號 進入時間 運行時間 1 0 4 2 1 3 3 2 6 4 3 2 5 4 4 作業(yè)號 進入時間 運行時間 開始執(zhí)行時間 完成時間 周轉(zhuǎn)時間 1 0 4 0 4 4 2 1 3 4 7 6 3 2 6 7 13 11 4 3 2 13 15 12 5 4 4 15 19 15 平均周轉(zhuǎn)時間 T＝（ 4+6+11+12+15） / 5= 平均帶權周轉(zhuǎn)時間 W=(4/4+6/3+11/6+12/2+15/4) / 5= 5． 4 ． 2 短作業(yè)（進程）優(yōu)先調(diào)度算法 ?實現(xiàn)方法： SJF調(diào)度算法是從后備隊列中選擇一個或若干個估計運行時間最短的作業(yè)，將它們調(diào)入內(nèi)存運行。該調(diào)度算法可以照顧到實際上在所有作業(yè)中占很大比例的短作業(yè)，使它們能比長作業(yè)優(yōu)先執(zhí)行。 ?優(yōu)缺點： 這種算法能有效地降低作業(yè)的平均周轉(zhuǎn)時間，提高系統(tǒng)的吞吐量，但是，它們存在著不容忽視的缺點： ?該算法對長作業(yè)不利。由于系統(tǒng)狀態(tài)是動態(tài)的，如果不斷地有短作業(yè)進入，則可能導致長作業(yè)長時間得不到響應； ?該算法未考慮作業(yè)的緊迫程度； 5． 4 ． 2 短作業(yè)（進程）優(yōu)先調(diào)度算法 ?由于作業(yè)（進程）的長短只是根據(jù)用戶所提供的估計運行時間而定，而用戶又可能會有意或無意地縮短其作業(yè)的估計執(zhí)行時間，致使該算法不一定能真正做到短作業(yè)優(yōu)先調(diào)度。 5． 4 ． 2 短作業(yè)（進程）優(yōu)先調(diào)度算法 【 例 52】 仍采用例 51的題目，在不剝奪方式的單道環(huán)境下，采用 SJF調(diào)度算法，試說明它們的調(diào)度順序，并計算在該種調(diào)度算法下的平均周轉(zhuǎn)時間和平均帶權周轉(zhuǎn)時間。 作業(yè)號 進入時間 運行時間 1 0 4 2 1 3 3 2 6 4 3 2 5 4 4 5． 4 ． 2 短作業(yè)（進程）優(yōu)先調(diào)度算法 解：采用 SJF調(diào)度算法，調(diào)度順序是 1， 4， 2， 5， 3 五道作業(yè)的執(zhí)行時間、完成時間和周轉(zhuǎn)時間如下表所示： 作業(yè)號 進入時間 運行時間 1 0 4 2 1 3 3 2 6 4