計算機操作系統(tǒng)第三版第3章

第三章處理機調(diào)度與死鎖3.1處理機調(diào)度的層次3.2調(diào)度隊列模型和調(diào)度準(zhǔn)則3.3調(diào)度算法3.4實時調(diào)度

3.5產(chǎn)生死鎖的原因和必要條件3.6預(yù)防死鎖的方法3.7死鎖的檢測與解除

3.1處理機調(diào)度的層次3.1.1高級、中級和低級調(diào)度1.高級調(diào)度(HighScheduling)在每次執(zhí)行作業(yè)調(diào)度時，都須做出以下兩個決定。

1)接納多少個作業(yè)

2)接納哪些作業(yè)2.低級調(diào)度(LowLevelScheduling)1)非搶占方式(Non-preemptiveMode)

在采用非搶占調(diào)度方式時，可能引起進(jìn)程調(diào)度的因素可歸結(jié)為這樣幾個：①正在執(zhí)行的進(jìn)程執(zhí)行完畢，或因發(fā)生某事件而不能再繼續(xù)執(zhí)行；②執(zhí)行中的進(jìn)程因提出I/O請求而暫停執(zhí)行；③在進(jìn)程通信或同步過程中執(zhí)行了某種原語操作，如P操作(wait操作)、Block原語、Wakeup原語等。這種調(diào)度方式的優(yōu)點是實現(xiàn)簡單、系統(tǒng)開銷小，適用于大多數(shù)的批處理系統(tǒng)環(huán)境。但它難以滿足緊急任務(wù)的要求——立即執(zhí)行，因而可能造成難以預(yù)料的后果。顯然，在要求比較嚴(yán)格的實時系統(tǒng)中，不宜采用這種調(diào)度方式。2)搶占方式(PreemptiveMode)搶占的原則有：優(yōu)先權(quán)原則。(2)短作業(yè)(進(jìn)程)優(yōu)先原則。(3)時間片原則。3.中級調(diào)度(Intermediate-LevelScheduling)中級調(diào)度又稱中程調(diào)度(Medium-TermScheduling)。引入中級調(diào)度的主要目的，是為了提高內(nèi)存利用率和系統(tǒng)吞吐量。為此，應(yīng)使那些暫時不能運行的進(jìn)程不再占用寶貴的內(nèi)存資源，而將它們調(diào)至外存上去等待，把此時的進(jìn)程狀態(tài)稱為就緒駐外存狀態(tài)或掛起狀態(tài)。當(dāng)這些進(jìn)程重又具備運行條件、且內(nèi)存又稍有空閑時，由中級調(diào)度來決定把外存上的哪些又具備運行條件的就緒進(jìn)程，重新調(diào)入內(nèi)存，并修改其狀態(tài)為就緒狀態(tài)，掛在就緒隊列上等待進(jìn)程調(diào)度。3.2調(diào)度隊列模型和調(diào)度準(zhǔn)則3.2.1調(diào)度隊列模型1.僅有進(jìn)程調(diào)度的調(diào)度隊列模型圖3-1僅具有進(jìn)程調(diào)度的調(diào)度隊列模型2.具有高級和低級調(diào)度的調(diào)度隊列模型圖3-2具有高、低兩級調(diào)度的調(diào)度隊列模型就緒隊列的形式。

(2)設(shè)置多個阻塞隊列。圖3-2示出了具有高、低兩級調(diào)度的調(diào)度隊列模型。該模型與上一模型的主要區(qū)別在于如下兩個方面。3同時具有三級調(diào)度的調(diào)度隊列模型圖3-3具有三級調(diào)度時的調(diào)度隊列模型3.2.2選擇調(diào)度方式和調(diào)度算法的若干準(zhǔn)則1.面向用戶的準(zhǔn)則(1)周轉(zhuǎn)時間短。

可把平均周轉(zhuǎn)時間描述為：作業(yè)的周轉(zhuǎn)時間T與系統(tǒng)為它提供服務(wù)的時間TS之比，即W=T/TS，稱為帶權(quán)周轉(zhuǎn)時間，而平均帶權(quán)周轉(zhuǎn)時間則可表示為:(2)響應(yīng)時間快。(3)截止時間的保證。(4)優(yōu)先權(quán)準(zhǔn)則。2.面向系統(tǒng)的準(zhǔn)則系統(tǒng)吞吐量高。(2)處理機利用率好。(3)各類資源的平衡利用。3.3調(diào)度算法3.3.1先來先服務(wù)和短作業(yè)(進(jìn)程)優(yōu)先調(diào)度算法1.先來先服務(wù)調(diào)度算法圖3-4FCFS和SJF調(diào)度算法的性能2.短作業(yè)(進(jìn)程)優(yōu)先調(diào)度算法短作業(yè)(進(jìn)程)優(yōu)先調(diào)度算法SJ(P)F，是指對短作業(yè)或短進(jìn)程優(yōu)先調(diào)度的算法。它們可以分別用于作業(yè)調(diào)度和進(jìn)程調(diào)度。短作業(yè)優(yōu)先(SJF)的調(diào)度算法，是從后備隊列中選擇一個或若干個估計運行時間最短的作業(yè)，將它們調(diào)入內(nèi)存運行。而短進(jìn)程優(yōu)先(SPF)調(diào)度算法，則是從就緒隊列中選出一估計運行時間最短的進(jìn)程，將處理機分配給它，使它立即執(zhí)行并一直執(zhí)行到完成，或發(fā)生某事件而被阻塞放棄處理機時，再重新調(diào)度。

SJ(P)F調(diào)度算法也存在不容忽視的缺點：(1)該算法對長作業(yè)不利，如作業(yè)C的周轉(zhuǎn)時間由10增至16，其帶權(quán)周轉(zhuǎn)時間由2增至3.1。更嚴(yán)重的是，如果有一長作業(yè)(進(jìn)程)進(jìn)入系統(tǒng)的后備隊列(就緒隊列)，由于調(diào)度程序總是優(yōu)先調(diào)度那些(即使是后進(jìn)來的)短作業(yè)(進(jìn)程)，將導(dǎo)致長作業(yè)(進(jìn)程)長期不被調(diào)度。(2)該算法完全未考慮作業(yè)的緊迫程度，因而不能保證緊迫性作業(yè)(進(jìn)程)會被及時處理。(3)由于作業(yè)(進(jìn)程)的長短只是根據(jù)用戶所提供的估計執(zhí)行時間而定的，而用戶又可能會有意或無意地縮短其作業(yè)的估計運行時間，致使該算法不一定能真正做到短作業(yè)優(yōu)先調(diào)度。3.3.2高優(yōu)先權(quán)優(yōu)先調(diào)度算法1.優(yōu)先權(quán)調(diào)度算法的類型非搶占式優(yōu)先權(quán)算法在這種方式下，系統(tǒng)一旦把處理機分配給就緒隊列中優(yōu)先權(quán)最高的進(jìn)程后，該進(jìn)程便一直執(zhí)行下去，直至完成；或因發(fā)生某事件使該進(jìn)程放棄處理機時，系統(tǒng)方可再將處理機重新分配給另一優(yōu)先權(quán)最高的進(jìn)程。這種調(diào)度算法主要用于批處理系統(tǒng)中；也可用于某些對實時性要求不嚴(yán)的實時系統(tǒng)中。2)搶占式優(yōu)先權(quán)調(diào)度算法在這種方式下，系統(tǒng)同樣是把處理機分配給優(yōu)先權(quán)最高的進(jìn)程，使之執(zhí)行。但在其執(zhí)行期間，只要又出現(xiàn)了另一個其優(yōu)先權(quán)更高的進(jìn)程，進(jìn)程調(diào)度程序就立即停止當(dāng)前進(jìn)程(原優(yōu)先權(quán)最高的進(jìn)程)的執(zhí)行，重新將處理機分配給新到的優(yōu)先權(quán)最高的進(jìn)程。因此，在采用這種調(diào)度算法時，是每當(dāng)系統(tǒng)中出現(xiàn)一個新的就緒進(jìn)程i時，就將其優(yōu)先權(quán)Pi與正在執(zhí)行的進(jìn)程j的優(yōu)先權(quán)Pj進(jìn)行比較。如果Pi≤Pj，原進(jìn)程Pj便繼續(xù)執(zhí)行；但如果是Pi＞Pj,則立即停止Pj的執(zhí)行，做進(jìn)程切換，使i進(jìn)程投入執(zhí)行。顯然，這種搶占式的優(yōu)先權(quán)調(diào)度算法，能更好地滿足緊迫作業(yè)的要求，故而常用于要求比較嚴(yán)格的實時系統(tǒng)中，以及對性能要求較高的批處理和分時系統(tǒng)中。2.優(yōu)先權(quán)的類型1)靜態(tài)優(yōu)先權(quán)靜態(tài)優(yōu)先權(quán)是在創(chuàng)建進(jìn)程時確定的，且在進(jìn)程的整個運行期間保持不變。一般地，優(yōu)先權(quán)是利用某一范圍內(nèi)的一個整數(shù)來表示的，例如，0~7或0~255中的某一整數(shù)，又把該整數(shù)稱為優(yōu)先數(shù)。只是具體用法各異：有的系統(tǒng)用“0”表示最高優(yōu)先權(quán)，當(dāng)數(shù)值愈大時，其優(yōu)先權(quán)愈低；而有的系統(tǒng)恰恰相反。確定進(jìn)程優(yōu)先權(quán)的依據(jù)有如下三個方面：進(jìn)程類型。(2)進(jìn)程對資源的需求。(3)用戶要求。2)動態(tài)優(yōu)先權(quán)動態(tài)優(yōu)先權(quán)是指，在創(chuàng)建進(jìn)程時所賦予的優(yōu)先權(quán)，是可以隨進(jìn)程的推進(jìn)或隨其等待時間的增加而改變的，以便獲得更好的調(diào)度性能。例如，我們可以規(guī)定，在就緒隊列中的進(jìn)程，隨其等待時間的增長，其優(yōu)先權(quán)以速率a提高。若所有的進(jìn)程都具有相同的優(yōu)先權(quán)初值，則顯然是最先進(jìn)入就緒隊列的進(jìn)程，將因其動態(tài)優(yōu)先權(quán)變得最高而優(yōu)先獲得處理機，此即FCFS算法。若所有的就緒進(jìn)程具有各不相同的優(yōu)先權(quán)初值，那么，對于優(yōu)先權(quán)初值低的進(jìn)程，在等待了足夠的時間后，其優(yōu)先權(quán)便可能升為最高，從而可以獲得處理機。當(dāng)采用搶占式優(yōu)先權(quán)調(diào)度算法時，如果再規(guī)定當(dāng)前進(jìn)程的優(yōu)先權(quán)以速率b下降，則可防止一個長作業(yè)長期地壟斷處理機。3.高響應(yīng)比優(yōu)先調(diào)度算法優(yōu)先權(quán)的變化規(guī)律可描述為：由于等待時間與服務(wù)時間之和，就是系統(tǒng)對該作業(yè)的響應(yīng)時間，故該優(yōu)先權(quán)又相當(dāng)于響應(yīng)比RP。據(jù)此，又可表示為：(1)如果作業(yè)的等待時間相同，則要求服務(wù)的時間愈短，其優(yōu)先權(quán)愈高，因而該算法有利于短作業(yè)。(2)當(dāng)要求服務(wù)的時間相同時，作業(yè)的優(yōu)先權(quán)決定于其等待時間，等待時間愈長，其優(yōu)先權(quán)愈高，因而它實現(xiàn)的是先來先服務(wù)。(3)對于長作業(yè)，作業(yè)的優(yōu)先級可以隨等待時間的增加而提高，當(dāng)其等待時間足夠長時，其優(yōu)先級便可升到很高，從而也可獲得處理機。3.3.3基于時間片的輪轉(zhuǎn)調(diào)度算法

1.時間片輪轉(zhuǎn)法在早期的時間片輪轉(zhuǎn)法中，系統(tǒng)將所有的就緒進(jìn)程按先來先服務(wù)的原則，排成一個隊列，每次調(diào)度時，把CPU分配給隊首進(jìn)程，并令其執(zhí)行一個時間片。時間片的大小從幾ms到幾百ms。當(dāng)執(zhí)行的時間片用完時，由一個計時器發(fā)出時鐘中斷請求，調(diào)度程序便據(jù)此信號來停止該進(jìn)程的執(zhí)行，并將它送往就緒隊列的末尾；然后，再把處理機分配給就緒隊列中新的隊首進(jìn)程，同時也讓它執(zhí)行一個時間片。這樣就可以保證就緒隊列中的所有進(jìn)程，在一給定的時間內(nèi)，均能獲得一時間片的處理機執(zhí)行時間。2.多級反饋隊列調(diào)度算法(1)應(yīng)設(shè)置多個就緒隊列，并為各個隊列賦予不同的優(yōu)先級。第一個隊列的優(yōu)先級最高，第二個隊列次之，其余各隊列的優(yōu)先權(quán)逐個降低。該算法賦予各個隊列中進(jìn)程執(zhí)行時間片的大小也各不相同，在優(yōu)先權(quán)愈高的隊列中，為每個進(jìn)程所規(guī)定的執(zhí)行時間片就愈小。例如，第二個隊列的時間片要比第一個隊列的時間片長一倍，……，第i+1個隊列的時間片要比第i個隊列的時間片長一倍。圖3-5是多級反饋隊列算法的示意。圖3-5多級反饋隊列調(diào)度算法(2)當(dāng)一個新進(jìn)程進(jìn)入內(nèi)存后，首先將它放入第一隊列的末尾，按FCFS原則排隊等待調(diào)度。當(dāng)輪到該進(jìn)程執(zhí)行時，如它能在該時間片內(nèi)完成，便可準(zhǔn)備撤離系統(tǒng)；如果它在一個時間片結(jié)束時尚未完成，調(diào)度程序便將該進(jìn)程轉(zhuǎn)入第二隊列的末尾，再同樣地按FCFS原則等待調(diào)度執(zhí)行；如果它在第二隊列中運行一個時間片后仍未完成，再依次將它放入第三隊列，……，如此下去，當(dāng)一個長作業(yè)(進(jìn)程)從第一隊列依次降到第n隊列后，在第n隊列中便采取按時間片輪轉(zhuǎn)的方式運行。(3)僅當(dāng)?shù)谝魂犃锌臻e時，調(diào)度程序才調(diào)度第二隊列中的進(jìn)程運行；僅當(dāng)?shù)?~(i-1)隊列均空時，才會調(diào)度第i隊列中的進(jìn)程運行。如果處理機正在第i隊列中為某進(jìn)程服務(wù)時，又有新進(jìn)程進(jìn)入優(yōu)先權(quán)較高的隊列(第1~(i-1)中的任何一個隊列)，則此時新進(jìn)程將搶占正在運行進(jìn)程的處理機，即由調(diào)度程序把正在運行的進(jìn)程放回到第i隊列的末尾，把處理機分配給新到的高優(yōu)先權(quán)進(jìn)程。3.多級反饋隊列調(diào)度算法的性能終端型作業(yè)用戶：較小、短時完成。(2)短批處理作業(yè)用戶：在前幾個隊列完成，周轉(zhuǎn)快。(3)長批處理作業(yè)用戶：長作業(yè)得到處理。3.4實時調(diào)度3.4.1實現(xiàn)實時調(diào)度的基本條件1.提供必要的信息就緒時間。(2)開始截止時間和完成截止時間。(3)處理時間。(4)資源要求。(5)優(yōu)先級。2.系統(tǒng)處理能力強在實時系統(tǒng)中，通常都有著多個實時任務(wù)。若處理機的處理能力不夠強，則有可能因處理機忙不過來而使某些實時任務(wù)不能得到及時處理，從而導(dǎo)致發(fā)生難以預(yù)料的后果。假定系統(tǒng)中有m個周期性的硬實時任務(wù)，它們的處理時間可表示為Ci，周期時間表示為Pi，則在單處理機情況下，必須滿足下面的限制條件：系統(tǒng)才是可調(diào)度的。假如系統(tǒng)中有6個硬實時任務(wù)，它們的周期時間都是50ms，而每次的處理時間為10ms，則不難算出，此時是不能滿足上式的，因而系統(tǒng)是不可調(diào)度的。解決的方法是提高系統(tǒng)的處理能力，其途徑有二：其一仍是采用單處理機系統(tǒng)，但須增強其處理能力，以顯著地減少對每一個任務(wù)的處理時間；其二是采用多處理機系統(tǒng)。假定系統(tǒng)中的處理機數(shù)為N，則應(yīng)將上述的限制條件改為：3.采用搶占式調(diào)度機制當(dāng)一個優(yōu)先權(quán)更高的任務(wù)到達(dá)時，允許將當(dāng)前任務(wù)暫時掛起，而令高優(yōu)先權(quán)任務(wù)立即投入運行，這樣便可滿足該硬實時任務(wù)對截止時間的要求。但這種調(diào)度機制比較復(fù)雜。對于一些小的實時系統(tǒng)，如果能預(yù)知任務(wù)的開始截止時間，則對實時任務(wù)的調(diào)度可采用非搶占調(diào)度機制，以簡化調(diào)度程序和對任務(wù)調(diào)度時所花費的系統(tǒng)開銷。但在設(shè)計這種調(diào)度機制時，應(yīng)使所有的實時任務(wù)都比較小，并在執(zhí)行完關(guān)鍵性程序和臨界區(qū)后，能及時地將自己阻塞起來，以便釋放出處理機，供調(diào)度程序去調(diào)度那種開始截止時間即將到達(dá)的任務(wù)。4.具有快速切換機制該機制應(yīng)具有如下兩方面的能力：(1)對外部中斷的快速響應(yīng)能力。為使在緊迫的外部事件請求中斷時系統(tǒng)能及時響應(yīng)，要求系統(tǒng)具有快速硬件中斷機構(gòu)，還應(yīng)使禁止中斷的時間間隔盡量短，以免耽誤時機(其它緊迫任務(wù))。(2)快速的任務(wù)分派能力。在完成任務(wù)調(diào)度后，便應(yīng)進(jìn)行任務(wù)切換。為了提高分派程序進(jìn)行任務(wù)切換時的速度，應(yīng)使系統(tǒng)中的每個運行功能單位適當(dāng)?shù)男?，以減少任務(wù)切換的時間開銷。3.4.2實時調(diào)度算法的分類1.非搶占式調(diào)度算法非搶占式輪轉(zhuǎn)調(diào)度算法。(2)非搶占式優(yōu)先調(diào)度算法。2.搶占式調(diào)度算法基于時鐘中斷的搶占式優(yōu)先權(quán)調(diào)度算法。(2)立即搶占(ImmediatePreemption)的優(yōu)先權(quán)調(diào)度算法。圖3-6實時進(jìn)程調(diào)度3.4.3常用的幾種實時調(diào)度算法1.最早截止時間優(yōu)先即EDF(EarliestDeadlineFirst)算法圖3-7EDF算法用于非搶占調(diào)度方式2.最低松弛度優(yōu)先即LLF(LeastLaxityFirst)算法該算法是根據(jù)任務(wù)緊急(或松弛)的程度，來確定任務(wù)的優(yōu)先級。任務(wù)的緊急程度愈高，為該任務(wù)所賦予的優(yōu)先級就愈高，以使之優(yōu)先執(zhí)行。例如，一個任務(wù)在200ms時必須完成，而它本身所需的運行時間就有100ms，因此，調(diào)度程序必須在100ms之前調(diào)度執(zhí)行，該任務(wù)的緊急程度(松弛程度)為100ms。又如，另一任務(wù)在400ms時必須完成，它本身需要運行150ms，則其松弛程度為250ms。在實現(xiàn)該算法時要求系統(tǒng)中有一個按松弛度排序的實時任務(wù)就緒隊列，松弛度最低的任務(wù)排在隊列最前面，調(diào)度程序總是選擇就緒隊列中的隊首任務(wù)執(zhí)行。該算法主要用于可搶占調(diào)度方式中。假如在一個實時系統(tǒng)中，有兩個周期性實時任務(wù)A和B，任務(wù)A要求每20ms執(zhí)行一次，執(zhí)行時間為10ms；任務(wù)B只要求每50ms執(zhí)行一次，執(zhí)行時間為25ms。圖3-8A和B任務(wù)每次必須完成的時間在剛開始時(t1=0)，A1必須在20ms時完成，而它本身運行又需10ms，可算出A1的松弛度為10ms；B1必須在50ms時完成，而它本身運行就需25ms，可算出B1的松弛度為25ms，故調(diào)度程序應(yīng)先調(diào)度A1執(zhí)行。在t2=10ms時，A2的松弛度可按下式算出：A2的松弛度=必須完成時間-其本身的運行時間-當(dāng)前時間=40ms-10ms-10ms=20ms類似地，可算出B1的松弛度為15ms，故調(diào)度程序應(yīng)選擇B2運行。在t3=30ms時，A2的松弛度已減為0(即40-10-30)，而B1的松弛度為15ms(即50-5-30)，于是調(diào)度程序應(yīng)搶占B1的處理機而調(diào)度A2運行。在t4=40ms時，A3的松弛度為10ms(即60-10-40)，而B1的松弛度僅為5ms(即50-5-40)，故又應(yīng)重新調(diào)度B1執(zhí)行。在t5=45ms時，B1執(zhí)行完成，而此時A3的松弛度已減為5ms(即60-10-45)，而B2的松弛度為30ms(即100-25-45)，于是又應(yīng)調(diào)度A3執(zhí)行。在t6=55ms時，任務(wù)A尚未進(jìn)入第4周期，而任務(wù)B已進(jìn)入第2周期，故再調(diào)度B2執(zhí)行。在t7=70ms時，A4的松弛度已減至0ms(即80-10-70)，而B2的松弛度為20ms(即100-10-70)，故此時調(diào)度又應(yīng)搶占B2的處理機而調(diào)度A4執(zhí)行。圖3-9利用ELLF算法進(jìn)行調(diào)度的情況3.5產(chǎn)生死鎖的原因和必要條件3.5.1產(chǎn)生死鎖的原因競爭資源。(2)進(jìn)程間推進(jìn)順序非法。1.競爭資源引起進(jìn)程死鎖可剝奪和非剝奪性資源：內(nèi)存VS打印機2)競爭非剝奪性資源：3)競爭臨時性資源：消息、緩沖區(qū)等圖3-12I/O設(shè)備共享時的死鎖情況圖3-13進(jìn)程之間通信時的死鎖2.進(jìn)程推進(jìn)順序不當(dāng)引起死鎖1)進(jìn)程推進(jìn)順序合法圖3-14進(jìn)程推進(jìn)順序?qū)λ梨i的影響2)進(jìn)程推進(jìn)順序非法若并發(fā)進(jìn)程P1和P2按曲線④所示的順序推進(jìn)，它們將進(jìn)入不安全區(qū)D內(nèi)。此時P1保持了資源R1,P2保持了資源R2,系統(tǒng)處于不安全狀態(tài)。因為，這時兩進(jìn)程再向前推進(jìn)，便可能發(fā)生死鎖。例如，當(dāng)P1運行到P1:Request(R2)時，將因R2已被P2占用而阻塞；當(dāng)P2運行到P2:Request(R1)時，也將因R1已被P1占用而阻塞，于是發(fā)生了進(jìn)程死鎖。3.5.2產(chǎn)生死鎖的必要條件互斥條件(2)請求和保持條件(3)不剝奪條件(4)環(huán)路等待條件3.5.3處理死鎖的基本方法預(yù)防死鎖。(2)避免死鎖。(3)檢測死鎖。(4)解除死鎖。3.6預(yù)防死鎖的方法3.6.1預(yù)防死鎖摒棄“請求和保持”條件：一次性分配2.摒棄“不剝奪”條件：產(chǎn)生副作用，如打印機3.摒棄“環(huán)路等待”條件:資源編號，順序申請3.6.2系統(tǒng)安全狀態(tài)

1.安全狀態(tài)在避免死鎖的方法中，允許進(jìn)程動態(tài)地申請資源，但系統(tǒng)在進(jìn)行資源分配之前，應(yīng)先計算此次資源分配的安全性。若此次分配不會導(dǎo)致系統(tǒng)進(jìn)入不安全狀態(tài)，則將資源分配給進(jìn)程；否則，令進(jìn)程等待。所謂安全狀態(tài)，是指系統(tǒng)能按某種進(jìn)程順序(P1,P2,…，Pn)(稱〈P1,P2,…,Pn〉序列為安全序列)，來為每個進(jìn)程Pi分配其所需資源，直至滿足每個進(jìn)程對資源的最大需求，使每個進(jìn)程都可順利地完成。如果系統(tǒng)無法找到這樣一個安全序列，則稱系統(tǒng)處于不安全狀態(tài)。2.安全狀態(tài)之例我們通過一個例子來說明安全性。假定系統(tǒng)中有三個進(jìn)程P1、P2和P3，共有12臺磁帶機。進(jìn)程P1總共要求10臺磁帶機，P2和P3分別要求4臺和9臺。假設(shè)在T0時刻，進(jìn)程P1、P2和P3已分別獲得5臺、2臺和2臺磁帶機，尚有3臺空閑未分配，如下表所示：進(jìn)程最大需求已分配可用P1P2P3104952233.由安全狀態(tài)向不安全狀態(tài)的轉(zhuǎn)換如果不按照安全序列分配資源，則系統(tǒng)可能會由安全狀態(tài)進(jìn)入不安全狀態(tài)。例如，在T0時刻以后，P3又請求1臺磁帶機，若此時系統(tǒng)把剩余3臺中的1臺分配給P3，則系統(tǒng)便進(jìn)入不安全狀態(tài)。因為，此時也無法再找到一個安全序列，例如，把其余的2臺分配給P2，這樣，在P2完成后只能釋放出4臺，既不能滿足P1尚需5臺的要求，也不能滿足P3尚需6臺的要求，致使它們都無法推進(jìn)到完成，彼此都在等待對方釋放資源，即陷入僵局，結(jié)果導(dǎo)致死鎖。3.6.3利用銀行家算法避免死鎖1.銀行家算法中的數(shù)據(jù)結(jié)構(gòu)(1)可利用資源向量Available。這是一個含有m個元素的數(shù)組，其中的每一個元素代表一類可利用的資源數(shù)目，其初始值是系統(tǒng)中所配置的該類全部可用資源的數(shù)目，其數(shù)值隨該類資源的分配和回收而動態(tài)地改變。如果Available［j］=K，則表示系統(tǒng)中現(xiàn)有Rj類資源K個。(2)最大需求矩陣Max。這是一個n×m的矩陣，它定義了系統(tǒng)中n個進(jìn)程中的每一個進(jìn)程對m類資源的最大需求。如果Max［i,j］=K，則表示進(jìn)程i需要Rj類資源的最大數(shù)目為K。(3)分配矩陣Allocation。這也是一個n×m的矩陣，它定義了系統(tǒng)中每一類資源當(dāng)前已分配給每一進(jìn)程的資源數(shù)。如果Allocation［i,j］=K，則表示進(jìn)程i當(dāng)前已分得Rj類資源的數(shù)目為K。(4)需求矩陣Need。這也是一個n×m的矩陣，用以表示每一個進(jìn)程尚需的各類資源數(shù)。如果Need［i,j］=K，則表示進(jìn)程i還需要Rj類資源K個，方能完成其任務(wù)。Need［i,j］=Max［i,j］-Allocation［i,j］

2.銀行家算法設(shè)Requesti是進(jìn)程Pi的請求向量，如果Requesti［j］=K，表示進(jìn)程Pi需要K個Rj類型的資源。當(dāng)Pi發(fā)出資源請求后，系統(tǒng)按下述步驟進(jìn)行檢查：(1)如果Requesti［j］≤Need［i,j］，便轉(zhuǎn)向步驟2；否則認(rèn)為出錯，因為它所需要的資源數(shù)已超過它所宣布的最大值。(2)如果Requesti［j］≤Available［j］，便轉(zhuǎn)向步驟(3)；否則，表示尚無足夠資源，Pi須等待。(3)系統(tǒng)試探著把資源分配給進(jìn)程Pi，并修改下面數(shù)據(jù)結(jié)構(gòu)中的數(shù)值：

Available［j］∶=Available［j］-Requesti［j］;Allocation［i,j］∶=Allocation［i,j］+Requesti［j］;Need［i,j］∶=Need［i,j］-Requesti［j］;(4)系統(tǒng)執(zhí)行安全性算法，檢查此次資源分配后，系統(tǒng)是否處于安全狀態(tài)。若安全，才正式將資源分配給進(jìn)程Pi，以完成本次分配；否則，將本次的試探分配作廢，恢復(fù)原來的資源分配狀態(tài)，讓進(jìn)程Pi等待。3.安全性算法(1)設(shè)置兩個向量：①工作向量Work:它表示系統(tǒng)可提供給進(jìn)程繼續(xù)運行所需的各類資源數(shù)目，它含有m個元素，在執(zhí)行安全算法開始時，Work∶=Available;②Finish:它表示系統(tǒng)是否有足夠的資源分配給進(jìn)程，使之運行完成。開始時先做Finish［i］∶=false;當(dāng)有足夠資源分配給進(jìn)程時，再令Finish［i］∶=true。(2)從進(jìn)程集合中找到一個能滿足下述條件的進(jìn)程：①Finish［i］=false;②Need［i,j］≤Work［j］；若找到，執(zhí)行步驟(3)，否則，執(zhí)行步驟(4)。(3)當(dāng)進(jìn)程Pi獲得資源后，可順利執(zhí)行，直至完成，并釋放出分配給它的資源，故應(yīng)執(zhí)行：

Work［j］∶=Work［i］+Allocation［i,j］;Finish［i］∶=true;gotostep2;(4)如果所有進(jìn)程的Finish［i］=true都滿足，則表示系統(tǒng)處于安全狀態(tài)；否則，系統(tǒng)處于不安全狀態(tài)。4.銀行家算法之例假定系統(tǒng)中有五個進(jìn)程｛P0,P1,P2,P3,P4｝和三類資源｛A,B,C｝，各種資源的數(shù)量分別為10、5、7，在T0時刻的資源分配情況如圖3-15所示。圖3-15T0時刻的資源分配表(1)T0時刻的安全性：圖3-16T0時刻的安全序列(2)P1請求資源：P1發(fā)出請求向量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向量，由此形成的資源變化情況如圖3-15中的圓括號所示。④再利用安全性算法檢查此時系統(tǒng)是否安全。圖3-17P1申請資源時的安全性檢查(3)P4請求資源：P4發(fā)出請求向量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請求資源：P0發(fā)出請求向量Requst0(0，2，0)，系統(tǒng)按銀行家算法進(jìn)行檢查：①Request0(0,2,0)≤Need0(7,4,3);②Reque