操作系統(tǒng)基礎(chǔ)03-1

1、Page 12021-10-18Page 22021-10-18q 處理機(jī)調(diào)度的基本概念處理機(jī)調(diào)度的基本概念 v處理機(jī)調(diào)度的目標(biāo)充分有效地利用處理機(jī)（CPU）資源q 調(diào)度算法調(diào)度算法 q 死鎖問題死鎖問題Page 32021-10-18q操作系統(tǒng)調(diào)度級別操作系統(tǒng)調(diào)度級別q進(jìn)程調(diào)度的任務(wù)進(jìn)程調(diào)度的任務(wù)q確定算法的原則確定算法的原則q進(jìn)程調(diào)度方式進(jìn)程調(diào)度方式Page 42021-10-183.1 處理機(jī)調(diào)度的基本概念處理機(jī)調(diào)度的基本概念 3.1.1 操作系統(tǒng)調(diào)度級別操作系統(tǒng)調(diào)度級別 1. 高級調(diào)度高級調(diào)度2. 低級調(diào)度低級調(diào)度3. 中級調(diào)度中級調(diào)度Page 52021-10-18q1.1.高級調(diào)度

2、高級調(diào)度 又稱又稱作業(yè)調(diào)度作業(yè)調(diào)度v主要任務(wù)是按一定的原則對外存上處于后備主要任務(wù)是按一定的原則對外存上處于后備狀態(tài)的作業(yè)進(jìn)行選擇，給選中的作業(yè)狀態(tài)的作業(yè)進(jìn)行選擇，給選中的作業(yè)分配分配內(nèi)內(nèi)存、輸入存、輸入/ /輸出設(shè)備等輸出設(shè)備等必要的資源必要的資源，并，并建立建立相相應(yīng)的應(yīng)的進(jìn)程進(jìn)程，插插入入就緒就緒隊列隊列，以使該作業(yè)的進(jìn)，以使該作業(yè)的進(jìn)程獲得競爭處理機(jī)的權(quán)利程獲得競爭處理機(jī)的權(quán)利Page 62021-10-18運行狀態(tài)運行狀態(tài)后備狀態(tài)后備狀態(tài)完成狀態(tài)完成狀態(tài)就緒就緒阻塞阻塞執(zhí)行執(zhí)行I/O完成完成I/O請求請求時間片完時間片完作業(yè)作業(yè)提交提交作業(yè)作業(yè)調(diào)度調(diào)度進(jìn)程進(jìn)程調(diào)度調(diào)度終止終止作業(yè)作業(yè)

3、q作業(yè)作業(yè)狀態(tài)間轉(zhuǎn)換狀態(tài)間轉(zhuǎn)換圖圖3-1 作業(yè)的基本狀態(tài)作業(yè)的基本狀態(tài) （1） 提交狀態(tài)提交狀態(tài)即用戶向系統(tǒng)提交一個作業(yè)時，即用戶向系統(tǒng)提交一個作業(yè)時， 該作業(yè)所處的狀態(tài)。該作業(yè)所處的狀態(tài)。 （2） 后備狀態(tài)后備狀態(tài)即用戶作業(yè)經(jīng)輸入設(shè)備（如讀卡機(jī)）即用戶作業(yè)經(jīng)輸入設(shè)備（如讀卡機(jī)）送入輸入井（磁盤）中存放，送入輸入井（磁盤）中存放， 等待進(jìn)入內(nèi)存時所處的等待進(jìn)入內(nèi)存時所處的狀況。狀況。 （3） 執(zhí)行狀態(tài)執(zhí)行狀態(tài)即作業(yè)分配到所需的資源，即作業(yè)分配到所需的資源， 被調(diào)被調(diào)入內(nèi)存，入內(nèi)存， 并且在處理機(jī)（并且在處理機(jī)（CPU）上執(zhí)行相應(yīng)的程序時）上執(zhí)行相應(yīng)的程序時所處的狀況。所處的狀況。 （4） 完成

4、狀態(tài)完成狀態(tài)即作業(yè)完成了計算任務(wù)，即作業(yè)完成了計算任務(wù)， 結(jié)果由結(jié)果由打印機(jī)輸出，打印機(jī)輸出， 最后由系統(tǒng)回收分配給它的全部資源，最后由系統(tǒng)回收分配給它的全部資源， 準(zhǔn)備退出系統(tǒng)時的作業(yè)狀況。準(zhǔn)備退出系統(tǒng)時的作業(yè)狀況。作業(yè)狀態(tài)作業(yè)狀態(tài)q 作業(yè)控制塊作業(yè)控制塊（JCB）q 在多道批處理系統(tǒng)中通常有上百個作業(yè)被收在多道批處理系統(tǒng)中通常有上百個作業(yè)被收容在容在輸入井輸入井（磁盤）中。（磁盤）中。 為了管理和調(diào)度作為了管理和調(diào)度作業(yè)，業(yè)， 系統(tǒng)為每個作業(yè)設(shè)置了一個作業(yè)控制塊系統(tǒng)為每個作業(yè)設(shè)置了一個作業(yè)控制塊（JCB），）， 它記錄該作業(yè)的有關(guān)信息。它記錄該作業(yè)的有關(guān)信息。 JCB的的主要內(nèi)容如圖主要內(nèi)

5、容如圖3-2所示。所示。圖3-2 作業(yè)控制塊 Page 102021-10-182.2.中級調(diào)度中級調(diào)度v目的：是目的：是為了提高內(nèi)存利用率和系統(tǒng)吞吐量為了提高內(nèi)存利用率和系統(tǒng)吞吐量。q功能功能： 暫時不能運行的暫時不能運行的進(jìn)程掛起進(jìn)程掛起，釋放寶貴的內(nèi)存資源。，釋放寶貴的內(nèi)存資源。 具備條件時：把外存上的就緒進(jìn)程，重新調(diào)入內(nèi)存，掛在就緒具備條件時：把外存上的就緒進(jìn)程，重新調(diào)入內(nèi)存，掛在就緒隊列上等待進(jìn)程調(diào)度。隊列上等待進(jìn)程調(diào)度。 Page 112021-10-183.3.低級調(diào)度低級調(diào)度 進(jìn)程調(diào)度進(jìn)程調(diào)度v主要任務(wù)是按照某種主要任務(wù)是按照某種策略和方法策略和方法選取選取一個處于一個處于就緒

6、就緒狀態(tài)的進(jìn)程，將處理機(jī)狀態(tài)的進(jìn)程，將處理機(jī)分配分配給它給它v常見的低級調(diào)度有常見的低級調(diào)度有非搶占式非搶占式和和搶占式搶占式兩種兩種Page 122021-10-18Page 132021-10-18q 高級、中級和低級調(diào)度高級、中級和低級調(diào)度q 進(jìn)程調(diào)度的任務(wù)進(jìn)程調(diào)度的任務(wù)q 確定算法的原則確定算法的原則q 進(jìn)程調(diào)度方式進(jìn)程調(diào)度方式Page 142021-10-18q 進(jìn)程調(diào)度的任務(wù)進(jìn)程調(diào)度的任務(wù) 是是控制、協(xié)調(diào)進(jìn)程控制、協(xié)調(diào)進(jìn)程對對CPUCPU的競爭的競爭, ,即按一定的即按一定的調(diào)度算法從就緒隊列中選中一個進(jìn)程，把調(diào)度算法從就緒隊列中選中一個進(jìn)程，把CPUCPU的的使用權(quán)交給被選中的進(jìn)

7、程使用權(quán)交給被選中的進(jìn)程Page 152021-10-18q 高級、中級和低級調(diào)度高級、中級和低級調(diào)度q 進(jìn)程調(diào)度的任務(wù)進(jìn)程調(diào)度的任務(wù)q 確定算法的原則確定算法的原則q 進(jìn)程調(diào)度方式進(jìn)程調(diào)度方式q 調(diào)度隊列模型調(diào)度隊列模型q 選擇調(diào)度方式和調(diào)度算法的若干準(zhǔn)則選擇調(diào)度方式和調(diào)度算法的若干準(zhǔn)則Page 162021-10-18q 具有具有公平性公平性q 資源資源利用率高利用率高（特別是（特別是CPUCPU利用率）利用率）q 在交互式系統(tǒng)情況下要追求在交互式系統(tǒng)情況下要追求響應(yīng)時間響應(yīng)時間（越短越好）（越短越好）q 在批處理系統(tǒng)情況下要追求系統(tǒng)在批處理系統(tǒng)情況下要追求系統(tǒng)吞吐量吞吐量Page 172

8、021-10-18q 高級、中級和低級調(diào)度高級、中級和低級調(diào)度q 進(jìn)程調(diào)度的任務(wù)進(jìn)程調(diào)度的任務(wù)q 確定算法的原則確定算法的原則q 進(jìn)程調(diào)度方式進(jìn)程調(diào)度方式Page 182021-10-18q 非搶占方式非搶占方式q 搶占方式搶占方式Page 192021-10-18q 非搶占方式非搶占方式(Non-preemptive Mode)(Non-preemptive Mode) 引起進(jìn)程調(diào)度的因素引起進(jìn)程調(diào)度的因素正在執(zhí)行的進(jìn)程執(zhí)行完畢，正在執(zhí)行的進(jìn)程執(zhí)行完畢， 或因發(fā)生某事或因發(fā)生某事件而不能再繼續(xù)執(zhí)行件而不能再繼續(xù)執(zhí)行執(zhí)行中的進(jìn)程因提出執(zhí)行中的進(jìn)程因提出I/OI/O請求而暫停執(zhí)行；請求而暫停執(zhí)行

9、；在進(jìn)程通信或同步過程中執(zhí)行了某種原語在進(jìn)程通信或同步過程中執(zhí)行了某種原語操作，如操作，如waitwait、BlockBlock、WakeupWakeup原語原語優(yōu)點優(yōu)點：算法簡單，：算法簡單，系統(tǒng)開銷小系統(tǒng)開銷小缺點缺點：緊急任務(wù)不：緊急任務(wù)不能及時響應(yīng)；短進(jìn)能及時響應(yīng)；短進(jìn)程到達(dá)要等待長進(jìn)程到達(dá)要等待長進(jìn)程運行結(jié)束程運行結(jié)束Page 202021-10-18q 搶占方式搶占方式q 搶占式調(diào)度主要有以下原則搶占式調(diào)度主要有以下原則優(yōu)先權(quán)原則優(yōu)先權(quán)原則 允許高優(yōu)先權(quán)的新到進(jìn)程搶允許高優(yōu)先權(quán)的新到進(jìn)程搶占當(dāng)前進(jìn)程的處理機(jī)占當(dāng)前進(jìn)程的處理機(jī)短作業(yè)短作業(yè)( (進(jìn)程進(jìn)程) )優(yōu)先原則優(yōu)先原則允許執(zhí)行時

10、間短允許執(zhí)行時間短的新到進(jìn)程搶占當(dāng)前進(jìn)程的處理機(jī)的新到進(jìn)程搶占當(dāng)前進(jìn)程的處理機(jī) 時間片原則時間片原則 時間片用完后停止執(zhí)行，時間片用完后停止執(zhí)行，重新進(jìn)行調(diào)度，適用于分時系統(tǒng)重新進(jìn)行調(diào)度，適用于分時系統(tǒng) 優(yōu)點優(yōu)點：適于時間要：適于時間要求嚴(yán)格的實時系統(tǒng)求嚴(yán)格的實時系統(tǒng)缺點缺點：調(diào)度算法復(fù)：調(diào)度算法復(fù)雜，系統(tǒng)開銷大雜，系統(tǒng)開銷大Page 212021-10-18q 算法性能衡量算法性能衡量v周轉(zhuǎn)時間短周轉(zhuǎn)時間短平均周轉(zhuǎn)時間平均周轉(zhuǎn)時間niiTnT11niSiiTTnW11帶權(quán)周轉(zhuǎn)時間：帶權(quán)周轉(zhuǎn)時間：進(jìn)程（或作業(yè)）的進(jìn)程（或作業(yè)）的周轉(zhuǎn)時周轉(zhuǎn)時間間T T與系統(tǒng)為它與系統(tǒng)為它提供服務(wù)的時間提供服務(wù)的

11、時間T TS S之比，即之比，即W=T/TW=T/TS S 。而。而平均帶權(quán)周轉(zhuǎn)時間平均帶權(quán)周轉(zhuǎn)時間則可表示為則可表示為: : Page 222021-10-18 通常把通常把周轉(zhuǎn)時間周轉(zhuǎn)時間作為評價批處理系統(tǒng)的性能、選擇作業(yè)作為評價批處理系統(tǒng)的性能、選擇作業(yè)調(diào)度方式與算法的準(zhǔn)則。調(diào)度方式與算法的準(zhǔn)則。 所謂所謂周轉(zhuǎn)時間周轉(zhuǎn)時間，是指從是指從作業(yè)作業(yè)提交給系統(tǒng)開始，到作業(yè)完提交給系統(tǒng)開始，到作業(yè)完成為止的這段時間間隔成為止的這段時間間隔( (稱為作業(yè)周轉(zhuǎn)時間稱為作業(yè)周轉(zhuǎn)時間) )。Page 232021-10-18可把平均周轉(zhuǎn)時間描述為可把平均周轉(zhuǎn)時間描述為： iiiTnT11niSiiTTn

12、W11 作業(yè)的周轉(zhuǎn)時間作業(yè)的周轉(zhuǎn)時間T與系統(tǒng)為它提供服務(wù)的時間與系統(tǒng)為它提供服務(wù)的時間TS之比，之比，即即W=T/TS，稱為，稱為帶權(quán)帶權(quán)周轉(zhuǎn)時間周轉(zhuǎn)時間，而，而平均帶權(quán)周轉(zhuǎn)時間平均帶權(quán)周轉(zhuǎn)時間則則可表示為可表示為: 系統(tǒng)以多個用戶都滿意為目標(biāo)系統(tǒng)以多個用戶都滿意為目標(biāo)周轉(zhuǎn)時間服務(wù)時間周轉(zhuǎn)時間服務(wù)時間周轉(zhuǎn)時間完成時間到達(dá)時間周轉(zhuǎn)時間完成時間到達(dá)時間Page 242021-10-18q處理機(jī)調(diào)度的基本概念處理機(jī)調(diào)度的基本概念 q調(diào)度算法調(diào)度算法 q死鎖問題死鎖問題Page 252021-10-18q 先來先服務(wù)和短作業(yè)優(yōu)先算法先來先服務(wù)和短作業(yè)優(yōu)先算法q 高優(yōu)先權(quán)優(yōu)先調(diào)度算法高優(yōu)先權(quán)優(yōu)先調(diào)度算法

13、q 基于時間片的輪轉(zhuǎn)調(diào)度算法基于時間片的輪轉(zhuǎn)調(diào)度算法Page 262021-10-18q 先來先服務(wù)先來先服務(wù)(FCFS)/先進(jìn)先出先進(jìn)先出(FIFO)調(diào)度算法調(diào)度算法v按照作業(yè)按照作業(yè)/進(jìn)程進(jìn)入系統(tǒng)的進(jìn)程進(jìn)入系統(tǒng)的先后次序先后次序進(jìn)行調(diào)度，進(jìn)行調(diào)度，先進(jìn)入系統(tǒng)者先調(diào)度；即啟動等待時間最長先進(jìn)入系統(tǒng)者先調(diào)度；即啟動等待時間最長的作業(yè)的作業(yè)/進(jìn)程進(jìn)程v是一種最簡單的調(diào)度算法，即可用于是一種最簡單的調(diào)度算法，即可用于作業(yè)調(diào)作業(yè)調(diào)度度，也可用于，也可用于進(jìn)程調(diào)度進(jìn)程調(diào)度q 幾個術(shù)語幾個術(shù)語v到達(dá)時間、服務(wù)時間、開始時間到達(dá)時間、服務(wù)時間、開始時間v完成時間、等待時間完成時間、等待時間v周轉(zhuǎn)時間：完成

14、時間周轉(zhuǎn)時間：完成時間-到達(dá)時間到達(dá)時間v帶權(quán)周轉(zhuǎn)時間：周轉(zhuǎn)時間帶權(quán)周轉(zhuǎn)時間：周轉(zhuǎn)時間/服務(wù)時間服務(wù)時間Page 272021-10-18進(jìn)程名進(jìn)程名到達(dá)時間到達(dá)時間 服務(wù)時間服務(wù)時間 開始時間開始時間 完成時間完成時間 周轉(zhuǎn)時間周轉(zhuǎn)時間帶權(quán)周帶權(quán)周轉(zhuǎn)時間轉(zhuǎn)時間平均平均04A13B25C32D44E044476先來先服務(wù)（先進(jìn)先出）：先來先服務(wù)（先進(jìn)先出）：712101214111418141225.53.592.8A A A A B B B C C C C C D D E E E E05101518tPage 282021-10-18q短作業(yè)短作業(yè)( (進(jìn)程進(jìn)程) )優(yōu)先調(diào)度算法優(yōu)先調(diào)度算法

15、SJ(P)FSJ(P)Fv短作業(yè)短作業(yè)( (進(jìn)程進(jìn)程) )優(yōu)先調(diào)度算法優(yōu)先調(diào)度算法SJ(P)FSJ(P)F，以要求以要求運運行時間長短行時間長短進(jìn)行調(diào)度，即啟動要求運行時間最進(jìn)行調(diào)度，即啟動要求運行時間最短的作業(yè)短的作業(yè)v可以分別用于可以分別用于作業(yè)調(diào)度作業(yè)調(diào)度和和進(jìn)程調(diào)度進(jìn)程調(diào)度Page 292021-10-18進(jìn)程名進(jìn)程名到達(dá)時間到達(dá)時間 服務(wù)時間服務(wù)時間 開始時間開始時間 完成時間完成時間 周轉(zhuǎn)時間周轉(zhuǎn)時間帶權(quán)周帶權(quán)周轉(zhuǎn)時間轉(zhuǎn)時間平均平均04A13B25C32D44E0441短作業(yè)短作業(yè)/短進(jìn)程優(yōu)先（短進(jìn)程優(yōu)先（SJF/SPF）：）：4633/26988/391399/413181616

16、/540/52.1A A A AB B BC C C C CD DE E E E05101518tPage 302021-10-18qFCFS/SJF調(diào)度算法的性能調(diào)度算法的性能 作業(yè)作業(yè)調(diào)度調(diào)度 情況情況 算法算法進(jìn)程名進(jìn)程名ABCDE平均平均到達(dá)時間到達(dá)時間01234服務(wù)時間服務(wù)時間43524FCFS完成時間完成時間47121418周轉(zhuǎn)時間周轉(zhuǎn)時間461011149帶權(quán)周轉(zhuǎn)時間帶權(quán)周轉(zhuǎn)時間1225.53.52.8SJF完成時間完成時間4918613周轉(zhuǎn)時間周轉(zhuǎn)時間4816398帶權(quán)周轉(zhuǎn)時間帶權(quán)周轉(zhuǎn)時間12.673.11.52.252.1SJFSJF平均周轉(zhuǎn)平均周轉(zhuǎn)時間和平均帶時間和平均帶權(quán)

17、周轉(zhuǎn)時間明權(quán)周轉(zhuǎn)時間明顯改善顯改善Page 312021-10-18q先來先服務(wù)和短作業(yè)優(yōu)先算法先來先服務(wù)和短作業(yè)優(yōu)先算法q高優(yōu)先權(quán)優(yōu)先調(diào)度算法高優(yōu)先權(quán)優(yōu)先調(diào)度算法q基于時間片的輪轉(zhuǎn)調(diào)度算法基于時間片的輪轉(zhuǎn)調(diào)度算法Page 322021-10-18q優(yōu)先權(quán)調(diào)度算法的類型優(yōu)先權(quán)調(diào)度算法的類型v非搶占式非搶占式優(yōu)先權(quán)調(diào)度算法優(yōu)先權(quán)調(diào)度算法v搶占式搶占式優(yōu)先權(quán)調(diào)度算法優(yōu)先權(quán)調(diào)度算法Page 332021-10-18q優(yōu)先權(quán)調(diào)度算法的類型優(yōu)先權(quán)調(diào)度算法的類型v非搶占式非搶占式優(yōu)先權(quán)調(diào)度算法優(yōu)先權(quán)調(diào)度算法特點：系統(tǒng)一旦把處理機(jī)分配給就緒隊特點：系統(tǒng)一旦把處理機(jī)分配給就緒隊列中列中優(yōu)先權(quán)最高優(yōu)先權(quán)最高的進(jìn)

18、程后，該進(jìn)程便的進(jìn)程后，該進(jìn)程便一一直執(zhí)行直執(zhí)行下去，直至完成，或因發(fā)生某事下去，直至完成，或因發(fā)生某事件使該進(jìn)程放棄處理機(jī)時，系統(tǒng)才將處件使該進(jìn)程放棄處理機(jī)時，系統(tǒng)才將處理機(jī)重新分配給另一優(yōu)先權(quán)最高的進(jìn)程理機(jī)重新分配給另一優(yōu)先權(quán)最高的進(jìn)程主要主要用于批處理系統(tǒng)用于批處理系統(tǒng)中，也可用于某些中，也可用于某些對對實時性實時性要求不嚴(yán)的實時系統(tǒng)要求不嚴(yán)的實時系統(tǒng)中中Page 342021-10-18q優(yōu)先權(quán)調(diào)度算法的類型優(yōu)先權(quán)調(diào)度算法的類型v搶占式搶占式優(yōu)先權(quán)調(diào)度算法優(yōu)先權(quán)調(diào)度算法把處理機(jī)分配給優(yōu)先權(quán)最高的進(jìn)程，但在執(zhí)行把處理機(jī)分配給優(yōu)先權(quán)最高的進(jìn)程，但在執(zhí)行期間，只要出現(xiàn)另一個優(yōu)先權(quán)更高的進(jìn)程，

19、則期間，只要出現(xiàn)另一個優(yōu)先權(quán)更高的進(jìn)程，則進(jìn)程調(diào)度程序就進(jìn)程調(diào)度程序就立即停止立即停止當(dāng)前進(jìn)程的執(zhí)行，并當(dāng)前進(jìn)程的執(zhí)行，并將處理機(jī)分配給新到的優(yōu)先權(quán)最高的進(jìn)程將處理機(jī)分配給新到的優(yōu)先權(quán)最高的進(jìn)程注意注意：只要只要系統(tǒng)中系統(tǒng)中出現(xiàn)出現(xiàn)一個新的就緒進(jìn)程，一個新的就緒進(jìn)程，就就進(jìn)行進(jìn)行優(yōu)先權(quán)優(yōu)先權(quán)比較比較該調(diào)度算法，能更好地該調(diào)度算法，能更好地滿足緊迫作業(yè)滿足緊迫作業(yè)的要求，的要求，故而常用于故而常用于要求比較嚴(yán)格的實時系統(tǒng)中，以及要求比較嚴(yán)格的實時系統(tǒng)中，以及對性能要求較高的批處理和分時系統(tǒng)中對性能要求較高的批處理和分時系統(tǒng)中Page 352021-10-18q優(yōu)先權(quán)的類型優(yōu)先權(quán)的類型v靜態(tài)優(yōu)先權(quán)

20、靜態(tài)優(yōu)先權(quán)v動態(tài)優(yōu)先權(quán)動態(tài)優(yōu)先權(quán)Page 362021-10-18q優(yōu)先權(quán)的類型優(yōu)先權(quán)的類型v靜態(tài)優(yōu)先權(quán)靜態(tài)優(yōu)先權(quán)靜態(tài)優(yōu)先權(quán)在創(chuàng)建進(jìn)程時確定，且在進(jìn)程的整個靜態(tài)優(yōu)先權(quán)在創(chuàng)建進(jìn)程時確定，且在進(jìn)程的整個運行期間運行期間保持不變保持不變。一般地，優(yōu)先權(quán)是利用某一。一般地，優(yōu)先權(quán)是利用某一范圍內(nèi)的一個整數(shù)來表示的，例如，范圍內(nèi)的一個整數(shù)來表示的，例如，0 0 7 7或或0 0 255255， 又把該整數(shù)稱為又把該整數(shù)稱為優(yōu)先數(shù)優(yōu)先數(shù)v確定進(jìn)程靜態(tài)優(yōu)先權(quán)的依據(jù)確定進(jìn)程靜態(tài)優(yōu)先權(quán)的依據(jù)進(jìn)程類型進(jìn)程類型: :系統(tǒng)進(jìn)程，用戶進(jìn)程系統(tǒng)進(jìn)程，用戶進(jìn)程進(jìn)程對資源的需求進(jìn)程對資源的需求( (對對CPUCPU和內(nèi)存需求

21、較少的進(jìn)程，和內(nèi)存需求較少的進(jìn)程，優(yōu)先級較高優(yōu)先級較高) )用戶要求用戶要求（緊迫程度和付費多少）（緊迫程度和付費多少）Page 372021-10-18v動態(tài)優(yōu)先權(quán)動態(tài)優(yōu)先權(quán)在在創(chuàng)建進(jìn)程創(chuàng)建進(jìn)程時賦予的優(yōu)先級，在進(jìn)程時賦予的優(yōu)先級，在進(jìn)程運行過程中可運行過程中可以自動改變以自動改變，以便獲得更好的調(diào)度性能。，以便獲得更好的調(diào)度性能?？梢?guī)定，在可規(guī)定，在就緒隊列中的進(jìn)程就緒隊列中的進(jìn)程，隨其，隨其等待時間的增等待時間的增長長，其優(yōu)先權(quán)，其優(yōu)先權(quán)以速率以速率a提高提高具有具有相同相同優(yōu)先權(quán)優(yōu)先權(quán)初值初值的進(jìn)程，則的進(jìn)程，則最先進(jìn)入最先進(jìn)入就緒就緒隊列，其將因其動態(tài)優(yōu)先權(quán)變得最高而隊列，其將因其動

22、態(tài)優(yōu)先權(quán)變得最高而優(yōu)先獲優(yōu)先獲得得處理機(jī)，此即處理機(jī)，此即FCFS算法算法具有各不相同的優(yōu)先權(quán)初值的就緒進(jìn)程，則具有各不相同的優(yōu)先權(quán)初值的就緒進(jìn)程，則優(yōu)優(yōu)先權(quán)初值低先權(quán)初值低的進(jìn)程，在的進(jìn)程，在等待了足夠的時間等待了足夠的時間后，后，其其優(yōu)先權(quán)便可能升為最高優(yōu)先權(quán)便可能升為最高，從而可以獲得處理，從而可以獲得處理機(jī)機(jī)當(dāng)采用搶占式優(yōu)先權(quán)調(diào)度算法時，如果再當(dāng)采用搶占式優(yōu)先權(quán)調(diào)度算法時，如果再規(guī)定當(dāng)前規(guī)定當(dāng)前進(jìn)程進(jìn)程的優(yōu)先權(quán)的優(yōu)先權(quán)以速率以速率b下降下降，則可防止一個長作業(yè)，則可防止一個長作業(yè)長期地長期地壟斷壟斷處理機(jī)處理機(jī)Page 382021-10-18進(jìn)程進(jìn)程名名到達(dá)到達(dá)時間時間服務(wù)服務(wù)時間時

23、間靜態(tài)優(yōu)靜態(tài)優(yōu)先權(quán)先權(quán)開始開始時間時間完成完成時間時間周轉(zhuǎn)周轉(zhuǎn)時間時間帶權(quán)周帶權(quán)周轉(zhuǎn)時間轉(zhuǎn)時間平均平均靜態(tài)優(yōu)先權(quán)，靜態(tài)優(yōu)先權(quán)，非搶占式非搶占式（1為高優(yōu)先權(quán)）為高優(yōu)先權(quán)）04A413B225C332D544E1044148418111010/311161414/516181515/29.42.93考慮一下考慮一下?lián)屨际綋屨际?，情況如何？，情況如何？Page 392021-10-18q高響應(yīng)比優(yōu)先調(diào)度算法（高響應(yīng)比優(yōu)先調(diào)度算法（HRF）v是是FCFS和和SJF的結(jié)合，克服了兩種算法的缺點的結(jié)合，克服了兩種算法的缺點v v 性能分析性能分析:p如果作業(yè)的等待時間相同，則要求執(zhí)行的時間愈短，如果作業(yè)

24、的等待時間相同，則要求執(zhí)行的時間愈短， 則則響應(yīng)比高，故有利于短作業(yè)；響應(yīng)比高，故有利于短作業(yè)；q當(dāng)要求執(zhí)行的時間相同時，響應(yīng)比決定于其等待時間，當(dāng)要求執(zhí)行的時間相同時，響應(yīng)比決定于其等待時間，因而實現(xiàn)了先來先服務(wù)；因而實現(xiàn)了先來先服務(wù)；q對于長作業(yè)，當(dāng)其等待時間足夠長時，其響應(yīng)比便可升對于長作業(yè)，當(dāng)其等待時間足夠長時，其響應(yīng)比便可升到很高，也可獲得處理機(jī)。到很高，也可獲得處理機(jī)。 響應(yīng)比響應(yīng)比Rp定義如下：定義如下： Rp=作業(yè)響應(yīng)時間作業(yè)響應(yīng)時間tR /要求執(zhí)行的時間要求執(zhí)行的時間Page 402021-10-18q先來先服務(wù)和短作業(yè)優(yōu)先算法先來先服務(wù)和短作業(yè)優(yōu)先算法q高優(yōu)先權(quán)優(yōu)先調(diào)度算法

25、高優(yōu)先權(quán)優(yōu)先調(diào)度算法q基于時間片的輪轉(zhuǎn)調(diào)度算法基于時間片的輪轉(zhuǎn)調(diào)度算法Page 412021-10-18q 簡單的時間片輪轉(zhuǎn)法簡單的時間片輪轉(zhuǎn)法(RRRound Robin)將系統(tǒng)中所有的就緒進(jìn)程按照FCFS原則，排成一個隊列；l 每次調(diào)度時將CPU分派給隊首進(jìn)程，讓其執(zhí)行一個時間片。時間片的長度從幾個ms到幾百ms；l 在一個時間片結(jié)束時，發(fā)生時鐘中斷；l 調(diào)度程序據(jù)此暫停當(dāng)前進(jìn)程的執(zhí)行，將其送到就緒隊列的末尾，并通過上下文切換執(zhí)行當(dāng)前的隊首進(jìn)程；l 進(jìn)程可以未使用完一個時間片，就出讓CPU（如阻塞）。優(yōu)點：公平。保證就緒隊列中所有進(jìn)程在一給定的優(yōu)點：公平。保證就緒隊列中所有進(jìn)程在一給定的時

26、間內(nèi)，均能獲得一時間片的處理機(jī)執(zhí)行時間時間內(nèi)，均能獲得一時間片的處理機(jī)執(zhí)行時間缺點：緊迫任務(wù)響應(yīng)慢。缺點：緊迫任務(wù)響應(yīng)慢。UNIX中采用：時間片中采用：時間片+優(yōu)先權(quán)優(yōu)先權(quán)Page 422021-10-18進(jìn)程名進(jìn)程名到達(dá)時間到達(dá)時間 服務(wù)時間服務(wù)時間 開始時間開始時間 完成時間完成時間 周轉(zhuǎn)時間周轉(zhuǎn)時間帶權(quán)周帶權(quán)周轉(zhuǎn)時間轉(zhuǎn)時間平均平均A B C D E A B C D E A B C E A C E C05101518t04A03B05C02D04E012349121517181515/41111/31616/566/21313/412.22.12若到達(dá)時間若到達(dá)時間為為0 0、1 1、2

27、2、3 3、4 4，又如，又如何？何？Page 432021-10-183.2.3 基于時間片的輪轉(zhuǎn)調(diào)度算法基于時間片的輪轉(zhuǎn)調(diào)度算法 q時間片長度變化的影響v過長退化為FCFS算法，進(jìn)程在一個時間片內(nèi)都執(zhí)行完，響應(yīng)時間長。v過短用戶的一次請求需要多個時間片才能處理完，上下文切換次數(shù)增加，響應(yīng)時間長。q對響應(yīng)時間的要求：vR(響應(yīng)時間)=Nmax(進(jìn)程數(shù)目)*q(時間片)q時間片長度的影響因素：v就緒進(jìn)程的數(shù)目：數(shù)目越多，時間片越?。ó?dāng)響應(yīng)時間一定時）v系統(tǒng)的處理能力：應(yīng)當(dāng)使用戶輸入通常在一個時間片內(nèi)能處理完，否則使響應(yīng)時間，平均周轉(zhuǎn)時間和平均帶權(quán)周轉(zhuǎn)時間延長。Page 442021-10-18

28、進(jìn)程調(diào)度要解決的問題WHAT：按什么原則分配CPU 進(jìn)程調(diào)度算法WHEN：何時分配CPU 進(jìn)程調(diào)度的時機(jī)HOW： 如何分配CPU CPU調(diào)度過程（進(jìn)程的上下文切換）Page 452021-10-18q當(dāng)一個進(jìn)程當(dāng)一個進(jìn)程運行完畢運行完畢或由于某種錯誤而終止運或由于某種錯誤而終止運行行q當(dāng)一個進(jìn)程在運行中處于當(dāng)一個進(jìn)程在運行中處于等待等待狀態(tài)（等待狀態(tài)（等待I/OI/O）q分時系統(tǒng)中分時系統(tǒng)中時間片到時間片到q當(dāng)有一個當(dāng)有一個優(yōu)先級更高優(yōu)先級更高的進(jìn)程就緒（可搶占式）的進(jìn)程就緒（可搶占式） 例如：新創(chuàng)建一個進(jìn)程，一個阻塞進(jìn)程變成就例如：新創(chuàng)建一個進(jìn)程，一個阻塞進(jìn)程變成就緒緒q在進(jìn)程通信中，執(zhí)行中

29、的進(jìn)程執(zhí)行了某種原語在進(jìn)程通信中，執(zhí)行中的進(jìn)程執(zhí)行了某種原語操作（操作（P P操作，阻塞原語，喚醒原語）操作，阻塞原語，喚醒原語）Page 462021-10-18* 保存現(xiàn)場保存現(xiàn)場：順序保存，最后一步保存：順序保存，最后一步保存PSW* 選擇要運行的程序選擇要運行的程序 （如果沒有就緒進(jìn)程（如果沒有就緒進(jìn)程,系統(tǒng)會安排一個系統(tǒng)會安排一個閑逛閑逛進(jìn)程進(jìn)程(idle)，沒有其他進(jìn)程時該進(jìn)程一直沒有其他進(jìn)程時該進(jìn)程一直運行運行,在執(zhí)行過程中可接收中斷）在執(zhí)行過程中可接收中斷）* 恢復(fù)現(xiàn)場：恢復(fù)現(xiàn)場：最后一步恢復(fù)選中進(jìn)程的最后一步恢復(fù)選中進(jìn)程的PSWCPU調(diào)度過程調(diào)度過程Page 472021-1

30、0-18 假如有4道作業(yè)，它們的提交時間及運行時間如下表所示：采用單道運行，試問下述調(diào)度算法下，它們的調(diào)度順序，并分別計算各調(diào)度算法下三個作業(yè)的平均周轉(zhuǎn)時間 T 和平均帶權(quán)周轉(zhuǎn)時間 W。（1）FCFS（先來先服務(wù)）（2）SJF（短作業(yè)優(yōu)先）（3）HRF（響應(yīng)比高者優(yōu)先） n n T=1/N（Ti）,Ti=結(jié)束時刻結(jié)束時刻-提交時刻提交時刻; W=1/N（Wi）, Wi= Ti /作業(yè)作業(yè) i 實際執(zhí)行時間實際執(zhí)行時間 i=1 i=1作業(yè)號作業(yè)號提交時刻提交時刻運行時間（分鐘）運行時間（分鐘）18：0012028：303039：00649：3012Page 482021-10-18（1）FCFS

31、：調(diào)度順序為1 2 3 4q T=1/4（120+120+96+78）=103.5分鐘q W=1/4（1+4+16+6.5）=6.875作業(yè)號作業(yè)號到達(dá)時刻到達(dá)時刻要求運行時間要求運行時間（分鐘）（分鐘）結(jié)束時刻結(jié)束時刻周轉(zhuǎn)時間周轉(zhuǎn)時間Ti（分鐘）分鐘）帶權(quán)周轉(zhuǎn)時間帶權(quán)周轉(zhuǎn)時間Wi18：0012010：00120128：303010：30120439：00610：36961649：301210：48786.5Page 492021-10-18（2）SJF(SPF)：調(diào)度順序為1 3 4 2q T=1/4（120+66+48+138）=93分鐘q W=1/4（1+11+4+4.6）=5.15作業(yè)

32、號作業(yè)號到達(dá)時刻到達(dá)時刻要求運行時間要求運行時間（分鐘）（分鐘）結(jié)束時刻結(jié)束時刻周轉(zhuǎn)時間周轉(zhuǎn)時間Ti（分鐘）分鐘）帶權(quán)周轉(zhuǎn)時間帶權(quán)周轉(zhuǎn)時間Wi18：0012010：00120139：00610：06661149：301210：1848428：303010：481384.6Page 502021-10-18q （3）HRFq 作業(yè)1最先到達(dá)并運行，當(dāng)作業(yè) 1 完成時（10：00），作業(yè) 2、3、4都到達(dá)，則計算它們的響應(yīng)比：作業(yè)2響應(yīng)比=（90+30）/30=4作業(yè)3響應(yīng)比=（60+6）/6=11作業(yè)4響應(yīng)比=（30+12）/12=3.5由于作業(yè)3的響應(yīng)比最高，所以作業(yè)3先運行。q 當(dāng)作業(yè)3完成

33、時（10：06），計算作業(yè)2、4的響應(yīng)比：作業(yè)2響應(yīng)比=（96+30）/30=4.2作業(yè)4響應(yīng)比=（36+12）/12=4由于作業(yè)2的響應(yīng)比大于作業(yè)4，所以接著作業(yè)2運行；最后由作業(yè)4運行。 Page 512021-10-18（3）HRF：調(diào)度順序為1 3 2 4q T=1/4（120+66+126+78）=97.5分鐘q W=1/4（1+11+4.2+6.5）=5.675作業(yè)號作業(yè)號到達(dá)時刻到達(dá)時刻要求運行時間要求運行時間（分鐘）（分鐘）結(jié)束時刻結(jié)束時刻周轉(zhuǎn)時間周轉(zhuǎn)時間Ti（分鐘）分鐘）帶權(quán)周轉(zhuǎn)時間帶權(quán)周轉(zhuǎn)時間Wi18：0012010：00120139：00610：06661128：3030

34、10：361264.249：301210：48786.5Page 522021-10-18（1）先來先服務(wù)算法（FCFS：First Come First Serve）（2）最短作業(yè)優(yōu)先算法 （SJF：Shortest Job First）（3）最高響應(yīng)比優(yōu)先算法 （HRN：Highest Response Ratio Next）（4）基于優(yōu)先數(shù)調(diào)度算法 （HPF：Highest Priority First） Page 532021-10-18q產(chǎn)生死鎖的原因q死鎖的預(yù)防q死鎖的避免q死鎖的檢測與恢復(fù)Page 542021-10-18Page 552021-10-18 早期的操作系統(tǒng)對申請某

35、種資源的進(jìn)程，若早期的操作系統(tǒng)對申請某種資源的進(jìn)程，若該資源尚未分配時，立即將該資源分配給這個進(jìn)該資源尚未分配時，立即將該資源分配給這個進(jìn)程。后來發(fā)現(xiàn)，對資源不加限制地分配可能導(dǎo)致程。后來發(fā)現(xiàn)，對資源不加限制地分配可能導(dǎo)致進(jìn)程間由于競爭資源而相互制約以至于無法繼續(xù)進(jìn)程間由于競爭資源而相互制約以至于無法繼續(xù)運行的局面，人們把這種局面稱為運行的局面，人們把這種局面稱為死鎖死鎖 (deadlock)。 死鎖死鎖問題在問題在1965年由年由Dijkstra發(fā)現(xiàn)，并隨著計發(fā)現(xiàn)，并隨著計算機(jī)技術(shù)的發(fā)展，逐漸成為人們關(guān)心的問題。那算機(jī)技術(shù)的發(fā)展，逐漸成為人們關(guān)心的問題。那么，什么是么，什么是死鎖死鎖？其確切

36、的定義是什么？其確切的定義是什么？死鎖死鎖是是怎么產(chǎn)生的？用什么方法來解決怎么產(chǎn)生的？用什么方法來解決死鎖死鎖？這些正是？這些正是今天我們要討論的問題。今天我們要討論的問題。Page 562021-10-18 死鎖死鎖(Deadlock)的定義的定義：一組進(jìn)程中，每個進(jìn)一組進(jìn)程中，每個進(jìn)程都無限等待被該組進(jìn)程中另一進(jìn)程所占有的資源，程都無限等待被該組進(jìn)程中另一進(jìn)程所占有的資源，因而永遠(yuǎn)無法得到的資源，這種現(xiàn)象稱為進(jìn)程因而永遠(yuǎn)無法得到的資源，這種現(xiàn)象稱為進(jìn)程死鎖死鎖，這一組進(jìn)程就稱為這一組進(jìn)程就稱為死鎖進(jìn)程死鎖進(jìn)程。關(guān)于死鎖的一些結(jié)論：關(guān)于死鎖的一些結(jié)論： 參與死鎖的進(jìn)程最少是兩個參與死鎖的進(jìn)程

37、至少有兩個已經(jīng)占有資源參與死鎖的所有進(jìn)程都在等待資源參與死鎖的進(jìn)程是當(dāng)前系統(tǒng)中所有進(jìn)程的子集Page 572021-10-183.5.1 產(chǎn)生死鎖的原因產(chǎn)生死鎖的原因 產(chǎn)生死鎖的原因有兩點：產(chǎn)生死鎖的原因有兩點： (1)(1)競爭資源：競爭資源：為多個進(jìn)程所共享的資源不夠，為多個進(jìn)程所共享的資源不夠，引起它們對資源的競爭而產(chǎn)生死鎖；引起它們對資源的競爭而產(chǎn)生死鎖； (2)(2)進(jìn)程推進(jìn)順序不當(dāng)：進(jìn)程推進(jìn)順序不當(dāng)：在進(jìn)程運行過程中，在進(jìn)程運行過程中，請求資源和釋放資源的順序不當(dāng)，也會產(chǎn)生死鎖。請求資源和釋放資源的順序不當(dāng)，也會產(chǎn)生死鎖。Page 582021-10-18q只有4個條件都滿足時，才會出現(xiàn)死鎖。v互斥：任一時刻只允許一個進(jìn)程使用資源v不剝奪：進(jìn)程已經(jīng)占用的資源，不會被強(qiáng)制剝奪v請求和保持（部分分配）：進(jìn)程在請求其余資源時，不主動釋放已經(jīng)占用的資源v環(huán)路等待：環(huán)路中的每一條邊是進(jìn)程在請求另一進(jìn)程已經(jīng)占有的資源。3.3.2 產(chǎn)生死鎖的必要條件產(chǎn)生死鎖的必要條件 Page 592021-10-18 1.互斥：互斥：在一段時間內(nèi)某資源僅為一個進(jìn)程所在一段時間內(nèi)某資源僅為一個進(jìn)程所占有，如果此時還有其它進(jìn)程要