1、第三章第三章處理機(jī)調(diào)度與死鎖處理機(jī)調(diào)度與死鎖第一節(jié)第一節(jié)處理機(jī)調(diào)度的層次處理機(jī)調(diào)度的層次第二節(jié)第二節(jié)調(diào)度隊(duì)列模型和調(diào)度準(zhǔn)則調(diào)度隊(duì)列模型和調(diào)度準(zhǔn)則第三節(jié)第三節(jié)調(diào)度算法調(diào)度算法第四節(jié)第四節(jié)實(shí)時調(diào)度實(shí)時調(diào)度第五節(jié)第五節(jié)產(chǎn)生死鎖的原因和必要條件產(chǎn)生死鎖的原因和必要條件第六節(jié)第六節(jié)預(yù)防死鎖的方法預(yù)防死鎖的方法第七節(jié)第七節(jié)死鎖的檢測和解除死鎖的檢測和解除3.1 處理機(jī)調(diào)度的層次處理機(jī)調(diào)度的層次高級調(diào)度高級調(diào)度低級調(diào)度低級調(diào)度中級調(diào)度中級調(diào)度3.1.1、高級調(diào)度、高級調(diào)度高級調(diào)度高級調(diào)度（作業(yè)調(diào)度（作業(yè)調(diào)度/ 長程調(diào)度）長程調(diào)度）l決定把外存上處于后備隊(duì)列中的哪些作業(yè)調(diào)入內(nèi)決定把外存上處于后備隊(duì)列中的哪些作

2、業(yè)調(diào)入內(nèi)存。存。l調(diào)度對象：作業(yè)調(diào)度對象：作業(yè)1、作業(yè)和作業(yè)步、作業(yè)和作業(yè)步l作業(yè)：程序 + 數(shù)據(jù) + 作業(yè)說明書l作業(yè)步：作業(yè)運(yùn)行期間的每個加工步驟例如：編譯例如：編譯 連結(jié)裝配連結(jié)裝配 運(yùn)行運(yùn)行2、作業(yè)控制塊、作業(yè)控制塊（JCB）lJCB：保存了系統(tǒng)對作業(yè)進(jìn)行管理和調(diào)度所需的保存了系統(tǒng)對作業(yè)進(jìn)行管理和調(diào)度所需的全部信息。作業(yè)在系統(tǒng)中存在的全部信息。作業(yè)在系統(tǒng)中存在的標(biāo)志標(biāo)志。lJCB包含的內(nèi)容有：包含的內(nèi)容有：作業(yè)標(biāo)識、用戶名稱、用戶作業(yè)標(biāo)識、用戶名稱、用戶賬號、作業(yè)類型、作業(yè)狀態(tài)、調(diào)度信息、資源需賬號、作業(yè)類型、作業(yè)狀態(tài)、調(diào)度信息、資源需求、時間信息、資源使用情況等。求、時間信息、資源使

3、用情況等。lJCB的創(chuàng)建和回收的創(chuàng)建和回收3、高級調(diào)度（作業(yè)、高級調(diào)度（作業(yè) / 長程長程 / 接納調(diào)度）接納調(diào)度）l概念：概念：決定把外存上處于后備隊(duì)列中的哪些作業(yè)決定把外存上處于后備隊(duì)列中的哪些作業(yè)調(diào)入內(nèi)存，并為它們創(chuàng)建進(jìn)程、分配必要的資源，調(diào)入內(nèi)存，并為它們創(chuàng)建進(jìn)程、分配必要的資源，準(zhǔn)備執(zhí)行。準(zhǔn)備執(zhí)行。l多用于批處理系統(tǒng)多用于批處理系統(tǒng)l每次調(diào)度時要考慮：每次調(diào)度時要考慮：l (1)接納多少作業(yè)：取決于多道程序度接納多少作業(yè)：取決于多道程序度l (2)接納哪些作業(yè)：取決于調(diào)度算法接納哪些作業(yè)：取決于調(diào)度算法l作業(yè)調(diào)度運(yùn)行頻率低，幾分鐘一次作業(yè)調(diào)度運(yùn)行頻率低，幾分鐘一次系統(tǒng)規(guī)模系統(tǒng)規(guī)模運(yùn)行

4、速度運(yùn)行速度低級調(diào)度低級調(diào)度（進(jìn)程（進(jìn)程/短程調(diào)度）短程調(diào)度）l決定就緒隊(duì)列中的哪個進(jìn)程應(yīng)獲得處理機(jī)，然后再決定就緒隊(duì)列中的哪個進(jìn)程應(yīng)獲得處理機(jī)，然后再由分派程序執(zhí)行把處理機(jī)分配給該進(jìn)程的具體操作由分派程序執(zhí)行把處理機(jī)分配給該進(jìn)程的具體操作是是最基本最基本的調(diào)度，在三種類型的的調(diào)度，在三種類型的OS中都必須配置中都必須配置3.1.2、低級調(diào)度、低級調(diào)度1、低級調(diào)度的功能、低級調(diào)度的功能l保存處理機(jī)的現(xiàn)場信息保存處理機(jī)的現(xiàn)場信息l按照某種算法選取進(jìn)程按照某種算法選取進(jìn)程l把處理機(jī)分配給進(jìn)程把處理機(jī)分配給進(jìn)程2、進(jìn)程調(diào)度中的三個基本機(jī)制、進(jìn)程調(diào)度中的三個基本機(jī)制l排隊(duì)器排隊(duì)器l分派器（分派程序）分

5、派器（分派程序）l上下文切換機(jī)制上下文切換機(jī)制3、進(jìn)程調(diào)度方式、進(jìn)程調(diào)度方式l非搶占方式非搶占方式l搶占方式搶占方式1）非搶占方式：）非搶占方式：l一旦進(jìn)程獲得處理機(jī)，則一直執(zhí)行，直到該進(jìn)程完一旦進(jìn)程獲得處理機(jī)，則一直執(zhí)行，直到該進(jìn)程完成或被阻塞成或被阻塞l此方式下，可能此方式下，可能引起進(jìn)程調(diào)度的因素引起進(jìn)程調(diào)度的因素：（1）正在執(zhí)行的進(jìn)程執(zhí)行完畢，或因發(fā)生某事件不）正在執(zhí)行的進(jìn)程執(zhí)行完畢，或因發(fā)生某事件不能再繼續(xù)執(zhí)行能再繼續(xù)執(zhí)行（2）執(zhí)行中的進(jìn)程因提出）執(zhí)行中的進(jìn)程因提出I/O請求而暫停執(zhí)行請求而暫停執(zhí)行（3）在進(jìn)程通信或同步過程中執(zhí)行了某原語，）在進(jìn)程通信或同步過程中執(zhí)行了某原語，P操操

6、作等作等l優(yōu)點(diǎn)：優(yōu)點(diǎn)：簡單、系統(tǒng)開銷小，適合大多數(shù)批處理系統(tǒng)簡單、系統(tǒng)開銷小，適合大多數(shù)批處理系統(tǒng)l缺點(diǎn)：缺點(diǎn)：無法滿足緊急任務(wù)的需要，不適合實(shí)時系統(tǒng)無法滿足緊急任務(wù)的需要，不適合實(shí)時系統(tǒng)2）搶占方式：）搶占方式：l允許調(diào)度程序根據(jù)某原則，暫停正在執(zhí)行的進(jìn)程，允許調(diào)度程序根據(jù)某原則，暫停正在執(zhí)行的進(jìn)程，將處理機(jī)重新分配將處理機(jī)重新分配搶占原則：搶占原則：l優(yōu)先權(quán)原則優(yōu)先權(quán)原則就緒的高優(yōu)先權(quán)進(jìn)程有權(quán)搶占低優(yōu)先權(quán)進(jìn)程的就緒的高優(yōu)先權(quán)進(jìn)程有權(quán)搶占低優(yōu)先權(quán)進(jìn)程的CPUl短作業(yè)優(yōu)先原則短作業(yè)優(yōu)先原則就緒的短作業(yè)就緒的短作業(yè)(進(jìn)程進(jìn)程)有權(quán)搶占長作業(yè)有權(quán)搶占長作業(yè)(進(jìn)程進(jìn)程)的的CPUl時間片原則時間片原

7、則一個時間片用完后，系統(tǒng)重新進(jìn)行進(jìn)程調(diào)度一個時間片用完后，系統(tǒng)重新進(jìn)行進(jìn)程調(diào)度中級調(diào)度（中程調(diào)度）中級調(diào)度（中程調(diào)度）l目的：目的：提高內(nèi)存利用率和系統(tǒng)吞吐量提高內(nèi)存利用率和系統(tǒng)吞吐量l按一定的算法將外存上已具備運(yùn)行條件的掛起進(jìn)按一定的算法將外存上已具備運(yùn)行條件的掛起進(jìn)程換入內(nèi)存，掛到就緒隊(duì)列上，準(zhǔn)備執(zhí)行；而將程換入內(nèi)存，掛到就緒隊(duì)列上，準(zhǔn)備執(zhí)行；而將內(nèi)存中處于阻塞狀態(tài)的某些進(jìn)程換出至外存。內(nèi)存中處于阻塞狀態(tài)的某些進(jìn)程換出至外存。3.1.3、中級調(diào)度、中級調(diào)度調(diào)度隊(duì)列模型調(diào)度隊(duì)列模型選擇調(diào)度方式和調(diào)度算法的若干準(zhǔn)則選擇調(diào)度方式和調(diào)度算法的若干準(zhǔn)則3.2、調(diào)度隊(duì)列模型、調(diào)度隊(duì)列模型3.2.1、調(diào)

8、度隊(duì)列模型、調(diào)度隊(duì)列模型僅具有進(jìn)程調(diào)度的調(diào)度隊(duì)列模型僅具有進(jìn)程調(diào)度的調(diào)度隊(duì)列模型就就緒緒隊(duì)隊(duì)列列阻阻塞塞隊(duì)隊(duì)列列CPU時間片完時間片完交互用戶交互用戶進(jìn)程調(diào)度進(jìn)程調(diào)度進(jìn)程完成進(jìn)程完成等待事件等待事件事件發(fā)生事件發(fā)生 具有高、低兩級調(diào)度的調(diào)度隊(duì)列模型具有高、低兩級調(diào)度的調(diào)度隊(duì)列模型就就緒緒隊(duì)隊(duì)列列阻阻塞塞隊(duì)隊(duì)列列CPU時間片完時間片完作業(yè)作業(yè)調(diào)度調(diào)度進(jìn)程調(diào)度進(jìn)程調(diào)度進(jìn)程完成進(jìn)程完成等待事件等待事件1阻阻塞塞隊(duì)隊(duì)列列阻阻塞塞隊(duì)隊(duì)列列等待事件等待事件2等待事件等待事件n事件事件1發(fā)生發(fā)生事件事件2發(fā)生發(fā)生事件事件n發(fā)生發(fā)生后后備備隊(duì)隊(duì)列列 具有高、低、中三級調(diào)度的調(diào)度隊(duì)列模型具有高、低、中三級調(diào)度的

9、調(diào)度隊(duì)列模型就就 緒緒 隊(duì)隊(duì) 列列緒緒就就、 掛掛 起起 隊(duì)隊(duì) 列列CPU時間片完時間片完作業(yè)作業(yè)調(diào)度調(diào)度進(jìn)程調(diào)度進(jìn)程調(diào)度進(jìn)程完成進(jìn)程完成事件出現(xiàn)事件出現(xiàn)阻阻 塞塞 隊(duì)隊(duì) 列列掛起掛起等待事件等待事件中級中級調(diào)度調(diào)度事件發(fā)生事件發(fā)生后后 備備 隊(duì)隊(duì) 列列塞塞阻阻、 掛掛 起起 隊(duì)隊(duì) 列列掛起掛起3.2.2、選擇調(diào)度方式和算法的選擇準(zhǔn)則、選擇調(diào)度方式和算法的選擇準(zhǔn)則1、面向用戶的準(zhǔn)則、面向用戶的準(zhǔn)則l（1）周轉(zhuǎn)時間短）周轉(zhuǎn)時間短評價(jià)批處理系統(tǒng)評價(jià)批處理系統(tǒng)周轉(zhuǎn)時間：周轉(zhuǎn)時間：是指從作業(yè)被提交系統(tǒng)開始，到作業(yè)是指從作業(yè)被提交系統(tǒng)開始，到作業(yè)完成為止的這段時間間隔。完成為止的這段時間間隔。包括四部分

10、時間：包括四部分時間： 1）等待作業(yè)調(diào)度時間）等待作業(yè)調(diào)度時間 2）等待進(jìn)程調(diào)度時間）等待進(jìn)程調(diào)度時間 3）執(zhí)行時間）執(zhí)行時間 4）進(jìn)程等待）進(jìn)程等待I/O操作完成時間操作完成時間平均周轉(zhuǎn)時間：平均周轉(zhuǎn)時間：niTinT11帶權(quán)周轉(zhuǎn)時間：帶權(quán)周轉(zhuǎn)時間：TsTW 周轉(zhuǎn)時間周轉(zhuǎn)時間服務(wù)時間服務(wù)時間niTsTinW11平均帶權(quán)周轉(zhuǎn)時間：平均帶權(quán)周轉(zhuǎn)時間：（2）響應(yīng)時間快）響應(yīng)時間快評價(jià)分時系統(tǒng)評價(jià)分時系統(tǒng) 響應(yīng)時間：響應(yīng)時間：從用戶通過鍵盤提交一個請求開始直從用戶通過鍵盤提交一個請求開始直至系統(tǒng)首次產(chǎn)生響應(yīng)為止。至系統(tǒng)首次產(chǎn)生響應(yīng)為止。包括三部分時間：包括三部分時間：1）從鍵盤輸入的請求信息傳送到處

11、理機(jī)的時間）從鍵盤輸入的請求信息傳送到處理機(jī)的時間2）處理時間）處理時間3）響應(yīng)信息回送終端的時間）響應(yīng)信息回送終端的時間（3）截止時間保證）截止時間保證評價(jià)實(shí)時系統(tǒng)評價(jià)實(shí)時系統(tǒng) 截止時間：截止時間：任務(wù)必須開始執(zhí)行的最遲時間，任務(wù)必須開始執(zhí)行的最遲時間，或必須完成的最遲時間?；虮仨毻瓿傻淖钸t時間。（4）優(yōu)先權(quán)準(zhǔn)則）優(yōu)先權(quán)準(zhǔn)則三種系統(tǒng)中皆適用三種系統(tǒng)中皆適用2、面向系統(tǒng)的準(zhǔn)則、面向系統(tǒng)的準(zhǔn)則l系統(tǒng)吞吐量高系統(tǒng)吞吐量高評價(jià)批處理系統(tǒng)評價(jià)批處理系統(tǒng)l處理機(jī)利用率好處理機(jī)利用率好針對大中型系統(tǒng)針對大中型系統(tǒng)l各類資源的平衡利用各類資源的平衡利用對大中型系統(tǒng)對大中型系統(tǒng)3.3 調(diào)度算法調(diào)度算法先來先服

12、務(wù)和短作業(yè)（進(jìn)程）優(yōu)先調(diào)度先來先服務(wù)和短作業(yè)（進(jìn)程）優(yōu)先調(diào)度算法算法高優(yōu)先權(quán)先調(diào)度算法高優(yōu)先權(quán)先調(diào)度算法基于時間片的輪轉(zhuǎn)調(diào)度算法基于時間片的輪轉(zhuǎn)調(diào)度算法3.2.1、先來先服務(wù)和短作業(yè)（進(jìn)程）優(yōu)先先來先服務(wù)和短作業(yè)（進(jìn)程）優(yōu)先調(diào)度算法調(diào)度算法1、先來先服務(wù)（、先來先服務(wù)（FCFS）調(diào)度算法）調(diào)度算法可用于作業(yè)調(diào)度和進(jìn)程調(diào)度可用于作業(yè)調(diào)度和進(jìn)程調(diào)度用于作業(yè)調(diào)度：用于作業(yè)調(diào)度：l每次從后備作業(yè)隊(duì)列中選擇最先進(jìn)入的作業(yè)，將每次從后備作業(yè)隊(duì)列中選擇最先進(jìn)入的作業(yè)，將它們調(diào)入內(nèi)存，為它們分配資源、創(chuàng)建進(jìn)程，然它們調(diào)入內(nèi)存，為它們分配資源、創(chuàng)建進(jìn)程，然后掛到就緒進(jìn)程隊(duì)列上。后掛到就緒進(jìn)程隊(duì)列上。用于進(jìn)程調(diào)度

13、：用于進(jìn)程調(diào)度：l每次從就緒進(jìn)程隊(duì)列中選擇最先進(jìn)入的進(jìn)程，為每次從就緒進(jìn)程隊(duì)列中選擇最先進(jìn)入的進(jìn)程，為之分配處理機(jī)，使之投入運(yùn)行。之分配處理機(jī)，使之投入運(yùn)行。l直到運(yùn)行完成進(jìn)程才會讓出處理機(jī)直到運(yùn)行完成進(jìn)程才會讓出處理機(jī)-非搶占式。非搶占式。l有利于長作業(yè)，而不利于短作業(yè)。有利于長作業(yè)，而不利于短作業(yè)。性能評價(jià)：性能評價(jià)：l周轉(zhuǎn)時間周轉(zhuǎn)時間=完成時間完成時間到達(dá)時間到達(dá)時間l帶權(quán)周轉(zhuǎn)時間帶權(quán)周轉(zhuǎn)時間=周轉(zhuǎn)時間周轉(zhuǎn)時間/服務(wù)（運(yùn)行）時間服務(wù)（運(yùn)行）時間2、短作業(yè)、短作業(yè) / 進(jìn)程優(yōu)先（進(jìn)程優(yōu)先（SJF/SPF）短作業(yè)優(yōu)先（短作業(yè)優(yōu)先（SJF）l從后備隊(duì)列中選擇估計(jì)運(yùn)行時間最短的作業(yè)，調(diào)從后備隊(duì)列

14、中選擇估計(jì)運(yùn)行時間最短的作業(yè)，調(diào)入內(nèi)存運(yùn)行。入內(nèi)存運(yùn)行。短進(jìn)程優(yōu)先（短進(jìn)程優(yōu)先（SPF）l從就緒隊(duì)列中選出估計(jì)運(yùn)行時間最短的進(jìn)程，將從就緒隊(duì)列中選出估計(jì)運(yùn)行時間最短的進(jìn)程，將處理機(jī)分配給它，使它立即執(zhí)行。處理機(jī)分配給它，使它立即執(zhí)行。l直到運(yùn)行完成進(jìn)程才會讓出處理機(jī)直到運(yùn)行完成進(jìn)程才會讓出處理機(jī)-非搶占式。非搶占式。缺點(diǎn)：缺點(diǎn)：l對長作業(yè)不利，有可能長期不被調(diào)度；對長作業(yè)不利，有可能長期不被調(diào)度；l完全沒考慮作業(yè)的緊迫程度（某些特殊的）；完全沒考慮作業(yè)的緊迫程度（某些特殊的）；l用戶做出的估計(jì)時間帶有很大的主觀性。用戶做出的估計(jì)時間帶有很大的主觀性。2.259133.5141844E3.116

15、182101252C2.678926731B1.5365.5111423D2.11帶權(quán)周轉(zhuǎn)時間帶權(quán)周轉(zhuǎn)時間84周轉(zhuǎn)時間周轉(zhuǎn)時間4完成時間完成時間FJS2.81帶權(quán)周轉(zhuǎn)時間帶權(quán)周轉(zhuǎn)時間94周轉(zhuǎn)時間周轉(zhuǎn)時間4完成時間完成時間FCFS4服務(wù)時間服務(wù)時間0到達(dá)時間到達(dá)時間平均平均A進(jìn)程名進(jìn)程名作作調(diào)調(diào) 業(yè)業(yè) 度度 情情 算算 況況 法法l周轉(zhuǎn)時間周轉(zhuǎn)時間=完成時間完成時間到達(dá)時間到達(dá)時間l帶權(quán)周轉(zhuǎn)時間帶權(quán)周轉(zhuǎn)時間=周轉(zhuǎn)時間周轉(zhuǎn)時間/服務(wù)時間服務(wù)時間3.3.2、高優(yōu)先權(quán)先調(diào)度算法、高優(yōu)先權(quán)先調(diào)度算法既能用于作業(yè)調(diào)度，也可用于進(jìn)程調(diào)度。既能用于作業(yè)調(diào)度，也可用于進(jìn)程調(diào)度。作業(yè)調(diào)度：從后備隊(duì)列中選擇若干個優(yōu)

16、先權(quán)最高的作業(yè)調(diào)度：從后備隊(duì)列中選擇若干個優(yōu)先權(quán)最高的作業(yè)裝入內(nèi)存。作業(yè)裝入內(nèi)存。進(jìn)程調(diào)度：把處理機(jī)分配給就緒隊(duì)列中優(yōu)先權(quán)最高進(jìn)程調(diào)度：把處理機(jī)分配給就緒隊(duì)列中優(yōu)先權(quán)最高的進(jìn)程的進(jìn)程兩種占用兩種占用CPU的方式：非搶占式優(yōu)先權(quán)算法的方式：非搶占式優(yōu)先權(quán)算法 搶占式優(yōu)先權(quán)算法搶占式優(yōu)先權(quán)算法1、優(yōu)先權(quán)調(diào)度算法的類型、優(yōu)先權(quán)調(diào)度算法的類型非搶占式優(yōu)先權(quán)算法非搶占式優(yōu)先權(quán)算法l系統(tǒng)一旦把處理機(jī)分配給就緒隊(duì)列中優(yōu)先權(quán)最高系統(tǒng)一旦把處理機(jī)分配給就緒隊(duì)列中優(yōu)先權(quán)最高的進(jìn)程后，該進(jìn)程就一直執(zhí)行下去，直至完成；的進(jìn)程后，該進(jìn)程就一直執(zhí)行下去，直至完成；或因發(fā)生某事件使該進(jìn)程放棄處理機(jī)時，系統(tǒng)方或因發(fā)生某事件使

17、該進(jìn)程放棄處理機(jī)時，系統(tǒng)方可再將處理機(jī)重新分配給另一優(yōu)先權(quán)最高的進(jìn)程?？稍賹⑻幚頇C(jī)重新分配給另一優(yōu)先權(quán)最高的進(jìn)程。l主要用于批處理系統(tǒng)主要用于批處理系統(tǒng)搶占式優(yōu)先權(quán)算法搶占式優(yōu)先權(quán)算法l新的就緒進(jìn)程新的就緒進(jìn)程i，優(yōu)先權(quán)，優(yōu)先權(quán)Pi。正在執(zhí)行的進(jìn)程。正在執(zhí)行的進(jìn)程j，優(yōu)，優(yōu)先權(quán)先權(quán)Pj。若。若PiPj，做進(jìn)程切換。新進(jìn)程做進(jìn)程切換。新進(jìn)程i執(zhí)行。執(zhí)行。l優(yōu)點(diǎn)：優(yōu)點(diǎn)：能更好的滿足緊迫作業(yè)的要求。主要用于能更好的滿足緊迫作業(yè)的要求。主要用于比較嚴(yán)格的實(shí)時系統(tǒng)。比較嚴(yán)格的實(shí)時系統(tǒng)。2、優(yōu)先權(quán)的類型、優(yōu)先權(quán)的類型1）靜態(tài)優(yōu)先權(quán)）靜態(tài)優(yōu)先權(quán)在進(jìn)程創(chuàng)建時確定的，在進(jìn)程整個運(yùn)行期間保持不變在進(jìn)程創(chuàng)建時確定的

18、，在進(jìn)程整個運(yùn)行期間保持不變優(yōu)先權(quán)優(yōu)先權(quán)利用某一范圍的利用某一范圍的整數(shù)整數(shù)來表示，該整數(shù)稱為優(yōu)來表示，該整數(shù)稱為優(yōu)先數(shù)。如：先數(shù)。如：07，0255確定優(yōu)先權(quán)的依據(jù)：確定優(yōu)先權(quán)的依據(jù)：（1）進(jìn)程類型）進(jìn)程類型（2）進(jìn)程對資源的需求）進(jìn)程對資源的需求（3）用戶要求）用戶要求 注：規(guī)定優(yōu)先數(shù)越小，其優(yōu)先權(quán)越高注：規(guī)定優(yōu)先數(shù)越小，其優(yōu)先權(quán)越高4/348334C15/81517482B119118D帶權(quán)周轉(zhuǎn)時間帶權(quán)周轉(zhuǎn)時間周轉(zhuǎn)時間周轉(zhuǎn)時間155完成時間完成時間2優(yōu)先權(quán)優(yōu)先權(quán)非搶占式優(yōu)非搶占式優(yōu)先權(quán)算法先權(quán)算法5服務(wù)時間服務(wù)時間0到達(dá)時間到達(dá)時間A進(jìn)程名進(jìn)程名作作調(diào)調(diào) 業(yè)業(yè) 度度 情情 算算 況況 法

19、法平均平均6.251.3例：非搶占式優(yōu)先權(quán)算法例：非搶占式優(yōu)先權(quán)算法t(等待等待)優(yōu)先權(quán)優(yōu)先權(quán)t(運(yùn)行運(yùn)行)優(yōu)先權(quán)優(yōu)先權(quán)l(xiāng)2) 動態(tài)優(yōu)先權(quán)動態(tài)優(yōu)先權(quán)在進(jìn)程創(chuàng)建時創(chuàng)立的優(yōu)先權(quán)，可隨進(jìn)程的推進(jìn)或等待在進(jìn)程創(chuàng)建時創(chuàng)立的優(yōu)先權(quán)，可隨進(jìn)程的推進(jìn)或等待時間的增加而改變。如等待時間長，優(yōu)先權(quán)升高。時間的增加而改變。如等待時間長，優(yōu)先權(quán)升高。 等待時間等待時間 + 要求服務(wù)時間要求服務(wù)時間優(yōu)先權(quán)優(yōu)先權(quán) = - 要求服務(wù)時間要求服務(wù)時間 等待時間等待時間 + 要求服務(wù)時間要求服務(wù)時間 響應(yīng)時間響應(yīng)時間 響應(yīng)比響應(yīng)比(Rp) = - = - 要求服務(wù)時間要求服務(wù)時間 要求服務(wù)時間要求服務(wù)時間3、高響應(yīng)比優(yōu)先調(diào)度算

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

21、進(jìn)程名進(jìn)程名作作調(diào)調(diào) 業(yè)業(yè) 度度 情情 算算 況況 法法RC1+(9-4)/4=2.25RD1+(9-6)/5=1.6RE1+(9-8)/2=1.5RD1+(13-6)/5=2.4RE1+(13-8)/2=3.5執(zhí)行順序：執(zhí)行順序：ABCEDHRRN（R大，大，優(yōu)先權(quán)高優(yōu)先權(quán)高）3.3.3、基于時間片的輪轉(zhuǎn)調(diào)度算法、基于時間片的輪轉(zhuǎn)調(diào)度算法1、時間片輪轉(zhuǎn)法、時間片輪轉(zhuǎn)法1）基本原理）基本原理系統(tǒng)將所有的就緒進(jìn)程按系統(tǒng)將所有的就緒進(jìn)程按FIFO原則排成一個隊(duì)原則排成一個隊(duì)列，將列，將CPU分配給分配給隊(duì)首隊(duì)首進(jìn)程，執(zhí)行進(jìn)程，執(zhí)行一個時間片一個時間片。在時間片內(nèi)進(jìn)程未完，則插入在時間片內(nèi)進(jìn)程未完，

22、則插入就緒隊(duì)列未尾就緒隊(duì)列未尾，CPU交給下一個進(jìn)程。交給下一個進(jìn)程。2）時間片大小的確定）時間片大小的確定時間片略大于一次典型的交互所需要的時間。時間片略大于一次典型的交互所需要的時間。3.3313173.33131744E2.259113.5141642C2673.67111231B5101336923D帶權(quán)周轉(zhuǎn)時間帶權(quán)周轉(zhuǎn)時間2.58.4周轉(zhuǎn)時間周轉(zhuǎn)時間144完成時間完成時間RRq=4帶權(quán)周轉(zhuǎn)時間帶權(quán)周轉(zhuǎn)時間3.4611.8周轉(zhuǎn)時間周轉(zhuǎn)時間3.751515完成時間完成時間RRq=14服務(wù)時間服務(wù)時間0到達(dá)時間到達(dá)時間平均平均A進(jìn)程名進(jìn)程名作作調(diào)調(diào) 業(yè)業(yè) 度度 情情 算算 況況 法法l周轉(zhuǎn)

23、時間周轉(zhuǎn)時間=完成時間完成時間到達(dá)時間到達(dá)時間l帶權(quán)周轉(zhuǎn)時間帶權(quán)周轉(zhuǎn)時間=周轉(zhuǎn)時間周轉(zhuǎn)時間/服務(wù)時間服務(wù)時間2、多級反饋隊(duì)列調(diào)度算法、多級反饋隊(duì)列調(diào)度算法原理：原理：l設(shè)置多個就緒隊(duì)列設(shè)置多個就緒隊(duì)列，并為各個隊(duì)列賦予不同的優(yōu)，并為各個隊(duì)列賦予不同的優(yōu)先級和不同長度的時間片；先級和不同長度的時間片；l新創(chuàng)建的進(jìn)程新創(chuàng)建的進(jìn)程掛到第一優(yōu)先級的隊(duì)列后，然后按掛到第一優(yōu)先級的隊(duì)列后，然后按FCFS原則排隊(duì)等待調(diào)度。當(dāng)輪到其執(zhí)行時，如原則排隊(duì)等待調(diào)度。當(dāng)輪到其執(zhí)行時，如它能在時間片內(nèi)完成，便撤離系統(tǒng)；如果不能完它能在時間片內(nèi)完成，便撤離系統(tǒng)；如果不能完成，便被掛入第二級隊(duì)列后，成，便被掛入第二級隊(duì)列后

24、，最后一級最后一級隊(duì)隊(duì)列采用列采用時間片輪轉(zhuǎn)法時間片輪轉(zhuǎn)法；l僅當(dāng)?shù)谝患夑?duì)列空閑時僅當(dāng)?shù)谝患夑?duì)列空閑時，調(diào)度程序才調(diào)度第二級，調(diào)度程序才調(diào)度第二級隊(duì)列中的進(jìn)程運(yùn)行，依次類推隊(duì)列中的進(jìn)程運(yùn)行，依次類推；新進(jìn)程可搶；新進(jìn)程可搶占低級進(jìn)程的處理機(jī)。占低級進(jìn)程的處理機(jī)。 多級反饋隊(duì)列調(diào)度算法示意圖多級反饋隊(duì)列調(diào)度算法示意圖CPU時間時間片完片完進(jìn)程進(jìn)程調(diào)度調(diào)度進(jìn)程完成進(jìn)程完成就就緒緒隊(duì)隊(duì)列列一一就就緒緒隊(duì)隊(duì)列列二二就就緒緒隊(duì)隊(duì)列列三三就就緒緒隊(duì)隊(duì)列列 n時間時間片完片完時間時間片完片完就就級級1緒緒 隊(duì)隊(duì) 列列空空就就級級2緒緒 隊(duì)隊(duì) 列列就就級級3緒緒 隊(duì)隊(duì) 列列運(yùn)行運(yùn)行等待等待12354時間片時間

25、片 小小 大大優(yōu)先級優(yōu)先級 高高 低低多級反饋隊(duì)列調(diào)度算法的性能多級反饋隊(duì)列調(diào)度算法的性能多級反饋隊(duì)列調(diào)度算法能較好地滿足各種類型用多級反饋隊(duì)列調(diào)度算法能較好地滿足各種類型用戶（進(jìn)程）的需要：戶（進(jìn)程）的需要：l終端（交互）型作業(yè)用戶終端（交互）型作業(yè)用戶l短批處理作業(yè)用戶短批處理作業(yè)用戶l長批處理作業(yè)用戶長批處理作業(yè)用戶3.3.4、基于公平原則的調(diào)度算法、基于公平原則的調(diào)度算法1、保證調(diào)度算法、保證調(diào)度算法如果系統(tǒng)中有如果系統(tǒng)中有n個相同類型的進(jìn)程同時運(yùn)行，保個相同類型的進(jìn)程同時運(yùn)行，保證每個進(jìn)程都獲得相同的處理機(jī)時間證每個進(jìn)程都獲得相同的處理機(jī)時間1/n。2、公平分享調(diào)度算法、公平分享調(diào)度

26、算法使所有用戶能獲得相同的處理機(jī)時間。使所有用戶能獲得相同的處理機(jī)時間。3.4 實(shí)時調(diào)度實(shí)現(xiàn)實(shí)時調(diào)度的基本概念和條件實(shí)時調(diào)度算法的分類常見的幾種實(shí)時調(diào)度算法 1.實(shí)時調(diào)度實(shí)時調(diào)度是為了完成實(shí)時處理任務(wù)而分配處理機(jī)是為了完成實(shí)時處理任務(wù)而分配處理機(jī)的調(diào)度方法。的調(diào)度方法。 2. 2.硬實(shí)時任務(wù)要求計(jì)算機(jī)系統(tǒng)必須在用戶給定的硬實(shí)時任務(wù)要求計(jì)算機(jī)系統(tǒng)必須在用戶給定的時時限內(nèi)限內(nèi)完成完成 3.3.軟實(shí)時任務(wù)允許計(jì)算機(jī)系統(tǒng)在用戶給定的軟實(shí)時任務(wù)允許計(jì)算機(jī)系統(tǒng)在用戶給定的時限左時限左右右處理完畢。處理完畢。提供更詳細(xì)的調(diào)度信息：提供更詳細(xì)的調(diào)度信息：就緒時間、開始截止時間或完成截止時間、處理時間就緒時間、

27、開始截止時間或完成截止時間、處理時間、資源要求、優(yōu)先級等；、資源要求、優(yōu)先級等；含有硬實(shí)時任務(wù)的實(shí)時系統(tǒng)中，廣泛采用基于優(yōu)先級含有硬實(shí)時任務(wù)的實(shí)時系統(tǒng)中，廣泛采用基于優(yōu)先級的搶占式調(diào)度策略的搶占式調(diào)度策略l實(shí)時調(diào)度算法分類：實(shí)時調(diào)度算法分類：n非搶占式輪轉(zhuǎn)調(diào)度算法：非搶占式輪轉(zhuǎn)調(diào)度算法：只適用于一般實(shí)時信息處理系統(tǒng)只適用于一般實(shí)時信息處理系統(tǒng)n非搶占式優(yōu)先級調(diào)度算法：非搶占式優(yōu)先級調(diào)度算法：優(yōu)先級最高的實(shí)時任務(wù)排在就優(yōu)先級最高的實(shí)時任務(wù)排在就緒隊(duì)列隊(duì)首，當(dāng)前任務(wù)終止或完成后才被調(diào)度。緒隊(duì)列隊(duì)首，當(dāng)前任務(wù)終止或完成后才被調(diào)度。n 基于時鐘中斷搶占式優(yōu)先級調(diào)度算法：基于時鐘中斷搶占式優(yōu)先級調(diào)度算法

28、：新到的實(shí)時任務(wù)新到的實(shí)時任務(wù)的優(yōu)先級高于當(dāng)前任務(wù)時，并不立即搶占的優(yōu)先級高于當(dāng)前任務(wù)時，并不立即搶占CPUCPU，而是等到時，而是等到時鐘中斷到來，才進(jìn)行切換。用于大多數(shù)的實(shí)時系統(tǒng)中。鐘中斷到來，才進(jìn)行切換。用于大多數(shù)的實(shí)時系統(tǒng)中。 n 立即搶占的優(yōu)先級調(diào)度算法：立即搶占的優(yōu)先級調(diào)度算法：這種算法適用于實(shí)時要求這種算法適用于實(shí)時要求比較嚴(yán)格的實(shí)時控制系統(tǒng)。比較嚴(yán)格的實(shí)時控制系統(tǒng)。常用的幾種實(shí)時調(diào)度算法常用的幾種實(shí)時調(diào)度算法1、最早截止時間優(yōu)先算法（、最早截止時間優(yōu)先算法（EDF） 該算法根據(jù)任務(wù)的該算法根據(jù)任務(wù)的開始截止時間開始截止時間來確定任務(wù)的優(yōu)先來確定任務(wù)的優(yōu)先級。截止時間越早，優(yōu)先級

29、越高。級。截止時間越早，優(yōu)先級越高。 該算法要求實(shí)時任務(wù)的就緒隊(duì)列按任務(wù)該算法要求實(shí)時任務(wù)的就緒隊(duì)列按任務(wù)截止時間截止時間的的早晚排序。調(diào)度程序總選擇隊(duì)首的任務(wù)執(zhí)行。早晚排序。調(diào)度程序總選擇隊(duì)首的任務(wù)執(zhí)行。 該算法可用于搶占式和非搶占式調(diào)度。該算法可用于搶占式和非搶占式調(diào)度。t任務(wù)到達(dá)任務(wù)到達(dá)任務(wù)執(zhí)行任務(wù)執(zhí)行開始截止時間開始截止時間134211224433非搶占式調(diào)度方式非搶占式調(diào)度方式2、最低松弛度優(yōu)先算法（、最低松弛度優(yōu)先算法（LLF） 該算法根據(jù)任務(wù)的松弛度來確定任務(wù)的優(yōu)先級。松該算法根據(jù)任務(wù)的松弛度來確定任務(wù)的優(yōu)先級。松弛度越低，優(yōu)先級越高。弛度越低，優(yōu)先級越高。松弛度任務(wù)必須完成的時

30、間運(yùn)行時間當(dāng)前時間松弛度任務(wù)必須完成的時間運(yùn)行時間當(dāng)前時間 該算法要求實(shí)時任務(wù)的就緒隊(duì)列按松弛度排序。調(diào)該算法要求實(shí)時任務(wù)的就緒隊(duì)列按松弛度排序。調(diào)度程序總選擇隊(duì)首的任務(wù)執(zhí)行。度程序總選擇隊(duì)首的任務(wù)執(zhí)行。 該算法主要用于該算法主要用于搶占式搶占式調(diào)度方式。調(diào)度方式。松弛度任務(wù)必須完成的時間運(yùn)行時間當(dāng)前時間松弛度任務(wù)必須完成的時間運(yùn)行時間當(dāng)前時間例：例：實(shí)時系統(tǒng)中有兩個周期性實(shí)時任務(wù)實(shí)時系統(tǒng)中有兩個周期性實(shí)時任務(wù)A、B，任務(wù)，任務(wù)A每每20ms執(zhí)行一次，執(zhí)行時間執(zhí)行一次，執(zhí)行時間10ms；任務(wù)；任務(wù)B每每50ms執(zhí)行執(zhí)行一次，執(zhí)行時間一次，執(zhí)行時間25ms。采用搶占式。采用搶占式LLF算法：算法

31、：t0 20 40 60 80 100 120 140 160A1 A2 A3 A4 A5 A6 A7 A8B1B2B3任務(wù)任務(wù)A B每次必須完成的時間每次必須完成的時間松弛度松弛度t0 10 20 30 40 45 50 55 60 70 80A1=10B1=25A2=20B1=15A2=0B1=15A3=10B1=5A3=5B2=30此時執(zhí)此時執(zhí)行行B2A4=0B2=20A4完完B2=103、優(yōu)先級倒置問題、優(yōu)先級倒置問題 （1）問題的形成）問題的形成 即即OS中廣泛采用的優(yōu)先級調(diào)度算法和搶占方式。中廣泛采用的優(yōu)先級調(diào)度算法和搶占方式。舉例舉例: 三個獨(dú)立進(jìn)程三個獨(dú)立進(jìn)程P1、P2、P3，

32、優(yōu)先級由高到低。，優(yōu)先級由高到低。P1、P3共享臨界資源進(jìn)行交互。代碼：共享臨界資源進(jìn)行交互。代碼：P1：.P(mutex);CS-1;V(mutex).;P2: .program2.;P3: .P(mutex);CS-3;V(mutex).;執(zhí)行順序：執(zhí)行順序：P3P2(搶占搶占)P1（阻塞）（阻塞）P2(執(zhí)行執(zhí)行結(jié)束結(jié)束)P3(執(zhí)行結(jié)束執(zhí)行結(jié)束)P1(執(zhí)行結(jié)束執(zhí)行結(jié)束)問題：問題：P1優(yōu)先級最高，但最后執(zhí)行結(jié)束優(yōu)先級最高，但最后執(zhí)行結(jié)束3、優(yōu)先級倒置問題（續(xù)）、優(yōu)先級倒置問題（續(xù)） （2）問題的解決方案）問題的解決方案方案方案2：建立在動態(tài)優(yōu)先級繼承基礎(chǔ)上。：建立在動態(tài)優(yōu)先級繼承基礎(chǔ)上。規(guī)

33、定：規(guī)定：P1阻塞時由阻塞時由P3繼承繼承P1的優(yōu)先級，一直保持到的優(yōu)先級，一直保持到P3退出臨界區(qū)。目的：防止退出臨界區(qū)。目的：防止P2進(jìn)程插進(jìn)來，延緩進(jìn)程插進(jìn)來，延緩P3退出退出臨界區(qū)。臨界區(qū)。方案方案1：P3進(jìn)入臨界區(qū)后不允許處理機(jī)被搶占。進(jìn)入臨界區(qū)后不允許處理機(jī)被搶占。適用情況：系統(tǒng)中臨界區(qū)較短且不多。適用情況：系統(tǒng)中臨界區(qū)較短且不多。3.5 產(chǎn)生死鎖的原因和必要條件產(chǎn)生死鎖的原因和必要條件產(chǎn)生死鎖的原因產(chǎn)生死鎖的原因產(chǎn)生死鎖的必要條件產(chǎn)生死鎖的必要條件處理死鎖的基本方法處理死鎖的基本方法.1、產(chǎn)生死鎖的原因、產(chǎn)生死鎖的原因一、死鎖（一、死鎖（Deadlock）定義：）

34、定義：l死鎖是指兩個或兩個以上的進(jìn)程在運(yùn)行過程中，死鎖是指兩個或兩個以上的進(jìn)程在運(yùn)行過程中，因爭奪資源而造成的一種互相等待（誰也無法因爭奪資源而造成的一種互相等待（誰也無法再繼續(xù)推進(jìn)）的現(xiàn)象，若無外力作用，它們都再繼續(xù)推進(jìn)）的現(xiàn)象，若無外力作用，它們都將無法推進(jìn)下去。將無法推進(jìn)下去。二、產(chǎn)生死鎖的原因：二、產(chǎn)生死鎖的原因：l1、競爭資源l2、進(jìn)程間推進(jìn)順序非法1、競爭資源引起進(jìn)程死鎖、競爭資源引起進(jìn)程死鎖1.1資源的兩種分類：資源的兩種分類：可搶占性資源：CPU、RAM等；不可搶占性資源：打印機(jī)、磁帶機(jī)等；可重用性資源：打印機(jī)可消耗性資源：進(jìn)程通信中的消息、數(shù)據(jù)等l1.2 競爭不可搶占性資源引

35、起死鎖： 系統(tǒng)中配備的非剝奪性資源的數(shù)量不能滿足諸進(jìn)程運(yùn)行的需要時，會使進(jìn)程因爭奪資源而陷入僵局。打印機(jī)打印機(jī)P1磁帶機(jī)磁帶機(jī)P21.3 競爭可消耗資源引起死鎖：2 2、進(jìn)程間推進(jìn)順序不當(dāng)引起死鎖、進(jìn)程間推進(jìn)順序不當(dāng)引起死鎖l進(jìn)程推進(jìn)順序進(jìn)程推進(jìn)順序合法合法不會導(dǎo)致死鎖不會導(dǎo)致死鎖l進(jìn)程推進(jìn)順序進(jìn)程推進(jìn)順序非法非法可能會導(dǎo)致死可能會導(dǎo)致死圖圖1：順序合法：順序合法消息消息1P1消息消息2P2P3消息消息3圖圖2：順序非法：順序非法消息消息1P1消息消息2P2P3消息消息33.5.2、產(chǎn)生死鎖的必要條件、產(chǎn)生死鎖的必要條件1、互斥條件、互斥條件l一個資源一次只能被一個進(jìn)程使用。一個資源一次只能被

36、一個進(jìn)程使用。2、請求和保持條件（部分分配）、請求和保持條件（部分分配）l保留已經(jīng)得到的資源，還要求其它的資源。保留已經(jīng)得到的資源，還要求其它的資源。3、不可搶占條件、不可搶占條件l資源只能被占有者釋放，不能被其它進(jìn)程強(qiáng)資源只能被占有者釋放，不能被其它進(jìn)程強(qiáng)行搶占。行搶占。4、循環(huán)等待循環(huán)等待條件（循環(huán)等待）條件（循環(huán)等待）l系統(tǒng)中的進(jìn)程形成了環(huán)形的資源請求鏈。系統(tǒng)中的進(jìn)程形成了環(huán)形的資源請求鏈。3.5.3、處理死鎖的基本方法、處理死鎖的基本方法（1）預(yù)防死鎖）預(yù)防死鎖（2）避免死鎖）避免死鎖（3）檢測死鎖）檢測死鎖（4）解除死鎖）解除死鎖3.6 預(yù)防死鎖的方法預(yù)防死鎖的方法預(yù)防死鎖預(yù)防死鎖系

37、統(tǒng)安全狀態(tài)系統(tǒng)安全狀態(tài)利用銀行家算法避免死鎖利用銀行家算法避免死鎖3.6.1、預(yù)防死鎖、預(yù)防死鎖一、預(yù)防死鎖的實(shí)質(zhì)：一、預(yù)防死鎖的實(shí)質(zhì)：l通過設(shè)置某些限制條件，預(yù)防發(fā)生死鎖。通過設(shè)置某些限制條件，預(yù)防發(fā)生死鎖。二、預(yù)防死鎖的方法：二、預(yù)防死鎖的方法：“互斥條件互斥條件”由資源的性質(zhì)決定。由資源的性質(zhì)決定。1、摒棄、摒棄“請求和保持請求和保持”條件條件l在開始運(yùn)行前（創(chuàng)建時），一次性分配給進(jìn)程它在開始運(yùn)行前（創(chuàng)建時），一次性分配給進(jìn)程它所需的所需的“全部全部”資源。資源。l簡單易實(shí)現(xiàn)，安全性高；資源浪費(fèi)。簡單易實(shí)現(xiàn)，安全性高；資源浪費(fèi)。2、摒棄、摒棄“不可搶占不可搶占”條件條件l當(dāng)進(jìn)程有新的資源

38、請求時，如果得不到滿足，要當(dāng)進(jìn)程有新的資源請求時，如果得不到滿足，要先先釋放釋放原先占有的資源，待以后重新申請。原先占有的資源，待以后重新申請。l等價(jià)于此進(jìn)程等價(jià)于此進(jìn)程“被剝奪被剝奪”了已經(jīng)占有的資源。了已經(jīng)占有的資源。3、摒棄、摒棄“循環(huán)等待循環(huán)等待”條件條件l把系統(tǒng)資源按把系統(tǒng)資源按類型類型排序，進(jìn)程要按照資源的序號排序，進(jìn)程要按照資源的序號遞增遞增的次序提出資源申請。的次序提出資源申請。l較上述兩種方法的綜合性能要好；但系統(tǒng)配置資較上述兩種方法的綜合性能要好；但系統(tǒng)配置資源的序號要穩(wěn)定，固定的訪問順序不一定合理。源的序號要穩(wěn)定，固定的訪問順序不一定合理。例例1： 進(jìn)程進(jìn)程A占有占有3號

39、資源，現(xiàn)在又申請?zhí)栙Y源，現(xiàn)在又申請5號資源號資源占有占有資源號小于申請資源號，此申請可以滿足。資源號小于申請資源號，此申請可以滿足。 進(jìn)程進(jìn)程B占有占有5號資源，現(xiàn)在又申請?zhí)栙Y源，現(xiàn)在又申請3號資源號資源由于由于53，所以此申請不能滿足。進(jìn)程，所以此申請不能滿足。進(jìn)程B要想得到要想得到3號資號資源，必須先放棄源，必須先放棄5號以及所有編號比號以及所有編號比3大的資源。大的資源。例例2 2：哲學(xué)家就餐：哲學(xué)家就餐給哲學(xué)家和筷子編號給哲學(xué)家和筷子編號04 信號量定義：信號量定義：var chopstick 0,4 of semaphore; 信號量初值均為信號量初值均為1； 第第i(i=0,1,2

40、,3)位哲學(xué)家活動描述：位哲學(xué)家活動描述： 第第4位哲學(xué)家活動描述位哲學(xué)家活動描述: while(true) while (true) P(chopsticki); P(chopstick0); P(chopstick(i+1); P(chopstick4); eating; eating; V(chopsticki); V(chopstick0); V (chopstick(i+1); V (chopstick4); thinking; thinking; 3.6.2、系統(tǒng)安全狀態(tài)、系統(tǒng)安全狀態(tài)不安全狀態(tài)不安全狀態(tài)安全狀態(tài)安全狀態(tài)死鎖死鎖實(shí)質(zhì)：實(shí)質(zhì)：把系統(tǒng)的狀態(tài)分為安全狀態(tài)和不安全狀態(tài)，只把

41、系統(tǒng)的狀態(tài)分為安全狀態(tài)和不安全狀態(tài)，只要能使系統(tǒng)始終處于安全狀態(tài)，便可避免發(fā)生死鎖要能使系統(tǒng)始終處于安全狀態(tài)，便可避免發(fā)生死鎖1、安全狀態(tài)安全狀態(tài)l允許進(jìn)程動態(tài)的申請資源，但在分配前，應(yīng)先計(jì)允許進(jìn)程動態(tài)的申請資源，但在分配前，應(yīng)先計(jì)算分配的安全性。算分配的安全性。l所謂所謂“安全狀態(tài)安全狀態(tài)”：指系統(tǒng)能按某種進(jìn)程順序：指系統(tǒng)能按某種進(jìn)程順序(P1,P2,Pn)，來為每個進(jìn)程，來為每個進(jìn)程Pi分配其所需資源，分配其所需資源，直至最大需求，使直至最大需求，使每個每個進(jìn)程都可以進(jìn)程都可以順利順利完成。反完成。反之，則系統(tǒng)處于之，則系統(tǒng)處于不安全狀態(tài)。不安全狀態(tài)。l 不安全狀態(tài)不一定發(fā)生死鎖，但死鎖一

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

43、 可用資源向量可用資源向量Available 最大需求矩陣最大需求矩陣Max 分配矩陣分配矩陣Allocation 需求矩陣需求矩陣Need 資源請求向量資源請求向量Requesti3、安全性算法：、安全性算法：工作向量工作向量Work、Finish2、銀行家算法：、銀行家算法：（1） Requesti=Need?（2） Requesti= Available?（3）修改相關(guān)向量的值）修改相關(guān)向量的值（4）執(zhí)行安全性算法）執(zhí)行安全性算法進(jìn)程進(jìn)程資源資源某時刻系統(tǒng)資源分配情況某時刻系統(tǒng)資源分配情況ABCWork AllocationABCABCABCFinishAllocationNeedWor

44、k進(jìn)程進(jìn)程資源資源安全序列安全序列(1)該時刻該時刻T0系統(tǒng)是安全的嗎？系統(tǒng)是安全的嗎？解：利用安全性算法解：利用安全性算法對該時刻的資源分配情況對該時刻的資源分配情況進(jìn)行分析，方法如下圖：進(jìn)行分析，方法如下圖：1 2 2 2 0 0 5 3 2 true 0 1 1 2 1 1 7 4 3 true 4 3 1 2 1 1 7 4 5 true 6 0 0 3 0 2 10 4 7 true 7 4 3 0 1 0 10 5 7 true 3 3 25 3 27 4 37 4 510 4 7P 1P 3P 4P 2P 0(2)若此時若此時P1請求資源，發(fā)出請求向量請求資源，發(fā)出請求向量Req

45、uest1(1,0,2)系統(tǒng)可以為滿足請求嗎？系統(tǒng)可以為滿足請求嗎？解：系統(tǒng)按銀行家算法進(jìn)行檢查：解：系統(tǒng)按銀行家算法進(jìn)行檢查： Request1(1,0,2)=Need1(1,2,2) Request1(1,0,2)=Available(3,3,2) 系系統(tǒng)先假定可為統(tǒng)先假定可為P1分配資源，分配資源，修改相關(guān)修改相關(guān)向量值：向量值： 利用利用安全性算法安全性算法檢查此時系統(tǒng)是否安全。具體檢查此時系統(tǒng)是否安全。具體：進(jìn)程進(jìn)程資源資源某時刻資源分配情況某時刻資源分配情況3 0 20 2 02 3 05327437457551057ABCWork AllocationABCABCABCtruetruetruetruetrue302211002010302020011431743600230532743745755P1P3P4P0P2FinishAllocationNeedWork進(jìn)程進(jìn)程資源資源安全序列安全序列3 0 20 2 02 3 0進(jìn)