操作系統(tǒng)OSppt_03

1、第三章第三章 處理機(jī)調(diào)度與死鎖處理機(jī)調(diào)度與死鎖教學(xué)目的和要求：教學(xué)目的和要求： 使學(xué)生理解和掌握處理機(jī)調(diào)度的調(diào)度算法和死鎖的相關(guān)使學(xué)生理解和掌握處理機(jī)調(diào)度的調(diào)度算法和死鎖的相關(guān)概念以及避免死鎖的方法。概念以及避免死鎖的方法。理解進(jìn)程調(diào)度的概念與分類。理解進(jìn)程調(diào)度的概念與分類。了解幾種常見的實(shí)時(shí)系統(tǒng)的調(diào)度算法，掌握死鎖的概念了解幾種常見的實(shí)時(shí)系統(tǒng)的調(diào)度算法，掌握死鎖的概念和產(chǎn)生的必要條件、死鎖的預(yù)防和避免方法。熟練掌握和產(chǎn)生的必要條件、死鎖的預(yù)防和避免方法。熟練掌握調(diào)度算法、銀行家算法。調(diào)度算法、銀行家算法。 重點(diǎn)難點(diǎn)：重點(diǎn)難點(diǎn)： 進(jìn)程調(diào)度和常見的調(diào)度算法、死鎖的概念和產(chǎn)生的必進(jìn)程調(diào)度和常見的調(diào)

2、度算法、死鎖的概念和產(chǎn)生的必要條件、銀行家算法避免死鎖。要條件、銀行家算法避免死鎖。 第一節(jié)第一節(jié) 處理機(jī)調(diào)度的基本概念處理機(jī)調(diào)度的基本概念第二節(jié)第二節(jié) 調(diào)度算法調(diào)度算法第三節(jié)第三節(jié) 實(shí)時(shí)調(diào)度實(shí)時(shí)調(diào)度第四節(jié)第四節(jié) 多處理機(jī)系統(tǒng)中的調(diào)度多處理機(jī)系統(tǒng)中的調(diào)度第五節(jié)第五節(jié) 產(chǎn)生死鎖的原因和必要條件產(chǎn)生死鎖的原因和必要條件第六節(jié)第六節(jié) 死鎖問題的解決方法死鎖問題的解決方法作業(yè)與復(fù)習(xí)題作業(yè)與復(fù)習(xí)題目錄第一節(jié)第一節(jié) 處理機(jī)調(diào)度的基本概念處理機(jī)調(diào)度的基本概念高高/中中/低級(jí)調(diào)度低級(jí)調(diào)度調(diào)度隊(duì)列模型調(diào)度隊(duì)列模型調(diào)度方式和算法的選擇準(zhǔn)則調(diào)度方式和算法的選擇準(zhǔn)則1、高、高/中中/低級(jí)調(diào)度低級(jí)調(diào)度高級(jí)調(diào)度高級(jí)調(diào)度（

3、作業(yè)（作業(yè) / 長(zhǎng)程長(zhǎng)程 / 接納調(diào)度）接納調(diào)度）l決定把外存上處于后備隊(duì)列中的哪些作業(yè)調(diào)入內(nèi)決定把外存上處于后備隊(duì)列中的哪些作業(yè)調(diào)入內(nèi)存，并為它們創(chuàng)建進(jìn)程、分配必要的資源，準(zhǔn)備存，并為它們創(chuàng)建進(jìn)程、分配必要的資源，準(zhǔn)備執(zhí)行。執(zhí)行。(作業(yè)、作業(yè)步、作業(yè)流，作業(yè)、作業(yè)步、作業(yè)流，JCB)l多用于批處理系統(tǒng)多用于批處理系統(tǒng)l每次調(diào)度時(shí)要考慮：每次調(diào)度時(shí)要考慮： (1)接納多少作業(yè)：取決于多道程序度接納多少作業(yè)：取決于多道程序度 (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)行速度運(yùn)行速度低級(jí)調(diào)度（進(jìn)程低

4、級(jí)調(diào)度（進(jìn)程 / 短程調(diào)度）短程調(diào)度）決定就緒隊(duì)列中的哪個(gè)進(jìn)程應(yīng)獲得處理機(jī)，然后決定就緒隊(duì)列中的哪個(gè)進(jìn)程應(yīng)獲得處理機(jī)，然后再由分派程序執(zhí)行把處理機(jī)分配給該進(jìn)程的具體再由分派程序執(zhí)行把處理機(jī)分配給該進(jìn)程的具體操作操作低級(jí)調(diào)度的功能：（1）保存處理機(jī)的現(xiàn)場(chǎng)信息。 （2）按某種算法選取進(jìn)程。（3）把處理器分配給進(jìn)程。三個(gè)基本機(jī)制：排隊(duì)器、分派器、上下文切換機(jī)制。是是最基本最基本的調(diào)度，在三種類型的的調(diào)度，在三種類型的OS中都必須配置中都必須配置運(yùn)行頻率高，幾十毫秒一次，算法不能太復(fù)雜運(yùn)行頻率高，幾十毫秒一次，算法不能太復(fù)雜進(jìn)程調(diào)度采用兩種方式：非搶占方式、搶占方式進(jìn)程調(diào)度采用兩種方式：非搶占方式、搶

5、占方式非搶占方式：非搶占方式：l一旦進(jìn)程獲得處理機(jī)，則一直執(zhí)行，直到該進(jìn)程完一旦進(jìn)程獲得處理機(jī)，則一直執(zhí)行，直到該進(jìn)程完成或被阻塞成或被阻塞l優(yōu)點(diǎn)：簡(jiǎn)單、系統(tǒng)開銷小，適合大多數(shù)批處理系統(tǒng)優(yōu)點(diǎn)：簡(jiǎn)單、系統(tǒng)開銷小，適合大多數(shù)批處理系統(tǒng)l缺點(diǎn)：無法滿足緊急任務(wù)的需要，不適合實(shí)時(shí)系統(tǒng)缺點(diǎn)：無法滿足緊急任務(wù)的需要，不適合實(shí)時(shí)系統(tǒng)搶占方式：搶占方式：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è)

6、優(yōu)先原則短作業(yè)優(yōu)先原則 就緒的短作業(yè)就緒的短作業(yè)(進(jìn)程進(jìn)程)有權(quán)搶占長(zhǎng)作業(yè)有權(quán)搶占長(zhǎng)作業(yè)(進(jìn)程進(jìn)程)的的CPUl時(shí)間片原則時(shí)間片原則 一個(gè)時(shí)間片用完后，系統(tǒng)重新進(jìn)行進(jìn)程調(diào)度一個(gè)時(shí)間片用完后，系統(tǒng)重新進(jìn)行進(jìn)程調(diào)度中級(jí)調(diào)度（中程調(diào)度）中級(jí)調(diào)度（中程調(diào)度）l目的：目的：為了解決內(nèi)存緊張問題，常用于分時(shí)系統(tǒng)為了解決內(nèi)存緊張問題，常用于分時(shí)系統(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)程換出至外存。總結(jié)總結(jié)引起進(jìn)

7、程調(diào)度的原因有：引起進(jìn)程調(diào)度的原因有：l進(jìn)程正常終止或異常終止進(jìn)程正常終止或異常終止l正在執(zhí)行的進(jìn)程因某種原因而阻塞（正在執(zhí)行的進(jìn)程因某種原因而阻塞（I/O請(qǐng)求）請(qǐng)求）l分時(shí)系統(tǒng)中時(shí)間片用盡分時(shí)系統(tǒng)中時(shí)間片用盡l當(dāng)有一個(gè)優(yōu)先級(jí)更高的進(jìn)程就緒（可搶占式）當(dāng)有一個(gè)優(yōu)先級(jí)更高的進(jìn)程就緒（可搶占式）l在進(jìn)程通信中，執(zhí)行中的進(jìn)程執(zhí)行了某種原語(yǔ)操在進(jìn)程通信中，執(zhí)行中的進(jìn)程執(zhí)行了某種原語(yǔ)操作。作。如：如：P操作、操作、Block原語(yǔ)、原語(yǔ)、wakeup原語(yǔ)等原語(yǔ)等2、調(diào)度隊(duì)列模型、調(diào)度隊(duì)列模型僅具有進(jìn)程調(diào)度的調(diào)度隊(duì)列模型僅具有進(jìn)程調(diào)度的調(diào)度隊(duì)列模型就就緒緒隊(duì)隊(duì)列列阻阻塞塞隊(duì)隊(duì)列列CPU時(shí)間片完時(shí)間片完交互用

8、戶交互用戶進(jìn)程調(diào)度進(jìn)程調(diào)度進(jìn)程完成進(jìn)程完成等待事件等待事件事件發(fā)生事件發(fā)生 具有高、低兩級(jí)調(diào)度的調(diào)度隊(duì)列模型具有高、低兩級(jí)調(diào)度的調(diào)度隊(duì)列模型就就緒緒隊(duì)隊(duì)列列阻阻塞塞隊(duì)隊(duì)列列CPU時(shí)間片完時(shí)間片完作業(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ì)列列 具有高、低、中三級(jí)調(diào)度的調(diào)度隊(duì)列模型具有高、低、中三級(jí)調(diào)度的調(diào)度隊(duì)列模型就就 緒緒 隊(duì)隊(duì) 列列緒緒就就、 掛掛 起起 隊(duì)隊(duì) 列列CPU時(shí)間片完時(shí)間片完作業(yè)作業(yè)調(diào)度調(diào)度進(jìn)程調(diào)度進(jìn)程調(diào)度進(jìn)程完成進(jìn)程完成事

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

10、時(shí)間、帶權(quán)周轉(zhuǎn)時(shí)間平均周轉(zhuǎn)時(shí)間、帶權(quán)周轉(zhuǎn)時(shí)間l響應(yīng)時(shí)間快響應(yīng)時(shí)間快評(píng)價(jià)分時(shí)系統(tǒng)評(píng)價(jià)分時(shí)系統(tǒng) 響應(yīng)時(shí)間：響應(yīng)時(shí)間：從用戶通過鍵盤提交一個(gè)請(qǐng)求開始直從用戶通過鍵盤提交一個(gè)請(qǐng)求開始直至系統(tǒng)首次產(chǎn)生響應(yīng)為止。至系統(tǒng)首次產(chǎn)生響應(yīng)為止。 包括三部分時(shí)間：從鍵盤輸入的請(qǐng)求信息傳送到包括三部分時(shí)間：從鍵盤輸入的請(qǐng)求信息傳送到處理機(jī)的時(shí)間、處理時(shí)間、響應(yīng)信息回送終端的處理機(jī)的時(shí)間、處理時(shí)間、響應(yīng)信息回送終端的時(shí)間。時(shí)間。l截止時(shí)間保證截止時(shí)間保證評(píng)價(jià)實(shí)時(shí)系統(tǒng)評(píng)價(jià)實(shí)時(shí)系統(tǒng)l優(yōu)先權(quán)準(zhǔn)則優(yōu)先權(quán)準(zhǔn)則三種系統(tǒng)中皆適用三種系統(tǒng)中皆適用面向系統(tǒng)的準(zhǔn)則面向系統(tǒng)的準(zhǔn)則l系統(tǒng)吞吐量高系統(tǒng)吞吐量高評(píng)價(jià)批處理系統(tǒng)評(píng)價(jià)批處理系統(tǒng)l處理機(jī)

11、利用率好處理機(jī)利用率好針對(duì)大中型系統(tǒng)針對(duì)大中型系統(tǒng)l各類資源的平衡利用各類資源的平衡利用對(duì)大中型系統(tǒng)對(duì)大中型系統(tǒng)第二節(jié)第二節(jié) 調(diào)度算法調(diào)度算法先來先服務(wù)先來先服務(wù)短作業(yè)（進(jìn)程）優(yōu)先短作業(yè)（進(jìn)程）優(yōu)先高優(yōu)先權(quán)先調(diào)度高優(yōu)先權(quán)先調(diào)度時(shí)間片輪轉(zhuǎn)時(shí)間片輪轉(zhuǎn)多級(jí)反饋隊(duì)列多級(jí)反饋隊(duì)列1、先來先服務(wù)（、先來先服務(wù)（FCFS）可用于作業(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ì)列上。

12、用于進(jìn)程調(diào)度：用于進(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)程才會(huì)讓出處理機(jī)直到運(yùn)行完成進(jìn)程才會(huì)讓出處理機(jī)-非搶占式。非搶占式。l有利于長(zhǎng)作業(yè)，而不利于短作業(yè)。有利于長(zhǎng)作業(yè)，而不利于短作業(yè)。進(jìn)程進(jìn)程名名到達(dá)到達(dá)時(shí)間時(shí)間服務(wù)服務(wù)時(shí)間時(shí)間開始執(zhí)開始執(zhí)行時(shí)間行時(shí)間完成完成時(shí)間時(shí)間周轉(zhuǎn)周轉(zhuǎn)時(shí)間時(shí)間帶權(quán)周帶權(quán)周轉(zhuǎn)時(shí)間轉(zhuǎn)時(shí)間A010111B110011011001C21101102100100D31001022021991.99性能評(píng)價(jià)：性能評(píng)價(jià)：l周轉(zhuǎn)時(shí)間周轉(zhuǎn)時(shí)間 = 完成時(shí)間完

13、成時(shí)間 到達(dá)時(shí)間到達(dá)時(shí)間l帶權(quán)周轉(zhuǎn)時(shí)間帶權(quán)周轉(zhuǎn)時(shí)間 = 周轉(zhuǎn)時(shí)間周轉(zhuǎn)時(shí)間 / 服務(wù)（運(yùn)行）時(shí)間服務(wù)（運(yùn)行）時(shí)間2、短作業(yè)、短作業(yè) / 進(jìn)程優(yōu)先（進(jìn)程優(yōu)先（SJ/PF）短作業(yè)優(yōu)先（短作業(yè)優(yōu)先（SJF）l從后備隊(duì)列中選擇估計(jì)運(yùn)行時(shí)間最短的作業(yè)，調(diào)從后備隊(duì)列中選擇估計(jì)運(yùn)行時(shí)間最短的作業(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)行時(shí)間最短的進(jìn)程，將從就緒隊(duì)列中選出估計(jì)運(yùn)行時(shí)間最短的進(jìn)程，將處理機(jī)分配給它，使它立即執(zhí)行。處理機(jī)分配給它，使它立即執(zhí)行。l直到運(yùn)行完成進(jìn)程才會(huì)讓出處理機(jī)直到運(yùn)行完成進(jìn)程才會(huì)讓出處理機(jī)-非搶占式。非搶占式。缺點(diǎn)：缺點(diǎn)：l對(duì)長(zhǎng)作業(yè)不利，有

14、可能長(zhǎng)期不被調(diào)度；對(duì)長(zhǎng)作業(yè)不利，有可能長(zhǎng)期不被調(diào)度；l完全沒考慮作業(yè)的緊迫程度（某些特殊的）；完全沒考慮作業(yè)的緊迫程度（某些特殊的）；l用戶做出的估計(jì)時(shí)間帶有很大的主觀性。用戶做出的估計(jì)時(shí)間帶有很大的主觀性。2.259133.5141844E3.116182101252C2.678926731B1.5365.5111423D2.11帶權(quán)周轉(zhuǎn)時(shí)間帶權(quán)周轉(zhuǎn)時(shí)間84周轉(zhuǎn)時(shí)間周轉(zhuǎn)時(shí)間4完成時(shí)間完成時(shí)間FJS2.81帶權(quán)周轉(zhuǎn)時(shí)間帶權(quán)周轉(zhuǎn)時(shí)間94周轉(zhuǎn)時(shí)間周轉(zhuǎn)時(shí)間4完成時(shí)間完成時(shí)間FCFS4服務(wù)時(shí)間服務(wù)時(shí)間0到達(dá)時(shí)間到達(dá)時(shí)間平均平均A進(jìn)程名進(jìn)程名 作作調(diào)調(diào) 業(yè)業(yè) 度度 情情 算算 況況 法法l周轉(zhuǎn)時(shí)間周轉(zhuǎn)時(shí)

15、間 = 完成時(shí)間完成時(shí)間 到達(dá)時(shí)間到達(dá)時(shí)間l帶權(quán)周轉(zhuǎn)時(shí)間帶權(quán)周轉(zhuǎn)時(shí)間 = 周轉(zhuǎn)時(shí)間周轉(zhuǎn)時(shí)間 / 服務(wù)時(shí)間服務(wù)時(shí)間3、高優(yōu)先權(quán)先調(diào)度算法（、高優(yōu)先權(quán)先調(diào)度算法（HPF）既能用于作業(yè)調(diào)度，也可用于進(jìn)程調(diào)度。既能用于作業(yè)調(diào)度，也可用于進(jìn)程調(diào)度。作業(yè)調(diào)度：從后備隊(duì)列中選擇若干個(gè)優(yōu)先權(quán)最高的作業(yè)調(diào)度：從后備隊(duì)列中選擇若干個(gè)優(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的方式：非搶占式、搶占式的方式：非搶占式、搶占式l非搶占式優(yōu)先權(quán)算法：非搶占式優(yōu)先權(quán)算法：l搶占式優(yōu)先權(quán)算法：搶占式優(yōu)先權(quán)算

16、法： 注：規(guī)定優(yōu)先數(shù)越小，其優(yōu)先權(quán)越高注：規(guī)定優(yōu)先數(shù)越小，其優(yōu)先權(quán)越高4/348334C15/81517482B119118D帶權(quán)周轉(zhuǎn)時(shí)間帶權(quán)周轉(zhuǎn)時(shí)間周轉(zhuǎn)時(shí)間周轉(zhuǎn)時(shí)間155完成時(shí)間完成時(shí)間2優(yōu)先權(quán)優(yōu)先權(quán)非搶占式優(yōu)非搶占式優(yōu)先權(quán)算法先權(quán)算法5服務(wù)時(shí)間服務(wù)時(shí)間0到達(dá)時(shí)間到達(dá)時(shí)間A進(jìn)程名進(jìn)程名 作作調(diào)調(diào) 業(yè)業(yè) 度度 情情 算算 況況 法法平均平均6.251.3關(guān)鍵：優(yōu)先權(quán)的確定關(guān)鍵：優(yōu)先權(quán)的確定l優(yōu)先權(quán)類型一：靜態(tài)優(yōu)先權(quán)（進(jìn)程類型，對(duì)資源的優(yōu)先權(quán)類型一：靜態(tài)優(yōu)先權(quán)（進(jìn)程類型，對(duì)資源的需求，用戶要求）需求，用戶要求）在進(jìn)程創(chuàng)建時(shí)確定的，在進(jìn)程整個(gè)運(yùn)行期間保持不變。在進(jìn)程創(chuàng)建時(shí)確定的，在進(jìn)程整個(gè)運(yùn)行期間

17、保持不變。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)優(yōu)先權(quán)類型二：動(dòng)態(tài)優(yōu)先權(quán)優(yōu)先權(quán)類型二：動(dòng)態(tài)優(yōu)先權(quán)在進(jìn)程創(chuàng)建時(shí)創(chuàng)立的優(yōu)先權(quán)，可隨進(jìn)程的推進(jìn)或等待在進(jìn)程創(chuàng)建時(shí)創(chuàng)立的優(yōu)先權(quán)，可隨進(jìn)程的推進(jìn)或等待時(shí)間的增加而改變。如等待時(shí)間長(zhǎng)，優(yōu)先權(quán)升高。時(shí)間的增加而改變。如等待時(shí)間長(zhǎng)，優(yōu)先權(quán)升高。 等待時(shí)間等待時(shí)間 + 要求服務(wù)時(shí)間要求服務(wù)時(shí)間優(yōu)先權(quán)優(yōu)先權(quán) = - 要求服務(wù)時(shí)間要求服務(wù)時(shí)間 等待時(shí)間等待時(shí)間 + 要求服務(wù)時(shí)間要求服務(wù)時(shí)間 響應(yīng)時(shí)間響應(yīng)時(shí)間 響應(yīng)比響應(yīng)比(Rp) = - = - 要求服務(wù)時(shí)間要求服務(wù)時(shí)間 要求服務(wù)時(shí)間要求服務(wù)時(shí)間高響應(yīng)比優(yōu)先調(diào)度算法高響應(yīng)比優(yōu)先調(diào)度算法(HRRN)l為每

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

19、算算 況況 法法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)高）4、時(shí)間片輪轉(zhuǎn)（、時(shí)間片輪轉(zhuǎn)（RR）特別適用特別適用于于分時(shí)系統(tǒng)分時(shí)系統(tǒng)的搶占方式調(diào)度算法。的搶占方式調(diào)度算法。系統(tǒng)將所有的就緒進(jìn)程按系統(tǒng)將所有的就緒進(jìn)程按FIFO原則排成一個(gè)隊(duì)列，原則排成一個(gè)隊(duì)列，將將CPU分配給分配給隊(duì)首隊(duì)首進(jìn)程，執(zhí)行進(jìn)程，執(zhí)行一個(gè)時(shí)間片一個(gè)時(shí)間片。在時(shí)。在時(shí)間片內(nèi)進(jìn)程未完，則插入間片內(nèi)進(jìn)程未完，則插入就緒隊(duì)列未尾就緒隊(duì)列未尾，CPU交

20、交給下一個(gè)進(jìn)程。給下一個(gè)進(jìn)程。時(shí)間片選擇問題：時(shí)間片選擇問題：l固定時(shí)間片、可變時(shí)間片固定時(shí)間片、可變時(shí)間片與時(shí)間片大小有關(guān)的因素：與時(shí)間片大小有關(guān)的因素：l系統(tǒng)響應(yīng)時(shí)間、就緒進(jìn)程個(gè)數(shù)、系統(tǒng)響應(yīng)時(shí)間、就緒進(jìn)程個(gè)數(shù)、CPU能力能力2）時(shí)間片大小的確定（a)q=1(b)q=4圖圖3-5 q=1和和q=5時(shí)的進(jìn)程運(yùn)行情況時(shí)的進(jìn)程運(yùn)行情況進(jìn)程名進(jìn)程名ABCDE平均平均到達(dá)時(shí)間01234服務(wù)時(shí)間43524RR q=1完成時(shí)間1210181117周轉(zhuǎn)時(shí)間1291681311.6帶權(quán)周轉(zhuǎn)時(shí)間333.243.253.29RR q=4完成時(shí)間47121418周轉(zhuǎn)時(shí)間461011149帶權(quán)周轉(zhuǎn)時(shí)間1225.53.

21、52.8作業(yè)作業(yè)情況情況時(shí)間片時(shí)間片圖圖3-6 q=1和和q=4時(shí)進(jìn)程的周轉(zhuǎn)時(shí)間時(shí)進(jìn)程的周轉(zhuǎn)時(shí)間5、多級(jí)反饋隊(duì)列、多級(jí)反饋隊(duì)列l(wèi)設(shè)置多個(gè)就緒隊(duì)列設(shè)置多個(gè)就緒隊(duì)列，并為各個(gè)隊(duì)列賦予不同的優(yōu)，并為各個(gè)隊(duì)列賦予不同的優(yōu)先級(jí)和不同長(zhǎng)度的時(shí)間片；先級(jí)和不同長(zhǎng)度的時(shí)間片；l新創(chuàng)建的進(jìn)程新創(chuàng)建的進(jìn)程掛到第一優(yōu)先級(jí)的隊(duì)列后，然后按掛到第一優(yōu)先級(jí)的隊(duì)列后，然后按 FCFS 原則排隊(duì)等待調(diào)度。當(dāng)輪到其執(zhí)行時(shí)，如原則排隊(duì)等待調(diào)度。當(dāng)輪到其執(zhí)行時(shí)，如它能在時(shí)間片內(nèi)完成，便撤離系統(tǒng)；如果不能完它能在時(shí)間片內(nèi)完成，便撤離系統(tǒng)；如果不能完成，便被掛入第二級(jí)隊(duì)列后，成，便被掛入第二級(jí)隊(duì)列后，最后一級(jí)最后一級(jí)隊(duì)隊(duì)列采用列采用時(shí)

22、間片輪轉(zhuǎn)法時(shí)間片輪轉(zhuǎn)法；l僅當(dāng)?shù)谝患?jí)隊(duì)列空閑時(shí)僅當(dāng)?shù)谝患?jí)隊(duì)列空閑時(shí)，調(diào)度程序才調(diào)度第二級(jí)，調(diào)度程序才調(diào)度第二級(jí)隊(duì)列中的進(jìn)程運(yùn)行，依次類推隊(duì)列中的進(jìn)程運(yùn)行，依次類推；新進(jìn)程可搶；新進(jìn)程可搶占低級(jí)進(jìn)程的處理機(jī)。占低級(jí)進(jìn)程的處理機(jī)。 多級(jí)反饋隊(duì)列調(diào)度算法示意圖多級(jí)反饋隊(duì)列調(diào)度算法示意圖CPU時(shí)間時(shí)間片完片完進(jìn)程進(jìn)程調(diào)度調(diào)度進(jìn)程完成進(jìn)程完成就就緒緒隊(duì)隊(duì)列列一一就就緒緒隊(duì)隊(duì)列列二二就就緒緒隊(duì)隊(duì)列列三三就就緒緒隊(duì)隊(duì)列列 n時(shí)間時(shí)間片完片完時(shí)間時(shí)間片完片完優(yōu)先權(quán)優(yōu)先權(quán)時(shí)間片時(shí)間片多級(jí)反饋隊(duì)列調(diào)度算法的性能多級(jí)反饋隊(duì)列調(diào)度算法的性能 多級(jí)反饋隊(duì)列調(diào)度算法能較好地滿足各種類型用多級(jí)反饋隊(duì)列調(diào)度算法能較好地滿足各

23、種類型用戶（進(jìn)程）的需要：戶（進(jìn)程）的需要：l終端（交互）型作業(yè)用戶終端（交互）型作業(yè)用戶l短批處理作業(yè)用戶短批處理作業(yè)用戶l長(zhǎng)批處理作業(yè)用戶長(zhǎng)批處理作業(yè)用戶第三節(jié) 實(shí)時(shí)調(diào)度實(shí)現(xiàn)實(shí)時(shí)調(diào)度的基本概念和條件實(shí)時(shí)調(diào)度算法的分類常見的幾種實(shí)時(shí)調(diào)度算法 1.實(shí)時(shí)調(diào)度實(shí)時(shí)調(diào)度是為了完成實(shí)時(shí)處理任務(wù)而分配處理機(jī)是為了完成實(shí)時(shí)處理任務(wù)而分配處理機(jī)的調(diào)度方法。的調(diào)度方法。 2. 2.硬實(shí)時(shí)任務(wù)要求計(jì)算機(jī)系統(tǒng)必須在用戶給定的硬實(shí)時(shí)任務(wù)要求計(jì)算機(jī)系統(tǒng)必須在用戶給定的時(shí)時(shí)限內(nèi)限內(nèi)完成完成 3.3.軟實(shí)時(shí)任務(wù)允許計(jì)算機(jī)系統(tǒng)在用戶給定的軟實(shí)時(shí)任務(wù)允許計(jì)算機(jī)系統(tǒng)在用戶給定的時(shí)限左時(shí)限左右右處理完畢。處理完畢。提供更詳細(xì)的調(diào)

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

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

26、任務(wù)的開始截止時(shí)間開始截止時(shí)間來確定任務(wù)的優(yōu)先來確定任務(wù)的優(yōu)先級(jí)。截止時(shí)間越早，優(yōu)先級(jí)越高。級(jí)。截止時(shí)間越早，優(yōu)先級(jí)越高。 該算法要求實(shí)時(shí)任務(wù)的就緒隊(duì)列按任務(wù)該算法要求實(shí)時(shí)任務(wù)的就緒隊(duì)列按任務(wù)截止時(shí)間截止時(shí)間的的早晚排序。調(diào)度程序總選擇隊(duì)首的任務(wù)執(zhí)行。早晚排序。調(diào)度程序總選擇隊(duì)首的任務(wù)執(zhí)行。 該算法可用于搶占式和非搶占式調(diào)度。該算法可用于搶占式和非搶占式調(diào)度。t任務(wù)到達(dá)任務(wù)到達(dá)任務(wù)執(zhí)行任務(wù)執(zhí)行開始截止時(shí)間開始截止時(shí)間134211224433非搶占式調(diào)度方式非搶占式調(diào)度方式2)搶占式調(diào)度方式用于周期實(shí)時(shí)任務(wù)有兩個(gè)周期性任務(wù)，任務(wù)A的周期時(shí)間為20ms,每個(gè)周期的處理時(shí)間為10ms;任務(wù)B的周期時(shí)

27、間為50ms,每個(gè)周期的處理時(shí)間為25ms.2、最低松弛度優(yōu)先算法（、最低松弛度優(yōu)先算法（LLF） 該算法根據(jù)任務(wù)的松弛度來確定任務(wù)的優(yōu)先級(jí)。松該算法根據(jù)任務(wù)的松弛度來確定任務(wù)的優(yōu)先級(jí)。松弛度越低，優(yōu)先級(jí)越高。弛度越低，優(yōu)先級(jí)越高。松弛度任務(wù)必須完成的時(shí)間運(yùn)行時(shí)間當(dāng)前時(shí)間松弛度任務(wù)必須完成的時(shí)間運(yùn)行時(shí)間當(dāng)前時(shí)間 該算法要求實(shí)時(shí)任務(wù)的就緒隊(duì)列按松弛度排序。調(diào)該算法要求實(shí)時(shí)任務(wù)的就緒隊(duì)列按松弛度排序。調(diào)度程序總選擇隊(duì)首的任務(wù)執(zhí)行。度程序總選擇隊(duì)首的任務(wù)執(zhí)行。 該算法主要用于該算法主要用于搶占式搶占式調(diào)度方式。調(diào)度方式。到達(dá)時(shí)間、執(zhí)行到達(dá)時(shí)間、執(zhí)行時(shí)間和最后期限時(shí)間和最后期限固定優(yōu)先級(jí)調(diào)度固定優(yōu)先級(jí)

28、調(diào)度（A有較高優(yōu)先級(jí)）有較高優(yōu)先級(jí)）固定優(yōu)先級(jí)調(diào)度固定優(yōu)先級(jí)調(diào)度（B有較高優(yōu)先級(jí)）有較高優(yōu)先級(jí)）使用完成最后使用完成最后期限最早和最期限最早和最后期限調(diào)度后期限調(diào)度松弛度任務(wù)必須完成的時(shí)間運(yùn)行時(shí)間當(dāng)前時(shí)間松弛度任務(wù)必須完成的時(shí)間運(yùn)行時(shí)間當(dāng)前時(shí)間例：例：實(shí)時(shí)系統(tǒng)中有兩個(gè)周期性實(shí)時(shí)任務(wù)實(shí)時(shí)系統(tǒng)中有兩個(gè)周期性實(shí)時(shí)任務(wù)A、B，任務(wù)，任務(wù)A每每20ms執(zhí)行一次，執(zhí)行時(shí)間執(zhí)行一次，執(zhí)行時(shí)間10ms；任務(wù)；任務(wù)B每每50ms執(zhí)行執(zhí)行一次，執(zhí)行時(shí)間一次，執(zhí)行時(shí)間25ms。采用搶占式。采用搶占式LLF算法：算法：t0 20 40 60 80 100 120 140 160A1 A2 A3 A4 A5 A6 A7

29、 A8B1B2B3任務(wù)任務(wù)A B每次必須完成的時(shí)間每次必須完成的時(shí)間松弛度松弛度t0 10 20 30 40 45 50 55 60 70 80A1=10B1=25A2=20B1=15A2=0B1=15A3=10B1=5A3=5B2=30此時(shí)執(zhí)此時(shí)執(zhí)行行B2A4=0B2=20A4完完B2=10t0 20 40 60 80 100 120 140 160A1 A2 A3 A4 A5 A6 A7 A8B1B2B3圖圖3-11 任務(wù)任務(wù)A和和B每次必須完成的時(shí)間每次必須完成的時(shí)間t1=0 ,A1的松弛度為的松弛度為20-10-0=10， B1松弛度為松弛度為50-25-0=25,A1運(yùn)行運(yùn)行t2=1

30、0, A尚未進(jìn)入第二個(gè)周期，所以尚未進(jìn)入第二個(gè)周期，所以B1運(yùn)行運(yùn)行t3=30 ,A2的松弛度為的松弛度為40-10-30=0， B1松弛度為松弛度為50-5-30=15,A2運(yùn)行運(yùn)行t4=40, A3的松弛度為的松弛度為60-10-40=10 ，B1松弛度為松弛度為50-5-40=5,B1運(yùn)行運(yùn)行t5=45 ,A3的松弛度為的松弛度為60-10-45=5 ，B尚未進(jìn)入第二個(gè)周期尚未進(jìn)入第二個(gè)周期,A3運(yùn)行運(yùn)行t6=55, A尚未進(jìn)入第四個(gè)周期，尚未進(jìn)入第四個(gè)周期，B2運(yùn)行運(yùn)行t7=70,A4的松弛度為的松弛度為80-10-70=0，B2松弛度為松弛度為100-10-70=20,A4運(yùn)行運(yùn)行2

31、0010304050607080t1=0B1(20)A2(10)A3(10)A4(10)A1(10)B1(5)B2(10)B2(15)t2t3t4t5t6t7t8圖圖3-12 利用利用LLF算法進(jìn)行調(diào)度的情況算法進(jìn)行調(diào)度的情況第五節(jié)第五節(jié) 產(chǎn)生死鎖的原因和必要條產(chǎn)生死鎖的原因和必要條件件產(chǎn)生死鎖的原因產(chǎn)生死鎖的原因產(chǎn)生死鎖的必要條件產(chǎn)生死鎖的必要條件1 1、產(chǎn)生死鎖的原因、產(chǎn)生死鎖的原因死鎖（死鎖（Deadlock）：）：l是指兩個(gè)或兩個(gè)以上的進(jìn)程在運(yùn)行過程中，因是指兩個(gè)或兩個(gè)以上的進(jìn)程在運(yùn)行過程中，因爭(zhēng)奪資源而造成的一種互相等待（誰(shuí)也無法再爭(zhēng)奪資源而造成的一種互相等待（誰(shuí)也無法再繼續(xù)推進(jìn)）的

32、現(xiàn)象，若無外力作用，它們都將繼續(xù)推進(jìn)）的現(xiàn)象，若無外力作用，它們都將無法推進(jìn)下去。無法推進(jìn)下去。產(chǎn)生死鎖的原因：產(chǎn)生死鎖的原因：l競(jìng)爭(zhēng)資源競(jìng)爭(zhēng)資源l進(jìn)程間推進(jìn)順序非法進(jìn)程間推進(jìn)順序非法1、競(jìng)爭(zhēng)資源引起進(jìn)程死鎖：、競(jìng)爭(zhēng)資源引起進(jìn)程死鎖：l可剝奪性資源：可剝奪性資源：CPU、RAM等；等；l非剝奪性資源：打印機(jī)、磁帶機(jī)等；非剝奪性資源：打印機(jī)、磁帶機(jī)等；l永久性資源：打印機(jī)；永久性資源：打印機(jī)；l臨時(shí)性資源：進(jìn)程通信中的消息、數(shù)據(jù)等臨時(shí)性資源：進(jìn)程通信中的消息、數(shù)據(jù)等l競(jìng)爭(zhēng)非剝奪性資源：競(jìng)爭(zhēng)非剝奪性資源： 系統(tǒng)中配備的非剝奪性資源的數(shù)量不能滿足系統(tǒng)中配備的非剝奪性資源的數(shù)量不能滿足諸進(jìn)程運(yùn)行的需要

33、時(shí)，會(huì)使進(jìn)程因爭(zhēng)奪資源而諸進(jìn)程運(yùn)行的需要時(shí)，會(huì)使進(jìn)程因爭(zhēng)奪資源而陷入僵局。陷入僵局。l競(jìng)爭(zhēng)臨時(shí)性資源：競(jìng)爭(zhēng)臨時(shí)性資源：打印機(jī)打印機(jī)P1磁帶機(jī)磁帶機(jī)P22 2、進(jìn)程間推進(jìn)順序不當(dāng)引起死鎖、進(jìn)程間推進(jìn)順序不當(dāng)引起死鎖l進(jìn)程推進(jìn)順序合法進(jìn)程推進(jìn)順序合法不會(huì)導(dǎo)致死鎖不會(huì)導(dǎo)致死鎖l進(jìn)程推進(jìn)順序非法進(jìn)程推進(jìn)順序非法可能會(huì)導(dǎo)致死可能會(huì)導(dǎo)致死順序合法順序合法消息消息1P1消息消息2P2P3消息消息3順序非法順序非法消息消息1P1消息消息2P2P3消息消息3在進(jìn)程在進(jìn)程P1和和P2并發(fā)執(zhí)行時(shí)，如果按下述順序推進(jìn)：并發(fā)執(zhí)行時(shí)，如果按下述順序推進(jìn)：P1:Request(R1);Request(R2);P1:Rele

34、ase(R1);Release(R2);P2:Request(R2);Request(R1);P2:Release(R2);Release(R1);曲線曲線兩進(jìn)程均可順利完成，曲線兩進(jìn)程均可順利完成，曲線 順序非法順序非法42、產(chǎn)生死鎖的必要條件、產(chǎn)生死鎖的必要條件互斥條件互斥條件l一個(gè)資源一次只能被一個(gè)進(jìn)程使用。一個(gè)資源一次只能被一個(gè)進(jìn)程使用。請(qǐng)求和保持條件（部分分配）請(qǐng)求和保持條件（部分分配）l保留已經(jīng)得到的資源，還要求其它的資源。保留已經(jīng)得到的資源，還要求其它的資源。不可剝奪條件（不可搶占）不可剝奪條件（不可搶占）l資源只能被占有者釋放，不能被其它進(jìn)程強(qiáng)資源只能被占有者釋放，不能被其它進(jìn)

35、程強(qiáng)行搶占。行搶占。環(huán)路等待條件（循環(huán)等待）環(huán)路等待條件（循環(huán)等待）l系統(tǒng)中的進(jìn)程形成了環(huán)形的資源請(qǐng)求鏈。系統(tǒng)中的進(jìn)程形成了環(huán)形的資源請(qǐng)求鏈。第六節(jié)第六節(jié) 死鎖問題的解決方法死鎖問題的解決方法預(yù)防死鎖預(yù)防死鎖避免死鎖避免死鎖檢測(cè)與解除死鎖檢測(cè)與解除死鎖1、預(yù)防死鎖、預(yù)防死鎖預(yù)防：預(yù)防：l通過設(shè)置某些限制條件，破壞導(dǎo)致死鎖的四個(gè)必通過設(shè)置某些限制條件，破壞導(dǎo)致死鎖的四個(gè)必要條件之一。要條件之一。l“互斥條件互斥條件”由資源的性質(zhì)決定。由資源的性質(zhì)決定。摒棄摒棄“請(qǐng)求和保持請(qǐng)求和保持”條件條件l在開始運(yùn)行前（創(chuàng)建時(shí)），一次性分配給進(jìn)程它在開始運(yùn)行前（創(chuàng)建時(shí)），一次性分配給進(jìn)程它所需的所需的“全部全

36、部”資源。資源。l簡(jiǎn)單易實(shí)現(xiàn)，安全性高；資源浪費(fèi)。簡(jiǎn)單易實(shí)現(xiàn)，安全性高；資源浪費(fèi)。摒棄摒棄“不可剝奪不可剝奪”條件條件l當(dāng)進(jìn)程有新的資源請(qǐng)求時(shí)，如果得不到滿足，要當(dāng)進(jìn)程有新的資源請(qǐng)求時(shí)，如果得不到滿足，要先釋放原先占有的資源，待以后重新申請(qǐng)。先釋放原先占有的資源，待以后重新申請(qǐng)。l等價(jià)于此進(jìn)程等價(jià)于此進(jìn)程“被剝奪被剝奪”了已經(jīng)占有的資源。了已經(jīng)占有的資源。l實(shí)現(xiàn)比較復(fù)雜，系統(tǒng)代價(jià)很高。實(shí)現(xiàn)比較復(fù)雜，系統(tǒng)代價(jià)很高。摒棄摒棄“循環(huán)等待循環(huán)等待”條件條件l把系統(tǒng)資源按類型排序，進(jìn)程要按照資源的序號(hào)把系統(tǒng)資源按類型排序，進(jìn)程要按照資源的序號(hào)遞增的次序提出資源申請(qǐng)。遞增的次序提出資源申請(qǐng)。l較上述兩種方

37、法的綜合性能要好；但系統(tǒng)配置資較上述兩種方法的綜合性能要好；但系統(tǒng)配置資源的序號(hào)要穩(wěn)定，固定的訪問順序不一定合理。源的序號(hào)要穩(wěn)定，固定的訪問順序不一定合理。例如：例如： 進(jìn)程進(jìn)程A占有占有3號(hào)資源，現(xiàn)在又申請(qǐng)?zhí)栙Y源，現(xiàn)在又申請(qǐng)5號(hào)資源號(hào)資源占有占有資源號(hào)小于申請(qǐng)資源號(hào)，此申請(qǐng)可以滿足。資源號(hào)小于申請(qǐng)資源號(hào)，此申請(qǐng)可以滿足。 進(jìn)程進(jìn)程B占有占有5號(hào)資源，現(xiàn)在又申請(qǐng)?zhí)栙Y源，現(xiàn)在又申請(qǐng)3號(hào)資源號(hào)資源由于由于53，所以此申請(qǐng)不能滿足。進(jìn)程，所以此申請(qǐng)不能滿足。進(jìn)程B要想得到要想得到3號(hào)資號(hào)資源，必須先放棄源，必須先放棄5號(hào)以及所有編號(hào)比號(hào)以及所有編號(hào)比3大的資源。大的資源。2、避免死鎖、避免死鎖避免死

38、鎖的方法：避免死鎖的方法： 在資源的動(dòng)態(tài)分配過程中，用某種方法防止系統(tǒng)進(jìn)入在資源的動(dòng)態(tài)分配過程中，用某種方法防止系統(tǒng)進(jìn)入不安全狀態(tài)。不安全狀態(tài)。安全狀態(tài)：安全狀態(tài)：l系統(tǒng)能按某種進(jìn)程順序系統(tǒng)能按某種進(jìn)程順序(P1,P2,P3)，來為每個(gè)，來為每個(gè)進(jìn)程進(jìn)程Pi分配其所需資源，直至最大需求，使每個(gè)分配其所需資源，直至最大需求，使每個(gè)進(jìn)程都可以順利完成。進(jìn)程都可以順利完成。l反之，則系統(tǒng)處于不安全狀態(tài)。反之，則系統(tǒng)處于不安全狀態(tài)。l不安全狀態(tài)不一定發(fā)生死鎖，但死鎖一定屬于不安全狀不安全狀態(tài)不一定發(fā)生死鎖，但死鎖一定屬于不安全狀態(tài)。態(tài)。進(jìn)程進(jìn)程最大需求最大需求已分配已分配系統(tǒng)可用系統(tǒng)可用P1P2P31

39、0495223系統(tǒng)資源總數(shù)：系統(tǒng)資源總數(shù)：12不不32利用銀行家算法避免死鎖利用銀行家算法避免死鎖l銀行家算法的實(shí)質(zhì)就是要設(shè)法保證系統(tǒng)動(dòng)態(tài)分配資銀行家算法的實(shí)質(zhì)就是要設(shè)法保證系統(tǒng)動(dòng)態(tài)分配資源后仍然保持安全狀態(tài)，從而避免死鎖的發(fā)生。源后仍然保持安全狀態(tài)，從而避免死鎖的發(fā)生。l要求進(jìn)程預(yù)先告知自己的最大資源需求，并且假設(shè)要求進(jìn)程預(yù)先告知自己的最大資源需求，并且假設(shè)系統(tǒng)擁有固定的資源總量。系統(tǒng)擁有固定的資源總量。l數(shù)據(jù)結(jié)構(gòu)：數(shù)據(jù)結(jié)構(gòu)： 可用資源向量可用資源向量Available 最大需求矩陣最大需求矩陣Max l分配矩陣分配矩陣Allocation 需求矩陣需求矩陣Need 資源請(qǐng)求向量資源請(qǐng)求向量

40、Requestil安全性算法：工作向量安全性算法：工作向量Work、FinishMaxAllocationNeedAvailableA B CA B CA B CA B CP0P1P2P3P47 5 33 2 29 0 22 2 24 3 30 1 02 0 03 0 22 1 10 0 27 4 31 2 26 0 00 1 14 3 13 3 2資源總數(shù)資源總數(shù) 10 5 7進(jìn)程進(jìn)程資源資源某時(shí)刻資源分配情況某時(shí)刻資源分配情況5 3 27 4 37 4 510 4 710 5 7A B CWork AllocationA B CA B CA B Ctruetruetruetruetrue2

41、 0 02 1 10 0 23 0 20 1 01 2 20 1 14 3 16 0 07 4 33 3 25 3 27 4 37 4 510 4 7P1P3P4P2P0FinishAllocationNeedWork進(jìn)程進(jìn)程資源資源安全序列安全序列3 0 20 2 02 3 0(2)若此時(shí)若此時(shí)P1請(qǐng)求資源，發(fā)出請(qǐng)求向量請(qǐng)求資源，發(fā)出請(qǐng)求向量Request1(1,0,2)系統(tǒng)按系統(tǒng)按銀行家算法銀行家算法進(jìn)行檢查：進(jìn)行檢查： Request1(1,0,2)=Need1(1,2,2) Request1(1,0,2)=Available(3,3,2) 系系統(tǒng)先假定可為統(tǒng)先假定可為P1分配資源，并修

42、改向量的值。分配資源，并修改向量的值。 再利用再利用安全性算法安全性算法檢查此時(shí)系統(tǒng)是否安全。檢查此時(shí)系統(tǒng)是否安全。 5 3 27 4 37 4 57 5 510 5 7A B CWork AllocationA B CA B CA B Ctruetruetruetruetrue3 0 22 1 10 0 20 1 03 0 20 2 00 1 14 3 17 4 36 0 02 3 05 3 27 4 37 4 57 5 5P1P3P4P0P2FinishAllocationNeedWork進(jìn)程進(jìn)程資源資源安全序列安全序列A B CA B CA B CA B C3 3 2資源總數(shù)資源總數(shù) 1

43、0 5 77 4 31 2 26 0 00 1 14 3 10 1 02 0 03 0 22 1 10 0 27 5 33 2 29 0 22 2 24 3 3P0P1P2P3P4AvailableNeedAllocationMax進(jìn)程進(jìn)程資源資源某時(shí)刻資源分配情況某時(shí)刻資源分配情況3 0 20 2 02 3 0（3）若此時(shí)）若此時(shí)P4請(qǐng)求資源，發(fā)出請(qǐng)求向量請(qǐng)求資源，發(fā)出請(qǐng)求向量Request4(3,3,0)系統(tǒng)按系統(tǒng)按銀行家算法銀行家算法進(jìn)行檢查：進(jìn)行檢查： Request4(3,3,0)Available(2,3,0) 因此，讓因此，讓P4等待。等待。A B CA B CA B CA B

44、C3 3 2資源總數(shù)資源總數(shù) 10 5 77 4 31 2 26 0 00 1 14 3 10 1 02 0 03 0 22 1 10 0 27 5 33 2 29 0 22 2 24 3 3P0P1P2P3P4AvailableNeedAllocationMax進(jìn)程進(jìn)程資源資源某時(shí)刻資源分配情況某時(shí)刻資源分配情況3 0 20 2 02 3 0（4）若此時(shí)）若此時(shí)P0請(qǐng)求資源，發(fā)出請(qǐng)求向量請(qǐng)求資源，發(fā)出請(qǐng)求向量Request0(0,2,0)系統(tǒng)按系統(tǒng)按銀行家算法銀行家算法進(jìn)行檢查：進(jìn)行檢查： Request0(0,2,0)=Need0(7,4,3) Request0(0,2,0)=Availa

45、ble(2,3,0) 系統(tǒng)系統(tǒng)暫時(shí)先假定暫時(shí)先假定可為可為P0分配資源，并修改有關(guān)數(shù)據(jù)分配資源，并修改有關(guān)數(shù)據(jù) 進(jìn)行進(jìn)行安全性檢查安全性檢查，Available(2,1,0)已不能滿足任何進(jìn)已不能滿足任何進(jìn)程的需要，故系統(tǒng)進(jìn)入不安全狀態(tài)，此時(shí)系統(tǒng)不分配資程的需要，故系統(tǒng)進(jìn)入不安全狀態(tài)，此時(shí)系統(tǒng)不分配資源源 。0 3 07 2 32 1 01. 銀行家算法中的數(shù)據(jù)結(jié)構(gòu)銀行家算法中的數(shù)據(jù)結(jié)構(gòu) (1) 可利用資源向量Available。這是一個(gè)含有m個(gè)元素的數(shù)組，其中的每一個(gè)元素代表一類可利用的資源數(shù)目，其初始值是系統(tǒng)中所配置的該類全部可用資源的數(shù)目，其數(shù)值隨該類資源的分配和回收而動(dòng)態(tài)地改變。如果Availablej=K，則表示系統(tǒng)中現(xiàn)有Rj類資源K個(gè)。 (2) 最