第三章CPU調(diào)度與死鎖

1、第三章處理機(jī)調(diào)度與死鎖 31處理機(jī)調(diào)度的基本概念 分配處理機(jī)的任務(wù)是由處理機(jī)調(diào)度程序完成的。 由于處理機(jī)是最重要的計(jì)算機(jī)資源，提高處理機(jī)的利用率及改善系統(tǒng)性能（吞吐量、響應(yīng)時(shí)間），在很大程度上取決于處理機(jī)調(diào)度性能的好壞， 311高級(jí)、中級(jí)和低級(jí)調(diào)度 1高級(jí)調(diào)度高級(jí)調(diào)度 稱為作業(yè)調(diào)度用于決定把外存上處于后備隊(duì)列中的哪些作稱為作業(yè)調(diào)度用于決定把外存上處于后備隊(duì)列中的哪些作業(yè)調(diào)人內(nèi)存，并為它們創(chuàng)建進(jìn)程、分配必要的資源，然后，業(yè)調(diào)人內(nèi)存，并為它們創(chuàng)建進(jìn)程、分配必要的資源，然后，再將新創(chuàng)建的進(jìn)程排在就緒隊(duì)列上，準(zhǔn)備執(zhí)行再將新創(chuàng)建的進(jìn)程排在就緒隊(duì)列上，準(zhǔn)備執(zhí)行 。2低級(jí)調(diào)度低級(jí)調(diào)度 低級(jí)調(diào)度用來決定就緒隊(duì)

2、列中的哪個(gè)進(jìn)程應(yīng)獲得處理機(jī)，然低級(jí)調(diào)度用來決定就緒隊(duì)列中的哪個(gè)進(jìn)程應(yīng)獲得處理機(jī)，然后再由分派程序把處理機(jī)分配給該進(jìn)程的具體操作。后再由分派程序把處理機(jī)分配給該進(jìn)程的具體操作。3中級(jí)調(diào)度中級(jí)調(diào)度 引入中級(jí)調(diào)度的主要目的，是為了提高內(nèi)存利用率和系統(tǒng)引入中級(jí)調(diào)度的主要目的，是為了提高內(nèi)存利用率和系統(tǒng)吞吐量。吞吐量。進(jìn)程調(diào)度可采用下述兩種調(diào)度方式。1）非搶占方式 在采用這種調(diào)度方式時(shí)，一旦把處理機(jī)分配給某進(jìn)程后，便讓該進(jìn)程一直執(zhí)行，直至該進(jìn)程完成或發(fā)生某事件而被阻塞時(shí)，才再把處理機(jī)分配給其他進(jìn)程，決不允許某進(jìn)程搶占已經(jīng)分配出去的處理機(jī)。2）搶占方式（Preemptive Mode） 這種調(diào)度方式，允許

3、調(diào)度程序根據(jù)某種原則，去暫停某個(gè)正在執(zhí)行的進(jìn)程，將已分配給該進(jìn)程的處理機(jī)重新分配給另一進(jìn)程。 ：（1）優(yōu)先權(quán)原則。 （2）短作業(yè)（進(jìn)程）優(yōu)先原則。 （3）時(shí)間片原則。 ：正在執(zhí)行的進(jìn)程執(zhí)行完畢，或因發(fā)生某事件而不能再繼續(xù)執(zhí)行；執(zhí)行中的進(jìn)程因提出1O請(qǐng)求而暫停執(zhí)行；在進(jìn)程通信或同步過程中執(zhí)行了某種原語操作，如P操作（wait操作）、Block原語、 Wakeup原語等。 3.1.2 調(diào)度隊(duì)列模型 1僅有進(jìn)程調(diào)度的調(diào)度隊(duì)列模型 2具有高級(jí)和低級(jí)調(diào)度的調(diào)度隊(duì)列模型 3同時(shí)具有三級(jí)調(diào)度的調(diào)度隊(duì)列模型 313選擇調(diào)度方式和調(diào)度算法的若干準(zhǔn)則 1.面向用戶的準(zhǔn)則 :這是為了滿足用戶的需求所應(yīng)遵循的一些準(zhǔn)則

4、。其中，比較重要的有以下幾點(diǎn)。（1）周轉(zhuǎn)時(shí)間短）周轉(zhuǎn)時(shí)間短。，是指從作業(yè)被提交給系統(tǒng)開始，到作業(yè)完成為止的這段時(shí)間間隔（稱為作業(yè)周轉(zhuǎn)時(shí)間）。 作業(yè)在外存后備隊(duì)列上等待調(diào)度的時(shí)間進(jìn)程在就緒隊(duì)列上等待進(jìn)程調(diào)度的時(shí)間進(jìn)程在CPU上執(zhí)行的時(shí)間進(jìn)程等待IO操作完成的時(shí)間。 （2）響應(yīng)時(shí)間快。）響應(yīng)時(shí)間快。 所謂響應(yīng)時(shí)間，是從用戶通過鍵盤提交一個(gè)請(qǐng)求開始，直至系統(tǒng)首次產(chǎn)生響應(yīng)為止的時(shí)間。響應(yīng)時(shí)間包括三部分時(shí)間響應(yīng)時(shí)間包括三部分時(shí)間：從鍵盤輸入的請(qǐng)求信息傳送到處理機(jī)的時(shí)間處理機(jī)對(duì)請(qǐng)求信息進(jìn)行處理的時(shí)間將所形成的響應(yīng)信息回送到終端顯示器的時(shí)間。（3）截止時(shí)間的保證）截止時(shí)間的保證。 所謂截止時(shí)間，是指某任務(wù)必

5、須開始執(zhí)所謂截止時(shí)間，是指某任務(wù)必須開始執(zhí)行的最遲時(shí)間，或必須完成的最遲時(shí)間。行的最遲時(shí)間，或必須完成的最遲時(shí)間。（4）優(yōu)先權(quán)準(zhǔn)則）優(yōu)先權(quán)準(zhǔn)則。基于優(yōu)先權(quán)讓某些緊急的作業(yè)能得到及基于優(yōu)先權(quán)讓某些緊急的作業(yè)能得到及時(shí)處理。時(shí)處理。在要求較嚴(yán)格的場(chǎng)合，往往還須選擇搶在要求較嚴(yán)格的場(chǎng)合，往往還須選擇搶占式調(diào)度方式，才能保證緊急作業(yè)得到占式調(diào)度方式，才能保證緊急作業(yè)得到及時(shí)處理。及時(shí)處理。 2面向系統(tǒng)的準(zhǔn)則面向系統(tǒng)的準(zhǔn)則 （1）系統(tǒng)吞吐量高。吞吐量是指在單位時(shí)間內(nèi)，系統(tǒng)所完成的作業(yè)數(shù)。 （2）處理機(jī)利用率好。（3）各類資源的平衡利用。 32 調(diào)度算法調(diào)度算法 調(diào)度算法是指：根據(jù)系統(tǒng)的資源分配策略所規(guī)定

6、的資源分配算法。對(duì)于不同的系統(tǒng)和系統(tǒng)目標(biāo)，通常采用不同的調(diào)度算法。3.2.1 先來先服務(wù)和短作業(yè)優(yōu)先調(diào)度算法先來先服務(wù)和短作業(yè)優(yōu)先調(diào)度算法 FCFS算法比較有利于長作業(yè)（進(jìn)程），而不利于短作業(yè)（進(jìn)程）。 舉例：下表列出了A、B、C、D四個(gè)作業(yè)分別到達(dá)系統(tǒng)的時(shí)間、要求服務(wù)的時(shí)間、開始執(zhí)行的時(shí)間及各自的完成時(shí)間，并計(jì)算出各自的周轉(zhuǎn)時(shí)間和帶權(quán)周轉(zhuǎn)時(shí)間。FCFS算法 進(jìn)程名到達(dá)時(shí)間服務(wù)時(shí)間開始執(zhí)行時(shí)間完成時(shí)間周轉(zhuǎn)時(shí)間帶權(quán)周轉(zhuǎn)時(shí)間A010111B110011011001C21101102100100D31001022021991.992短作業(yè)優(yōu)先調(diào)度算法短作業(yè)優(yōu)先調(diào)度算法的缺點(diǎn)： (1)該算法對(duì)長作業(yè)不

7、利. (2)該算法完全未考慮作業(yè)的緊迫程度，因而不能保證緊迫性作業(yè)（進(jìn)程）會(huì)被及時(shí)處理。 (3)由于作業(yè)（進(jìn)程）的長短只是根據(jù)用戶所提供的估計(jì)執(zhí)行時(shí)間而定的，而用戶又可能會(huì)估計(jì)不準(zhǔn)運(yùn)行時(shí)間，致使該算法不一定能真正做到短作業(yè)優(yōu)先調(diào)度。 3.2.2 高優(yōu)先權(quán)優(yōu)先調(diào)度算法 該算法是把處理機(jī)分配給就緒隊(duì)列中優(yōu)先權(quán)最高的進(jìn)程。 該算法分兩種類型： （1）非搶占式優(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)程。（2）搶占式優(yōu)先權(quán)調(diào)度算法 在這種方式下，系統(tǒng)同樣

8、是把處理機(jī)分配給優(yōu)先權(quán)最高的進(jìn)程，使之執(zhí)行。但在其執(zhí)行期間，只要又出現(xiàn)了另一個(gè)其優(yōu)先權(quán)更高的進(jìn)程，進(jìn)程調(diào)度程序就立即停止當(dāng)前進(jìn)程的執(zhí)行，重新將處理機(jī)分配給新到的優(yōu)先權(quán)最高的進(jìn)程。 2優(yōu)先權(quán)的類型（1）靜態(tài)優(yōu)先權(quán) 靜態(tài)優(yōu)先權(quán)是在創(chuàng)建進(jìn)程時(shí)確定的，且在進(jìn)程的整個(gè)運(yùn)行期間保持不變。 確定進(jìn)程優(yōu)先權(quán)的依據(jù)有三個(gè)方面確定進(jìn)程優(yōu)先權(quán)的依據(jù)有三個(gè)方面： （1）進(jìn)程類型。系統(tǒng)進(jìn)程的優(yōu)先權(quán)高于一般用戶進(jìn)程的優(yōu)先權(quán)。 （2）進(jìn)程對(duì)資源的需求。對(duì)要求少的進(jìn)程應(yīng)賦予較高的優(yōu)先權(quán)。 （3）用戶要求。（2）動(dòng)態(tài)優(yōu)先權(quán)）動(dòng)態(tài)優(yōu)先權(quán) 動(dòng)態(tài)優(yōu)先權(quán)是指，在創(chuàng)建進(jìn)程時(shí)所賦予的優(yōu)先權(quán)，是可以隨進(jìn)程的推進(jìn)或隨其等待時(shí)間的增加而改變的，

9、以便獲得更好的調(diào)度性能。 3高響應(yīng)比優(yōu)先調(diào)度算法 該算法既照顧了短作業(yè)，又考慮了作業(yè)到達(dá)的先后次序，不會(huì)使長作業(yè)長期得不到服務(wù)。 利用該算法時(shí)，每次調(diào)度之前，都須先做響應(yīng)比的計(jì)算，會(huì)增加系統(tǒng)開銷。3.2.3 基于時(shí)間片的輪轉(zhuǎn)調(diào)度算法 在時(shí)間片輪轉(zhuǎn)法中，系統(tǒng)將所有的就緒進(jìn)程按先來先服務(wù)的原則，排成一個(gè)隊(duì)列，每次調(diào)度時(shí)，把CPU分配給隊(duì)首進(jìn)程。并令其執(zhí)行一個(gè)時(shí)間片。當(dāng)執(zhí)行的時(shí)間片用完時(shí)，由一個(gè)計(jì)時(shí)器發(fā)出時(shí)鐘中斷請(qǐng)求，調(diào)度程序便據(jù)此信號(hào)來停止該進(jìn)程的執(zhí)行，并將它送往就緒隊(duì)列的末尾；然后，再把處理機(jī)分配給就緒隊(duì)列中新的隊(duì)首進(jìn)程，同時(shí)也讓它執(zhí)行一個(gè)時(shí)間片。這樣就可以保證就緒隊(duì)列中的所有進(jìn)程，在一給定的時(shí)

10、間內(nèi)，均能獲得一時(shí)間片的處理機(jī)執(zhí)行時(shí)間，換言之，系統(tǒng)能在給定的時(shí)間內(nèi)，響應(yīng)所有用戶的請(qǐng)求。2.多級(jí)反饋隊(duì)列調(diào)度算法 多級(jí)反饋隊(duì)列調(diào)度算法實(shí)施過程如下：（1）應(yīng)設(shè)置多個(gè)就緒隊(duì)列，并為各個(gè)隊(duì)列賦予不同的優(yōu)先級(jí)。 （2）當(dāng)一個(gè)新進(jìn)程進(jìn)入內(nèi)存后，首先將它放入第一隊(duì)列的末尾，按FCFS原則排隊(duì)等待調(diào)度。當(dāng)輪到該進(jìn)程執(zhí)行時(shí)，如它能在該時(shí)間片內(nèi)完成，便可準(zhǔn)備撤離系統(tǒng)；如果它在一個(gè)時(shí)間片結(jié)束時(shí)尚未完成，調(diào)度程序便將該進(jìn)程轉(zhuǎn)入第二隊(duì)列的末尾，再同樣地按FCFS原則等待調(diào)度執(zhí)行；如果它在第二隊(duì)列中運(yùn)行一個(gè)時(shí)間片后仍未完成，再依次將它放入第三隊(duì)列，。（3）僅當(dāng)?shù)谝魂?duì)列空閑時(shí)，調(diào)度程序才調(diào)度第二隊(duì)列中的進(jìn)程運(yùn)行；圖3

11、-5 多級(jí)反饋隊(duì)列調(diào)度算法 3多級(jí)反饋隊(duì)列調(diào)度算法的性能 多級(jí)反饋隊(duì)列調(diào)度算法具有較好的性能，能較好地滿足各種類型用戶的需要。（1）終端型作業(yè)用戶。 能在第一隊(duì)列所規(guī)定的時(shí)間片內(nèi)完成，可使終端型作業(yè)用戶都感到滿意。 （2）對(duì)短作業(yè)用戶有利。 （3）長批處理作業(yè)用戶。對(duì)于長作業(yè)，它將依次在第1，2,，n個(gè)隊(duì)列中運(yùn)行，然后再按輪轉(zhuǎn)方式運(yùn)行，用戶不必?fù)?dān)心其作業(yè)長期得不到處理。3.3 實(shí)時(shí)調(diào)度 由于在實(shí)時(shí)系統(tǒng)中都存在著若干個(gè)實(shí)時(shí)進(jìn)程或任務(wù)，它們用來反應(yīng)或控制某個(gè)外部事件，往往帶有某種程度的緊迫性，因而對(duì)實(shí)時(shí)系統(tǒng)中的調(diào)度提出了某些特殊要求，前面所介紹的多種調(diào)度算法，并不能很好地滿足實(shí)時(shí)系統(tǒng)對(duì)調(diào)度的要求，

12、為此，需要引入一種新的調(diào)度，即實(shí)時(shí)調(diào)度。 3.3.1實(shí)現(xiàn)實(shí)時(shí)調(diào)度的基本條件1提供必要的信息 （1）就緒時(shí)間。這是該任務(wù)成為就緒狀態(tài)的起始時(shí)間。（2）開始截止時(shí)間和完成截止時(shí)間。（3）處理時(shí)間。這是指一個(gè)任務(wù)從開始執(zhí)行直至完成所需的時(shí)間。 （4）資源要求。（5）優(yōu)先級(jí)。 2系統(tǒng)處理能力強(qiáng) 在實(shí)時(shí)系統(tǒng)中，通常都有著多個(gè)實(shí)時(shí)任務(wù)。若處理機(jī)的處理能力不夠強(qiáng)，則有可能因處理機(jī)忙不過來而使某些實(shí)時(shí)任務(wù)不能得到及時(shí)處理。 解決的方法是提高系統(tǒng)的處理能力，其途徑有二：其一仍是采用單處理機(jī)系統(tǒng)，但須增強(qiáng)其處理能力，以顯著地減少對(duì)每一個(gè)任務(wù)的處理時(shí)間；其二是采用多處理機(jī)系統(tǒng)。 3采用搶占式調(diào)度機(jī)制 在含有硬實(shí)時(shí)任

13、務(wù)的實(shí)時(shí)系統(tǒng)中，廣泛采用搶占機(jī)制。當(dāng)一個(gè)優(yōu)先權(quán)更高的任務(wù)到達(dá)時(shí)，允許將當(dāng)前任務(wù)暫時(shí)掛起，而令高優(yōu)先權(quán)任務(wù)立即投入運(yùn)行，這樣便可滿足該硬實(shí)時(shí)任務(wù)對(duì)截止時(shí)間的要求。 4具有快速切換機(jī)制 （1）對(duì)外部中斷的快速響應(yīng)能力。 （2）快速的任務(wù)分派能力。 3.3.2 實(shí)時(shí)調(diào)度算法的分類 調(diào)度程序每次選擇隊(duì)列中的第一個(gè)任務(wù)投入運(yùn)行。當(dāng)該任務(wù)完成后，便把它掛在輪轉(zhuǎn)隊(duì)列的末尾，等待下次調(diào)度運(yùn)行。 : 如果在系統(tǒng)中存在著實(shí)時(shí)要求較為嚴(yán)格的任務(wù)，則可采用非搶占式優(yōu)先調(diào)度算法，為這些任務(wù)賦予較高的優(yōu)先級(jí)。當(dāng)這些實(shí)時(shí)任務(wù)到達(dá)時(shí)，把它們安排在就緒隊(duì)列的隊(duì)首，等待當(dāng)前任務(wù)自我終止或運(yùn)行完成后，才能被調(diào)度執(zhí)行。 : 某實(shí)時(shí)任

14、務(wù)到達(dá)后，如果該任務(wù)的優(yōu)先級(jí)高于當(dāng)前任務(wù)的優(yōu)先級(jí)，這時(shí)并不立即搶占當(dāng)前任務(wù)的處理機(jī)，而是等到時(shí)鐘中斷到來時(shí)，調(diào)度程序才剝奪當(dāng)前任務(wù)的執(zhí)行，將處理機(jī)分配給新到的高優(yōu)先權(quán)任務(wù)。 （: 一旦出現(xiàn)外部中斷，只要當(dāng)前任務(wù)未處于臨界區(qū)，便能立即剝奪當(dāng)前任務(wù)的執(zhí)行，把處理機(jī)分配給請(qǐng)求中斷的緊迫任務(wù)。 實(shí)時(shí)進(jìn)程調(diào)度 3.3.3 常用的幾種實(shí)時(shí)調(diào)度算法 該算法要求在系統(tǒng)中保持一個(gè)實(shí)時(shí)任務(wù)就緒隊(duì)列，該隊(duì)列按各任務(wù)截止時(shí)間的早晚排序；具有最早截止時(shí)間的任務(wù)排在隊(duì)列的最前面。調(diào)度程序總是選擇就緒隊(duì)列中的第一個(gè)任務(wù)，為之分配處理機(jī)，使之投入運(yùn)行。 松弛度松弛度=必須完成時(shí)間一本身的運(yùn)行時(shí)間一當(dāng)前時(shí)間必須完成時(shí)間一本身的

15、運(yùn)行時(shí)間一當(dāng)前時(shí)間 該算法按松弛度排序?qū)崟r(shí)任務(wù)的就緒隊(duì)列，松弛度值最小的任務(wù)排在隊(duì)列最前面，調(diào)度程序總是選擇就緒隊(duì)列中的隊(duì)首任務(wù)執(zhí)行。 假如在一個(gè)實(shí)時(shí)系統(tǒng)中，有兩個(gè)周期性實(shí)時(shí)任務(wù)A和B任務(wù)，A要求每20ms執(zhí)行一次，執(zhí)行時(shí)間為10ms；任務(wù)B只要求每50ms執(zhí)行一次，執(zhí)行時(shí)間為25ms。見圖3一8。 A和和B任務(wù)每次必須完成的時(shí)間任務(wù)每次必須完成的時(shí)間 利用利用LLF算法進(jìn)行調(diào)度的情況算法進(jìn)行調(diào)度的情況3.5產(chǎn)生死鎖的原因和必要條件 所謂死鎖（Deadlock），是指多個(gè)進(jìn)程在運(yùn)行過程中因爭(zhēng)奪資源而造成的一種僵局（Deadly- Embrace），當(dāng)進(jìn)程處于這種僵持狀態(tài)時(shí)，若無外力作用，它們都

16、將無法再向前推進(jìn)。 351產(chǎn)生死鎖的原因 產(chǎn)生死鎖的原因可歸結(jié)為如下兩點(diǎn)。 （1）競(jìng)爭(zhēng)資源。 （2）進(jìn)程間推進(jìn)順序非法。 1競(jìng)爭(zhēng)資源引起進(jìn)程死鎖1）可剝奪和非剝奪性資源 可剝奪性資源: 是指某進(jìn)程在獲得這類資源后，該資源可以再被其他進(jìn)程或系統(tǒng)剝奪。 不可剝奪性資源: 當(dāng)系統(tǒng)把這類資源分配給某進(jìn)程后，再不能強(qiáng)行收回，只能在進(jìn)程用完后自行釋放。 2）競(jìng)爭(zhēng)非剝奪性資源 在系統(tǒng)中所配置的非剝奪性資源，由于它們的數(shù)量不能滿足諸進(jìn)程運(yùn)行的需要，會(huì)使進(jìn)程在運(yùn)行過程中，因爭(zhēng)奪這些資源而陷入僵局。 例如，系統(tǒng)中只有一臺(tái)打印機(jī)R1和一臺(tái)磁帶機(jī)R2，可供進(jìn)程P1和P2共享。處理不好，在P1與P2之間會(huì)形成僵局，引起

17、死鎖。 3）競(jìng)爭(zhēng)臨時(shí)性資源 永久性資源：可順序重復(fù)使用型資源稱為永久性資源。 臨時(shí)性資源，是指由一個(gè)進(jìn)程產(chǎn)生，被另一進(jìn)程使用一暫短時(shí)間后便無用的資源，故也稱之為消耗性資源，它也可能引起死鎖。 例如：S1、S2和S3是臨時(shí)性資源，由進(jìn)程P1、P2和P3產(chǎn)生的消息。如果消息通信處理順序不當(dāng)也會(huì)發(fā)生死鎖。2.進(jìn)程推進(jìn)順序不當(dāng)引起死鎖1）進(jìn)程推進(jìn)順序合法進(jìn)程推進(jìn)順序是合法不會(huì)引起進(jìn)程死鎖的。 2）進(jìn)程推進(jìn)順序非法 若并發(fā)進(jìn)程P1和P2推進(jìn)順序不合法，進(jìn)入不安全狀態(tài)，于是發(fā)生了進(jìn)程死鎖 352產(chǎn)生死鎖的必要條件（1）互斥條件：指進(jìn)程對(duì)所分配到的資源進(jìn)行排它性使用 。（2）請(qǐng)求和保持條件：指進(jìn)程已經(jīng)保持了

18、至少一個(gè)資源，但又提出了新的資源請(qǐng)求 （3）不剝奪條件：指進(jìn)程已獲得的資源，在未使用完之前，不能被剝奪，只能在使用完時(shí)由自己釋放。 （4）環(huán)路等待條件：指在發(fā)生死鎖時(shí)，必然存在一個(gè)進(jìn)程資源的環(huán)形鏈 353處理死鎖的基本方法（1）預(yù)防死鎖：是通過設(shè)置某些限 制條件，去破壞產(chǎn)生死鎖的四個(gè)必要條件中的一個(gè)或幾個(gè)條件，來預(yù)防發(fā)生死鎖。（2）避免死鎖：是在資源的動(dòng)態(tài)分配過程中，用某種方法去防止系統(tǒng)進(jìn)入不安全狀態(tài)，從而避免發(fā)生死鎖。 （3）檢測(cè)死鎖：通過系統(tǒng)所設(shè)置的檢測(cè)機(jī)構(gòu)，及時(shí)地檢測(cè)出死鎖的發(fā)生，并精確地確定與死鎖有關(guān)的進(jìn)程和資源；（4）解除死鎖：當(dāng)檢測(cè)到系統(tǒng)中已發(fā)生死鎖時(shí)，須將進(jìn)程從死鎖狀態(tài)中解脫出來

19、。常用的實(shí)施方法是撤消或掛起一些進(jìn)程。 36預(yù)防死鎖的方法 3.6.1預(yù)防死鎖 預(yù)防死鎖的方法是使四個(gè)必要條件中的第2、3、4條件之一不能成立，來避免發(fā)生死鎖。至于必要條件1，因?yàn)樗怯稍O(shè)備的固有屬性所決定的，不僅不能改變，還應(yīng)加以保證。1摒棄“請(qǐng)求和保持”條件 系統(tǒng)規(guī)定所有進(jìn)程在開始運(yùn)行之前，都必須一次性地申請(qǐng)其在整個(gè)運(yùn)行過程所需的全部資源。這樣，該進(jìn)程在整個(gè)運(yùn)行期間：便不會(huì)再提出資源要求，從而摒棄了請(qǐng)求和保持條件，從而可以避免發(fā)生死鎖。 這種預(yù)防死鎖的方法的優(yōu)點(diǎn)：簡(jiǎn)單、易于實(shí)現(xiàn)且很安全。其缺點(diǎn)：資源被嚴(yán)重浪費(fèi)，使進(jìn)程延遲運(yùn)行。 2摒棄“不剝奪”條件 進(jìn)程是逐個(gè)地提出對(duì)資源的要求的。當(dāng)一個(gè)已

20、經(jīng)保持了某些資源的進(jìn)程，再提出新的資源請(qǐng)求而不能立即得到滿足時(shí)，必須釋放它已經(jīng)保持了的所有資源。待以后需要時(shí)再重新申請(qǐng)。從而摒棄了“不剝奪”條件。 這種預(yù)防死鎖的方法，實(shí)現(xiàn)起來比較復(fù)雜且要付出很大代價(jià)。因?yàn)橐粋€(gè)資源在使用一段時(shí)間后，它的被迫釋放可能會(huì)造成前段工作的失效。還會(huì)使進(jìn)程前后兩次運(yùn)行的信息不連續(xù) 3摒棄“環(huán)路等待”條件 這種方法中規(guī)定，系統(tǒng)將所有資源按類型進(jìn)行線性排隊(duì)，并賦予不同的序號(hào)。 所有進(jìn)程對(duì)資源的請(qǐng)求必須嚴(yán)格按照資源序號(hào)遞增的次序提出，這樣，在所形成的資源分配圖中，不可能再出現(xiàn)環(huán)路，因而摒棄了“環(huán)路等待”條件。 存在的問題：首先是為系統(tǒng)中各類資源所分配（確定）的序號(hào)，必須相對(duì)穩(wěn)

21、定，這就限制了新類型設(shè)備的增加； 作業(yè)（進(jìn)程）使用各類資源的順序，與系統(tǒng)規(guī)定的順序不同，造成對(duì)資源的浪費(fèi) 。 限制用戶簡(jiǎn)單、自主地編程 362系統(tǒng)安全狀態(tài)1安全狀態(tài) 所謂安全狀態(tài)，是指系統(tǒng)能按某種進(jìn)程順序（P1，P2，Pn），來為每個(gè)進(jìn)程Pi分配其所需資源，直至滿足每個(gè)進(jìn)程對(duì)資源的最大需求，使每個(gè)進(jìn)程都可順利地完成，稱系統(tǒng)處于安全狀態(tài)，稱P1，P2，Pn序列為安全序列 。否則，如果系統(tǒng)無法找到這樣一個(gè)安全序列，則稱系統(tǒng)處于不安全狀態(tài)。 2安全狀態(tài)之例 假定系統(tǒng)中有三個(gè)進(jìn)程P1、P2和P3，共有12臺(tái)磁帶機(jī)。進(jìn)程P1總共要求10臺(tái)磁帶機(jī)，P2和P3分別要求4臺(tái)和9臺(tái)。假設(shè)在T0 時(shí)刻進(jìn)程P1、P

22、2和P3已分別獲得5臺(tái)、2臺(tái)和2臺(tái)磁帶機(jī)，尚有3臺(tái)空閑未分配，在T0時(shí)刻系統(tǒng)是否安全？3由安全狀態(tài)向不安全狀態(tài)的轉(zhuǎn)換 363利用銀行家算法避免死鎖 1. 銀行象算法中的數(shù)據(jù)結(jié)構(gòu) （1）可利用資源向量Available：這是一個(gè)含有m個(gè)元素的數(shù)組，其中的每一個(gè)元素代表一類可利用的資源數(shù)目。其數(shù)值隨該類資源的分配和回收而動(dòng)態(tài)地改變。（2）最大需求矩陣Max。這是一個(gè)nXm的矩陣，它定義了系統(tǒng)中n個(gè)進(jìn)程中的每一個(gè)進(jìn)程對(duì)m類資源的最大需求。如果Maxi,j=K，則表示進(jìn)程i需要Rj類資源的最大數(shù)目為K。 （3）分配矩陣Allocation。這是一個(gè)nm的矩陣，它定義了系統(tǒng)中每一類資源當(dāng)前已分配給每一進(jìn)

23、程的資源數(shù)。如果Allocationi,j=K，則表示進(jìn)程i當(dāng)前已分得Rj類資源的數(shù)目為K。（4）需求矩陣Need。這也是一個(gè)nm的矩陣，用以表示每一個(gè)進(jìn)程尚需的各類資源數(shù)。如果Needi,j=K，則表示進(jìn)程Pi還需要Rj類資源K個(gè)，方能完成其任務(wù)。 Needi,jMaxi,j一Allocationi,j2銀行家算法 設(shè)Requesti，是進(jìn)程Pi的請(qǐng)求向量，當(dāng)Pi發(fā)出資源請(qǐng)求后，系統(tǒng)按下述步驟進(jìn)行檢查： （1）如果RequestijNeedi,j,便轉(zhuǎn)向步驟2；否則認(rèn)為出錯(cuò)，因?yàn)樗枰馁Y源數(shù)已超過它所宣布的最大值。 （2）如果RequestijAvailablej，便轉(zhuǎn)向步驟（3）；否則

24、，表示尚無足夠資源，Pi須等待。（3）系統(tǒng)試探著把資源分配給進(jìn)程Pi，并修改下面數(shù)據(jù)結(jié)構(gòu)中的數(shù)值： Availablej：Availablej一一Requestij； Allocationi,j：Allocationi,jRequestij; Needi,j: =Needi,j一一Requestij；（4）系統(tǒng)執(zhí)行安全性算法，檢查此次資源分配后，系統(tǒng)是否處于安全狀態(tài)。若安全，才正式將資源分配給進(jìn)程Pi，以完成本次分配；否則，將本次的試探分配作廢，恢復(fù)原來的資源分配狀態(tài)，讓進(jìn)程Pi等待。 開始RequestijNeedi,j,出錯(cuò)NRequestijAvailablejPi進(jìn)程等待Availab

25、lej：Availablej一一Requestij；Allocationi,j：Allocationi,jRequestij; Needi,j: =Needi,j一一Requestij；系統(tǒng)安全性檢查N安全不分配資源分配資源NY 3安全性算法： :它表示系統(tǒng)可提供給進(jìn)程繼續(xù)運(yùn)行所需的各類資源數(shù)目，Work：Available 開始時(shí)先做Finishi:=false；當(dāng)有足夠資源分配給進(jìn)程時(shí)，再令Finishi:=true。 Finishi=false； Needi,jwork； 若找到，執(zhí)行步驟（3),否則，執(zhí)行步驟（4）。 Work：= Work+Allocationi,j； Finishi

26、 ：=true; go to step 2； Work:=AvailableFinishI:=false從進(jìn)程集合中找能滿足下述條件的進(jìn)程： Finishi=false, Needi,jwork；Workj:= Work+Allocationi,j; Finishi ：=true;所有進(jìn)程都滿足:Finishitrue系統(tǒng)不安全系統(tǒng)安全安全檢查開始安全檢查結(jié)束NyNY 4銀行家算法之例假定系統(tǒng)中有五個(gè)進(jìn)程P0，P1，P2，P3，P4 和三類資源A ，B,C,各種資源的數(shù)量分別為10、5、7，在T0 時(shí)刻的資源分配情況資源情況進(jìn)程MaxAllocationNeedAvailableA B CA

27、B CA B CA B CP07 5 30 1 07 4 33 3 2P13 2 22 0 01 2 2P29 0 23 0 2600 P32 2 22 1 1 0 1 1 P44 3 30 0 24 3 1 （1）T0時(shí)刻的安全性利用安全性算法對(duì)T0時(shí)刻的資源分配情況進(jìn)行分析 資源情況進(jìn)程WorkA B CNeedA B CAllocationA B CWork+AllocationA B CFinishP13 3 21 2 22 0 05 3 2 TRUEP35 3 20 1 12 1 17 4 3 TRUEP47 4 34 3 10 0 27 4 5TRUEP27 4 56 0 03 0

28、 210 4 7TRUEP010 4 77 4 30 1 010 5 7TRUE（2）P1請(qǐng)求資源：P1發(fā)出請(qǐng)求向量Request1(1,0,2),系統(tǒng)按銀行家算法進(jìn)行檢查Request1（1，0，2）Need1（1，2，2）Request1（1，0，2）Available1（3,3,2)系統(tǒng)先假定可為P1分配資源，并修改Available，Allocation1和Need1向量，由此形成的資源變化情況如下圖所示。再利用安全性算法檢查此時(shí)系統(tǒng)是否安全。如圖3一17所示。資源情況進(jìn)程MaxAllocationNeedAvailableA B CA B CA B CA B CP07 5 30 1

29、07 4 32 3 0P13 2 23 0 20 2 0P29 0 23 0 21 2 2 P32 2 22 1 1 0 1 1 P44 3 30 0 24 3 1 圖3一17 P1 申請(qǐng)資源時(shí)的安全性檢查 資源情況進(jìn)程WorkA B CNeedA B CAllocationA B CWork+AllocationA B CFinishP12 3 00 2 03 0 25 3 2 TRUEP35 3 20 1 12 1 17 4 3 TRUEP47 4 34 3 10 0 27 4 5TRUEP07 4 57 4 30 1 07 5 5TRUEP210 5 56 0 03 0 210 5 7T

30、RUE（3）P4請(qǐng)求資源：P4發(fā)出請(qǐng)求向量Request4（3,3,0），系統(tǒng)按銀行家算法進(jìn)行檢查： Request4（3，3，0）Need4（4，3，1）； Request4(3，3， 0) Available（2，3，0），讓P4等待。(4)P0請(qǐng)求資源：P0發(fā)出請(qǐng)求向量Requst0(0,2,0），系統(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ù)，如圖3一18所示。 進(jìn)行安全性檢查：可用資源Available（2，1，0）已不能滿足任何進(jìn)程的需要，故系統(tǒng)進(jìn)入不安全狀態(tài)，此時(shí)系統(tǒng)不分配資源。 資源情況進(jìn)程AllocationNeedAvailableA B