第三章_處理機(jī)調(diào)度

1、第三章第三章 處理機(jī)調(diào)度與死鎖處理機(jī)調(diào)度與死鎖內(nèi)容提要內(nèi)容提要l 策略：處理機(jī)調(diào)度策略：處理機(jī)調(diào)度l 避免：死鎖避免：死鎖處理機(jī)調(diào)度處理機(jī)調(diào)度 處理機(jī)管理的工作是對(duì)處理機(jī)管理的工作是對(duì)CPUCPU資源進(jìn)行合理的分資源進(jìn)行合理的分配使用，以提高處理機(jī)利用率，并使各用戶公平配使用，以提高處理機(jī)利用率，并使各用戶公平地得到處理機(jī)資源。地得到處理機(jī)資源。3.1 3.1 處理機(jī)調(diào)度的類型及其功能處理機(jī)調(diào)度的類型及其功能什么是調(diào)度什么是調(diào)度n調(diào)度指在一個(gè)隊(duì)列中，按照某種方法，選擇一調(diào)度指在一個(gè)隊(duì)列中，按照某種方法，選擇一個(gè)合適的個(gè)體的過程個(gè)合適的個(gè)體的過程n調(diào)度的關(guān)鍵是使用好的調(diào)度算法，好的調(diào)度算調(diào)度的關(guān)

2、鍵是使用好的調(diào)度算法，好的調(diào)度算法有利于選擇到合適的個(gè)體法有利于選擇到合適的個(gè)體n如何判斷、設(shè)計(jì)一個(gè)好的調(diào)度算法？如何判斷、設(shè)計(jì)一個(gè)好的調(diào)度算法？調(diào)度實(shí)例調(diào)度目標(biāo)調(diào)度目標(biāo)n公平性：防止進(jìn)程長(zhǎng)期不能獲得調(diào)度而饑餓；公平性：防止進(jìn)程長(zhǎng)期不能獲得調(diào)度而饑餓；n盡量提高處理機(jī)利用率盡量提高處理機(jī)利用率n提高系統(tǒng)吞吐量提高系統(tǒng)吞吐量n盡量減少進(jìn)程的響應(yīng)時(shí)間盡量減少進(jìn)程的響應(yīng)時(shí)間調(diào)度原則調(diào)度原則n滿足用戶的要求：響應(yīng)時(shí)間、周轉(zhuǎn)時(shí)間滿足用戶的要求：響應(yīng)時(shí)間、周轉(zhuǎn)時(shí)間n滿足系統(tǒng)的需求：系統(tǒng)吞吐量、處理機(jī)利用率、滿足系統(tǒng)的需求：系統(tǒng)吞吐量、處理機(jī)利用率、各類資源的平衡使用、公平性及優(yōu)先級(jí)各類資源的平衡使用、公平

3、性及優(yōu)先級(jí)響應(yīng)時(shí)間響應(yīng)時(shí)間n響應(yīng)時(shí)間指從用戶提交一個(gè)請(qǐng)求開始，直到系響應(yīng)時(shí)間指從用戶提交一個(gè)請(qǐng)求開始，直到系統(tǒng)產(chǎn)生響應(yīng)為止的時(shí)間間隔統(tǒng)產(chǎn)生響應(yīng)為止的時(shí)間間隔n響應(yīng)時(shí)間響應(yīng)時(shí)間=輸入的請(qǐng)求傳送到處理機(jī)的時(shí)間輸入的請(qǐng)求傳送到處理機(jī)的時(shí)間+處處理機(jī)對(duì)請(qǐng)求信息進(jìn)行處理的時(shí)間理機(jī)對(duì)請(qǐng)求信息進(jìn)行處理的時(shí)間+將響應(yīng)結(jié)果發(fā)將響應(yīng)結(jié)果發(fā)送到輸出終端的時(shí)間送到輸出終端的時(shí)間n調(diào)度算法應(yīng)考慮盡可能使絕大多數(shù)用戶的請(qǐng)求調(diào)度算法應(yīng)考慮盡可能使絕大多數(shù)用戶的請(qǐng)求能在響應(yīng)時(shí)間內(nèi)完成能在響應(yīng)時(shí)間內(nèi)完成n常用于評(píng)價(jià)分時(shí)系統(tǒng)的性能常用于評(píng)價(jià)分時(shí)系統(tǒng)的性能 周轉(zhuǎn)時(shí)間周轉(zhuǎn)時(shí)間n指從作業(yè)提交給系統(tǒng)開始，到作業(yè)完成為止的指從作業(yè)提交給系

4、統(tǒng)開始，到作業(yè)完成為止的時(shí)間間隔時(shí)間間隔n周轉(zhuǎn)時(shí)間周轉(zhuǎn)時(shí)間=作業(yè)在外存排隊(duì)等待調(diào)度的時(shí)間作業(yè)在外存排隊(duì)等待調(diào)度的時(shí)間+進(jìn)進(jìn)程在就緒隊(duì)列中等待調(diào)度的時(shí)間程在就緒隊(duì)列中等待調(diào)度的時(shí)間+進(jìn)程被處理機(jī)進(jìn)程被處理機(jī)執(zhí)行的時(shí)間執(zhí)行的時(shí)間+等待等待I/O操作完成的時(shí)間操作完成的時(shí)間n常用于評(píng)價(jià)批處理系統(tǒng)的性能常用于評(píng)價(jià)批處理系統(tǒng)的性能影響周轉(zhuǎn)時(shí)間的調(diào)度影響周轉(zhuǎn)時(shí)間的調(diào)度n作業(yè)從外存調(diào)度到內(nèi)存（作業(yè)調(diào)度）作業(yè)從外存調(diào)度到內(nèi)存（作業(yè)調(diào)度）n進(jìn)入內(nèi)存還需在就緒隊(duì)列中排隊(duì)，等待進(jìn)程調(diào)進(jìn)入內(nèi)存還需在就緒隊(duì)列中排隊(duì)，等待進(jìn)程調(diào)度度n甚至，可能會(huì)掛起進(jìn)程，在外存等待被激活甚至，可能會(huì)掛起進(jìn)程，在外存等待被激活（存儲(chǔ)對(duì)換或

5、中級(jí)調(diào)度）（存儲(chǔ)對(duì)換或中級(jí)調(diào)度）截止時(shí)間截止時(shí)間n指實(shí)時(shí)系統(tǒng)中，某任務(wù)必須開始執(zhí)行的最遲時(shí)指實(shí)時(shí)系統(tǒng)中，某任務(wù)必須開始執(zhí)行的最遲時(shí)間，或必須完成的最遲時(shí)間間，或必須完成的最遲時(shí)間n常用于評(píng)價(jià)實(shí)時(shí)系統(tǒng)的性能常用于評(píng)價(jià)實(shí)時(shí)系統(tǒng)的性能系統(tǒng)吞吐量系統(tǒng)吞吐量n指單位時(shí)間內(nèi)系統(tǒng)完成的作業(yè)數(shù)指單位時(shí)間內(nèi)系統(tǒng)完成的作業(yè)數(shù)n常用于評(píng)價(jià)批處理系統(tǒng)的性能常用于評(píng)價(jià)批處理系統(tǒng)的性能處理機(jī)利用率處理機(jī)利用率n處理機(jī)處于忙狀態(tài)的時(shí)間和處理機(jī)運(yùn)行總時(shí)間處理機(jī)處于忙狀態(tài)的時(shí)間和處理機(jī)運(yùn)行總時(shí)間的比值的比值n大中型多用戶系統(tǒng)，由于處理機(jī)價(jià)格昂貴，處大中型多用戶系統(tǒng)，由于處理機(jī)價(jià)格昂貴，處理機(jī)利用率是衡量系統(tǒng)性能的一個(gè)重要指標(biāo)。

6、理機(jī)利用率是衡量系統(tǒng)性能的一個(gè)重要指標(biāo)。n單用戶微機(jī)或某些實(shí)時(shí)系統(tǒng)，并非很重要。單用戶微機(jī)或某些實(shí)時(shí)系統(tǒng)，并非很重要。各類資源的平衡使用各類資源的平衡使用n多道程序系統(tǒng)的目標(biāo)之一就是為了提高系統(tǒng)資多道程序系統(tǒng)的目標(biāo)之一就是為了提高系統(tǒng)資源的利用率，因此，調(diào)度算法有責(zé)任使系統(tǒng)中源的利用率，因此，調(diào)度算法有責(zé)任使系統(tǒng)中的各種資源都盡量處于忙碌狀態(tài)。的各種資源都盡量處于忙碌狀態(tài)。n該原則同時(shí)適用于作業(yè)調(diào)度和中級(jí)調(diào)度，因?yàn)樵撛瓌t同時(shí)適用于作業(yè)調(diào)度和中級(jí)調(diào)度，因?yàn)樗鼈兛梢詻Q定哪些作業(yè)進(jìn)入內(nèi)存，可以考慮系它們可以決定哪些作業(yè)進(jìn)入內(nèi)存，可以考慮系統(tǒng)資源的均衡使用統(tǒng)資源的均衡使用公平性公平性n調(diào)度算法應(yīng)該對(duì)所

7、有進(jìn)程公平，不偏袒任何進(jìn)調(diào)度算法應(yīng)該對(duì)所有進(jìn)程公平，不偏袒任何進(jìn)程程優(yōu)先權(quán)優(yōu)先權(quán)n優(yōu)先權(quán)高的進(jìn)程應(yīng)該先調(diào)度。優(yōu)先權(quán)高的進(jìn)程應(yīng)該先調(diào)度。n可以根據(jù)進(jìn)程的優(yōu)先權(quán)不同，組織不同的就緒可以根據(jù)進(jìn)程的優(yōu)先權(quán)不同，組織不同的就緒隊(duì)列。進(jìn)程調(diào)度時(shí)首先選擇高優(yōu)先權(quán)隊(duì)列中的隊(duì)列。進(jìn)程調(diào)度時(shí)首先選擇高優(yōu)先權(quán)隊(duì)列中的進(jìn)程，直到該隊(duì)列空，再調(diào)度較低優(yōu)先權(quán)隊(duì)列進(jìn)程，直到該隊(duì)列空，再調(diào)度較低優(yōu)先權(quán)隊(duì)列中的進(jìn)程。中的進(jìn)程。n幾乎所有操作系統(tǒng)的調(diào)度算法都可考慮優(yōu)先權(quán)幾乎所有操作系統(tǒng)的調(diào)度算法都可考慮優(yōu)先權(quán)原則。原則。n考慮優(yōu)先權(quán)，可能會(huì)出現(xiàn)饑餓現(xiàn)象，對(duì)低優(yōu)先考慮優(yōu)先權(quán)，可能會(huì)出現(xiàn)饑餓現(xiàn)象，對(duì)低優(yōu)先權(quán)的進(jìn)程不公平。權(quán)的進(jìn)程不公

8、平。n可以將進(jìn)程排隊(duì)的等待時(shí)間等因素納入優(yōu)先權(quán)可以將進(jìn)程排隊(duì)的等待時(shí)間等因素納入優(yōu)先權(quán)的計(jì)算，隨著進(jìn)程等待時(shí)間的增長(zhǎng)，其優(yōu)先權(quán)的計(jì)算，隨著進(jìn)程等待時(shí)間的增長(zhǎng)，其優(yōu)先權(quán)也不斷提高。也不斷提高。處理機(jī)調(diào)度的類型處理機(jī)調(diào)度的類型n作業(yè)調(diào)度（高級(jí)調(diào)度）作業(yè)調(diào)度（高級(jí)調(diào)度）n存儲(chǔ)對(duì)換（中級(jí)調(diào)度）存儲(chǔ)對(duì)換（中級(jí)調(diào)度）n進(jìn)程調(diào)度（低級(jí)調(diào)度）進(jìn)程調(diào)度（低級(jí)調(diào)度）處理機(jī)調(diào)度的層次處理機(jī)調(diào)度的層次作業(yè)輸入作業(yè)輸入后備后備就緒就緒阻塞阻塞就緒就緒阻塞阻塞執(zhí)行執(zhí)行完成完成作業(yè)調(diào)度作業(yè)調(diào)度存儲(chǔ)對(duì)換存儲(chǔ)對(duì)換進(jìn)程調(diào)度進(jìn)程調(diào)度內(nèi)存內(nèi)存外存外存作業(yè)輸出作業(yè)輸出作業(yè)調(diào)度作業(yè)調(diào)度n在批處理系統(tǒng)中，作業(yè)進(jìn)入系統(tǒng)后，先駐留在在批處理系

9、統(tǒng)中，作業(yè)進(jìn)入系統(tǒng)后，先駐留在磁盤上，組織成批處理隊(duì)列，稱為后備隊(duì)列。磁盤上，組織成批處理隊(duì)列，稱為后備隊(duì)列。n作業(yè)調(diào)度從該隊(duì)列中選擇一個(gè)或多個(gè)作業(yè)，為作業(yè)調(diào)度從該隊(duì)列中選擇一個(gè)或多個(gè)作業(yè)，為之創(chuàng)建進(jìn)程，分配必要的系統(tǒng)資源，并將新創(chuàng)之創(chuàng)建進(jìn)程，分配必要的系統(tǒng)資源，并將新創(chuàng)建的進(jìn)程插入就緒隊(duì)列，等待進(jìn)程調(diào)度。建的進(jìn)程插入就緒隊(duì)列，等待進(jìn)程調(diào)度。n某些具有交換技術(shù)的系統(tǒng)將新創(chuàng)建的進(jìn)程插入某些具有交換技術(shù)的系統(tǒng)將新創(chuàng)建的進(jìn)程插入到就緒到就緒/掛起隊(duì)列，等待中級(jí)調(diào)度。掛起隊(duì)列，等待中級(jí)調(diào)度。作業(yè)調(diào)度模型后備隊(duì)列就緒隊(duì)列就緒/掛起隊(duì)列處理機(jī)進(jìn)程調(diào)度作業(yè)調(diào)度交互用戶中級(jí)調(diào)度作業(yè)調(diào)度需要考慮的問題作業(yè)調(diào)度需

10、要考慮的問題n選擇多少個(gè)作業(yè)進(jìn)入內(nèi)存，為之創(chuàng)建進(jìn)程？選擇多少個(gè)作業(yè)進(jìn)入內(nèi)存，為之創(chuàng)建進(jìn)程？取決于允許同時(shí)在內(nèi)存中運(yùn)行的進(jìn)程數(shù)取決于允許同時(shí)在內(nèi)存中運(yùn)行的進(jìn)程數(shù)n選擇哪些作業(yè)？選擇哪些作業(yè)？取決于作業(yè)調(diào)度算法取決于作業(yè)調(diào)度算法進(jìn)程調(diào)度進(jìn)程調(diào)度n也稱低級(jí)調(diào)度，決定就緒隊(duì)列中的哪個(gè)進(jìn)程將也稱低級(jí)調(diào)度，決定就緒隊(duì)列中的哪個(gè)進(jìn)程將獲得處理機(jī)。獲得處理機(jī)。n進(jìn)程調(diào)度的運(yùn)行頻率是最高的。進(jìn)程調(diào)度的運(yùn)行頻率是最高的。n現(xiàn)代操作系統(tǒng)幾乎都具有進(jìn)程調(diào)度?，F(xiàn)代操作系統(tǒng)幾乎都具有進(jìn)程調(diào)度。進(jìn)程調(diào)度方式進(jìn)程調(diào)度方式n根據(jù)執(zhí)行進(jìn)程的處理機(jī)是由進(jìn)程自己釋放，還根據(jù)執(zhí)行進(jìn)程的處理機(jī)是由進(jìn)程自己釋放，還是被強(qiáng)行剝奪，可以將進(jìn)程

11、調(diào)度方式分為兩種是被強(qiáng)行剝奪，可以將進(jìn)程調(diào)度方式分為兩種非搶占方式非搶占方式搶占方式搶占方式進(jìn)程調(diào)度方式：非搶占方式進(jìn)程調(diào)度方式：非搶占方式n一旦把一旦把CPUCPU分配給某一進(jìn)程后分配給某一進(jìn)程后, ,便讓它一直運(yùn)行便讓它一直運(yùn)行下去，直到進(jìn)程運(yùn)行完成或發(fā)生某事件（申請(qǐng)下去，直到進(jìn)程運(yùn)行完成或發(fā)生某事件（申請(qǐng)I/OI/O）而不能運(yùn)行時(shí)，才將）而不能運(yùn)行時(shí)，才將CPUCPU分給其它進(jìn)程分給其它進(jìn)程n主要優(yōu)點(diǎn)是簡(jiǎn)單、系統(tǒng)開銷小。主要優(yōu)點(diǎn)是簡(jiǎn)單、系統(tǒng)開銷小。n該方式不利于該方式不利于“及時(shí)性及時(shí)性”要求較高的分時(shí)系統(tǒng)要求較高的分時(shí)系統(tǒng)和實(shí)時(shí)系統(tǒng)，主要用在批處理系統(tǒng)中。和實(shí)時(shí)系統(tǒng)，主要用在批處理系統(tǒng)

12、中。進(jìn)程調(diào)度方式：搶占方式進(jìn)程調(diào)度方式：搶占方式n系統(tǒng)可以基于某種策略（優(yōu)先級(jí)策略、時(shí)間片系統(tǒng)可以基于某種策略（優(yōu)先級(jí)策略、時(shí)間片策略等）剝奪現(xiàn)行進(jìn)程的策略等）剝奪現(xiàn)行進(jìn)程的CPUCPU，調(diào)度新的進(jìn)程執(zhí)，調(diào)度新的進(jìn)程執(zhí)行。行。n操作系統(tǒng)可以在新進(jìn)程到來時(shí)，或某個(gè)具有較操作系統(tǒng)可以在新進(jìn)程到來時(shí)，或某個(gè)具有較高優(yōu)先權(quán)的被阻塞進(jìn)程插入就緒隊(duì)列時(shí)，或在高優(yōu)先權(quán)的被阻塞進(jìn)程插入就緒隊(duì)列時(shí)，或在基于時(shí)間片調(diào)度的系統(tǒng)中，時(shí)間片用完而中斷基于時(shí)間片調(diào)度的系統(tǒng)中，時(shí)間片用完而中斷當(dāng)前進(jìn)程的運(yùn)行，調(diào)度新的進(jìn)程執(zhí)行。當(dāng)前進(jìn)程的運(yùn)行，調(diào)度新的進(jìn)程執(zhí)行。n該方式會(huì)產(chǎn)生較多的中斷，主要用在對(duì)實(shí)時(shí)性該方式會(huì)產(chǎn)生較多的中斷

13、，主要用在對(duì)實(shí)時(shí)性要求較高的實(shí)時(shí)系統(tǒng)及對(duì)性能要求較高的分時(shí)要求較高的實(shí)時(shí)系統(tǒng)及對(duì)性能要求較高的分時(shí)系統(tǒng)和批處理系統(tǒng)中，以便及時(shí)響應(yīng)各進(jìn)程的系統(tǒng)和批處理系統(tǒng)中，以便及時(shí)響應(yīng)各進(jìn)程的請(qǐng)求。請(qǐng)求。存儲(chǔ)對(duì)換存儲(chǔ)對(duì)換n又稱中級(jí)調(diào)度，它是對(duì)換功能的一部分。又稱中級(jí)調(diào)度，它是對(duì)換功能的一部分。n目的：為了提高內(nèi)存的利用率和系統(tǒng)吞吐量目的：為了提高內(nèi)存的利用率和系統(tǒng)吞吐量n當(dāng)內(nèi)存空間非常緊張時(shí)，或處理機(jī)找不到一個(gè)當(dāng)內(nèi)存空間非常緊張時(shí)，或處理機(jī)找不到一個(gè)可執(zhí)行的就緒進(jìn)程時(shí)，需要選擇一個(gè)進(jìn)程（阻可執(zhí)行的就緒進(jìn)程時(shí)，需要選擇一個(gè)進(jìn)程（阻塞或就緒狀態(tài)）換出到外存，釋放出內(nèi)存空間塞或就緒狀態(tài)）換出到外存，釋放出內(nèi)存空間

14、給別的進(jìn)程使用；當(dāng)內(nèi)存空間較充裕時(shí)，從外給別的進(jìn)程使用；當(dāng)內(nèi)存空間較充裕時(shí)，從外存選擇一個(gè)掛起狀態(tài)的進(jìn)程調(diào)度到內(nèi)存（換存選擇一個(gè)掛起狀態(tài)的進(jìn)程調(diào)度到內(nèi)存（換入）。入）。處理機(jī)調(diào)度模型就緒隊(duì)列就緒/掛起隊(duì)列阻塞/掛起隊(duì)列阻塞隊(duì)列作業(yè)調(diào)度進(jìn)程調(diào)度處理機(jī)存儲(chǔ)對(duì)換時(shí)間片用完完成事件發(fā)生事件等待后備隊(duì)列3.2 3.2 調(diào)度算法調(diào)度算法先來先服務(wù)（先來先服務(wù)（FCFS）n該方法按照進(jìn)程（作業(yè)）到達(dá)的先后順序排隊(duì)，每次調(diào)度隊(duì)首的進(jìn)程（作業(yè)）。nFCFS算法屬于非剝奪調(diào)度方式，實(shí)現(xiàn)簡(jiǎn)單，看似公平n但是，對(duì)于那些后進(jìn)入隊(duì)列而運(yùn)行時(shí)間較短的進(jìn)程（作業(yè)） ，或I/O型的進(jìn)程（作業(yè)）而言，可能需要長(zhǎng)時(shí)間等待。先來先服

15、務(wù)（先來先服務(wù)（FCFS）n假設(shè)就緒隊(duì)列中從隊(duì)首開始依次排列有三個(gè)進(jìn)程P1，P2，P3，P4（四個(gè)進(jìn)程同時(shí)到達(dá)內(nèi)存）。進(jìn)程P1運(yùn)行時(shí)間為12，進(jìn)程P2運(yùn)行時(shí)間為5，進(jìn)程P3運(yùn)行時(shí)間為3，進(jìn)程P4運(yùn)行時(shí)間為6 。若采用FCFS方法調(diào)度，試計(jì)算進(jìn)程P1，P2，P3，P4的周轉(zhuǎn)時(shí)間分別是多少？平均周轉(zhuǎn)時(shí)間是多少？先來先服務(wù)（先來先服務(wù)（FCFS）進(jìn)程進(jìn)程 到達(dá)時(shí)間到達(dá)時(shí)間 運(yùn)行時(shí)間運(yùn)行時(shí)間 開始時(shí)間開始時(shí)間 完成時(shí)間完成時(shí)間 周轉(zhuǎn)時(shí)間周轉(zhuǎn)時(shí)間平均周轉(zhuǎn)時(shí)間平均周轉(zhuǎn)時(shí)間 T=18.75P1 0 12 0 12 12P2 0 5 12 17 17P3 0 3 17 20 20FCFS調(diào)度算法性能調(diào)度算法性

16、能P4 0 6 20 26 26先來先服務(wù)（先來先服務(wù)（FCFS）n對(duì)短進(jìn)程（作業(yè)）不公平。n平均周轉(zhuǎn)時(shí)間長(zhǎng)：由于長(zhǎng)進(jìn)程（作業(yè)）可能排在隊(duì)列前面，必將增加隊(duì)列后部進(jìn)程（作業(yè)）的等待時(shí)間，從而將增加平均周轉(zhuǎn)時(shí)間。n不利于I/O型進(jìn)程（作業(yè)） ，未有效利用系統(tǒng)資源。n一般地，F(xiàn)CFS與其它調(diào)度算法混合使用。nFCFS算法同時(shí)適合于作業(yè)調(diào)度，進(jìn)程調(diào)度和存儲(chǔ)對(duì)換三種調(diào)度類型。短進(jìn)程（作業(yè)）優(yōu)先算法短進(jìn)程（作業(yè)）優(yōu)先算法n從就緒隊(duì)列中選出一估計(jì)運(yùn)行時(shí)間最短的進(jìn)程（作業(yè)） ，將處理機(jī)分配給它，使它立即執(zhí)行并一直執(zhí)行到完成或發(fā)生某事件而被阻塞放棄處理機(jī)時(shí)。n屬于非剝奪調(diào)度算法。當(dāng)某進(jìn)程獲得處理機(jī)，直到其執(zhí)行

17、完成，或需要等待某事件而阻塞時(shí)，才自動(dòng)釋放處理機(jī)。系統(tǒng)又調(diào)度新的進(jìn)程。短進(jìn)程（作業(yè)）優(yōu)先算法短進(jìn)程（作業(yè)）優(yōu)先算法n假設(shè)就緒隊(duì)列中從隊(duì)首開始依次排列有三個(gè)進(jìn)程P1，P2，P3，P4（四個(gè)進(jìn)程同時(shí)到達(dá)內(nèi)存）。進(jìn)程P1運(yùn)行時(shí)間為12，進(jìn)程P2運(yùn)行時(shí)間為5，進(jìn)程P3運(yùn)行時(shí)間為3，進(jìn)程P4運(yùn)行時(shí)間為6 。 若采用短進(jìn)程優(yōu)先方法調(diào)度，按照進(jìn)程預(yù)期執(zhí)行時(shí)間排序?yàn)檫M(jìn)程P3、進(jìn)程P2、進(jìn)程P4，進(jìn)程P1。試分別計(jì)算進(jìn)程P1，P2，P3，P4的周轉(zhuǎn)時(shí)間分別是多少？平均周轉(zhuǎn)時(shí)間是多少？短進(jìn)程（作業(yè)）優(yōu)先算法短進(jìn)程（作業(yè)）優(yōu)先算法進(jìn)程進(jìn)程 到達(dá)時(shí)間到達(dá)時(shí)間 運(yùn)行時(shí)間運(yùn)行時(shí)間 開始時(shí)間開始時(shí)間 完成時(shí)間完成時(shí)間 周轉(zhuǎn)

18、時(shí)間周轉(zhuǎn)時(shí)間平均周轉(zhuǎn)時(shí)間平均周轉(zhuǎn)時(shí)間 T=12.75P1 0 12 14 26 26 P2 0 5 3 8 8P3 0 3 0 3 3短進(jìn)程優(yōu)先調(diào)度算法性能短進(jìn)程優(yōu)先調(diào)度算法性能P4 0 6 8 14 14短作業(yè)（進(jìn)程）優(yōu)先算法短作業(yè)（進(jìn)程）優(yōu)先算法n與FCFS算法比較，短進(jìn)程優(yōu)先算法改善了系統(tǒng)的性能，降低了系統(tǒng)的平均等待時(shí)間，提高了系統(tǒng)的吞吐量。但是，該算法也存在一些問題：（1）可能導(dǎo)致長(zhǎng)進(jìn)程饑餓，這對(duì)長(zhǎng)進(jìn)程不公平（2）采用非剝奪調(diào)度方式，未考慮進(jìn)程的緊迫程度，不適合分時(shí)系統(tǒng)和事務(wù)處理系統(tǒng)。（3）很難準(zhǔn)確預(yù)測(cè)進(jìn)程的執(zhí)行時(shí)間時(shí)間片輪轉(zhuǎn)法時(shí)間片輪轉(zhuǎn)法n在一個(gè)分時(shí)聯(lián)機(jī)系統(tǒng)中，同時(shí)有n個(gè)人通過各自的

19、終端共享一臺(tái)主機(jī)。終端完成輸入/輸出操作，主機(jī)負(fù)責(zé)處理從終端發(fā)來的請(qǐng)求，為之建立進(jìn)程、協(xié)調(diào)各進(jìn)程的運(yùn)行，調(diào)度各個(gè)進(jìn)程等，并盡量滿足每個(gè)終端用戶對(duì)響應(yīng)時(shí)間的要求。時(shí)間片輪轉(zhuǎn)法時(shí)間片輪轉(zhuǎn)法終端1服務(wù)進(jìn)程終端2服務(wù)進(jìn)程終端n服務(wù)進(jìn)程終端1終端2終端n基于時(shí)間片輪轉(zhuǎn)調(diào)度主機(jī)一個(gè)基于時(shí)間片輪轉(zhuǎn)調(diào)度的聯(lián)機(jī)系統(tǒng)時(shí)間片輪轉(zhuǎn)法時(shí)間片輪轉(zhuǎn)法n在分時(shí)聯(lián)機(jī)系統(tǒng)中，n個(gè)進(jìn)程循環(huán)地獲得時(shí)間片而執(zhí)行。從系統(tǒng)中來看，它們是交替執(zhí)行的，但就每個(gè)終端用戶而言，都感覺到自己獨(dú)占了一臺(tái)主機(jī)，不受其他用戶的影響。這是通過進(jìn)程并發(fā)執(zhí)行實(shí)現(xiàn)的。n如果用戶數(shù)太多，主機(jī)處理的進(jìn)程將會(huì)急劇增加，進(jìn)程排隊(duì)等待的時(shí)間也會(huì)很長(zhǎng)，進(jìn)程的響應(yīng)時(shí)間也可能增

20、長(zhǎng)，用戶將明顯感覺到主機(jī)的速度變慢而不滿意n另外，時(shí)間片的大小也會(huì)影響進(jìn)程的響應(yīng)時(shí)間。時(shí)間片的設(shè)置時(shí)間片的設(shè)置n時(shí)間片輪轉(zhuǎn)屬于剝奪的調(diào)度算法，會(huì)產(chǎn)生中斷，進(jìn)行進(jìn)程切換。而進(jìn)程切換將會(huì)增加系統(tǒng)的額外開銷。n時(shí)間片太長(zhǎng) ， 不能保證系統(tǒng)各個(gè)用戶進(jìn)程及時(shí)得到響應(yīng)；時(shí)間片太短 ，用戶的一次請(qǐng)求需要多個(gè)時(shí)間片才能執(zhí)行完，增加調(diào)度開銷，降低系統(tǒng)的效率。n時(shí)間片大小的確定應(yīng)該綜合考慮系統(tǒng)的最大用戶數(shù)、響應(yīng)時(shí)間、系統(tǒng)效率等多種因素。時(shí)間片輪轉(zhuǎn)法時(shí)間片輪轉(zhuǎn)法n假設(shè)就緒隊(duì)列中從隊(duì)首開始依次排列有四個(gè)進(jìn)程P1，P2，P3，P4（四個(gè)進(jìn)程同時(shí)到達(dá)內(nèi)存）。進(jìn)程P1運(yùn)行時(shí)間為12，進(jìn)程P2運(yùn)行時(shí)間為5，進(jìn)程P3運(yùn)行時(shí)間為

21、3，進(jìn)程P4運(yùn)行時(shí)間為6 。若采用時(shí)間片輪轉(zhuǎn)調(diào)度算法，設(shè)時(shí)間片分別為4和1，試分別計(jì)算進(jìn)程P1，P2，P3，P4的周轉(zhuǎn)時(shí)間分別是多少？平均周轉(zhuǎn)時(shí)間是多少？時(shí)間片輪轉(zhuǎn)法時(shí)間片輪轉(zhuǎn)法0 5 10 15 20 25 TDCBADCBA進(jìn)程進(jìn)程q=4q=1運(yùn)行實(shí)例常用的調(diào)度算法（續(xù)）常用的調(diào)度算法（續(xù)）進(jìn)程名進(jìn)程名到達(dá)時(shí)間到達(dá)時(shí)間到達(dá)時(shí)間到達(dá)時(shí)間 運(yùn)行時(shí)間運(yùn)行時(shí)間 開始時(shí)間開始時(shí)間 完成時(shí)間完成時(shí)間 周轉(zhuǎn)時(shí)間周轉(zhuǎn)時(shí)間P1P2P3P4P1P2P3P4時(shí)間片時(shí)間片q=1時(shí)間片時(shí)間片q=4 0 12 0 26 26 0 5 1 17 17 0 3 2 11 11 0 6 3 20 20 平均周轉(zhuǎn)時(shí)間平均周轉(zhuǎn)

22、時(shí)間 T = 18.5 0 12 0 26 26 0 5 4 20 20 0 3 8 11 11 0 6 11 22 22 平均周轉(zhuǎn)時(shí)間平均周轉(zhuǎn)時(shí)間 T = 19.75時(shí)間片輪轉(zhuǎn)法時(shí)間片輪轉(zhuǎn)法n為了簡(jiǎn)單，圖中忽略了進(jìn)程切換時(shí)的系統(tǒng)開銷，而實(shí)際操作系統(tǒng)中，這類額外開銷是客觀存在的。n可見，采用基于時(shí)間片輪轉(zhuǎn)調(diào)度法，進(jìn)程的周轉(zhuǎn)時(shí)間和平均周轉(zhuǎn)時(shí)間并不比采用FCFS和短進(jìn)程優(yōu)先調(diào)度算法小。n加上進(jìn)程切換所需要的系統(tǒng)開銷，該算法的平均周轉(zhuǎn)時(shí)間還會(huì)增長(zhǎng)。時(shí)間片輪轉(zhuǎn)法時(shí)間片輪轉(zhuǎn)法n常用于分時(shí)系統(tǒng)及事務(wù)處理系統(tǒng)，合理的時(shí)間片大小將帶來滿意的響應(yīng)時(shí)間n通常，合理的時(shí)間片指，能讓80%左右的進(jìn)程在一個(gè)時(shí)間片內(nèi)完成

23、。n對(duì)于短的、計(jì)算型的進(jìn)程較有利n不適合于批處理系統(tǒng)的進(jìn)程調(diào)度n不利于I/O型的進(jìn)程基于優(yōu)先級(jí)的調(diào)度算法基于優(yōu)先級(jí)的調(diào)度算法n基于時(shí)間片輪轉(zhuǎn)調(diào)度法循環(huán)式地為每個(gè)被調(diào)度的進(jìn)程分配一個(gè)時(shí)間片，對(duì)每個(gè)進(jìn)程都是公平的。n然而，實(shí)際應(yīng)用中，進(jìn)程的性質(zhì)可能是不同的。例如，一個(gè)與用戶進(jìn)行交互的前臺(tái)進(jìn)程急迫地需要對(duì)用戶的輸入作出響應(yīng)，而一個(gè)后臺(tái)打印進(jìn)程的迫切性也許就不那么重要。n因此，可以為每個(gè)進(jìn)程定義一個(gè)優(yōu)先級(jí)，優(yōu)先級(jí)高的進(jìn)程將優(yōu)先獲得處理機(jī)的調(diào)度。如何設(shè)定進(jìn)程的優(yōu)先級(jí)如何設(shè)定進(jìn)程的優(yōu)先級(jí)n進(jìn)程完成功能的重要性n進(jìn)程完成功能的急迫性n為均衡系統(tǒng)資源的使用，指定進(jìn)程（作業(yè)）優(yōu)先級(jí)n進(jìn)程對(duì)資源的占用程度，例如，

24、可以為短進(jìn)程（或作業(yè)）賦予較高的優(yōu)先級(jí)靜態(tài)優(yōu)先級(jí)和動(dòng)態(tài)優(yōu)先級(jí)靜態(tài)優(yōu)先級(jí)和動(dòng)態(tài)優(yōu)先級(jí)n靜態(tài)優(yōu)先級(jí)：靜態(tài)優(yōu)先級(jí)：在進(jìn)程創(chuàng)建時(shí)確定的，運(yùn)行時(shí)保持不變通常賦予系統(tǒng)進(jìn)程較高優(yōu)先級(jí)；申請(qǐng)資源量少的賦予較高優(yōu)先級(jí)。n動(dòng)態(tài)優(yōu)先級(jí)：動(dòng)態(tài)優(yōu)先級(jí)：在創(chuàng)建進(jìn)程時(shí)賦予的優(yōu)先級(jí)，在進(jìn)程運(yùn)行過程中可以自動(dòng)改變，以使進(jìn)程獲得更好的調(diào)度性能。動(dòng)態(tài)優(yōu)先級(jí)動(dòng)態(tài)優(yōu)先級(jí)n影響進(jìn)程動(dòng)態(tài)優(yōu)先級(jí)的因素：進(jìn)程等待時(shí)間和占用處理機(jī)時(shí)間 進(jìn)程優(yōu)先級(jí)隨著進(jìn)程運(yùn)行的剩余時(shí)間的減少而上升，使將要執(zhí)行結(jié)束的進(jìn)程盡快完成。就緒隊(duì)列中，等待時(shí)間延長(zhǎng)則優(yōu)先級(jí)提高，從而使優(yōu)先級(jí)較低的進(jìn)程在等待足夠的時(shí)間后，其優(yōu)先級(jí)提高到可被調(diào)度執(zhí)行。n具體實(shí)現(xiàn)方法，可以在每個(gè)時(shí)

25、鐘中斷時(shí)，或需要進(jìn)程切換時(shí)，重新計(jì)算就緒隊(duì)列中各進(jìn)程的優(yōu)先級(jí)，并優(yōu)先調(diào)度優(yōu)先級(jí)高的進(jìn)程。動(dòng)態(tài)優(yōu)先級(jí)動(dòng)態(tài)優(yōu)先級(jí)n采用動(dòng)態(tài)優(yōu)先級(jí)的兩種調(diào)度算法：剩余時(shí)間最短者優(yōu)先和響應(yīng)比高者優(yōu)先剩余時(shí)間最短者優(yōu)先剩余時(shí)間最短者優(yōu)先n為了使將要結(jié)束的進(jìn)程盡早結(jié)束，釋放系統(tǒng)資源，讓別的進(jìn)程執(zhí)行。可以在每個(gè)時(shí)鐘中斷時(shí)，根據(jù)就緒隊(duì)列中各進(jìn)程的剩余執(zhí)行時(shí)間動(dòng)態(tài)調(diào)整其優(yōu)先級(jí)，剩余時(shí)間最短的進(jìn)程優(yōu)先級(jí)最高。n顯然，該算法是剝奪型的短進(jìn)程優(yōu)先調(diào)度算法，調(diào)度程序總是選擇剩余執(zhí)行時(shí)間最短的進(jìn)程調(diào)度執(zhí)行。剩余時(shí)間最短者優(yōu)先剩余時(shí)間最短者優(yōu)先n與短進(jìn)程優(yōu)先調(diào)度算法一樣，該調(diào)度算法很難準(zhǔn)確估計(jì)進(jìn)程的剩余執(zhí)行時(shí)間n由于長(zhǎng)進(jìn)程在未執(zhí)行時(shí)，或剛

26、開始執(zhí)行的一段時(shí)間內(nèi)，其剩余執(zhí)行時(shí)間都不會(huì)最短，所以該算法對(duì)長(zhǎng)進(jìn)程不公平n但是，它不像FCFS算法偏袒長(zhǎng)進(jìn)程，也不像輪轉(zhuǎn)調(diào)度算法會(huì)產(chǎn)生很多中斷而增加系統(tǒng)負(fù)擔(dān)。另一方面，它必須記錄過去的服務(wù)時(shí)間，增加了系統(tǒng)開銷。n由于短進(jìn)程提前完成，故采用剩余時(shí)間最短者優(yōu)先的調(diào)度算法獲得的平均周轉(zhuǎn)時(shí)間比采用短進(jìn)程優(yōu)先算法短。響應(yīng)比高者優(yōu)先響應(yīng)比高者優(yōu)先n將進(jìn)程的等待時(shí)間和進(jìn)程的預(yù)期執(zhí)行時(shí)間納入優(yōu)先級(jí)的計(jì)算，進(jìn)程預(yù)期執(zhí)行時(shí)間越長(zhǎng)優(yōu)先級(jí)越低，而隨著進(jìn)程的等待時(shí)間增長(zhǎng)優(yōu)先級(jí)上升，即進(jìn)程的優(yōu)先級(jí)與等待時(shí)間成正比，與進(jìn)程執(zhí)行時(shí)間成反比。令w表示等待時(shí)間，s表示預(yù)期執(zhí)行時(shí)間，則響應(yīng)比： w+ss=ws+1R=響應(yīng)比高者優(yōu)先

27、響應(yīng)比高者優(yōu)先n調(diào)度方法：若當(dāng)前執(zhí)行進(jìn)程執(zhí)行完畢，或需要阻塞等待某事件而釋放處理機(jī)，調(diào)度程序選擇就緒隊(duì)列中響應(yīng)比最大的進(jìn)程執(zhí)行n若等待時(shí)間相同，短進(jìn)程因?yàn)閟較小，R較大而優(yōu)先調(diào)度。若進(jìn)程的預(yù)期執(zhí)行時(shí)間相同，則等待時(shí)間長(zhǎng)的進(jìn)程優(yōu)先調(diào)度，相當(dāng)于FCFS。n隨著等待時(shí)間的增加，長(zhǎng)進(jìn)程的響應(yīng)比不斷增大，在某個(gè)時(shí)刻，也必然被調(diào)度。 響應(yīng)比高者優(yōu)先響應(yīng)比高者優(yōu)先n同短進(jìn)程優(yōu)先和剩余時(shí)間最短者優(yōu)先調(diào)度算法一樣，很難準(zhǔn)確估計(jì)進(jìn)程的預(yù)期執(zhí)行時(shí)間n每次調(diào)度之前都需要計(jì)算響應(yīng)比，增加了系統(tǒng)開銷。 多級(jí)反饋隊(duì)列調(diào)度算法多級(jí)反饋隊(duì)列調(diào)度算法n前面介紹的幾種調(diào)度算法都存在各自不同的問題，尤其是短進(jìn)程優(yōu)先、剩余時(shí)間最短者優(yōu)

28、先以及響應(yīng)比高者優(yōu)先調(diào)度算法都需要估計(jì)進(jìn)程的預(yù)期執(zhí)行時(shí)間，如果估計(jì)不準(zhǔn)確，將影響調(diào)度結(jié)果和系統(tǒng)性能。n如果根據(jù)進(jìn)程執(zhí)行歷史，而非未來，進(jìn)行調(diào)度，將解決這個(gè)問題。n反饋調(diào)度法就是一種根據(jù)進(jìn)程執(zhí)行歷史調(diào)整調(diào)度方式的調(diào)度方法，它結(jié)合了優(yōu)先級(jí)和時(shí)間片輪轉(zhuǎn)調(diào)度思想。 多級(jí)反饋隊(duì)列調(diào)度算法多級(jí)反饋隊(duì)列調(diào)度算法n多級(jí)反饋隊(duì)列算法中，系統(tǒng)設(shè)置多個(gè)就緒隊(duì)列，進(jìn)程在其生命期內(nèi)可能在多個(gè)就緒隊(duì)列中存在。n各個(gè)隊(duì)列賦予不同的優(yōu)先級(jí)。第一個(gè)隊(duì)列的優(yōu)先級(jí)最高，其余各隊(duì)列的優(yōu)先權(quán)逐個(gè)降低。n各個(gè)隊(duì)列中進(jìn)程執(zhí)行的時(shí)間片大小也各不相同，在優(yōu)先權(quán)越高的隊(duì)列中，每個(gè)進(jìn)程的執(zhí)行時(shí)間片就越小。就緒隊(duì)列0就緒隊(duì)列1就緒隊(duì)列n處理機(jī)處理機(jī)

29、處理機(jī)調(diào)度調(diào)度調(diào)度完成完成完成接納其中，優(yōu)先級(jí)按就緒隊(duì)列0,1，,n逐級(jí)降低 時(shí)間片按就緒隊(duì)列0,1，,n逐級(jí)增長(zhǎng)多級(jí)反饋隊(duì)列調(diào)度算法的實(shí)施過程多級(jí)反饋隊(duì)列調(diào)度算法的實(shí)施過程n新創(chuàng)建的進(jìn)程進(jìn)入內(nèi)存后，排在最高優(yōu)先級(jí)隊(duì)列的末尾，按FCFS原則等待調(diào)度。n該進(jìn)程執(zhí)行時(shí)， 如果它在一個(gè)時(shí)間片結(jié)束時(shí)尚未完成，調(diào)度程序便將該進(jìn)程轉(zhuǎn)入下一個(gè)較低優(yōu)先級(jí)隊(duì)列的隊(duì)尾。n當(dāng)一個(gè)長(zhǎng)進(jìn)程從第一隊(duì)列依次降到第n隊(duì)列后，在第n隊(duì)列中便采取按時(shí)間片輪轉(zhuǎn)的方式運(yùn)行。n調(diào)度時(shí)，總是先調(diào)度優(yōu)先級(jí)高的隊(duì)列。僅當(dāng)該隊(duì)列空時(shí)，才調(diào)度次高優(yōu)先級(jí)隊(duì)列，以此類推，第n個(gè)隊(duì)列進(jìn)程被調(diào)度時(shí)，必須是前n-1個(gè)隊(duì)列為空。n如果處理機(jī)正在第i個(gè)隊(duì)列中

30、為某進(jìn)程服務(wù)時(shí)，又有新進(jìn)程進(jìn)入優(yōu)先權(quán)較高的隊(duì)列，則此時(shí)新進(jìn)程將搶占處理機(jī)，由調(diào)度程序把正在運(yùn)行的進(jìn)程放回到第i+1個(gè)隊(duì)列的末尾，把處理機(jī)分配給新到的進(jìn)程。多級(jí)反饋隊(duì)列調(diào)度算法多級(jí)反饋隊(duì)列調(diào)度算法l優(yōu)點(diǎn)：多級(jí)反饋隊(duì)列調(diào)度算法能較好的滿足各種類型用戶的需要 終端型作業(yè)用戶：終端型作業(yè)大都屬于交互型作業(yè)，作業(yè)通常較小，系統(tǒng)只要能使這些作業(yè)在第一就緒隊(duì)列所規(guī)定的時(shí)間片內(nèi)完成，便可使終端用戶得到滿意。短批處理作業(yè)用戶：如果可在第一隊(duì)列中執(zhí)行一個(gè)時(shí)間片即可完成，便可獲得與終端用戶一樣的響應(yīng)時(shí)間，對(duì)于稍長(zhǎng)的作業(yè)，通常也只須在第二隊(duì)列和第三隊(duì)列各執(zhí)行一個(gè)時(shí)間片即可完成。長(zhǎng)批處理作業(yè)用戶：對(duì)于長(zhǎng)作業(yè)，它將依次在

31、第1,2，,n個(gè)隊(duì)列中運(yùn)行，然后再按時(shí)間片輪轉(zhuǎn)方式運(yùn)行，用戶不必?fù)?dān)心其作業(yè)長(zhǎng)期得不到處理。多級(jí)反饋隊(duì)列調(diào)度算法多級(jí)反饋隊(duì)列調(diào)度算法缺點(diǎn)：n但可能使長(zhǎng)進(jìn)程的周轉(zhuǎn)時(shí)間急劇增加。n如果不斷地有新進(jìn)程到來，還可能出現(xiàn)長(zhǎng)進(jìn)程饑餓現(xiàn)象。進(jìn)程調(diào)度算法小結(jié)進(jìn)程調(diào)度算法小結(jié)n如何選擇進(jìn)程調(diào)度算法與系統(tǒng)設(shè)計(jì)的目標(biāo)有關(guān)n交互式多任務(wù)系統(tǒng)，主要考慮聯(lián)機(jī)用戶對(duì)響應(yīng)時(shí)間的要求，一般采用基于時(shí)間片輪轉(zhuǎn)調(diào)度算法，同時(shí)，根據(jù)進(jìn)程的性質(zhì)設(shè)置不同的優(yōu)先級(jí)n批處理系統(tǒng)往往以作業(yè)的平均周轉(zhuǎn)時(shí)間來衡量調(diào)度性能，常選用基于優(yōu)先級(jí)的短進(jìn)程優(yōu)先調(diào)度算法。3.3 3.3 死鎖死鎖n進(jìn)程的并發(fā)控制不僅要控制若干進(jìn)程的同步和互斥，確保進(jìn)程之間正常通

32、信，還需要解決進(jìn)程死鎖問題n一旦出現(xiàn)進(jìn)程死鎖，相應(yīng)的進(jìn)程將無法向前推進(jìn)。如果系統(tǒng)內(nèi)的絕大多數(shù)進(jìn)程或全部進(jìn)程死鎖，那么，整個(gè)系統(tǒng)將處于癱瘓狀態(tài)，造成系統(tǒng)“死機(jī)”。交通中的死鎖現(xiàn)象交通中的死鎖現(xiàn)象死鎖的例子死鎖的例子1例：一個(gè)計(jì)算機(jī)系統(tǒng)中，有兩臺(tái)打印機(jī)和兩個(gè)進(jìn)程，某一時(shí)刻，每個(gè)進(jìn)程都各自占有一臺(tái)打印機(jī)，同時(shí)還要再請(qǐng)求一臺(tái)打印機(jī)才能完成他們各自的任務(wù)，由于系統(tǒng)再無空閑的打印機(jī)，兩個(gè)進(jìn)程就處于永遠(yuǎn)的等待狀態(tài)。我們就說系統(tǒng)產(chǎn)生了死鎖。死鎖的例子死鎖的例子2例：兩個(gè)進(jìn)程：P1，P2 共享兩類系統(tǒng)資源：R1，R2進(jìn)程 P1:Get(R1)Get(R2)Release(R1)Release(R2)進(jìn)程 P2:

33、Get(R2)Get(R1)Release(R2)Release(R1)死鎖的例子死鎖的例子2P1、P2推進(jìn)順序l合法順序 P1：Get（R1）；P1： Get （R2）； P1：Release（R1）； P1：Release（R2）； P2： Get （R2）；P2： Get （R1）； P2：Release（R2）； P2：Release（R1）；l非法順序死鎖 P1： Get （R1）；P2： Get （R2）； P1： Get （R2）；P2： Get （R1）；進(jìn)程推進(jìn)順序和死鎖進(jìn)程推進(jìn)順序和死鎖P2得到R2P2得到R1P2釋放R2P2釋放R1死鎖區(qū)P1得到R1P1得到R2P1釋放R

34、1P1釋放R2進(jìn)程P2進(jìn)程P1死鎖的定義死鎖的定義n多個(gè)進(jìn)程在運(yùn)行過程中因競(jìng)爭(zhēng)資源或推進(jìn)順序不當(dāng)而造成的一種僵局，處于這種僵局狀態(tài)的進(jìn)程，若無外力作用，將永遠(yuǎn)不能向前推進(jìn)。n若系統(tǒng)出現(xiàn)死鎖，必須有相應(yīng)的措施進(jìn)行解決。死鎖產(chǎn)生的原因死鎖產(chǎn)生的原因n競(jìng)爭(zhēng)資源。競(jìng)爭(zhēng)資源。當(dāng)系統(tǒng)中供多個(gè)進(jìn)程共享的資源數(shù)目不足以滿足進(jìn)程的需要時(shí)，會(huì)引起諸進(jìn)程對(duì)資源的競(jìng)爭(zhēng)而可能產(chǎn)生死鎖。n進(jìn)程推進(jìn)順序不當(dāng)。進(jìn)程推進(jìn)順序不當(dāng)。進(jìn)程運(yùn)行過程中，請(qǐng)求和釋放資源的順序不當(dāng)而產(chǎn)生死鎖。競(jìng)爭(zhēng)資源n引起進(jìn)程死鎖的一個(gè)主要原因是由于進(jìn)程競(jìng)爭(zhēng)系統(tǒng)中的資源，而進(jìn)程對(duì)資源的總需求量超過系統(tǒng)能夠提供的最大資源量。n系統(tǒng)中的資源大體可以分為兩類：

35、可重用資源和可消耗資源可重用資源n可重用資源指某一時(shí)刻僅允許一個(gè)進(jìn)程使用的、不能被進(jìn)程消耗的、釋放以后還可以被其他進(jìn)程使用的資源n如處理機(jī)、I/O通道、主存和輔存、設(shè)備以及諸如文件、數(shù)據(jù)庫、信號(hào)量之類的數(shù)據(jù)結(jié)構(gòu)。剝奪資源和不可剝奪資源剝奪資源和不可剝奪資源n按照可重用資源的特性，可分成兩類： 可剝奪性資源，又稱可搶占資源可剝奪性資源，又稱可搶占資源，當(dāng)資源從占用它的進(jìn)程被剝奪走時(shí)，對(duì)進(jìn)程不產(chǎn)生破壞性的影響。如CPU 不可剝奪性資源，又稱不可搶占資源不可剝奪性資源，又稱不可搶占資源，資源一旦分配，不能強(qiáng)行回收，只能在進(jìn)程用完后由其自動(dòng)釋放。如打印機(jī)，磁帶機(jī)，刻錄機(jī)進(jìn)程對(duì)不可搶占資源的使用順序進(jìn)程

36、對(duì)不可搶占資源的使用順序n一個(gè)進(jìn)程必須按照下述順序使用不可搶占資源 請(qǐng)求資源：請(qǐng)求資源：若請(qǐng)求的資源不能立即滿足，則申請(qǐng)者等待。 使用資源：使用資源：獲得資源后，可以使用它。 釋放資源：釋放資源：資源使用完畢，要?dú)w還系統(tǒng)。進(jìn)程競(jìng)爭(zhēng)不可搶占資源可能會(huì)發(fā)生死鎖n例如：兩個(gè)進(jìn)程P1和P2，競(jìng)爭(zhēng)磁盤文件D和磁帶設(shè)備T。某一時(shí)刻，進(jìn)程P1獲得了磁盤文件D，進(jìn)程P2獲得了磁帶設(shè)備T，進(jìn)程P1要想繼續(xù)執(zhí)行必須得到磁帶設(shè)備T，而磁帶設(shè)備T已經(jīng)分配給了進(jìn)程P2，所有P1阻塞等待；而進(jìn)程P2要想繼續(xù)執(zhí)行必須得到磁盤文件D，而磁盤文件已經(jīng)分配給了進(jìn)程P1，所以P2阻塞等待。這樣系統(tǒng)出現(xiàn)了死鎖?？上馁Y源n可消費(fèi)資源

37、，指可以創(chuàng)造（生產(chǎn)）和撤消（消耗）的資源，其數(shù)量不限。n如中斷、信號(hào)、消息、緩沖區(qū)中的數(shù)據(jù)等。n進(jìn)程競(jìng)爭(zhēng)可消耗資源也可能產(chǎn)生死鎖。進(jìn)程競(jìng)爭(zhēng)可消耗資源可能會(huì)發(fā)生死鎖Process P1：receive(P2,msg1)send(P2,msg3)Process P2：receive(P1,msg2)send(P1,msg4)資源分配圖資源分配圖n用有向圖研究進(jìn)程和資源的關(guān)系資源已經(jīng)分配給進(jìn)程進(jìn)程請(qǐng)求資源進(jìn)程對(duì)資源的各種情況進(jìn)程對(duì)資源的各種情況RA資源R分配給進(jìn)程ASB進(jìn)程B請(qǐng)求資源SP1P2R1R2死鎖狀態(tài)資源分配圖資源分配圖進(jìn)進(jìn)程程占用情況占用情況請(qǐng)求情況請(qǐng)求情況r1r2r3r1r2r3P11個(gè)

38、個(gè)2個(gè)個(gè)1個(gè)個(gè)P22個(gè)個(gè)1個(gè)個(gè)P32個(gè)個(gè)2個(gè)個(gè)1個(gè)個(gè)死鎖產(chǎn)生的條件死鎖產(chǎn)生的條件1. 1. 互斥條件互斥條件：指進(jìn)程對(duì)所分配到的資源進(jìn)行排它性使用。2. 2. 請(qǐng)求和保持條件請(qǐng)求和保持條件：進(jìn)程已經(jīng)保持了至少一個(gè)資源，但又請(qǐng)求新資源，而所請(qǐng)求的資源已被其它進(jìn)程占用，此時(shí)請(qǐng)求進(jìn)程阻塞等待，但又對(duì)已經(jīng)分配給它的資源保持不放。3. 3. 不剝奪條件不剝奪條件：進(jìn)程已經(jīng)獲得的資源，在未用完之前不能被剝奪，只能是使用完時(shí)自己釋放。死鎖產(chǎn)生的條件死鎖產(chǎn)生的條件4. 4. 環(huán)路等待條件環(huán)路等待條件：發(fā)生死鎖時(shí)，必然存在一個(gè)進(jìn)程-資源循環(huán)鏈，鏈中有二個(gè)或多個(gè)進(jìn)程，每一個(gè)進(jìn)程正在等待鏈中的下一個(gè)成員保持的資源。

39、死鎖產(chǎn)生的條件死鎖產(chǎn)生的條件n前三個(gè)條件是死鎖產(chǎn)生的必要條件，但不是充分條件。n互斥條件是臨界資源固有的屬性，保證進(jìn)程互斥訪問臨界資源是必要的。不能因?yàn)榛コ鈺?huì)導(dǎo)致死鎖而禁止互斥。n“請(qǐng)求和保持”條件很多時(shí)候都存在，也是合理的。不可能要求進(jìn)程每次申請(qǐng)新資源時(shí)，必須釋放已占有資源。n“不剝奪”條件也是應(yīng)該保留的。允許剝奪的資源是指那些一旦剝奪中斷進(jìn)程的執(zhí)行以后，可以從斷點(diǎn)恢復(fù)執(zhí)行的資源。否則，屬于非剝奪資源。死鎖產(chǎn)生的條件死鎖產(chǎn)生的條件n第四個(gè)條件實(shí)際上是前三個(gè)條件的可能導(dǎo)致的結(jié)果，即只有存在互斥、占有且等待與非剝奪條件，就可能出現(xiàn)循環(huán)等待。n只要系統(tǒng)出現(xiàn)循環(huán)等待，則一定出現(xiàn)死鎖。n這四個(gè)條件構(gòu)成

40、了死鎖產(chǎn)生的充分必要條件。處理死鎖的方法處理死鎖的方法n預(yù)防死鎖預(yù)防死鎖：通過設(shè)置某些限制條件，去破壞產(chǎn)生死鎖的四個(gè)必要條件中的一個(gè)或幾個(gè)。n避免死鎖避免死鎖：在系統(tǒng)的資源分配過程中，用某種方法去防止系統(tǒng)進(jìn)入不安全狀態(tài)（可能會(huì)導(dǎo)致思索的狀態(tài)），從而避免發(fā)生死鎖。n檢測(cè)和解除死鎖檢測(cè)和解除死鎖：當(dāng)進(jìn)程申請(qǐng)資源時(shí)，不進(jìn)行任何限制，即允許死鎖發(fā)生。但要求系統(tǒng)定期或不定期檢測(cè)是否有死鎖發(fā)生。當(dāng)檢測(cè)到系統(tǒng)中已發(fā)生死鎖時(shí)，將進(jìn)程從死鎖狀態(tài)中解脫出來。預(yù)防死鎖預(yù)防死鎖破壞死鎖產(chǎn)生的條件：l破壞互斥條件l破壞保持和請(qǐng)求條件l破壞非剝奪條件l破壞循環(huán)等待條件預(yù)防死鎖：破壞“互斥”n產(chǎn)生死鎖的第一個(gè)條件是“互斥”

41、，而資源“互斥使用”是臨界資源的固有屬性，保證進(jìn)程互斥訪問臨界資源是必要的。不能因?yàn)榛コ鈺?huì)導(dǎo)致死鎖而禁止互斥。預(yù)防死鎖：破壞“請(qǐng)求和保持”n為了破壞“請(qǐng)求和保持”條件，系統(tǒng)將要求所有進(jìn)程一次性地申請(qǐng)其所需的全部資源。n不合理 第一，降低了系統(tǒng)吞吐量和資源利用率 第二，浪費(fèi)資源。預(yù)防死鎖：破壞“非剝奪”n當(dāng)一個(gè)已經(jīng)獲得了某些資源的進(jìn)程，再申請(qǐng)的新資源不能立即得到滿足時(shí)，必須釋放其已獲得的所有資源， 不論是何種資源。n這種預(yù)防死鎖的策略實(shí)現(xiàn)起來比較復(fù)雜，而且要付出很大代價(jià)。n只有在資源狀態(tài)可以很容易地保存和恢復(fù)的情況下，這種方法才是實(shí)用的。預(yù)防死鎖：破壞“環(huán)路等待”n為了避免進(jìn)程申請(qǐng)資源形成環(huán)路，

42、首先將系統(tǒng)中的所有資源按類型進(jìn)行線性排序，并賦予不同的序號(hào)。n所有進(jìn)程對(duì)資源的請(qǐng)求，必須嚴(yán)格按資源序號(hào)遞增的次序提出，這樣在所形成的資源分配圖中不可能再出現(xiàn)環(huán)路。預(yù)防死鎖：破壞“環(huán)路等待”例題： 系統(tǒng)擁有資源為：輸入機(jī)（序號(hào)1），打印機(jī)（序號(hào)2） ，繪圖機(jī)（序號(hào)3） ，磁帶機(jī)（序號(hào)4） ，光盤（序號(hào)5） 。 系統(tǒng)有兩個(gè)進(jìn)程A和B 所有進(jìn)程對(duì)資源的請(qǐng)求必須嚴(yán)格按序號(hào)遞增順序進(jìn)行。如果A占有資源j，B占有資源i。若ij，允許A請(qǐng)求B占有的資源i，但絕不允許B請(qǐng)求A占有的資源j，故進(jìn)程資源分配圖絕不會(huì)形成環(huán)路。預(yù)防死鎖：破壞“環(huán)路等待”n較之前兩種策略，不論是資源利用率還是系統(tǒng)吞吐量，都有顯著的改善

43、。n但也存在嚴(yán)重問題 第一，為系統(tǒng)中各類資源分配的序號(hào)必須相對(duì)穩(wěn)定，這就限制了新設(shè)備類型的增加 第二，會(huì)經(jīng)常發(fā)生作業(yè)使用的順序與系統(tǒng)規(guī)定順序不同的情況，造成資源浪費(fèi) 第三，增加了程序設(shè)計(jì)難度。避免死鎖n預(yù)防死鎖限制條件太強(qiáng)，不利于提高系統(tǒng)吞吐量和資源利用率，而且增加了程序設(shè)計(jì)難度。因此，該方法在死鎖解決中不常用。n避免死鎖方法通過資源分配之前預(yù)測(cè)是否會(huì)導(dǎo)致死鎖，決定是否進(jìn)行此次資源分配。只有不會(huì)導(dǎo)致死鎖的資源請(qǐng)求才實(shí)施分配，否則，讓請(qǐng)求進(jìn)程阻塞等待。n首先介紹系統(tǒng)的兩種狀態(tài)：安全狀態(tài)和不安全狀態(tài)。安全狀態(tài)和不安全狀態(tài)n安全狀態(tài)：安全狀態(tài)：是指系統(tǒng)如果能夠按照某種進(jìn)程順序（p1,p2,pn）,來

44、為每個(gè)進(jìn)程pi分配其所需資源，直至滿足每個(gè)進(jìn)程對(duì)資源的最大需求，使每個(gè)進(jìn)程都可順利的完成，則稱系統(tǒng)處于不安全狀態(tài)。n稱（p1，p2，,pn）序列為安全序列n不安全狀態(tài)：不安全狀態(tài)：如果系統(tǒng)無法找到一個(gè)安全序列，則稱系統(tǒng)處于不安全狀態(tài)。安全狀態(tài)和不安全狀態(tài)n若系統(tǒng)處于安全狀態(tài)，且按照某個(gè)安全序列分配資源，可以保證系統(tǒng)不會(huì)出現(xiàn)死鎖。n并非所有不安全狀態(tài)都是死鎖狀態(tài)。n當(dāng)系統(tǒng)進(jìn)入不安全狀態(tài)以后，便可能進(jìn)入死鎖狀態(tài)。n因此，避免死鎖的實(shí)質(zhì)在于：如何避免系統(tǒng)進(jìn)入不安全狀態(tài)。安全狀態(tài)的實(shí)例n假定系統(tǒng)中有三個(gè)進(jìn)程P1、P2、P3，共有16臺(tái)打印機(jī)，進(jìn)程P1總共要求12臺(tái)打印機(jī)，進(jìn)程P2總共要求7臺(tái)打印機(jī)，進(jìn)

45、程P3總共要求10臺(tái)打印機(jī)，在T0時(shí)刻，資源分配情況如下表所示： 進(jìn)程最大需求已分配尚需請(qǐng)求系統(tǒng)可用數(shù)P112483P2743P31055安全狀態(tài)的實(shí)例 在上表中，空閑打印機(jī)的數(shù)目為3臺(tái)，可把3臺(tái)打印機(jī)分配給P2，使P2繼續(xù)運(yùn)行直至完成；P2完成后便釋放出所占據(jù)的4臺(tái)打印機(jī)，使可用打印機(jī)數(shù)目增至7臺(tái)，可取出5臺(tái)分配給P3，使P3運(yùn)行直至完成；P3完成后將釋放出10臺(tái)打印機(jī)，P1便能獲得足夠的資源，從而P1、P2、P3均能順利完成。 由上分析可知，在T0時(shí)刻存在著一個(gè)安全序列P2,P3,P1，因此T0時(shí)刻是安全的。不安全狀態(tài)的實(shí)例n假定系統(tǒng)中有三個(gè)進(jìn)程P1、P2、P3，共有16臺(tái)打印機(jī)，進(jìn)程P1

46、總共要求12臺(tái)打印機(jī)，進(jìn)程P2總共要求7臺(tái)打印機(jī)，進(jìn)程P3總共要求10臺(tái)打印機(jī)，在T1時(shí)刻，資源分配情況如下表所示： 進(jìn)程最大需求已分配尚需請(qǐng)求系統(tǒng)可用數(shù)P112661P2743P31055不安全狀態(tài)的實(shí)例 此時(shí)，系統(tǒng)中只剩下1臺(tái)打印機(jī)，不能滿足P1P3任一進(jìn)程的資源需求，因此，從T1狀態(tài)繼續(xù)向前推進(jìn)，無論按照何種序列，P1P3進(jìn)程都將因?yàn)榈貌坏阶銐虻拇蛴C(jī)資源而相繼進(jìn)入阻塞，系統(tǒng)將陷入死鎖狀態(tài)。 由于在T1時(shí)刻找不到一個(gè)安全序列，故T1時(shí)刻是一個(gè)不安全狀態(tài)。安全狀態(tài)可以向不安全狀態(tài)轉(zhuǎn)換n如果不按照安全序列分配資源，系統(tǒng)將由安全狀態(tài)進(jìn)入不安全狀態(tài)n例如，在T0時(shí)刻，P3請(qǐng)求一臺(tái)打印機(jī)，若系統(tǒng)把

47、剩余的3臺(tái)中的1臺(tái)分配給P3，則系統(tǒng)進(jìn)入不安全狀態(tài)。避免死鎖：銀行家算法n最有代表性的避免死鎖的算法，是Dijkstra的銀行家算法。n該算法可用于銀行發(fā)放一筆貸款前，預(yù)測(cè)該筆貸款是否會(huì)引起銀行資金周轉(zhuǎn)問題。n例如：有四個(gè)顧客：A，B，C，D，每個(gè)顧客提出的最大貸款數(shù)量分別為6、5、4、7(以千美元為單位)。銀行家知道不是所有顧客都馬上需要其全部貸款（22）。因此，他只保留10個(gè)單位的貸款數(shù)量為這些顧客服務(wù)。n這里，銀行的資金就類似于計(jì)算機(jī)系統(tǒng)的資源，貸款業(yè)務(wù)類似于計(jì)算機(jī)的資源分配。初始狀態(tài)n銀行家擁有的貸款數(shù)量: 10顧客最大貸款數(shù) 擁有貸款數(shù) 還需貸款數(shù)A606B505C404D707安全

48、狀態(tài)n當(dāng)前銀行家擁有的貸款數(shù)量2，存在安全序列：CBAD，系統(tǒng)處于安全狀態(tài)。顧客最大貸款數(shù)擁有貸款數(shù)還需貸款數(shù)A615B514C422D743不安全狀態(tài)n當(dāng)B請(qǐng)求一個(gè)單位的貸款時(shí)，銀行家把錢貸給他，當(dāng)前銀行家擁有的貸款數(shù)量: 1，系統(tǒng)處于不安全狀態(tài)。顧客最大貸款數(shù)擁有貸款數(shù)還需貸款數(shù)A615B523C422D743銀行家算法n 銀行家算法可陳述如下：當(dāng)一個(gè)進(jìn)程提出資源請(qǐng)求時(shí)，假定分配給它，并檢查系統(tǒng)因此是否會(huì)不安全。如果安全，則滿足它的請(qǐng)求。否則，推遲它的請(qǐng)求。為了檢查狀態(tài)是否安全，銀行家要檢查他是否還有足夠資源滿足某一個(gè)顧客。如果能滿足，這個(gè)顧客很快將貸款歸還。如果所有貸款都能滿足，這個(gè)狀態(tài)

49、是安全的，實(shí)施實(shí)際的分配。安全性算法銀行家算法銀行家算法n這個(gè)算法利用了避免進(jìn)程進(jìn)入不安全狀態(tài)的原理。n要求進(jìn)程在執(zhí)行前，能提供所需資源的數(shù)量。n為實(shí)現(xiàn)銀行家算法，系統(tǒng)中必須設(shè)置若干數(shù)據(jù)結(jié)構(gòu)。銀行家算法的數(shù)據(jù)結(jié)構(gòu)銀行家算法的數(shù)據(jù)結(jié)構(gòu)lAvailable：可用資源向量。一個(gè)含有m個(gè)元素的數(shù)組，每個(gè)元素代表一類資源可用的數(shù)目。lMax：最大需求矩陣。nm矩陣，Max(i,j)=k表示進(jìn)程i 需要j類資源最大數(shù)目為k。lA l l o c a t i o n ： 分 配 矩 陣 。 n m 矩 陣 ，Allocation(i,j)=k表示進(jìn)程i當(dāng)前已分得j類資源數(shù)目為k。lNeed：需求矩陣。 nm

50、矩陣，Need(i,j)=k表示進(jìn)程i 還需要j類資源k個(gè)。銀行家算法的數(shù)據(jù)結(jié)構(gòu)銀行家算法的數(shù)據(jù)結(jié)構(gòu)l上述三個(gè)矩陣存在下述關(guān)系： Max(i,j) -Allocation(i,j)=Need(i,j)銀行家算法銀行家算法 設(shè) R e q u e s ti是 進(jìn) 程 Pi的 請(qǐng) 求 向 量 。 若Requestij=k，表示進(jìn)程Pi需要k個(gè)j類資源。當(dāng)Pi發(fā)出資源請(qǐng)求后，系統(tǒng)按下述步驟進(jìn)行檢查： 若RequestiNeedi ，則轉(zhuǎn)；否則，認(rèn)為出錯(cuò)。因?yàn)樗枰馁Y源數(shù)已超過它所宣布的最大它所需要的資源數(shù)已超過它所宣布的最大值值。 若RequestiAvailable，則轉(zhuǎn)；否則，表示系表示系統(tǒng)

51、中尚無足夠的資源統(tǒng)中尚無足夠的資源，Pi必須等待。 系統(tǒng)試探把要求的資源分配給進(jìn)程Pi，并修改下面數(shù)據(jù)結(jié)構(gòu)中的數(shù)值。 Available=Available Requesti Allocationi = Allocationi + Requesti Needi = Needi Requesti系統(tǒng)執(zhí)行安全性算法，檢測(cè)此次資源分配后，系統(tǒng)是否處于安全狀態(tài)。若安全，才正式將資源分給進(jìn)程Pi；否則，將試探分配作廢，恢復(fù)資源狀態(tài)，讓Pi等待。銀行家算法銀行家算法安全性算法安全性算法n安全性算法： 設(shè)置兩個(gè)向量work和finishp工作向量work，它表示系統(tǒng)可提供給進(jìn)程繼續(xù)運(yùn)行的各類資源數(shù)，含有m個(gè)

52、元素，其初始值為：workj=availablej。p完成向量finish，它表示系統(tǒng)是否有足夠資源使進(jìn)程推進(jìn)完成，開始執(zhí)行安全性算法時(shí)，F(xiàn)inishi=false;當(dāng)有足夠資源分配給進(jìn)程Pi，Pi推進(jìn)完成時(shí)，令Finishi=true。安全性算法安全性算法 從進(jìn)程集合中找到一個(gè)進(jìn)程，其滿足： Finishi=false Needi,j Workj 如找到則執(zhí)行步驟 ，找不到則執(zhí)行步驟。 當(dāng)進(jìn)程Pi獲得資源后，便可以向前推進(jìn)，直至完 成，并釋放出分配給它的全部資源，故應(yīng)執(zhí)行： Workj=Workj+Allocationi,j; Finishi=true; 執(zhí)行步驟。 若所有進(jìn)程的Finish

53、都為true，則系統(tǒng)為安全狀態(tài)；否則，系統(tǒng)為不安全狀態(tài)。銀行家算法示例銀行家算法示例 假定系統(tǒng)中有五個(gè)進(jìn)程P0， P1， P2， P3， P4和三類資源A，B，C，各類資源的數(shù)目分別是10、5、7。在T0時(shí)刻的資源分配圖如下表所示。銀行家算法示例銀行家算法示例MaxA B CAllocationA B CNeedA B CAvailableA B CP0 P1 P2 P3 P4 7 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 2l利用安全性算法，利用安全性算法，T0時(shí)刻存在一個(gè)安全序列

54、時(shí)刻存在一個(gè)安全序列P1， P3， P4， P2， P0，故系統(tǒng)是安全的。，故系統(tǒng)是安全的。lP1請(qǐng)求資源，請(qǐng)求向量為請(qǐng)求資源，請(qǐng)求向量為Request1，0，2，系統(tǒng)按銀，系統(tǒng)按銀行家算法進(jìn)行檢查，可以找到一個(gè)安全序列行家算法進(jìn)行檢查，可以找到一個(gè)安全序列P1， P3， P4， P2， P0，因此系統(tǒng)是安全的?？梢粤⒓磳ⅲ虼讼到y(tǒng)是安全的?？梢粤⒓磳1所申請(qǐng)的資所申請(qǐng)的資源分配給它。資源分配表如下表所示。源分配給它。資源分配表如下表所示。銀行家算法示例銀行家算法示例MaxA B CAllocationA B CNeedA B CAvailableA B CP0 P1 P2 P3 P47 5

55、 33 2 29 0 22 2 24 3 30 1 03 0 23 0 22 1 10 0 27 4 30 2 06 0 00 1 14 3 12 3 0lP4請(qǐng)求資源，請(qǐng)求向量為請(qǐng)求資源，請(qǐng)求向量為Request3，3，0，系統(tǒng)按，系統(tǒng)按銀行家算法進(jìn)行檢查，可用資源不能滿足請(qǐng)求資源，銀行家算法進(jìn)行檢查，可用資源不能滿足請(qǐng)求資源， P4等待。等待。lP0請(qǐng)求資源，請(qǐng)求向量為請(qǐng)求資源，請(qǐng)求向量為Request0，2，0，系統(tǒng)按，系統(tǒng)按銀行家算法進(jìn)行檢查，銀行家算法進(jìn)行檢查， P0分配資源后已不能滿足任何進(jìn)分配資源后已不能滿足任何進(jìn)程的需要，故系統(tǒng)進(jìn)入不安全狀態(tài)，此時(shí)系統(tǒng)不分配資程的需要，故系統(tǒng)進(jìn)入不安全狀態(tài)，此時(shí)系統(tǒng)不分配資源。如下圖。源。如下圖。銀行家算法示例銀行家算法示例MaxA B CAllocationA B CNee