計(jì)算機(jī)操作系統(tǒng)課件(第四版)第三章

第三章

處理機(jī)調(diào)度與死鎖第一節(jié)

處理機(jī)調(diào)度的層次第二節(jié)

調(diào)度隊(duì)列模型和調(diào)度準(zhǔn)則第三節(jié)

調(diào)度算法第四節(jié)實(shí)時(shí)調(diào)度第五節(jié)

產(chǎn)生死鎖的原因和必要條件第六節(jié)預(yù)防死鎖的方法第七節(jié)死鎖的檢測(cè)和解除1第三章

處理機(jī)調(diào)度與死鎖第一節(jié)

處理機(jī)調(diào)度的層次13.1處理機(jī)調(diào)度的層次高級(jí)調(diào)度低級(jí)調(diào)度中級(jí)調(diào)度23.1處理機(jī)調(diào)度的層次高級(jí)調(diào)度23.1.1、高級(jí)調(diào)度高級(jí)調(diào)度（作業(yè)調(diào)度/長(zhǎng)程調(diào)度）決定把外存上處于后備隊(duì)列中的哪些作業(yè)調(diào)入內(nèi)存。調(diào)度對(duì)象：作業(yè)1、作業(yè)和作業(yè)步作業(yè)：程序+數(shù)據(jù)+作業(yè)說明書作業(yè)步：作業(yè)運(yùn)行期間的每個(gè)加工步驟例如：編譯

連結(jié)裝配

運(yùn)行33.1.1、高級(jí)調(diào)度高級(jí)調(diào)度（作業(yè)調(diào)度/長(zhǎng)程調(diào)度）1、作業(yè)2、作業(yè)控制塊（JCB）JCB：保存了系統(tǒng)對(duì)作業(yè)進(jìn)行管理和調(diào)度所需的全部信息。作業(yè)在系統(tǒng)中存在的標(biāo)志。JCB包含的內(nèi)容有：作業(yè)標(biāo)識(shí)、用戶名稱、用戶賬號(hào)、作業(yè)類型、作業(yè)狀態(tài)、調(diào)度信息、資源需求、時(shí)間信息、資源使用情況等。JCB的創(chuàng)建和回收42、作業(yè)控制塊（JCB）43、高級(jí)調(diào)度（作業(yè)/長(zhǎng)程/接納調(diào)度）概念：決定把外存上處于后備隊(duì)列中的哪些作業(yè)調(diào)入內(nèi)存，并為它們創(chuàng)建進(jìn)程、分配必要的資源，準(zhǔn)備執(zhí)行。多用于批處理系統(tǒng)每次調(diào)度時(shí)要考慮：

(1)接納多少作業(yè)：取決于多道程序度

(2)接納哪些作業(yè)：取決于調(diào)度算法作業(yè)調(diào)度運(yùn)行頻率低，幾分鐘一次系統(tǒng)規(guī)模運(yùn)行速度53、高級(jí)調(diào)度（作業(yè)/長(zhǎng)程/接納調(diào)度）系統(tǒng)規(guī)模5低級(jí)調(diào)度（進(jìn)程/短程調(diào)度）決定就緒隊(duì)列中的哪個(gè)進(jìn)程應(yīng)獲得處理機(jī)，然后再由分派程序執(zhí)行把處理機(jī)分配給該進(jìn)程的具體操作是最基本的調(diào)度，在三種類型的OS中都必須配置3.1.2、低級(jí)調(diào)度1、低級(jí)調(diào)度的功能保存處理機(jī)的現(xiàn)場(chǎng)信息按照某種算法選取進(jìn)程把處理機(jī)分配給進(jìn)程6低級(jí)調(diào)度（進(jìn)程/短程調(diào)度）3.1.2、低級(jí)調(diào)度1、低級(jí)調(diào)2、進(jìn)程調(diào)度中的三個(gè)基本機(jī)制排隊(duì)器分派器（分派程序）上下文切換機(jī)制3、進(jìn)程調(diào)度方式非搶占方式搶占方式72、進(jìn)程調(diào)度中的三個(gè)基本機(jī)制3、進(jìn)程調(diào)度方式71）非搶占方式：一旦進(jìn)程獲得處理機(jī)，則一直執(zhí)行，直到該進(jìn)程完成或被阻塞此方式下，可能引起進(jìn)程調(diào)度的因素：（1）正在執(zhí)行的進(jìn)程執(zhí)行完畢，或因發(fā)生某事件不能再繼續(xù)執(zhí)行（2）執(zhí)行中的進(jìn)程因提出I/O請(qǐng)求而暫停執(zhí)行（3）在進(jìn)程通信或同步過程中執(zhí)行了某原語，P操作等優(yōu)點(diǎn)：簡(jiǎn)單、系統(tǒng)開銷小，適合大多數(shù)批處理系統(tǒng)缺點(diǎn)：無法滿足緊急任務(wù)的需要，不適合實(shí)時(shí)系統(tǒng)81）非搶占方式：82）搶占方式：允許調(diào)度程序根據(jù)某原則，暫停正在執(zhí)行的進(jìn)程，將處理機(jī)重新分配搶占原則：優(yōu)先權(quán)原則就緒的高優(yōu)先權(quán)進(jìn)程有權(quán)搶占低優(yōu)先權(quán)進(jìn)程的CPU短作業(yè)優(yōu)先原則就緒的短作業(yè)(進(jìn)程)有權(quán)搶占長(zhǎng)作業(yè)(進(jìn)程)的CPU時(shí)間片原則一個(gè)時(shí)間片用完后，系統(tǒng)重新進(jìn)行進(jìn)程調(diào)度92）搶占方式：9中級(jí)調(diào)度（中程調(diào)度）目的：提高內(nèi)存利用率和系統(tǒng)吞吐量按一定的算法將外存上已具備運(yùn)行條件的掛起進(jìn)程換入內(nèi)存，掛到就緒隊(duì)列上，準(zhǔn)備執(zhí)行；而將內(nèi)存中處于阻塞狀態(tài)的某些進(jìn)程換出至外存。3.1.3、中級(jí)調(diào)度10中級(jí)調(diào)度（中程調(diào)度）3.1.3、中級(jí)調(diào)度10調(diào)度隊(duì)列模型選擇調(diào)度方式和調(diào)度算法的若干準(zhǔn)則3.2、調(diào)度隊(duì)列模型11調(diào)度隊(duì)列模型3.2、調(diào)度隊(duì)列模型113.2.1、調(diào)度隊(duì)列模型僅具有進(jìn)程調(diào)度的調(diào)度隊(duì)列模型就緒隊(duì)列阻塞隊(duì)列CPU時(shí)間片完交互用戶進(jìn)程調(diào)度進(jìn)程完成等待事件事件發(fā)生……具有高、低兩級(jí)調(diào)度的調(diào)度隊(duì)列模型就緒隊(duì)列阻塞隊(duì)列CPU時(shí)間片完作業(yè)調(diào)度進(jìn)程調(diào)度進(jìn)程完成等待事件1阻塞隊(duì)列阻塞隊(duì)列等待事件2等待事件n事件1發(fā)生事件2發(fā)生事件n發(fā)生后備隊(duì)列

具有高、低、中三級(jí)調(diào)度的調(diào)度隊(duì)列模型就緒隊(duì)列緒就、掛起隊(duì)列CPU時(shí)間片完作業(yè)調(diào)度進(jìn)程調(diào)度進(jìn)程完成事件出現(xiàn)阻塞隊(duì)列掛起等待事件中級(jí)調(diào)度事件發(fā)生后備隊(duì)列塞阻、掛起隊(duì)列掛起123.2.1、調(diào)度隊(duì)列模型就緒隊(duì)列阻塞隊(duì)列CPU時(shí)間片完交互用3.2.2、選擇調(diào)度方式和算法的選擇準(zhǔn)則1、面向用戶的準(zhǔn)則（1）周轉(zhuǎn)時(shí)間短——評(píng)價(jià)批處理系統(tǒng)

周轉(zhuǎn)時(shí)間：是指從作業(yè)被提交系統(tǒng)開始，到作業(yè)完成為止的這段時(shí)間間隔。包括四部分時(shí)間：

1）等待作業(yè)調(diào)度時(shí)間

2）等待進(jìn)程調(diào)度時(shí)間

3）執(zhí)行時(shí)間

4）進(jìn)程等待I/O操作完成時(shí)間133.2.2、選擇調(diào)度方式和算法的選擇準(zhǔn)則1、面向用戶的準(zhǔn)則包平均周轉(zhuǎn)時(shí)間：帶權(quán)周轉(zhuǎn)時(shí)間：周轉(zhuǎn)時(shí)間服務(wù)時(shí)間平均帶權(quán)周轉(zhuǎn)時(shí)間：14平均周轉(zhuǎn)時(shí)間：帶權(quán)周轉(zhuǎn)時(shí)間：周轉(zhuǎn)時(shí)間服務(wù)時(shí)間平均帶權(quán)周轉(zhuǎn)時(shí)間（2）響應(yīng)時(shí)間快——評(píng)價(jià)分時(shí)系統(tǒng)

響應(yīng)時(shí)間：從用戶通過鍵盤提交一個(gè)請(qǐng)求開始直至系統(tǒng)首次產(chǎn)生響應(yīng)為止。

包括三部分時(shí)間：1）從鍵盤輸入的請(qǐng)求信息傳送到處理機(jī)的時(shí)間2）處理時(shí)間3）響應(yīng)信息回送終端的時(shí)間15（2）響應(yīng)時(shí)間快——評(píng)價(jià)分時(shí)系統(tǒng)15（3）截止時(shí)間保證——評(píng)價(jià)實(shí)時(shí)系統(tǒng)

截止時(shí)間：任務(wù)必須開始執(zhí)行的最遲時(shí)間，或必須完成的最遲時(shí)間。（4）優(yōu)先權(quán)準(zhǔn)則——三種系統(tǒng)中皆適用16（3）截止時(shí)間保證——評(píng)價(jià)實(shí)時(shí)系統(tǒng)162、面向系統(tǒng)的準(zhǔn)則系統(tǒng)吞吐量高——評(píng)價(jià)批處理系統(tǒng)處理機(jī)利用率好——針對(duì)大中型系統(tǒng)各類資源的平衡利用——對(duì)大中型系統(tǒng)172、面向系統(tǒng)的準(zhǔn)則173.3

調(diào)度算法先來先服務(wù)和短作業(yè)（進(jìn)程）優(yōu)先調(diào)度算法高優(yōu)先權(quán)先調(diào)度算法基于時(shí)間片的輪轉(zhuǎn)調(diào)度算法183.3

調(diào)度算法先來先服務(wù)和短作業(yè)（進(jìn)程）優(yōu)先調(diào)度算法183.2.1、先來先服務(wù)和短作業(yè)（進(jìn)程）優(yōu)先調(diào)度算法1、先來先服務(wù)（FCFS）調(diào)度算法可用于作業(yè)調(diào)度和進(jìn)程調(diào)度用于作業(yè)調(diào)度：每次從后備作業(yè)隊(duì)列中選擇最先進(jìn)入的作業(yè)，將它們調(diào)入內(nèi)存，為它們分配資源、創(chuàng)建進(jìn)程，然后掛到就緒進(jìn)程隊(duì)列上。193.2.1、先來先服務(wù)和短作業(yè)（進(jìn)程）優(yōu)先調(diào)度算法1、先來先用于進(jìn)程調(diào)度：每次從就緒進(jìn)程隊(duì)列中選擇最先進(jìn)入的進(jìn)程，為之分配處理機(jī)，使之投入運(yùn)行。直到運(yùn)行完成進(jìn)程才會(huì)讓出處理機(jī)--非搶占式。有利于長(zhǎng)作業(yè)，而不利于短作業(yè)。20用于進(jìn)程調(diào)度：20進(jìn)程名到達(dá)時(shí)間服務(wù)時(shí)間開始執(zhí)行時(shí)間完成時(shí)間周轉(zhuǎn)時(shí)間帶權(quán)周轉(zhuǎn)時(shí)間A010111B110011011001C21101102100100D31001022021991.99性能評(píng)價(jià)：周轉(zhuǎn)時(shí)間=完成時(shí)間–到達(dá)時(shí)間帶權(quán)周轉(zhuǎn)時(shí)間=周轉(zhuǎn)時(shí)間/服務(wù)（運(yùn)行）時(shí)間21進(jìn)程到達(dá)服務(wù)開始執(zhí)完成周轉(zhuǎn)帶權(quán)周性能評(píng)價(jià)：212、短作業(yè)/進(jìn)程優(yōu)先（SJF/SPF）短作業(yè)優(yōu)先（SJF）從后備隊(duì)列中選擇估計(jì)運(yùn)行時(shí)間最短的作業(yè)，調(diào)入內(nèi)存運(yùn)行。短進(jìn)程優(yōu)先（SPF）從就緒隊(duì)列中選出估計(jì)運(yùn)行時(shí)間最短的進(jìn)程，將處理機(jī)分配給它，使它立即執(zhí)行。直到運(yùn)行完成進(jìn)程才會(huì)讓出處理機(jī)--非搶占式。缺點(diǎn)：對(duì)長(zhǎng)作業(yè)不利，有可能長(zhǎng)期不被調(diào)度；完全沒考慮作業(yè)的緊迫程度（某些特殊的）；用戶做出的估計(jì)時(shí)間帶有很大的主觀性。222、短作業(yè)/進(jìn)程優(yōu)先（SJF/SPF）短作業(yè)優(yōu)先（SJF2.259133.5141844E3.116182101252C2.678926731B1.5365.5111423D2.11帶權(quán)周轉(zhuǎn)時(shí)間84周轉(zhuǎn)時(shí)間4完成時(shí)間FJS2.81帶權(quán)周轉(zhuǎn)時(shí)間94周轉(zhuǎn)時(shí)間4完成時(shí)間FCFS4服務(wù)時(shí)間0到達(dá)時(shí)間平均A進(jìn)程名

作調(diào)業(yè)度情算況法周轉(zhuǎn)時(shí)間=完成時(shí)間–到達(dá)時(shí)間帶權(quán)周轉(zhuǎn)時(shí)間=周轉(zhuǎn)時(shí)間/服務(wù)時(shí)間232.259133.5141844E3.116182101253.3.2、高優(yōu)先權(quán)先調(diào)度算法既能用于作業(yè)調(diào)度，也可用于進(jìn)程調(diào)度。作業(yè)調(diào)度：從后備隊(duì)列中選擇若干個(gè)優(yōu)先權(quán)最高的作業(yè)裝入內(nèi)存。進(jìn)程調(diào)度：把處理機(jī)分配給就緒隊(duì)列中優(yōu)先權(quán)最高的進(jìn)程兩種占用CPU的方式：非搶占式優(yōu)先權(quán)算法搶占式優(yōu)先權(quán)算法1、優(yōu)先權(quán)調(diào)度算法的類型243.3.2、高優(yōu)先權(quán)先調(diào)度算法既能用于作業(yè)調(diào)度，也可用于進(jìn)程非搶占式優(yōu)先權(quán)算法系統(tǒng)一旦把處理機(jī)分配給就緒隊(duì)列中優(yōu)先權(quán)最高的進(jìn)程后，該進(jìn)程就一直執(zhí)行下去，直至完成；或因發(fā)生某事件使該進(jìn)程放棄處理機(jī)時(shí)，系統(tǒng)方可再將處理機(jī)重新分配給另一優(yōu)先權(quán)最高的進(jìn)程。主要用于批處理系統(tǒng)25非搶占式優(yōu)先權(quán)算法25搶占式優(yōu)先權(quán)算法新的就緒進(jìn)程i，優(yōu)先權(quán)Pi。正在執(zhí)行的進(jìn)程j，優(yōu)先權(quán)Pj。若Pi<=Pj，原進(jìn)程j繼續(xù)執(zhí)行。若Pi>Pj，做進(jìn)程切換。新進(jìn)程i執(zhí)行。優(yōu)點(diǎn)：能更好的滿足緊迫作業(yè)的要求。主要用于比較嚴(yán)格的實(shí)時(shí)系統(tǒng)。26搶占式優(yōu)先權(quán)算法262、優(yōu)先權(quán)的類型

1）靜態(tài)優(yōu)先權(quán)在進(jìn)程創(chuàng)建時(shí)確定的，在進(jìn)程整個(gè)運(yùn)行期間保持不變優(yōu)先權(quán)利用某一范圍的整數(shù)來表示，該整數(shù)稱為優(yōu)先數(shù)。如：0—7，0—255確定優(yōu)先權(quán)的依據(jù)：（1）進(jìn)程類型（2）進(jìn)程對(duì)資源的需求（3）用戶要求272、優(yōu)先權(quán)的類型優(yōu)先權(quán)利用某一范圍的整數(shù)來表示，該整數(shù)稱為優(yōu)

注：規(guī)定優(yōu)先數(shù)越小，其優(yōu)先權(quán)越高4/348334C15/81517482B119118D帶權(quán)周轉(zhuǎn)時(shí)間周轉(zhuǎn)時(shí)間155完成時(shí)間2優(yōu)先權(quán)非搶占式優(yōu)先權(quán)算法5服務(wù)時(shí)間0到達(dá)時(shí)間A進(jìn)程名

作調(diào)業(yè)度情算況法平均6.251.3例：非搶占式優(yōu)先權(quán)算法28注：規(guī)定優(yōu)先數(shù)越小，其優(yōu)先權(quán)越高4/348334C15/8t(等待)優(yōu)先權(quán)t(運(yùn)行)優(yōu)先權(quán)2)動(dòng)態(tài)優(yōu)先權(quán)在進(jìn)程創(chuàng)建時(shí)創(chuàng)立的優(yōu)先權(quán)，可隨進(jìn)程的推進(jìn)或等待時(shí)間的增加而改變。如等待時(shí)間長(zhǎng)，優(yōu)先權(quán)升高。29t(等待)優(yōu)先權(quán)t(運(yùn)行)優(yōu)先權(quán)2)動(dòng)態(tài)優(yōu)先權(quán)29

等待時(shí)間+要求服務(wù)時(shí)間優(yōu)先權(quán)=------------------------------------

要求服務(wù)時(shí)間等待時(shí)間+要求服務(wù)時(shí)間響應(yīng)時(shí)間響應(yīng)比(Rp)=------------------------------------=-------------------

要求服務(wù)時(shí)間要求服務(wù)時(shí)間3、高響應(yīng)比優(yōu)先調(diào)度算法(HRRN)為每個(gè)進(jìn)程引入動(dòng)態(tài)優(yōu)先權(quán)，隨著等待時(shí)間增加優(yōu)先權(quán)提高。優(yōu)點(diǎn)：等待時(shí)間相同，短作業(yè)優(yōu)先權(quán)高(即SPF)要求服務(wù)時(shí)間相同，等待時(shí)間長(zhǎng)，優(yōu)先權(quán)高(即FCFS)對(duì)于長(zhǎng)作業(yè)，在等待足夠時(shí)間后，可獲得處理機(jī)30等待時(shí)間+要3.571528E2.2591344C1.177962B2.8142056D2.141帶權(quán)周轉(zhuǎn)時(shí)間83周轉(zhuǎn)時(shí)間3完成時(shí)間3服務(wù)時(shí)間0到達(dá)時(shí)間平均A進(jìn)程名

作調(diào)業(yè)度情算況法RC＝1+(9-4)/4=2.25RD＝1+(9-6)/5=1.6RE＝1+(9-8)/2=1.5RD＝1+(13-6)/5=2.4RE＝1+(13-8)/2=3.5執(zhí)行順序：A－>B－>C－>E－>DHRRN（R大，優(yōu)先權(quán)高）313.571528E2.2591344C1.177962B、基于時(shí)間片的輪轉(zhuǎn)調(diào)度算法1、時(shí)間片輪轉(zhuǎn)法1）基本原理系統(tǒng)將所有的就緒進(jìn)程按FIFO原則排成一個(gè)隊(duì)列，將CPU分配給隊(duì)首進(jìn)程，執(zhí)行一個(gè)時(shí)間片。在時(shí)間片內(nèi)進(jìn)程未完，則插入就緒隊(duì)列未尾，CPU交給下一個(gè)進(jìn)程。2）時(shí)間片大小的確定時(shí)間片略大于一次典型的交互所需要的時(shí)間。323.3.3、基于時(shí)間片的輪轉(zhuǎn)調(diào)度算法1、時(shí)間片輪轉(zhuǎn)法1）基本3.3313173.33131744E2.259113.5141642C2673.67111231B5101336923D帶權(quán)周轉(zhuǎn)時(shí)間2.58.4周轉(zhuǎn)時(shí)間144完成時(shí)間RRq=4帶權(quán)周轉(zhuǎn)時(shí)間3.4611.8周轉(zhuǎn)時(shí)間3.751515完成時(shí)間RRq=14服務(wù)時(shí)間0到達(dá)時(shí)間平均A進(jìn)程名

作調(diào)業(yè)度情算況法周轉(zhuǎn)時(shí)間=完成時(shí)間–到達(dá)時(shí)間帶權(quán)周轉(zhuǎn)時(shí)間=周轉(zhuǎn)時(shí)間/服務(wù)時(shí)間333.3313173.33131744E2.259113.512、多級(jí)反饋隊(duì)列調(diào)度算法

原理：設(shè)置多個(gè)就緒隊(duì)列，并為各個(gè)隊(duì)列賦予不同的優(yōu)先級(jí)和不同長(zhǎng)度的時(shí)間片；新創(chuàng)建的進(jìn)程掛到第一優(yōu)先級(jí)的隊(duì)列后，然后按FCFS

原則排隊(duì)等待調(diào)度。當(dāng)輪到其執(zhí)行時(shí)，如它能在時(shí)間片內(nèi)完成，便撤離系統(tǒng)；如果不能完成，便被掛入第二級(jí)隊(duì)列后，……，最后一級(jí)隊(duì)列采用時(shí)間片輪轉(zhuǎn)法；僅當(dāng)?shù)谝患?jí)隊(duì)列空閑時(shí)，調(diào)度程序才調(diào)度第二級(jí)隊(duì)列中的進(jìn)程運(yùn)行，依次類推……；新進(jìn)程可搶占低級(jí)進(jìn)程的處理機(jī)。342、多級(jí)反饋隊(duì)列調(diào)度算法原理：34……多級(jí)反饋隊(duì)列調(diào)度算法示意圖CPU時(shí)間片完進(jìn)程調(diào)度進(jìn)程完成就緒隊(duì)列一就緒隊(duì)列二就緒隊(duì)列三就緒隊(duì)列n時(shí)間片完時(shí)間片完35CPU時(shí)間進(jìn)程進(jìn)程完成就緒隊(duì)列一就緒隊(duì)列二就緒隊(duì)列三就緒隊(duì)列就級(jí)1緒隊(duì)列空就級(jí)2緒隊(duì)列就級(jí)3緒隊(duì)列運(yùn)行等待12354時(shí)間片小－－－－大優(yōu)先級(jí)高－－－－低36就級(jí)1緒隊(duì)列空就級(jí)2緒隊(duì)列就級(jí)3緒隊(duì)列運(yùn)行等待12354時(shí)間多級(jí)反饋隊(duì)列調(diào)度算法的性能多級(jí)反饋隊(duì)列調(diào)度算法能較好地滿足各種類型用戶（進(jìn)程）的需要：終端（交互）型作業(yè)用戶短批處理作業(yè)用戶長(zhǎng)批處理作業(yè)用戶37多級(jí)反饋隊(duì)列調(diào)度算法的性能373.3.4、基于公平原則的調(diào)度算法1、保證調(diào)度算法如果系統(tǒng)中有n個(gè)相同類型的進(jìn)程同時(shí)運(yùn)行，保證每個(gè)進(jìn)程都獲得相同的處理機(jī)時(shí)間1/n。2、公平分享調(diào)度算法使所有用戶能獲得相同的處理機(jī)時(shí)間。383.3.4、基于公平原則的調(diào)度算法1、保證調(diào)度算法如果系統(tǒng)中3.4實(shí)時(shí)調(diào)度實(shí)現(xiàn)實(shí)時(shí)調(diào)度的基本概念和條件實(shí)時(shí)調(diào)度算法的分類常見的幾種實(shí)時(shí)調(diào)度算法選學(xué)393.4實(shí)時(shí)調(diào)度實(shí)現(xiàn)實(shí)時(shí)調(diào)度的基本概念和條件選學(xué)391.實(shí)時(shí)調(diào)度是為了完成實(shí)時(shí)處理任務(wù)而分配處理機(jī)的調(diào)度方法。2.硬實(shí)時(shí)任務(wù)要求計(jì)算機(jī)系統(tǒng)必須在用戶給定的時(shí)限內(nèi)完成

3.軟實(shí)時(shí)任務(wù)允許計(jì)算機(jī)系統(tǒng)在用戶給定的時(shí)限左右處理完畢。提供更詳細(xì)的調(diào)度信息：就緒時(shí)間、開始截止時(shí)間或完成截止時(shí)間、處理時(shí)間、資源要求、優(yōu)先級(jí)等；含有硬實(shí)時(shí)任務(wù)的實(shí)時(shí)系統(tǒng)中，廣泛采用基于優(yōu)先級(jí)的搶占式調(diào)度策略401.實(shí)時(shí)調(diào)度是為了完成實(shí)時(shí)處理任務(wù)而分配處理機(jī)的調(diào)度實(shí)時(shí)調(diào)度算法分類：非搶占式輪轉(zhuǎn)調(diào)度算法：只適用于一般實(shí)時(shí)信息處理系統(tǒng)非搶占式優(yōu)先級(jí)調(diào)度算法：優(yōu)先級(jí)最高的實(shí)時(shí)任務(wù)排在就緒隊(duì)列隊(duì)首，當(dāng)前任務(wù)終止或完成后才被調(diào)度。

基于時(shí)鐘中斷搶占式優(yōu)先級(jí)調(diào)度算法：新到的實(shí)時(shí)任務(wù)的優(yōu)先級(jí)高于當(dāng)前任務(wù)時(shí)，并不立即搶占CPU，而是等到時(shí)鐘中斷到來，才進(jìn)行切換。用于大多數(shù)的實(shí)時(shí)系統(tǒng)中。

立即搶占的優(yōu)先級(jí)調(diào)度算法：這種算法適用于實(shí)時(shí)要求比較嚴(yán)格的實(shí)時(shí)控制系統(tǒng)。41實(shí)時(shí)調(diào)度算法分類：非搶占式輪轉(zhuǎn)調(diào)度算法：只適用于一般實(shí)時(shí)信息常用的幾種實(shí)時(shí)調(diào)度算法1、最早截止時(shí)間優(yōu)先算法（EDF）該算法根據(jù)任務(wù)的開始截止時(shí)間來確定任務(wù)的優(yōu)先級(jí)。截止時(shí)間越早，優(yōu)先級(jí)越高。該算法要求實(shí)時(shí)任務(wù)的就緒隊(duì)列按任務(wù)截止時(shí)間的早晚排序。調(diào)度程序總選擇隊(duì)首的任務(wù)執(zhí)行。

該算法可用于搶占式和非搶占式調(diào)度。t任務(wù)到達(dá)任務(wù)執(zhí)行開始截止時(shí)間134211224433非搶占式調(diào)度方式42常用的幾種實(shí)時(shí)調(diào)度算法1、最早截止時(shí)間優(yōu)先算法（EDF）t任2、最低松弛度優(yōu)先算法（LLF）該算法根據(jù)任務(wù)的松弛度來確定任務(wù)的優(yōu)先級(jí)。松弛度越低，優(yōu)先級(jí)越高。松弛度＝任務(wù)必須完成的時(shí)間－運(yùn)行時(shí)間－當(dāng)前時(shí)間該算法要求實(shí)時(shí)任務(wù)的就緒隊(duì)列按松弛度排序。調(diào)度程序總選擇隊(duì)首的任務(wù)執(zhí)行。該算法主要用于搶占式調(diào)度方式。432、最低松弛度優(yōu)先算法（LLF）43松弛度＝任務(wù)必須完成的時(shí)間－運(yùn)行時(shí)間－當(dāng)前時(shí)間例：實(shí)時(shí)系統(tǒng)中有兩個(gè)周期性實(shí)時(shí)任務(wù)A、B，任務(wù)A每20ms執(zhí)行一次，執(zhí)行時(shí)間10ms；任務(wù)B每50ms執(zhí)行一次，執(zhí)行時(shí)間25ms。采用搶占式LLF算法：t020406080100120140160A1A2A3A4A5A6A7A8B1B2B3任務(wù)AB每次必須完成的時(shí)間松弛度t010203040455055607080A1=10B1=25A2=20B1=15A2=0B1=15A3=10B1=5A3=5B2=30此時(shí)執(zhí)行B2A4=0B2=20A4完B2=1044松弛度＝任務(wù)必須完成的時(shí)間－運(yùn)行時(shí)間－當(dāng)前時(shí)間例：實(shí)時(shí)系統(tǒng)中3、優(yōu)先級(jí)倒置問題（1）問題的形成即OS中廣泛采用的優(yōu)先級(jí)調(diào)度算法和搶占方式。舉例:三個(gè)獨(dú)立進(jìn)程P1、P2、P3，優(yōu)先級(jí)由高到低。P1、P3共享臨界資源進(jìn)行交互。代碼：P1：...P(mutex);CS-1;V(mutex)...;P2:...program2...;P3:...P(mutex);CS-3;V(mutex)...;執(zhí)行順序：P3—>P2(搶占)—>P1（阻塞）—>P2(執(zhí)行結(jié)束)—>P3(執(zhí)行結(jié)束)—>P1(執(zhí)行結(jié)束)問題：P1優(yōu)先級(jí)最高，但最后執(zhí)行結(jié)束453、優(yōu)先級(jí)倒置問題舉例:三個(gè)獨(dú)立進(jìn)程P1、P2、P33、優(yōu)先級(jí)倒置問題（續(xù)）（2）問題的解決方案方案2：建立在動(dòng)態(tài)優(yōu)先級(jí)繼承基礎(chǔ)上。規(guī)定：P1阻塞時(shí)由P3繼承P1的優(yōu)先級(jí)，一直保持到P3退出臨界區(qū)。目的：防止P2進(jìn)程插進(jìn)來，延緩P3退出臨界區(qū)。方案1：P3進(jìn)入臨界區(qū)后不允許處理機(jī)被搶占。適用情況：系統(tǒng)中臨界區(qū)較短且不多。463、優(yōu)先級(jí)倒置問題（續(xù)）方案2：建立在動(dòng)態(tài)優(yōu)先級(jí)繼承基礎(chǔ)上。3.5

產(chǎn)生死鎖的原因和必要條件產(chǎn)生死鎖的原因產(chǎn)生死鎖的必要條件處理死鎖的基本方法473.5

產(chǎn)生死鎖的原因和必要條件產(chǎn)生死鎖的原因473.5.1、產(chǎn)生死鎖的原因一、死鎖（Deadlock）定義：死鎖是指兩個(gè)或兩個(gè)以上的進(jìn)程在運(yùn)行過程中，因爭(zhēng)奪資源而造成的一種互相等待（誰也無法再繼續(xù)推進(jìn)）的現(xiàn)象，若無外力作用，它們都將無法推進(jìn)下去。二、產(chǎn)生死鎖的原因：1、競(jìng)爭(zhēng)資源2、進(jìn)程間推進(jìn)順序非法483.5.1、產(chǎn)生死鎖的原因一、死鎖（Deadlock）定義：1、競(jìng)爭(zhēng)資源引起進(jìn)程死鎖

1.1資源的兩種分類：可搶占性資源：CPU、RAM等；不可搶占性資源：打印機(jī)、磁帶機(jī)等；可重用性資源：打印機(jī)可消耗性資源：進(jìn)程通信中的消息、數(shù)據(jù)等491、競(jìng)爭(zhēng)資源引起進(jìn)程死鎖可搶占性資源：CPU、RAM等；可重1.2競(jìng)爭(zhēng)不可搶占性資源引起死鎖：系統(tǒng)中配備的非剝奪性資源的數(shù)量不能滿足諸進(jìn)程運(yùn)行的需要時(shí)，會(huì)使進(jìn)程因爭(zhēng)奪資源而陷入僵局。打印機(jī)P1磁帶機(jī)P21.3競(jìng)爭(zhēng)可消耗資源引起死鎖：501.2競(jìng)爭(zhēng)不可搶占性資源引起死鎖：打印機(jī)P1磁帶機(jī)P21.2、進(jìn)程間推進(jìn)順序不當(dāng)引起死鎖進(jìn)程推進(jìn)順序合法——不會(huì)導(dǎo)致死鎖進(jìn)程推進(jìn)順序非法——可能會(huì)導(dǎo)致死圖1：順序合法消息1P1消息2P2P3消息3圖2：順序非法消息1P1消息2P2P3消息3512、進(jìn)程間推進(jìn)順序不當(dāng)引起死鎖圖1：順序合法消息1P1消息23.5.2、產(chǎn)生死鎖的必要條件1、互斥條件一個(gè)資源一次只能被一個(gè)進(jìn)程使用。2、請(qǐng)求和保持條件（部分分配）保留已經(jīng)得到的資源，還要求其它的資源。3、不可搶占條件資源只能被占有者釋放，不能被其它進(jìn)程強(qiáng)行搶占。4、循環(huán)等待條件（循環(huán)等待）系統(tǒng)中的進(jìn)程形成了環(huán)形的資源請(qǐng)求鏈。523.5.2、產(chǎn)生死鎖的必要條件1、互斥條件523.5.3、處理死鎖的基本方法（1）預(yù)防死鎖（2）避免死鎖（3）檢測(cè)死鎖（4）解除死鎖533.5.3、處理死鎖的基本方法（1）預(yù)防死鎖533.6預(yù)防死鎖的方法預(yù)防死鎖系統(tǒng)安全狀態(tài)利用銀行家算法避免死鎖543.6預(yù)防死鎖的方法預(yù)防死鎖543.6.1、預(yù)防死鎖一、預(yù)防死鎖的實(shí)質(zhì)：通過設(shè)置某些限制條件，預(yù)防發(fā)生死鎖。二、預(yù)防死鎖的方法：

“互斥條件”——由資源的性質(zhì)決定。

1、摒棄“請(qǐng)求和保持”條件在開始運(yùn)行前（創(chuàng)建時(shí)），一次性分配給進(jìn)程它所需的“全部”資源。簡(jiǎn)單易實(shí)現(xiàn)，安全性高；資源浪費(fèi)。553.6.1、預(yù)防死鎖一、預(yù)防死鎖的實(shí)質(zhì)：552、摒棄“不可搶占”條件當(dāng)進(jìn)程有新的資源請(qǐng)求時(shí)，如果得不到滿足，要先釋放原先占有的資源，待以后重新申請(qǐng)。等價(jià)于此進(jìn)程“被剝奪”了已經(jīng)占有的資源。3、摒棄“循環(huán)等待”條件把系統(tǒng)資源按類型排序，進(jìn)程要按照資源的序號(hào)遞增的次序提出資源申請(qǐng)。較上述兩種方法的綜合性能要好；但系統(tǒng)配置資源的序號(hào)要穩(wěn)定，固定的訪問順序不一定合理。562、摒棄“不可搶占”條件56例1：

進(jìn)程A占有3號(hào)資源，現(xiàn)在又申請(qǐng)5號(hào)資源——占有資源號(hào)小于申請(qǐng)資源號(hào)，此申請(qǐng)可以滿足。進(jìn)程B占有5號(hào)資源，現(xiàn)在又申請(qǐng)3號(hào)資源——由于5>3，所以此申請(qǐng)不能滿足。進(jìn)程B要想得到3號(hào)資源，必須先放棄5號(hào)以及所有編號(hào)比3大的資源。57例1：57例2：哲學(xué)家就餐——給哲學(xué)家和筷子編號(hào)0－4

信號(hào)量定義：varchopstick[0,…,4]ofsemaphore;

信號(hào)量初值均為1；

第i(i=0,1,2,3)位哲學(xué)家活動(dòng)描述：第4位哲學(xué)家活動(dòng)描述:while(true){while(true){P(chopstick[i]);P(chopstick[0]);P(chopstick[(i+1)]);P(chopstick[4]); …………eating;eating; …………V(chopstick[i]);V(chopstick[0]);V(chopstick[(i+1)]);V(chopstick[4]); …………thinking;thinking;}}58例2：哲學(xué)家就餐——給哲學(xué)家和筷子編號(hào)0－4信號(hào)量3.6.2、系統(tǒng)安全狀態(tài)不安全狀態(tài)安全狀態(tài)死鎖實(shí)質(zhì)：把系統(tǒng)的狀態(tài)分為安全狀態(tài)和不安全狀態(tài)，只要能使系統(tǒng)始終處于安全狀態(tài)，便可避免發(fā)生死鎖593.6.2、系統(tǒng)安全狀態(tài)不安全狀態(tài)安全狀態(tài)死鎖實(shí)質(zhì)：把系統(tǒng)的1、安全狀態(tài)允許進(jìn)程動(dòng)態(tài)的申請(qǐng)資源，但在分配前，應(yīng)先計(jì)算分配的安全性。所謂“安全狀態(tài)”：指系統(tǒng)能按某種進(jìn)程順序(P1,P2,…,Pn)，來為每個(gè)進(jìn)程Pi分配其所需資源，直至最大需求，使每個(gè)進(jìn)程都可以順利完成。反之，則系統(tǒng)處于不安全狀態(tài)。

不安全狀態(tài)不一定發(fā)生死鎖，但死鎖一定屬于不安全狀態(tài)。601、安全狀態(tài)60進(jìn)程最大需求已分配系統(tǒng)可用P1P2P310495223系統(tǒng)資源總數(shù)：12進(jìn)程最大需求已分配系統(tǒng)可用P1P2P310495232系統(tǒng)資源總數(shù)：122、安全狀態(tài)之例：轉(zhuǎn)化安全狀態(tài)不安全狀態(tài)61進(jìn)程最大需求已分配系統(tǒng)可用P1105系統(tǒng)資源總數(shù)：12進(jìn)程最該算法能用于銀行系統(tǒng)現(xiàn)金貸款的發(fā)放而得名銀行家算法的實(shí)質(zhì)就是要設(shè)法保證系統(tǒng)動(dòng)態(tài)分配資源后仍然保持安全狀態(tài)，從而避免死鎖的發(fā)生。要求進(jìn)程預(yù)先告知自己的最大資源需求，并且假設(shè)系統(tǒng)擁有固定的資源總量。3.6.2、利用銀行家算法避免死鎖62該算法能用于銀行系統(tǒng)現(xiàn)金貸款的發(fā)放而得名3.6.2、利用銀行1、相關(guān)的數(shù)據(jù)結(jié)構(gòu)：可用資源向量Available最大需求矩陣Max

分配矩陣Allocation

需求矩陣Need資源請(qǐng)求向量Requesti3、安全性算法：工作向量Work、Finish2、銀行家算法：（1）Requesti<=Need?（2）Requesti<=Available?（3）修改相關(guān)向量的值（4）執(zhí)行安全性算法631、相關(guān)的數(shù)據(jù)結(jié)構(gòu)：MaxAllocationNeedAvailableABCABCABCABCP0P1P2P3P4753322902222433010200302211002743122600011431332資源總數(shù)

1057進(jìn)程資源某時(shí)刻系統(tǒng)資源分配情況ABCWork＋AllocationABCABCABCFinishAllocationNeedWork進(jìn)程資源安全序列(1)該時(shí)刻T0系統(tǒng)是安全的嗎？解：利用安全性算法對(duì)該時(shí)刻的資源分配情況進(jìn)行分析，方法如下圖：122200532true011211743true431211745true6003021047true7430101057true3325327437451047P1P3P4P2P064MaxAllocationNeedAvailableA(2)若此時(shí)P1請(qǐng)求資源，發(fā)出請(qǐng)求向量Request1(1,0,2)系統(tǒng)可以為滿足請(qǐng)求嗎？解：系統(tǒng)按銀行家算法進(jìn)行檢查：

Request1(1,0,2)<=Need1(1,2,2)

Request1(1,0,2)<=Available(3,3,2)

系統(tǒng)先假定可為P1分配資源，修改相關(guān)向量值：

利用安全性算法檢查此時(shí)系統(tǒng)是否安全。具體：MaxAllocationNeedAvailableABCABCABCABCP0P1P2P3P4753322902222433010200302211002743122600011431332資源總數(shù)

1057進(jìn)程資源某時(shí)刻資源分配情況30202023065(2)若此時(shí)P1請(qǐng)求資源，發(fā)出請(qǐng)求向量Request1(1,5327437457551057ABCWork＋AllocationABCABCABCtruetruetruetruetrue302211002010302020011431743600230532743745755P1P3P4P0P2FinishAllocationNeedWork進(jìn)程資源安全序列MaxAllocationNeedAvailableABCABCABCABCP0P1P2P3P4753322902222433010200302211002743122600011431332資源總數(shù)

1057302020230進(jìn)程資源某時(shí)刻資源分配情況66532ABCWork＋AllocABCABCABCABC332資源總數(shù)

1057743122600011431010200302211002753322902222433P0P1P2P3P4AvailableNeedAllocationMax進(jìn)程資源某時(shí)刻資源分配情況302020230（3）若此時(shí)P4請(qǐng)求資源，發(fā)出請(qǐng)求向量Request4(3,3,0)系統(tǒng)可以滿足請(qǐng)求嗎？

解：系統(tǒng)按銀行家算法進(jìn)行檢查：

Request4(3,3,0)<=Need4(4,3,1)

Request4(3,3,0)>Available(2,3,0)

因此，讓P4等待。67ABCABCABCAABCABCABCABC332資源總數(shù)

1057743122600011431010200302211002753322902222433P0P1P2P3P4AvailableNeedAllocationMax進(jìn)程資源某時(shí)刻資源分配情況302020230（4）若此時(shí)P0請(qǐng)求資源，發(fā)出請(qǐng)求向量Request0(0,2,0)系統(tǒng)可以滿足請(qǐng)求嗎？解：系統(tǒng)按銀行家算法進(jìn)行檢查：

Request0(0,2,0)<=Need0(7,4,3)

Request0(0,2,0)<=Available(2,3,0)

系統(tǒng)暫時(shí)先假定可為P0分配資源，并修改有關(guān)數(shù)據(jù)

進(jìn)行安全性檢查，Available(2,1,0)已不能滿足任何進(jìn)程的需要，故系統(tǒng)進(jìn)入不安全狀態(tài)，系統(tǒng)不能分配資源

03072321068ABCABCABCA3.7、死鎖的檢測(cè)與解除含義：通過系統(tǒng)的檢測(cè)機(jī)構(gòu)，及時(shí)地檢測(cè)出死鎖的發(fā)生，確定與死鎖有關(guān)的進(jìn)程和資源。方法：對(duì)資源分配圖進(jìn)行化簡(jiǎn)，檢查是否存在循環(huán)等待。1、資源分配圖P112含義：該圖是由一組結(jié)點(diǎn)N和一組邊E組成的一個(gè)對(duì)偶G＝（N，E）e=(Pi,ri)是資源請(qǐng)求邊，e=(ri，Pi)是資源分配邊3.7.1、死鎖的檢測(cè)693.7、死鎖的檢測(cè)與解除含義：通過系統(tǒng)的檢測(cè)機(jī)構(gòu)，及時(shí)地檢測(cè)P1P2r1r2資源分配圖資源請(qǐng)求邊資源分配邊進(jìn)程資源70P1P2r1r2資源分配圖資源請(qǐng)求邊資源分配邊進(jìn)程資源702、死鎖定理含義：

S為死鎖狀態(tài)的充分條件是：當(dāng)且僅當(dāng)S狀態(tài)的資源分配圖是不可完全簡(jiǎn)化的。該充分條件被稱為死鎖定理。簡(jiǎn)化方法：找一個(gè)既不阻塞又不孤立的進(jìn)程結(jié)點(diǎn)，消去所有的邊。

最終，當(dāng)所有進(jìn)程結(jié)點(diǎn)都成為孤立結(jié)點(diǎn)，則該圖稱為可完全簡(jiǎn)化的，否則，稱為不可完全簡(jiǎn)化的712、死鎖定理71P1P2r1r2資源分配圖的簡(jiǎn)化過程例1：資源分配圖的簡(jiǎn)化72P1P2r1r2資源分配圖的簡(jiǎn)化過程例1：資源分配圖的簡(jiǎn)化7練習(xí)題：對(duì)下圖進(jìn)行簡(jiǎn)化P1P2P3P4r1r273練習(xí)題：對(duì)下圖進(jìn)行簡(jiǎn)化P1P2P3P4r1r273

含義：將進(jìn)程從死鎖狀態(tài)中解脫出來。方法：

1、撤銷進(jìn)程：撤銷全部死鎖進(jìn)程或者選擇被撤進(jìn)程代價(jià)最小的。

2、剝奪資源：從其他進(jìn)程剝奪足夠的資源給死鎖進(jìn)程3.7.2、死鎖的解除74含義：將進(jìn)程從死鎖狀態(tài)中解脫出來。3.7.2、死鎖危險(xiǎn)區(qū)0占用輸入機(jī)

A進(jìn)程的進(jìn)展占用打印機(jī)B進(jìn)程的進(jìn)展禁區(qū)75危險(xiǎn)區(qū)0占用輸?shù)谌?/p>

處理機(jī)調(diào)度與死鎖第一節(jié)

處理機(jī)調(diào)度的層次第二節(jié)

調(diào)度隊(duì)列模型和調(diào)度準(zhǔn)則第三節(jié)

調(diào)度算法第四節(jié)實(shí)時(shí)調(diào)度第五節(jié)

產(chǎn)生死鎖的原因和必要條件第六節(jié)預(yù)防死鎖的方法第七節(jié)死鎖的檢測(cè)和解除76第三章

處理機(jī)調(diào)度與死鎖第一節(jié)

處理機(jī)調(diào)度的層次13.1處理機(jī)調(diào)度的層次高級(jí)調(diào)度低級(jí)調(diào)度中級(jí)調(diào)度773.1處理機(jī)調(diào)度的層次高級(jí)調(diào)度23.1.1、高級(jí)調(diào)度高級(jí)調(diào)度（作業(yè)調(diào)度/長(zhǎng)程調(diào)度）決定把外存上處于后備隊(duì)列中的哪些作業(yè)調(diào)入內(nèi)存。調(diào)度對(duì)象：作業(yè)1、作業(yè)和作業(yè)步作業(yè)：程序+數(shù)據(jù)+作業(yè)說明書作業(yè)步：作業(yè)運(yùn)行期間的每個(gè)加工步驟例如：編譯

連結(jié)裝配

運(yùn)行783.1.1、高級(jí)調(diào)度高級(jí)調(diào)度（作業(yè)調(diào)度/長(zhǎng)程調(diào)度）1、作業(yè)2、作業(yè)控制塊（JCB）JCB：保存了系統(tǒng)對(duì)作業(yè)進(jìn)行管理和調(diào)度所需的全部信息。作業(yè)在系統(tǒng)中存在的標(biāo)志。JCB包含的內(nèi)容有：作業(yè)標(biāo)識(shí)、用戶名稱、用戶賬號(hào)、作業(yè)類型、作業(yè)狀態(tài)、調(diào)度信息、資源需求、時(shí)間信息、資源使用情況等。JCB的創(chuàng)建和回收792、作業(yè)控制塊（JCB）43、高級(jí)調(diào)度（作業(yè)/長(zhǎng)程/接納調(diào)度）概念：決定把外存上處于后備隊(duì)列中的哪些作業(yè)調(diào)入內(nèi)存，并為它們創(chuàng)建進(jìn)程、分配必要的資源，準(zhǔn)備執(zhí)行。多用于批處理系統(tǒng)每次調(diào)度時(shí)要考慮：

(1)接納多少作業(yè)：取決于多道程序度

(2)接納哪些作業(yè)：取決于調(diào)度算法作業(yè)調(diào)度運(yùn)行頻率低，幾分鐘一次系統(tǒng)規(guī)模運(yùn)行速度803、高級(jí)調(diào)度（作業(yè)/長(zhǎng)程/接納調(diào)度）系統(tǒng)規(guī)模5低級(jí)調(diào)度（進(jìn)程/短程調(diào)度）決定就緒隊(duì)列中的哪個(gè)進(jìn)程應(yīng)獲得處理機(jī)，然后再由分派程序執(zhí)行把處理機(jī)分配給該進(jìn)程的具體操作是最基本的調(diào)度，在三種類型的OS中都必須配置3.1.2、低級(jí)調(diào)度1、低級(jí)調(diào)度的功能保存處理機(jī)的現(xiàn)場(chǎng)信息按照某種算法選取進(jìn)程把處理機(jī)分配給進(jìn)程81低級(jí)調(diào)度（進(jìn)程/短程調(diào)度）3.1.2、低級(jí)調(diào)度1、低級(jí)調(diào)2、進(jìn)程調(diào)度中的三個(gè)基本機(jī)制排隊(duì)器分派器（分派程序）上下文切換機(jī)制3、進(jìn)程調(diào)度方式非搶占方式搶占方式822、進(jìn)程調(diào)度中的三個(gè)基本機(jī)制3、進(jìn)程調(diào)度方式71）非搶占方式：一旦進(jìn)程獲得處理機(jī)，則一直執(zhí)行，直到該進(jìn)程完成或被阻塞此方式下，可能引起進(jìn)程調(diào)度的因素：（1）正在執(zhí)行的進(jìn)程執(zhí)行完畢，或因發(fā)生某事件不能再繼續(xù)執(zhí)行（2）執(zhí)行中的進(jìn)程因提出I/O請(qǐng)求而暫停執(zhí)行（3）在進(jìn)程通信或同步過程中執(zhí)行了某原語，P操作等優(yōu)點(diǎn)：簡(jiǎn)單、系統(tǒng)開銷小，適合大多數(shù)批處理系統(tǒng)缺點(diǎn)：無法滿足緊急任務(wù)的需要，不適合實(shí)時(shí)系統(tǒng)831）非搶占方式：82）搶占方式：允許調(diào)度程序根據(jù)某原則，暫停正在執(zhí)行的進(jìn)程，將處理機(jī)重新分配搶占原則：優(yōu)先權(quán)原則就緒的高優(yōu)先權(quán)進(jìn)程有權(quán)搶占低優(yōu)先權(quán)進(jìn)程的CPU短作業(yè)優(yōu)先原則就緒的短作業(yè)(進(jìn)程)有權(quán)搶占長(zhǎng)作業(yè)(進(jìn)程)的CPU時(shí)間片原則一個(gè)時(shí)間片用完后，系統(tǒng)重新進(jìn)行進(jìn)程調(diào)度842）搶占方式：9中級(jí)調(diào)度（中程調(diào)度）目的：提高內(nèi)存利用率和系統(tǒng)吞吐量按一定的算法將外存上已具備運(yùn)行條件的掛起進(jìn)程換入內(nèi)存，掛到就緒隊(duì)列上，準(zhǔn)備執(zhí)行；而將內(nèi)存中處于阻塞狀態(tài)的某些進(jìn)程換出至外存。3.1.3、中級(jí)調(diào)度85中級(jí)調(diào)度（中程調(diào)度）3.1.3、中級(jí)調(diào)度10調(diào)度隊(duì)列模型選擇調(diào)度方式和調(diào)度算法的若干準(zhǔn)則3.2、調(diào)度隊(duì)列模型86調(diào)度隊(duì)列模型3.2、調(diào)度隊(duì)列模型113.2.1、調(diào)度隊(duì)列模型僅具有進(jìn)程調(diào)度的調(diào)度隊(duì)列模型就緒隊(duì)列阻塞隊(duì)列CPU時(shí)間片完交互用戶進(jìn)程調(diào)度進(jìn)程完成等待事件事件發(fā)生……具有高、低兩級(jí)調(diào)度的調(diào)度隊(duì)列模型就緒隊(duì)列阻塞隊(duì)列CPU時(shí)間片完作業(yè)調(diào)度進(jìn)程調(diào)度進(jìn)程完成等待事件1阻塞隊(duì)列阻塞隊(duì)列等待事件2等待事件n事件1發(fā)生事件2發(fā)生事件n發(fā)生后備隊(duì)列

具有高、低、中三級(jí)調(diào)度的調(diào)度隊(duì)列模型就緒隊(duì)列緒就、掛起隊(duì)列CPU時(shí)間片完作業(yè)調(diào)度進(jìn)程調(diào)度進(jìn)程完成事件出現(xiàn)阻塞隊(duì)列掛起等待事件中級(jí)調(diào)度事件發(fā)生后備隊(duì)列塞阻、掛起隊(duì)列掛起873.2.1、調(diào)度隊(duì)列模型就緒隊(duì)列阻塞隊(duì)列CPU時(shí)間片完交互用3.2.2、選擇調(diào)度方式和算法的選擇準(zhǔn)則1、面向用戶的準(zhǔn)則（1）周轉(zhuǎn)時(shí)間短——評(píng)價(jià)批處理系統(tǒng)

周轉(zhuǎn)時(shí)間：是指從作業(yè)被提交系統(tǒng)開始，到作業(yè)完成為止的這段時(shí)間間隔。包括四部分時(shí)間：

1）等待作業(yè)調(diào)度時(shí)間

2）等待進(jìn)程調(diào)度時(shí)間

3）執(zhí)行時(shí)間

4）進(jìn)程等待I/O操作完成時(shí)間883.2.2、選擇調(diào)度方式和算法的選擇準(zhǔn)則1、面向用戶的準(zhǔn)則包平均周轉(zhuǎn)時(shí)間：帶權(quán)周轉(zhuǎn)時(shí)間：周轉(zhuǎn)時(shí)間服務(wù)時(shí)間平均帶權(quán)周轉(zhuǎn)時(shí)間：89平均周轉(zhuǎn)時(shí)間：帶權(quán)周轉(zhuǎn)時(shí)間：周轉(zhuǎn)時(shí)間服務(wù)時(shí)間平均帶權(quán)周轉(zhuǎn)時(shí)間（2）響應(yīng)時(shí)間快——評(píng)價(jià)分時(shí)系統(tǒng)

響應(yīng)時(shí)間：從用戶通過鍵盤提交一個(gè)請(qǐng)求開始直至系統(tǒng)首次產(chǎn)生響應(yīng)為止。

包括三部分時(shí)間：1）從鍵盤輸入的請(qǐng)求信息傳送到處理機(jī)的時(shí)間2）處理時(shí)間3）響應(yīng)信息回送終端的時(shí)間90（2）響應(yīng)時(shí)間快——評(píng)價(jià)分時(shí)系統(tǒng)15（3）截止時(shí)間保證——評(píng)價(jià)實(shí)時(shí)系統(tǒng)

截止時(shí)間：任務(wù)必須開始執(zhí)行的最遲時(shí)間，或必須完成的最遲時(shí)間。（4）優(yōu)先權(quán)準(zhǔn)則——三種系統(tǒng)中皆適用91（3）截止時(shí)間保證——評(píng)價(jià)實(shí)時(shí)系統(tǒng)162、面向系統(tǒng)的準(zhǔn)則系統(tǒng)吞吐量高——評(píng)價(jià)批處理系統(tǒng)處理機(jī)利用率好——針對(duì)大中型系統(tǒng)各類資源的平衡利用——對(duì)大中型系統(tǒng)922、面向系統(tǒng)的準(zhǔn)則173.3

調(diào)度算法先來先服務(wù)和短作業(yè)（進(jìn)程）優(yōu)先調(diào)度算法高優(yōu)先權(quán)先調(diào)度算法基于時(shí)間片的輪轉(zhuǎn)調(diào)度算法933.3

調(diào)度算法先來先服務(wù)和短作業(yè)（進(jìn)程）優(yōu)先調(diào)度算法183.2.1、先來先服務(wù)和短作業(yè)（進(jìn)程）優(yōu)先調(diào)度算法1、先來先服務(wù)（FCFS）調(diào)度算法可用于作業(yè)調(diào)度和進(jìn)程調(diào)度用于作業(yè)調(diào)度：每次從后備作業(yè)隊(duì)列中選擇最先進(jìn)入的作業(yè)，將它們調(diào)入內(nèi)存，為它們分配資源、創(chuàng)建進(jìn)程，然后掛到就緒進(jìn)程隊(duì)列上。943.2.1、先來先服務(wù)和短作業(yè)（進(jìn)程）優(yōu)先調(diào)度算法1、先來先用于進(jìn)程調(diào)度：每次從就緒進(jìn)程隊(duì)列中選擇最先進(jìn)入的進(jìn)程，為之分配處理機(jī)，使之投入運(yùn)行。直到運(yùn)行完成進(jìn)程才會(huì)讓出處理機(jī)--非搶占式。有利于長(zhǎng)作業(yè)，而不利于短作業(yè)。95用于進(jìn)程調(diào)度：20進(jìn)程名到達(dá)時(shí)間服務(wù)時(shí)間開始執(zhí)行時(shí)間完成時(shí)間周轉(zhuǎn)時(shí)間帶權(quán)周轉(zhuǎn)時(shí)間A010111B110011011001C21101102100100D31001022021991.99性能評(píng)價(jià)：周轉(zhuǎn)時(shí)間=完成時(shí)間–到達(dá)時(shí)間帶權(quán)周轉(zhuǎn)時(shí)間=周轉(zhuǎn)時(shí)間/服務(wù)（運(yùn)行）時(shí)間96進(jìn)程到達(dá)服務(wù)開始執(zhí)完成周轉(zhuǎn)帶權(quán)周性能評(píng)價(jià)：212、短作業(yè)/進(jìn)程優(yōu)先（SJF/SPF）短作業(yè)優(yōu)先（SJF）從后備隊(duì)列中選擇估計(jì)運(yùn)行時(shí)間最短的作業(yè)，調(diào)入內(nèi)存運(yùn)行。短進(jìn)程優(yōu)先（SPF）從就緒隊(duì)列中選出估計(jì)運(yùn)行時(shí)間最短的進(jìn)程，將處理機(jī)分配給它，使它立即執(zhí)行。直到運(yùn)行完成進(jìn)程才會(huì)讓出處理機(jī)--非搶占式。缺點(diǎn)：對(duì)長(zhǎng)作業(yè)不利，有可能長(zhǎng)期不被調(diào)度；完全沒考慮作業(yè)的緊迫程度（某些特殊的）；用戶做出的估計(jì)時(shí)間帶有很大的主觀性。972、短作業(yè)/進(jìn)程優(yōu)先（SJF/SPF）短作業(yè)優(yōu)先（SJF2.259133.5141844E3.116182101252C2.678926731B1.5365.5111423D2.11帶權(quán)周轉(zhuǎn)時(shí)間84周轉(zhuǎn)時(shí)間4完成時(shí)間FJS2.81帶權(quán)周轉(zhuǎn)時(shí)間94周轉(zhuǎn)時(shí)間4完成時(shí)間FCFS4服務(wù)時(shí)間0到達(dá)時(shí)間平均A進(jìn)程名

作調(diào)業(yè)度情算況法周轉(zhuǎn)時(shí)間=完成時(shí)間–到達(dá)時(shí)間帶權(quán)周轉(zhuǎn)時(shí)間=周轉(zhuǎn)時(shí)間/服務(wù)時(shí)間982.259133.5141844E3.116182101253.3.2、高優(yōu)先權(quán)先調(diào)度算法既能用于作業(yè)調(diào)度，也可用于進(jìn)程調(diào)度。作業(yè)調(diào)度：從后備隊(duì)列中選擇若干個(gè)優(yōu)先權(quán)最高的作業(yè)裝入內(nèi)存。進(jìn)程調(diào)度：把處理機(jī)分配給就緒隊(duì)列中優(yōu)先權(quán)最高的進(jìn)程兩種占用CPU的方式：非搶占式優(yōu)先權(quán)算法搶占式優(yōu)先權(quán)算法1、優(yōu)先權(quán)調(diào)度算法的類型993.3.2、高優(yōu)先權(quán)先調(diào)度算法既能用于作業(yè)調(diào)度，也可用于進(jìn)程非搶占式優(yōu)先權(quán)算法系統(tǒng)一旦把處理機(jī)分配給就緒隊(duì)列中優(yōu)先權(quán)最高的進(jìn)程后，該進(jìn)程就一直執(zhí)行下去，直至完成；或因發(fā)生某事件使該進(jìn)程放棄處理機(jī)時(shí)，系統(tǒng)方可再將處理機(jī)重新分配給另一優(yōu)先權(quán)最高的進(jìn)程。主要用于批處理系統(tǒng)100非搶占式優(yōu)先權(quán)算法25搶占式優(yōu)先權(quán)算法新的就緒進(jìn)程i，優(yōu)先權(quán)Pi。正在執(zhí)行的進(jìn)程j，優(yōu)先權(quán)Pj。若Pi<=Pj，原進(jìn)程j繼續(xù)執(zhí)行。若Pi>Pj，做進(jìn)程切換。新進(jìn)程i執(zhí)行。優(yōu)點(diǎn)：能更好的滿足緊迫作業(yè)的要求。主要用于比較嚴(yán)格的實(shí)時(shí)系統(tǒng)。101搶占式優(yōu)先權(quán)算法262、優(yōu)先權(quán)的類型

1）靜態(tài)優(yōu)先權(quán)在進(jìn)程創(chuàng)建時(shí)確定的，在進(jìn)程整個(gè)運(yùn)行期間保持不變優(yōu)先權(quán)利用某一范圍的整數(shù)來表示，該整數(shù)稱為優(yōu)先數(shù)。如：0—7，0—255確定優(yōu)先權(quán)的依據(jù)：（1）進(jìn)程類型（2）進(jìn)程對(duì)資源的需求（3）用戶要求1022、優(yōu)先權(quán)的類型優(yōu)先權(quán)利用某一范圍的整數(shù)來表示，該整數(shù)稱為優(yōu)

注：規(guī)定優(yōu)先數(shù)越小，其優(yōu)先權(quán)越高4/348334C15/81517482B119118D帶權(quán)周轉(zhuǎn)時(shí)間周轉(zhuǎn)時(shí)間155完成時(shí)間2優(yōu)先權(quán)非搶占式優(yōu)先權(quán)算法5服務(wù)時(shí)間0到達(dá)時(shí)間A進(jìn)程名

作調(diào)業(yè)度情算況法平均6.251.3例：非搶占式優(yōu)先權(quán)算法103注：規(guī)定優(yōu)先數(shù)越小，其優(yōu)先權(quán)越高4/348334C15/8t(等待)優(yōu)先權(quán)t(運(yùn)行)優(yōu)先權(quán)2)動(dòng)態(tài)優(yōu)先權(quán)在進(jìn)程創(chuàng)建時(shí)創(chuàng)立的優(yōu)先權(quán)，可隨進(jìn)程的推進(jìn)或等待時(shí)間的增加而改變。如等待時(shí)間長(zhǎng)，優(yōu)先權(quán)升高。104t(等待)優(yōu)先權(quán)t(運(yùn)行)優(yōu)先權(quán)2)動(dòng)態(tài)優(yōu)先權(quán)29

等待時(shí)間+要求服務(wù)時(shí)間優(yōu)先權(quán)=------------------------------------

要求服務(wù)時(shí)間等待時(shí)間+要求服務(wù)時(shí)間響應(yīng)時(shí)間響應(yīng)比(Rp)=------------------------------------=-------------------

要求服務(wù)時(shí)間要求服務(wù)時(shí)間3、高響應(yīng)比優(yōu)先調(diào)度算法(HRRN)為每個(gè)進(jìn)程引入動(dòng)態(tài)優(yōu)先權(quán)，隨著等待時(shí)間增加優(yōu)先權(quán)提高。優(yōu)點(diǎn)：等待時(shí)間相同，短作業(yè)優(yōu)先權(quán)高(即SPF)要求服務(wù)時(shí)間相同，等待時(shí)間長(zhǎng)，優(yōu)先權(quán)高(即FCFS)對(duì)于長(zhǎng)作業(yè)，在等待足夠時(shí)間后，可獲得處理機(jī)105等待時(shí)間+要3.571528E2.2591344C1.177962B2.8142056D2.141帶權(quán)周轉(zhuǎn)時(shí)間83周轉(zhuǎn)時(shí)間3完成時(shí)間3服務(wù)時(shí)間0到達(dá)時(shí)間平均A進(jìn)程名

作調(diào)業(yè)度情算況法RC＝1+(9-4)/4=2.25RD＝1+(9-6)/5=1.6RE＝1+(9-8)/2=1.5RD＝1+(13-6)/5=2.4RE＝1+(13-8)/2=3.5執(zhí)行順序：A－>B－>C－>E－>DHRRN（R大，優(yōu)先權(quán)高）1063.571528E2.2591344C1.177962B、基于時(shí)間片的輪轉(zhuǎn)調(diào)度算法1、時(shí)間片輪轉(zhuǎn)法1）基本原理系統(tǒng)將所有的就緒進(jìn)程按FIFO原則排成一個(gè)隊(duì)列，將CPU分配給隊(duì)首進(jìn)程，執(zhí)行一個(gè)時(shí)間片。在時(shí)間片內(nèi)進(jìn)程未完，則插入就緒隊(duì)列未尾，CPU交給下一個(gè)進(jìn)程。2）時(shí)間片大小的確定時(shí)間片略大于一次典型的交互所需要的時(shí)間。1073.3.3、基于時(shí)間片的輪轉(zhuǎn)調(diào)度算法1、時(shí)間片輪轉(zhuǎn)法1）基本3.3313173.33131744E2.259113.5141642C2673.67111231B5101336923D帶權(quán)周轉(zhuǎn)時(shí)間2.58.4周轉(zhuǎn)時(shí)間144完成時(shí)間RRq=4帶權(quán)周轉(zhuǎn)時(shí)間3.4611.8周轉(zhuǎn)時(shí)間3.751515完成時(shí)間RRq=14服務(wù)時(shí)間0到達(dá)時(shí)間平均A進(jìn)程名

作調(diào)業(yè)度情算況法周轉(zhuǎn)時(shí)間=完成時(shí)間–到達(dá)時(shí)間帶權(quán)周轉(zhuǎn)時(shí)間=周轉(zhuǎn)時(shí)間/服務(wù)時(shí)間1083.3313173.33131744E2.259113.512、多級(jí)反饋隊(duì)列調(diào)度算法

原理：設(shè)置多個(gè)就緒隊(duì)列，并為各個(gè)隊(duì)列賦予不同的優(yōu)先級(jí)和不同長(zhǎng)度的時(shí)間片；新創(chuàng)建的進(jìn)程掛到第一優(yōu)先級(jí)的隊(duì)列后，然后按FCFS

原則排隊(duì)等待調(diào)度。當(dāng)輪到其執(zhí)行時(shí)，如它能在時(shí)間片內(nèi)完成，便撤離系統(tǒng)；如果不能完成，便被掛入第二級(jí)隊(duì)列后，……，最后一級(jí)隊(duì)列采用時(shí)間片輪轉(zhuǎn)法；僅當(dāng)?shù)谝患?jí)隊(duì)列空閑時(shí)，調(diào)度程序才調(diào)度第二級(jí)隊(duì)列中的進(jìn)程運(yùn)行，依次類推……；新進(jìn)程可搶占低級(jí)進(jìn)程的處理機(jī)。1092、多級(jí)反饋隊(duì)列調(diào)度算法原理：34……多級(jí)反饋隊(duì)列調(diào)度算法示意圖CPU時(shí)間片完進(jìn)程調(diào)度進(jìn)程完成就緒隊(duì)列一就緒隊(duì)列二就緒隊(duì)列三就緒隊(duì)列n時(shí)間片完時(shí)間片完110CPU時(shí)間進(jìn)程進(jìn)程完成就緒隊(duì)列一就緒隊(duì)列二就緒隊(duì)列三就緒隊(duì)列就級(jí)1緒隊(duì)列空就級(jí)2緒隊(duì)列就級(jí)3緒隊(duì)列運(yùn)行等待12354時(shí)間片小－－－－大優(yōu)先級(jí)高－－－－低111就級(jí)1緒隊(duì)列空就級(jí)2緒隊(duì)列就級(jí)3緒隊(duì)列運(yùn)行等待12354時(shí)間多級(jí)反饋隊(duì)列調(diào)度算法的性能多級(jí)反饋隊(duì)列調(diào)度算法能較好地滿足各種類型用戶（進(jìn)程）的需要：終端（交互）型作業(yè)用戶短批處理作業(yè)用戶長(zhǎng)批處理作業(yè)用戶112多級(jí)反饋隊(duì)列調(diào)度算法的性能373.3.4、基于公平原則的調(diào)度算法1、保證調(diào)度算法如果系統(tǒng)中有n個(gè)相同類型的進(jìn)程同時(shí)運(yùn)行，保證每個(gè)進(jìn)程都獲得相同的處理機(jī)時(shí)間1/n。2、公平分享調(diào)度算法使所有用戶能獲得相同的處理機(jī)時(shí)間。1133.3.4、基于公平原則的調(diào)度算法1、保證調(diào)度算法如果系統(tǒng)中3.4實(shí)時(shí)調(diào)度實(shí)現(xiàn)實(shí)時(shí)調(diào)度的基本概念和條件實(shí)時(shí)調(diào)度算法的分類常見的幾種實(shí)時(shí)調(diào)度算法選學(xué)1143.4實(shí)時(shí)調(diào)度實(shí)現(xiàn)實(shí)時(shí)調(diào)度的基本概念和條件選學(xué)391.實(shí)時(shí)調(diào)度是為了完成實(shí)時(shí)處理任務(wù)而分配處理機(jī)的調(diào)度方法。2.硬實(shí)時(shí)任務(wù)要求計(jì)算機(jī)系統(tǒng)必須在用戶給定的時(shí)限內(nèi)完成

3.軟實(shí)時(shí)任務(wù)允許計(jì)算機(jī)系統(tǒng)在用戶給定的時(shí)限左右處理完畢。提供更詳細(xì)的調(diào)度信息：就緒時(shí)間、開始截止時(shí)間或完成截止時(shí)間、處理時(shí)間、資源要求、優(yōu)先級(jí)等；含有硬實(shí)時(shí)任務(wù)的實(shí)時(shí)系統(tǒng)中，廣泛采用基于優(yōu)先級(jí)的搶占式調(diào)度策略1151.實(shí)時(shí)調(diào)度是為了完成實(shí)時(shí)處理任務(wù)而分配處理機(jī)的調(diào)度實(shí)時(shí)調(diào)度算法分類：非搶占式輪轉(zhuǎn)調(diào)度算法：只適用于一般實(shí)時(shí)信息處理系統(tǒng)非搶占式優(yōu)先級(jí)調(diào)度算法：優(yōu)先級(jí)最高的實(shí)時(shí)任務(wù)排在就緒隊(duì)列隊(duì)首，當(dāng)前任務(wù)終止或完成后才被調(diào)度。

基于時(shí)鐘中斷搶占式優(yōu)先級(jí)調(diào)度算法：新到的實(shí)時(shí)任務(wù)的優(yōu)先級(jí)高于當(dāng)前任務(wù)時(shí)，并不立即搶占CPU，而是等到時(shí)鐘中斷到來，才進(jìn)行切換。用于大多數(shù)的實(shí)時(shí)系統(tǒng)中。

立即搶占的優(yōu)先級(jí)調(diào)度算法：這種算法適用于實(shí)時(shí)要求比較嚴(yán)格的實(shí)時(shí)控制系統(tǒng)。116實(shí)時(shí)調(diào)度算法分類：非搶占式輪轉(zhuǎn)調(diào)度算法：只適用于一般實(shí)時(shí)信息常用的幾種實(shí)時(shí)調(diào)度算法1、最早截止時(shí)間優(yōu)先算法（EDF）該算法根據(jù)任務(wù)的開始截止時(shí)間來確定任務(wù)的優(yōu)先級(jí)。截止時(shí)間越早，優(yōu)先級(jí)越高。該算法要求實(shí)時(shí)任務(wù)的就緒隊(duì)列按任務(wù)截止時(shí)間的早晚排序。調(diào)度程序總選擇隊(duì)首的任務(wù)執(zhí)行。

該算法可用于搶占式和非搶占式調(diào)度。t任務(wù)到達(dá)任務(wù)執(zhí)行開始截止時(shí)間134211224433非搶占式調(diào)度方式117常用的幾種實(shí)時(shí)調(diào)度算法1、最早截止時(shí)間優(yōu)先算法（EDF）t任2、最低松弛度優(yōu)先算法（LLF）該算法根據(jù)任務(wù)的松弛度來確定任務(wù)的優(yōu)先級(jí)。松弛度越低，優(yōu)先級(jí)越高。松弛度＝任務(wù)必須完成的時(shí)間－運(yùn)行時(shí)間－當(dāng)前時(shí)間該算法要求實(shí)時(shí)任務(wù)的就緒隊(duì)列按松弛度排序。調(diào)度程序總選擇隊(duì)首的任務(wù)執(zhí)行。該算法主要用于搶占式調(diào)度方式。1182、最低松弛度優(yōu)先算法（LLF）43松弛度＝任務(wù)必須完成的時(shí)間－運(yùn)行時(shí)間－當(dāng)前時(shí)間例：實(shí)時(shí)系統(tǒng)中有兩個(gè)周期性實(shí)時(shí)任務(wù)A、B，任務(wù)A每20ms執(zhí)行一次，執(zhí)行時(shí)間10ms；任務(wù)B每50ms執(zhí)行一次，執(zhí)行時(shí)間25ms。采用搶占式LLF算法：t020406080100120140160A1A2A3A4A5A6A7A8B1B2B3任務(wù)AB每次必須完成的時(shí)間松弛度t010203040455055607080A1=10B1=25A2=20B1=15A2=0B1=15A3=10B1=5A3=5B2=30此時(shí)執(zhí)行B2A4=0B2=20A4完B2=10119松弛度＝任務(wù)必須完成的時(shí)間－運(yùn)行時(shí)間－當(dāng)前時(shí)間例：實(shí)時(shí)系統(tǒng)中3、優(yōu)先級(jí)倒置問題（1）問題的形成即OS中廣泛采用的優(yōu)先級(jí)調(diào)度算法和搶占方式。舉例:三個(gè)獨(dú)立進(jìn)程P1、P2、P3，優(yōu)先級(jí)由高到低。P1、P3共享臨界資源進(jìn)行交互。代碼：P1：...P(mutex);CS-1;V(mutex)...;P2:...program2...;P3:...P(mutex);CS-3;V(mutex)...;執(zhí)行順序：P3—>P2(搶占)—>P1（阻塞）—>P2(執(zhí)行結(jié)束)—>P3(執(zhí)行結(jié)束)—>P1(執(zhí)行結(jié)束)問題：P1優(yōu)先級(jí)最高，但最后執(zhí)行結(jié)束1203、優(yōu)先級(jí)倒置問題舉例:三個(gè)獨(dú)立進(jìn)程P1、P2、P33、優(yōu)先級(jí)倒置問題（續(xù)）（2）問題的解決方案方案2：建立在動(dòng)態(tài)優(yōu)先級(jí)繼承基礎(chǔ)上。規(guī)定：P1阻塞時(shí)由P3繼承P1的優(yōu)先級(jí)，一直保持到P3退出臨界區(qū)。目的：防止P2進(jìn)程插進(jìn)來，延緩P3退出臨界區(qū)。方案1：P3進(jìn)入臨界區(qū)后不允許處理機(jī)被搶占。適用情況：系統(tǒng)中臨界區(qū)較短且不多。1213、優(yōu)先級(jí)倒置問題（續(xù)）方案2：建立在動(dòng)態(tài)優(yōu)先級(jí)繼承基礎(chǔ)上。3.5

產(chǎn)生死鎖的原因和必要條件產(chǎn)生死鎖的原因產(chǎn)生死鎖的必要條件處理死鎖的基本方法1223.5

產(chǎn)生死鎖的原因和必要條件產(chǎn)生死鎖的原因473.5.1、產(chǎn)生死鎖的原因一、死鎖（Deadlock）定義：死鎖是指兩個(gè)或兩個(gè)以上的進(jìn)程在運(yùn)行過程中，因爭(zhēng)奪資源而造成的一種互相等待（誰也無法再繼續(xù)推進(jìn)）的現(xiàn)象，若無外力作用，它們都將無法推進(jìn)下去。二、產(chǎn)生死鎖的原因：1、競(jìng)爭(zhēng)資源2、進(jìn)程間推進(jìn)順序非法1233.5.1、產(chǎn)生死鎖的原因一、死鎖（Deadlock）定義：1、競(jìng)爭(zhēng)資源引起進(jìn)程死鎖

1.1資源的兩種分類：可搶占性資源：CPU、RAM等；不可搶占性資源：打印機(jī)、磁帶機(jī)等；可重用性資源：打印機(jī)可消耗性資源：進(jìn)程通信中的消息、數(shù)據(jù)等1241、競(jìng)爭(zhēng)資源引起進(jìn)程死鎖可搶占性資源：CPU、RAM等；可重1.2競(jìng)爭(zhēng)不可搶占性資源引起死鎖：系統(tǒng)中配備的非剝奪性資源的數(shù)量不能滿足諸進(jìn)程運(yùn)行的需要時(shí)，會(huì)使進(jìn)程因爭(zhēng)奪資源而陷入僵局。打印機(jī)P1磁帶機(jī)P21.3競(jìng)爭(zhēng)可消耗資源引起死鎖：1251.2競(jìng)爭(zhēng)不可搶占性資源引起死鎖：打印機(jī)P1磁帶機(jī)P21.2、進(jìn)程間推進(jìn)順序不當(dāng)引起死鎖進(jìn)程推進(jìn)順序合法——不會(huì)導(dǎo)致死鎖進(jìn)程推進(jìn)順序非法——可能會(huì)導(dǎo)致死圖1：順序合法消息1P1消息2P2P3消息3圖2：順序非法消息1P1消息2P2P3消息31262、進(jìn)程間推進(jìn)順序不當(dāng)引起死鎖圖1：順序合法消息1P1消息23.5.2、產(chǎn)生死鎖的必要條件1、互斥條件一個(gè)資源一次只能被一個(gè)進(jìn)程使用。2、請(qǐng)求和保持條件（部分分配）保留已經(jīng)得到的資源，還要求其它的資源。3、不可搶占條件資源只能被占有者釋放，不能被其它進(jìn)程強(qiáng)行搶占。4、循環(huán)等待條件（循環(huán)等待）系統(tǒng)中的進(jìn)程形成了環(huán)形的資源請(qǐng)求鏈。1273.5.2、產(chǎn)生死鎖的必要條件1、互斥條件523.5.3、處理死鎖的基本方法（1）預(yù)防死鎖（2）避免死鎖（3）檢測(cè)死鎖（4）解除死鎖1283.5.3、處理死鎖的基本方法（1）預(yù)防死鎖533.6預(yù)防死鎖的方法預(yù)防死鎖系統(tǒng)安全狀態(tài)利用銀行家算法避免死鎖1293.6預(yù)防死鎖的方法預(yù)防死鎖543.6.1、預(yù)防死鎖一、預(yù)防死鎖的實(shí)質(zhì)：通過設(shè)置某些限制條件，預(yù)防發(fā)生死鎖。二、預(yù)防死鎖的方法：

“互斥條件”——由資源的性質(zhì)決定。

1、摒棄“請(qǐng)求和保持”條件在開始運(yùn)行前（創(chuàng)建時(shí)），一次性分配給進(jìn)程它所需的“全部”資源。簡(jiǎn)單易實(shí)現(xiàn)，安全性高；資源浪費(fèi)。1303.6.1、預(yù)防死鎖一、預(yù)防死鎖的實(shí)質(zhì)：552、摒棄“不可搶占”條件當(dāng)進(jìn)程有新的資源請(qǐng)求時(shí)，如果得不到滿足，要先釋放原先占有的資源