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