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

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

2、高級調度 又稱又稱作業(yè)調度作業(yè)調度v主要任務是按一定的原則對外存上處于后備主要任務是按一定的原則對外存上處于后備狀態(tài)的作業(yè)進行選擇，給選中的作業(yè)狀態(tài)的作業(yè)進行選擇，給選中的作業(yè)分配分配內內存、輸入存、輸入/ /輸出設備等輸出設備等必要的資源必要的資源，并，并建立建立相相應的應的進程進程，插插入入就緒就緒隊列隊列，以使該作業(yè)的進，以使該作業(yè)的進程獲得競爭處理機的權利程獲得競爭處理機的權利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è)調度調度進程進程調度調度終止終止作業(yè)作業(yè)

3、q作業(yè)作業(yè)狀態(tài)間轉換狀態(tài)間轉換圖圖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è)經輸入設備（如讀卡機）即用戶作業(yè)經輸入設備（如讀卡機）送入輸入井（磁盤）中存放，送入輸入井（磁盤）中存放， 等待進入內存時所處的等待進入內存時所處的狀況。狀況。 （3） 執(zhí)行狀態(tài)執(zhí)行狀態(tài)即作業(yè)分配到所需的資源，即作業(yè)分配到所需的資源， 被調被調入內存，入內存， 并且在處理機（并且在處理機（CPU）上執(zhí)行相應的程序時）上執(zhí)行相應的程序時所處的狀況。所處的狀況。 （4） 完成

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

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

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

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

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

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

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

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

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

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

14、時間周轉時間：完成時間-到達時間到達時間v帶權周轉時間：周轉時間帶權周轉時間：周轉時間/服務時間服務時間Page 272021-10-18進程名進程名到達時間到達時間 服務時間服務時間 開始時間開始時間 完成時間完成時間 周轉時間周轉時間帶權周帶權周轉時間轉時間平均平均04A13B25C32D44E044476先來先服務（先進先出）：先來先服務（先進先出）：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è)( (進程進程) )優(yōu)先調度算法優(yōu)先調度算法

15、SJ(P)FSJ(P)Fv短作業(yè)短作業(yè)( (進程進程) )優(yōu)先調度算法優(yōu)先調度算法SJ(P)FSJ(P)F，以要求以要求運運行時間長短行時間長短進行調度，即啟動要求運行時間最進行調度，即啟動要求運行時間最短的作業(yè)短的作業(yè)v可以分別用于可以分別用于作業(yè)調度作業(yè)調度和和進程調度進程調度Page 292021-10-18進程名進程名到達時間到達時間 服務時間服務時間 開始時間開始時間 完成時間完成時間 周轉時間周轉時間帶權周帶權周轉時間轉時間平均平均04A13B25C32D44E0441短作業(yè)短作業(yè)/短進程優(yōu)先（短進程優(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調度算法的性能調度算法的性能 作業(yè)作業(yè)調度調度 情況情況 算法算法進程名進程名ABCDE平均平均到達時間到達時間01234服務時間服務時間43524FCFS完成時間完成時間47121418周轉時間周轉時間461011149帶權周轉時間帶權周轉時間1225.53.52.8SJF完成時間完成時間4918613周轉時間周轉時間4816398帶權周轉時間帶權周轉時間12.673.11.52.252.1SJFSJF平均周轉平均周轉時間和平均帶時間和平均帶權

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

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

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

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

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

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

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

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

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

26、間內，均能獲得一時間片的處理機執(zhí)行時間時間內，均能獲得一時間片的處理機執(zhí)行時間缺點：緊迫任務響應慢。缺點：緊迫任務響應慢。UNIX中采用：時間片中采用：時間片+優(yōu)先權優(yōu)先權Page 422021-10-18進程名進程名到達時間到達時間 服務時間服務時間 開始時間開始時間 完成時間完成時間 周轉時間周轉時間帶權周帶權周轉時間轉時間平均平均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若到達時間若到達時間為為0 0、1 1、2

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

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

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

30、0-18 假如有4道作業(yè)，它們的提交時間及運行時間如下表所示：采用單道運行，試問下述調度算法下，它們的調度順序，并分別計算各調度算法下三個作業(yè)的平均周轉時間 T 和平均帶權周轉時間 W。（1）FCFS（先來先服務）（2）SJF（短作業(yè)優(yōu)先）（3）HRF（響應比高者優(yōu)先） n n T=1/N（Ti）,Ti=結束時刻結束時刻-提交時刻提交時刻; 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、：調度順序為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è)號到達時刻到達時刻要求運行時間要求運行時間（分鐘）（分鐘）結束時刻結束時刻周轉時間周轉時間Ti（分鐘）分鐘）帶權周轉時間帶權周轉時間Wi18：0012010：00120128：303010：30120439：00610：36961649：301210：48786.5Page 492021-10-18（2）SJF(SPF)：調度順序為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è)號到達時刻到達時刻要求運行時間要求運行時間（分鐘）（分鐘）結束時刻結束時刻周轉時間周轉時間Ti（分鐘）分鐘）帶權周轉時間帶權周轉時間Wi18：0012010：00120139：00610：06661149：301210：1848428：303010：481384.6Page 502021-10-18q （3）HRFq 作業(yè)1最先到達并運行，當作業(yè) 1 完成時（10：00），作業(yè) 2、3、4都到達，則計算它們的響應比：作業(yè)2響應比=（90+30）/30=4作業(yè)3響應比=（60+6）/6=11作業(yè)4響應比=（30+12）/12=3.5由于作業(yè)3的響應比最高，所以作業(yè)3先運行。q 當作業(yè)3完成

33、時（10：06），計算作業(yè)2、4的響應比：作業(yè)2響應比=（96+30）/30=4.2作業(yè)4響應比=（36+12）/12=4由于作業(yè)2的響應比大于作業(yè)4，所以接著作業(yè)2運行；最后由作業(yè)4運行。 Page 512021-10-18（3）HRF：調度順序為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è)號到達時刻到達時刻要求運行時間要求運行時間（分鐘）（分鐘）結束時刻結束時刻周轉時間周轉時間Ti（分鐘）分鐘）帶權周轉時間帶權周轉時間Wi18：0012010：00120139：00610：06661128：3030

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

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

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

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