操作系統(tǒng)原理與實踐教程(第四版) 第4章 進程同步與死鎖

第4章進程同步與死鎖4.1進程的同步和互斥4.2經(jīng)典同步問題4.3管程4.4進程通信4.5死鎖4.6死鎖的預(yù)防和避免4.7死鎖的檢測和解除4.1.1進程的同步操作系統(tǒng)中的進程都是各自獨立并以不可預(yù)知的速度向前推進，也就是一個進程相對另一個進程的執(zhí)行速度是無法確定的，即它們具有異步性。但是對于需要相互合作的進程來說，其執(zhí)行順序需要在某些特定時刻進行協(xié)調(diào)，先達到條件的進程需要等待后到達的進程，此時這些進程間存在一種制約關(guān)系。4.1.1進程的同步同步是進程間的直接制約關(guān)系，這種制約主要源于進程間的合作。進程同步的主要任務(wù)就是使并發(fā)執(zhí)行的各進程之間能有效地共享資源和相互合作，從而在執(zhí)行時間、次序上相互制約，按照一定的協(xié)議協(xié)調(diào)執(zhí)行，使程序的執(zhí)行具有可再現(xiàn)性。4.1.2進程互斥當(dāng)多個進程需要使用相同的資源，而此類資源在任一時刻卻只能供一個進程使用，獲得資源的進程可以繼續(xù)執(zhí)行，沒有獲得資源的進程必須等待。這是進程之間的間接制約關(guān)系。這種關(guān)系與源于進程間合作的同步關(guān)系不同，它們的運行具有時間次序的特征，誰先從系統(tǒng)獲得共享資源，誰就先運行。這種對共享資源的排它性使用所造成的進程間的間接制約關(guān)系稱為進程互斥?；コ馐且环N特殊的同步方式4.1.2進程互斥臨界資源在同一時段只能被一個進程使用的計算機資源，比如打印機。臨界資源可能是硬件，也可能是軟件，如變量、數(shù)據(jù)、表格、隊列等。它們雖然可以被若干個進程共享，但一次只能為一個進程使用。臨界資源的管理由操作系統(tǒng)完成，它通常將臨界資源分配給首先提出使用申請的進程。4.1.2進程互斥臨界區(qū)(CriticalSection)為保證多個進程對臨界資源進行正確的互斥訪問，人們把每個進程中訪問臨界資源的那段代碼使用特殊手段管理，這段代碼被稱為臨界區(qū)

如果能保證諸進程互斥地進入自己的臨界區(qū)，即可實現(xiàn)對臨界資源的互斥訪問。進程在進入臨界區(qū)之前，首先要對臨界資源的使用情況進行查詢，如果臨界資源處于空閑狀態(tài)，則該進程可以進入臨界區(qū)，同時把臨界資源的狀態(tài)設(shè)置為正在使用狀態(tài)；如果臨界資源正在被使用，那么該進程不能進入臨界區(qū)。4.1.2進程互斥進入?yún)^(qū)(EntrySection)位于臨界區(qū)前面的一段用于檢查臨界區(qū)使用狀態(tài)的代碼被稱為進入?yún)^(qū)。退出區(qū)(ExitSection)在進程完成對臨界區(qū)的訪問之后，要把臨界區(qū)訪問標(biāo)志恢復(fù)為未被訪問標(biāo)志，完成該任務(wù)的代碼段被稱為退出區(qū)(ExitSection)剩余區(qū)進程中除了進入?yún)^(qū)、臨界區(qū)和退出區(qū)之外的部分被稱為剩余區(qū)。

4.1.2進程互斥一個描述臨界資源的循環(huán)進程可以描述如下:boolbFlag=true;do{進入?yún)^(qū)臨界區(qū)退出區(qū)剩余區(qū)}while(bFlag==true);4.1.2進程互斥所有的同步機制都應(yīng)遵循下面的4條準(zhǔn)則：（1）空閑讓進當(dāng)無進程處于臨界區(qū)時，允許進程進入臨界區(qū)，并且只能在臨界區(qū)運行有限的時間。（2）忙則等待當(dāng)有一個進程在臨界區(qū)時，其它欲進入臨界區(qū)的進程必須等待，以保證進程互斥地訪問臨界資源。

4.1.2進程互斥（3）有限等待對要求訪問臨界資源的進程，應(yīng)保證進程能在有限時間內(nèi)進入臨界區(qū)，以免陷入“饑餓”狀態(tài)。（4）讓權(quán)等待當(dāng)進程不能進入臨界區(qū)時，應(yīng)立即放棄占用CPU，以使其它進程有機會得到CPU的使用權(quán)，以免陷入“饑餓”狀態(tài)。4.1.3信號量機制信號量的發(fā)展歷程信號量(Semaphore)是荷蘭學(xué)者Dijkstra在1965年提出的一種有效的進程同步和互斥工具，它負責(zé)協(xié)調(diào)各個進程，以保證它們能夠正確、合理地使用公共資源，有時也被稱為信號燈。經(jīng)過長期廣泛的應(yīng)用實踐，信號量機制已經(jīng)有了很大的發(fā)展，形成了整型信號量、記錄型信號量、信號量集等機制。信號量機制已經(jīng)被廣泛地應(yīng)用到單處理機和多處理機系統(tǒng)以及計算機網(wǎng)絡(luò)中。

4.1.3信號量機制整型信號量與P、V操作在整型信號量機制中，信號量S是個整型變量，通常被初始化為相應(yīng)資源的初始數(shù)量。除了初始化之外，對信號量S只能通過wait和signal這兩個標(biāo)準(zhǔn)的原子操作來訪問，這就保證了當(dāng)一個進程在修改某信號量時，沒有其它進程同時對它進行修改。因為希臘語wait的首字母為P，signal的首字母為V，所以wait和signal操作通常又稱為P、V操作。

4.1.3信號量機制wait操作可以表示為如下形式：voidwait(intS){while(S<=0);//當(dāng)信號量S的值小于等于0時，做空操作，//否則將其值減1S=S-1;}signal操作可以表示為如下形式：voidsignal(intS){S=S+1;}4.1.3信號量機制記錄型信號量除了需要一個用于代表資源數(shù)目的整形變量value之外，又增加一個進程鏈表L，用于鏈接上述所有等待進程，這兩者共同構(gòu)成了記錄型信號量。4.1.3信號量機制記錄型信號量的wait操作描述如下：voidwait(semaphoreS){S.value=S.value-1;//申請資源，嘗試分配if(S.value<0){/*若申請不成功，即在本次操作前value的值小于等于零，說明系統(tǒng)中沒有該資源，則阻塞本進程，并把本進程加入到S.L鏈表中*/block(S.L);}}4.1.3信號量機制記錄型信號量的signal操作描述如下：voidsignal(semaphoreS){S.value=S.value+1;//釋放資源，系統(tǒng)中該類資源當(dāng)前可用數(shù)量增1if(S.value<=0){/*若還有進程因該資源而阻塞，則喚醒阻塞進程，被喚醒者在阻塞鏈表L的鏈?zhǔn)孜恢?，從鏈表S.L頭部移出一個進程P*/wakeup(S.L);//喚醒被移出的進程P}}4.1.3信號量機制其中，block(S.L)操作用于阻塞調(diào)用它的進程，wakeup(P)操作用于喚醒鏈表L的鏈?zhǔn)鬃枞M程P。這兩個操作均以基本系統(tǒng)調(diào)用的形式由操作系統(tǒng)提供。4.1.3信號量機制AND型信號量AND同步機制的基本思想是：將進程在整個運行過程中需要的所有資源，一次性全部地分配給進程，等到進程使用完畢后再一起釋放。只要還有一個資源未能分配給進程，其它所有可能為之分配的資源，也不分配給它。也就是說，對若干個臨界資源的分配，采取原子操作的方式：要么全部分配給進程，要么一個也不分配。由死鎖理論可知，這樣就可避免上述死鎖情況的發(fā)生。

4.1.4信號量的使用方法互斥進程組織結(jié)構(gòu)模型

4.2經(jīng)典同步問題生產(chǎn)者-消費者問題讀者-寫者問題哲學(xué)家進餐問題理發(fā)師問題

4.2.1生產(chǎn)者-消費者問題問題描述

一批生產(chǎn)者生產(chǎn)特定結(jié)構(gòu)的產(chǎn)品，并將其放入具有n個緩沖區(qū)的環(huán)狀緩沖池，即若當(dāng)前使用的是n-1號緩沖區(qū)，下一個可用的就是0號緩沖區(qū)。生產(chǎn)者一次只能生產(chǎn)并放入一個產(chǎn)品，消費者一次只能取出并消費一個產(chǎn)品，且生產(chǎn)者和消費者、消費者之間、生產(chǎn)者之間均對緩沖池互斥訪問。在這個問題中，生產(chǎn)者和消費者使用固定的有限數(shù)目的n個緩沖區(qū)來進行任意數(shù)目消息的傳遞，因此也被稱為有限緩沖區(qū)問題。4.2.1生產(chǎn)者-消費者問題顯然，緩沖池是臨界資源，因此需要為其設(shè)置一個互斥信號量mutex。此外，為了讓生產(chǎn)者和消費者都能使用正確的空、滿緩沖區(qū)，還需要設(shè)置兩個資源信號量empty和full，其初值分別為空、滿緩沖區(qū)的初值n和0。在進程選擇緩沖區(qū)時，還需要使用兩個特殊指針in和out，分別指向生產(chǎn)者使用的空緩沖區(qū)和消費者使用的滿緩沖區(qū)。每當(dāng)in或out當(dāng)前指向的緩沖區(qū)被生產(chǎn)者或消費者使用后，均需要后移一個緩沖區(qū)。4.2.1生產(chǎn)者-消費者問題使用偽代碼對生產(chǎn)者-消費者問題描述如下：semaphoremutex=1;semaphorefull=0;semaphoreempty=n;buffTypebuffer[n];Producer(){bufType*next,*in;while(TRUE){ produceItem(next);//生產(chǎn)者生產(chǎn)產(chǎn)品放入next緩沖區(qū)暫存 P(empty)；//申請一個空緩沖區(qū) P(mutex);//為緩沖池加鎖，使其它進程無法對其中任一緩沖區(qū)操作 copyBuffer(next,in);//將next緩沖區(qū)中的數(shù)據(jù)放入in所指向的公共空緩沖區(qū) in=(in+1)modn;//in指針后移一位，下一位生產(chǎn)者到來時將使用新的空區(qū) V(mutex);//為緩沖池解鎖，使其它進程可以進入緩沖池操作 V(full);/*釋放已經(jīng)裝滿數(shù)據(jù)的滿緩沖區(qū)，V操作使得滿緩沖區(qū)數(shù)量增1，若有因找不到滿緩沖區(qū)而被阻塞的消費者時，該操作還會喚醒它*/}}4.2.1生產(chǎn)者-消費者問題使用偽代碼對生產(chǎn)者-消費者問題描述如下：（續(xù)）Consumer(){ bufType*next,*out; while(TRUE){ P(full);//消費者申請一個滿緩沖區(qū) P(mutex); //為緩沖池加鎖 copyBuffer(out,next);/*將out指針指向的滿緩沖區(qū)整體復(fù)制到next緩沖區(qū)暫存*/ out=(out+1)modn;/*將out指針后移一位，下一個到來的消費者將使用out指針新指向的滿緩沖區(qū)*/ V(mutex); //為緩沖池解鎖 V(empty); /*釋放已經(jīng)清空的空緩沖區(qū)，該V操作將使得空緩沖區(qū)數(shù)量增1，若有因找不到空緩沖區(qū)而阻塞的生產(chǎn)者時，該操作還會喚醒它*/ consumeItem(next); //消費者消費商品}}4.2.1生產(chǎn)者-消費者問題有三個細節(jié)需要注意：第一，對信號量的P操作要注意順序問題，即當(dāng)程序中出現(xiàn)多個P操作時順序不能顛倒，應(yīng)先對資源信號量進行P操作，再對互斥信號量進行P操作。第二，在同一個進程中，用于實現(xiàn)互斥的信號量的P、V操作必須成對出現(xiàn)。第三，在合作進程之間，通過資源信號量傳遞信息。4.2.2讀者-寫者問題問題描述該問題假設(shè)一種資源在兩種截然不同的進程間共享，一類進程可以和同類的其它進程一起共享資源，且不會對資源進行改寫，只獲取資源的副本，它們的行為與去圖書館讀書的讀者很相似，因此被形象的稱為讀者(reader)；而另一類進程則能夠?qū)Y源進行改寫，且在使用資源的時候排斥其它任何類型的進程使用該資源，這樣的行為又與書籍的作者類似，因此被稱為寫者(writer)。

4.2.2讀者-寫者問題

讀者-寫者問題經(jīng)常用來描述一組進程共享一個文件時，多個只讀權(quán)限的進程可以同時共享該文件，一旦有進程對文件進行改寫時，其它任何進程(無論是讀者還是寫者)均不可共享該文件。4.2.2讀者-寫者問題讀者-寫者問題的解決方案

第一種方案是讀者優(yōu)先，由于讀者對資源沒有修改且通常只需獲取一個副本即可離開，因此其操作時間比較短，所以可以考慮讓讀者優(yōu)先，即只要有一個讀者持有資源，后繼到達的讀者可以被允許立即進入臨界區(qū)，而后繼到達的寫者將被當(dāng)前的讀者排斥而無法進入臨界區(qū)，只能阻塞自身。這種方法中，只有第一個到達的讀者才需要與寫者競爭共享資源，只要讀者獲得共享資源后，在資源沒有被釋放之前，后繼的讀者都可以直接進入臨界區(qū)訪問。這種讀者優(yōu)先的方案被稱為第一讀者-寫者問題。4.2.2讀者-寫者問題第二種解決方案是寫者優(yōu)先的。該方法中，當(dāng)一個寫者請求訪問共享資源時，任一隨后到達的讀者進程必須等待，直到先到的讀者完成共享資源的訪問并釋放該資源后才繼續(xù)。當(dāng)?shù)谝粋€寫者離開臨界區(qū)后，由于寫者的優(yōu)先級高于讀者，則第二個寫者將進入臨界區(qū)，讀者將會等待。只有所有的寫者都離開臨界區(qū)后，讀者才可進入自身臨界區(qū)。4.2.3哲學(xué)家進餐問題問題描述五個哲學(xué)家一生都在思考和進餐中度過，他們圍坐在一個圓桌周圍，每人面前放了一份美味的餐點，兩份相鄰的餐盤中間都放了一根筷子，哲學(xué)家需要把自己左右兩側(cè)的兩個筷子分別拿起才能進餐。哲學(xué)家的行為模式就是平時思考，餓了就分別拿起兩側(cè)的筷子，若兩次都能成功，即獲得了兩根筷子時，該哲學(xué)家就可以進餐了。當(dāng)他吃飽后，為了不讓其他人挨餓，需要馬上將兩根筷子分別放下，注意，這里并沒有對拿起和放下筷子的次序做強制規(guī)定。4.2.3哲學(xué)家進餐問題一種最直接的解法是強制每個哲學(xué)家都先拿起左邊的筷子，成功后再去拿起右邊的筷子。缺點是可能會產(chǎn)生嚴重的“饑餓”現(xiàn)象。若五個哲學(xué)家同時拿起左筷子，此時桌子上沒有一根未用的筷子，每個哲學(xué)家都在等待其右邊的鄰居進餐完畢后釋放筷子給自己。那么所有的哲學(xué)家將僵持并永久等待下去，導(dǎo)致長期饑餓。4.2.4理發(fā)師問題問題描述：在理發(fā)店中有一位理發(fā)師、一把理發(fā)椅和n把供顧客等待的等待位。若沒有顧客，理發(fā)師便在理發(fā)椅上睡覺。當(dāng)?shù)谝粋€顧客到來時，他必須先叫醒理發(fā)師為其服務(wù)。當(dāng)理發(fā)師正在為顧客服務(wù)時，新到來的顧客將查看是否有空閑的等待位，若有就坐下等待，若無就離開理發(fā)店。理發(fā)師在為當(dāng)前顧客服務(wù)完時要查看是否有等待的顧客，若有就繼續(xù)服務(wù)，若無就馬上睡去。

4.2.4理發(fā)師問題解決這個問題需要設(shè)置三個信號量：customers，用來記錄等待理發(fā)的顧客數(shù)(不包括正在理發(fā)的顧客)；barbers，記錄正在等候顧客的理發(fā)師數(shù)，其值應(yīng)為0或1；mutex，用于互斥。此外還應(yīng)設(shè)置一個變量waiting，它也是記錄等待的顧客數(shù)，是customers的一個副本。設(shè)置waiting的原因是customers是一個信號量，無法讀取其當(dāng)前值。當(dāng)一個顧客進入理發(fā)店后，首先做的就是檢查等候的顧客數(shù)量waiting，若該數(shù)量少于等待位數(shù)，顧客坐下等待，否則離開。4.2.4理發(fā)師問題偽代碼描述如下：intCHAIRS=5; //設(shè)等待位為5semaphorecustomers=0; //等待服務(wù)的顧客數(shù)semaphorebarbers=0; //等待顧客的理發(fā)師數(shù)semaphoremutex=1; intwaiting=0;barber(){ while(TRUE){ P(customers); //等待的顧客數(shù)為0就進入睡眠狀態(tài)(阻塞) P(mutex); //獲得對waiting的訪問權(quán) waiting=waiting-1; //將等待的顧客數(shù)減1 V(barbers); //理發(fā)師準(zhǔn)備理發(fā) V(mutex); //釋放對waiting的訪問權(quán) 理發(fā)； }}4.2.4理發(fā)師問題偽代碼描述如下：（續(xù)）customer(){ P(mutex); //進入臨界區(qū) if(waiting<CHAIRS){ //若沒有空閑等待位就離開 waiting=waiting+1; //將等待的顧客數(shù)加1 V(customers); //如果理發(fā)師在睡覺就喚醒他 V(mutex); //釋放對waiting的訪問權(quán) P(barbers); //若無顧客可服務(wù)理發(fā)師就睡覺 享受理發(fā)服務(wù); }else{ V(mutex); //理發(fā)店已滿，不進入 }}4.3管程管程的基本概念條件變量使用管程解決生產(chǎn)者-消費者問題4.3.1管程的基本概念信號量機制功能強大，是一種既方便、又有效的進程同步機制，但是在使用過程中對信號量的操作分散在各個進程中，不易控制。管程定義管程是由過程、變量及數(shù)據(jù)結(jié)構(gòu)等組成，它們共同構(gòu)成了一個特殊的模塊或軟件包。進程可以在任意時刻調(diào)用管程中的過程，但不允許使用管程外的過程來訪問管程內(nèi)的數(shù)據(jù)結(jié)構(gòu)。管程中在任一時刻只能有一個活躍進程，這一特性可以幫助管程有效地實現(xiàn)互斥。4.3.1管程的基本概念管程示意圖4.3.1管程的基本概念管程與進程的區(qū)別：(1)雖然二者都定義了數(shù)據(jù)結(jié)構(gòu)，但進程定義的是私有數(shù)據(jù)結(jié)構(gòu)PCB，而管程定義的是公共數(shù)據(jù)結(jié)構(gòu)，如條件變量等；(2)二者都存在對各自數(shù)據(jù)結(jié)構(gòu)上的操作，但進程是順序執(zhí)行的，而管程則是進行同步操作和初始化操作；(3)進程是為了保證系統(tǒng)并發(fā)而設(shè)計的，管程則是為了解決共享資源的互斥；(4)進程通過調(diào)用管程中的過程來進行共享數(shù)據(jù)結(jié)構(gòu)的操作，該過程就表現(xiàn)為進程的子程序，因此進程是主動的，管程是被動的；(5)進程間可并發(fā)，管程作為子程序不能與其調(diào)用者并發(fā)；(6)進程具有動態(tài)性和生命周期，而管程只是一個資源管理模塊，供進程調(diào)用。4.3.2條件變量在管程中，除了完成互斥外，還要保證能將無法繼續(xù)運行的進程正確阻塞。因此，需要引入條件變量(conditionvariable)以及對其的一對wait、signal操作。4.3.2條件變量wait操作的含義：x.wait表示正在調(diào)用管程的進程因x條件需要被阻塞或掛起，該進程在執(zhí)行wait操作時將自己插入x條件的等待隊列中，并釋放管程。此時其它進程可以使用該管程完成自身工作，當(dāng)x條件產(chǎn)生變化時，系統(tǒng)調(diào)度程序?qū)⑦x擇等待隊列中的一個進程繼續(xù)執(zhí)行。4.3.2條件變量signal操作的含義：x.signal表示正在調(diào)用管程的進程發(fā)現(xiàn)x條件發(fā)生了變化，則使用signal操作喚醒一個因x條件被阻塞或掛起的進程。當(dāng)一個管程中的過程發(fā)現(xiàn)自身無法運行下去(如生產(chǎn)者進程發(fā)現(xiàn)緩沖池滿)時，它將對某個條件變量(如full)執(zhí)行wait操作。該操作會阻塞調(diào)用進程自身，并將其它在管程外等待的進程調(diào)入管程。4.3.3使用管程解決生產(chǎn)者-消費者問題使用管程機制可以很好地解決生產(chǎn)者-消費者問題。此時需要首先建立一個管程ProducerConsumer，其中包含兩個過程insert(item)和consumer(item)。4.3.3使用管程解決生產(chǎn)者-消費者問題偽代碼描述如下：monitorProducerConsumer conditionfull,empty; intcount; voidinsert(intitem) { if(count==N)wait(full); insert(item); count=count+1; if(count==1)signal(empty); } intremover() { if(count==0)wait(empty); remove=remove_item; count=count-1; if(count==N-1)signal(full); } count=0;endmonitor4.3.3使用管程解決生產(chǎn)者-消費者問題偽代碼描述如下:(續(xù))voidproducer(){ while(true) { item=produce_item; ProducerConsumer.insert(item); }}voidconsumer(){ while(true) { item=ProducerConsumer.remove; consume(item) }}4.4進程通信進程通信的概念進程通信的方式消息傳遞系統(tǒng)消息緩沖隊列通信機制管道通信方式4.4.1進程通信的概念進程通信指的是進程間的信息交換。所謂高級進程通信，是指用戶可直接利用操作系統(tǒng)所提供的一組通信原語，高效地傳送大量數(shù)據(jù)的一種通信方式。進程通信對用戶是透明的。程序員只需要簡單調(diào)用操作系統(tǒng)提供的通信原語就能方便地實現(xiàn)進程間的通信，使通信程序編制的復(fù)雜性大大降低。4.4.2進程通信的方式高級通信機制可以分為三大類：共享存儲系統(tǒng)、消息傳遞系統(tǒng)和管道通信系統(tǒng)。共享存儲器系統(tǒng):在共享存儲器系統(tǒng)中，相互通信的進程通過共享某些數(shù)據(jù)結(jié)構(gòu)或共享存儲區(qū)實現(xiàn)進程之間的通信。4.4.2進程通信的方式共享存儲器系統(tǒng)可進一步細分為兩種方式：基于共享數(shù)據(jù)結(jié)構(gòu)的通信方式和基于共享存儲區(qū)的通信方式?；诠蚕頂?shù)據(jù)結(jié)構(gòu)的通信方式:在該方式中，操作系統(tǒng)只提供共享存儲器，對共享的公共數(shù)據(jù)結(jié)構(gòu)的定義及進程間的同步處理都要由程序員完成，這種方式是低效的，只能傳遞相對少量的數(shù)據(jù)?；诠蚕泶鎯^(qū)的通訊方式:在該方式中，操作系統(tǒng)要將存儲器中的一個子空間用作共享存儲區(qū)，各進程都可以對該存儲區(qū)進行讀寫操作，每個進程都可以讀到其它合作進程放入該區(qū)的數(shù)據(jù)。4.4.2進程通信的方式消息傳遞系統(tǒng)消息傳遞機制可以實現(xiàn)不同主機間多個CPU上進程的通信。這種方式需要使用兩條原語send和receive來發(fā)送和接收格式化的消息(message)。send原語用來向一個指定目標(biāo)發(fā)送一條消息，receive原語用來從一個指定目標(biāo)接收一條消息。沒有消息傳遞時，消息的發(fā)送者和接收者都按自己的進度不斷工作。4.4.2進程通信的方式管道通信系統(tǒng)管道通信是一種以文件系統(tǒng)為基礎(chǔ)實現(xiàn)的適用于在進程之間實現(xiàn)大量數(shù)據(jù)傳送的通信方式。所謂管道(pipeline)是指連接一個接收(讀)進程和一個發(fā)送(寫)進程以實現(xiàn)它們之間通信的一個特殊的共享文件，又稱為pipe文件、管線。管道實質(zhì)上是一個共享文件，可以借助于文件系統(tǒng)的機制實現(xiàn)，包括(管道)文件的創(chuàng)建、打開、關(guān)閉和讀寫。4.4.3消息傳遞系統(tǒng)消息傳遞系統(tǒng)中需要定義兩條原語send和receive，它們是一種特殊的系統(tǒng)調(diào)用，能將格式化的消息在合作進程間傳遞。其調(diào)用形式如Send(receiver,message)Receive(sender,message)前者Send用于將消息message發(fā)送給receiver，后者Receive用來接收來自于發(fā)送者sender的消息message。這兩個原語不僅可以用于本機上進程間的通信，還可以用于通過網(wǎng)絡(luò)互連的多個主機間的通信，這種通信分為直接通信和間接通信兩種方式。4.4.3消息傳遞系統(tǒng)直接通信指的是發(fā)送進程直接利用send原語將消息發(fā)送給目標(biāo)進程，此時要求發(fā)送和接收兩方都要以顯式方式提供對方的標(biāo)識符。間接通信方式中進程間通信需要使用共享數(shù)據(jù)結(jié)構(gòu)的實體，發(fā)送進程用該實體暫存發(fā)送給目標(biāo)進程的消息，接收進程則從該實體中提取發(fā)送給自己的消息。4.4.4消息緩沖隊列通信機制消息緩沖隊列通信機制首先由美國的Hansan提出，并在RC4000系統(tǒng)上實現(xiàn)，后來被廣泛應(yīng)用于本地進程之間的通信中。在這種通信機制中，發(fā)送進程利用Send原語將消息直接發(fā)送給接收進程，接收進程則使用Receive原語接收消息。4.4.4消息緩沖隊列通信機制消息緩沖隊列通信機制中的相關(guān)數(shù)據(jù)結(jié)構(gòu)消息緩沖隊列通信機制中最重要的數(shù)據(jù)結(jié)構(gòu)就是一組緩沖區(qū)，每個緩沖區(qū)中都可以放置一條消息。當(dāng)需要傳送一條消息時，發(fā)送進程首先調(diào)用Send原語，將需要發(fā)送消息的請求提交給系統(tǒng)，系統(tǒng)立即為其分配一個空緩沖區(qū)，發(fā)送進程將自己要發(fā)送的消息放入剛獲得的這個緩沖區(qū)中，最后再將該緩沖區(qū)放在接收者的消息緩沖隊列的隊尾即可完成發(fā)送工作。而接收者在某時刻調(diào)用Receive原語從自己的消息緩沖隊列中取出隊首元素，該緩沖區(qū)中放置的是其它進程發(fā)送給它的消息，此時系統(tǒng)將該緩沖區(qū)中的信息放入進程自身空間，再把空緩沖區(qū)回收即可。4.4.4消息緩沖隊列通信機制發(fā)送原語send發(fā)送進程在發(fā)送消息前需要先在自身空間開辟一個發(fā)送區(qū)，其中放入本次將要發(fā)送的消息體、發(fā)送進程標(biāo)識符、消息長度等必要信息。然后發(fā)送進程將調(diào)用發(fā)送原語將發(fā)送區(qū)中的數(shù)據(jù)打包發(fā)給接收進程。接收原語receive接收進程在收到消息后，需要調(diào)用接收原語receive()，以完成將自身消息緩沖隊列的隊首元素取下并復(fù)制到自身內(nèi)存空間的工作區(qū)。4.4.6Linux的進程通信Linux支持多種進程間的通信方式，如管道、信號、SysV和套接口等。這節(jié)將介紹SysV進程間通信的三種方式：信號量、消息隊列、共享內(nèi)存。4.4.6Linux的進程通信信號量信號量也叫信號燈，是一個確定的二元組（S，Q），其中S是個具有非負初值的整形變量，表示的是臨界資源的實體。信號量的值有以下兩種情況：代表可用資源的數(shù)量，此時Q的隊列為空。代表由于等待此種資源而被阻塞的進程的數(shù)量，也就是Q隊列中進程的個數(shù)。4.4.6Linux的進程通信信號量集合在內(nèi)核中的結(jié)構(gòu)體為sem_array，定義如下：structsem_array{ structkern_ipc_permsem_perm; time_tsem_otime;/*最近一次操作時間*/ time_tsem_ctime;/*最近一次改變時間*/ structsem*sem_base;/*指向第一個信號量*/ structsem_queue*sem_pending;/*掛起操作隊列*/ structsem_queue**sem_pending_last; structsem_undo*undo; unsignedlongsem_nsems;/*信號量的個數(shù)*/};4.4.6Linux的進程通信信號量的初始值可以調(diào)用函數(shù)semctl()進行設(shè)置，用戶調(diào)用semop()函數(shù)同時對一個或多個信號量進行操作，在實際應(yīng)用中，對應(yīng)多種資源的申請或釋放。Semop()保證操作的原子性，尤其對于多種資源的申請來說，要么一次性獲得所有的資源，要么放棄申請，要么在不占有任何資源的情況下繼續(xù)等待。Semop()的結(jié)構(gòu)體如下：

intsemop(intsemid,structsembuf*sops,intnsops);

其中，semid是信號量集合的ID；sops是一個數(shù)組，表示在一個或多個信號量上操作的集合；nsops為sops指向數(shù)組的大小。4.4.6Linux的進程通信消息隊列Linux采用消息隊列的方式來實現(xiàn)消息傳遞。這種消息的發(fā)送方式是：發(fā)送方不必等待接收方檢查它所收到的消息就可以繼續(xù)工作下去，而接收方如果沒有收到消息也不需等待。消息隊列的數(shù)據(jù)結(jié)構(gòu)(structipc_idsmsg_ids)位于內(nèi)核中，系統(tǒng)中的所有消息隊列都可以在結(jié)構(gòu)msg_ids中找到訪問入口。4.4.6Linux的進程通信消息隊列的編程接口(API)共有4個：msgget：調(diào)用者提供一個消息隊列的鍵標(biāo)(用于表示一個消息隊列的唯一名字)。msgsnd：向一個消息隊列發(fā)送一個消息，主要由sys_msgsnd執(zhí)行。msgrcv：從一個消息隊列中收到一個消息，主要由sys_msgrcv執(zhí)行。msgctl：在消息隊列上執(zhí)行指定的操作。根據(jù)參數(shù)的不同和權(quán)限的不同，可以執(zhí)行檢索、刪除等操作，主要由sys_msgctl執(zhí)行.4.4.6Linux的進程通信內(nèi)核中消息隊列用msg_queue結(jié)構(gòu)表示，定義如下：

structmsg_queue{ structkern_ipc_permq_perm; time_tq_stime;/*最近一次magsnd時間*/ time_tq_rtime/*最近一次msgrcv時間*/ time_tq_ctime;/*最近的改變時間*/ unsignedlongq_chytes;/*隊列中的字節(jié)數(shù)*/ unsignedlongq_qnum;/*隊列中消息數(shù)目*/ unsignedlongq_qhytes;/*隊列允許的最大字節(jié)數(shù)*/ pid_tq_lspid;/*最近一次msgsnd()函數(shù)發(fā)送進程的pid*/ pid_tq_lrpid;/*最近一次msgrcv()函數(shù)接收進程的pid*/

structlist_headq_messages;/*消息隊列*/ structlist_headq_senders;/*待發(fā)送消息的阻塞進程隊列*/ structlist_headq_receivers;/*待接收消息的阻塞進程隊列*/};4.4.6Linux的進程通信共享內(nèi)存是進程間通信的一種方式，它允許多個進程訪問同一塊內(nèi)存。不同的進程把共享內(nèi)存映射到自己的一塊地址空間，不同的進程映射的空間地址不一定相同。當(dāng)映射后，一個進程對該地址空間進程寫操作時，共享該內(nèi)存的其他進程就會察覺到這個更改，從而實現(xiàn)進程通信。因為共享內(nèi)存沒有提供進程間同步和互斥的機制，通常需要和信號量配合使用。4.4.6Linux的進程通信

共享內(nèi)存原理圖4.4.6Linux的進程通信進程通過共享內(nèi)存通信時，Linux為之提供了4個系統(tǒng)調(diào)用函數(shù)：shmget()：創(chuàng)建共享內(nèi)存，獲取一個內(nèi)部標(biāo)識為shmid的共享存儲區(qū)。shmat()：映射共享內(nèi)存，邏輯上將內(nèi)部標(biāo)識符為shmid的共享內(nèi)存區(qū)附接到進程的虛擬地址空間shmaddr。shmdt()：撤銷映射，將一個共享存儲區(qū)從指定的進程的虛擬地址空間斷開。shmctl()：共享內(nèi)存的控制，對與共享存儲區(qū)關(guān)聯(lián)的各種參數(shù)進行操作，從而對共享存儲區(qū)進行控制，包括刪除共享存儲區(qū)。4.4.6Linux的進程通信管道管道是指用于連接一個讀進程和一個寫進程，以實現(xiàn)它們之間通信的共享文件，又稱pipe文件。管道在進程間開辟一個固定大小的緩沖區(qū)，需要發(fā)布信息的進程運行寫操作，需要接收信息的進程運行讀操作。管道是單向的字節(jié)流，它把一個進程的標(biāo)準(zhǔn)輸出和另一個進程的標(biāo)準(zhǔn)輸入連接在一起。Linux中有兩種管道：無名管道和命名管道。4.4.6Linux的進程通信無名管道無名管道沒有磁盤節(jié)點，它僅作為一個內(nèi)存對象存在，用完后就銷毀了。它以先進先出的方式保存一定數(shù)量的數(shù)據(jù)，一個進程從管道的一端寫，另一個進程從管道的另一端讀。無名管道進行進程間通信的步驟如下：創(chuàng)建管道；生成子進程（多個）；關(guān)閉/復(fù)制文件描述符，使之與相應(yīng)的管道末端相聯(lián)系；關(guān)閉不需要的管道末端；進行通信活動；關(guān)閉剩余所有的打開文件描述符；等待子進程結(jié)束。4.4.6Linux的進程通信命名管道命名管道沒有文件名和磁盤節(jié)點，它可由任意兩個或多個進程間通信使用，它的使用方法和普通文件類似，都遵循打開、讀、寫、關(guān)閉這樣的過程，但是讀寫的內(nèi)部實現(xiàn)和普通文件不同，而和無名管道一樣。在Linux系統(tǒng)中，可以識別命名管道文件。例如：

$ls-lfilename

prs-r--r--lroot0sep2719:40filename|Filename文件名后跟著一個“|”符號表明該文件時管道文件。4.4.6Linux的進程通信信號信號是Linux進程間通信的一種異步通信機制，可以看作是異步通知，即告訴接受信號的進程有哪些事情發(fā)生，收到信號的進程對各種信號有不同的處理方式。信號通信的處理過程：通常情況下，把從開始發(fā)送信號到信號處理結(jié)束的過程稱為信號生命周期，它包括四部分：信號產(chǎn)生、信號注冊、信號注銷和信號處理。其中前兩項可歸為信號發(fā)送，后兩項可歸為信號接收。4.4.6Linux的進程通信操作系統(tǒng)中每個進程中都有一個進程控制塊（PCB），用于表述和控制單個進程。PCB的數(shù)據(jù)結(jié)構(gòu)中主要包括三部分：掛起信號（pending）：掛起信號是一個鏈表，記錄了等待進程處理的信號（sigID）以及信號的發(fā)起者（sender），具有信號寄存器的作用。信號描述符（sig_flag）：表項中包含了進程對信號的處理方式（sig_flag）和信號處理程序的入口。信號阻塞位（blocked）：標(biāo)記了暫時不處理的信號，具有信號屏蔽寄存器的作業(yè)用。每個信號都有一個數(shù)字（sigID）標(biāo)識，在信號描述符中占有相應(yīng)的表項。4.4.6Linux的進程通信進程通過系統(tǒng)調(diào)用來設(shè)置對某種信號的處理方式和處理程序，信號必須由接收今后的進程完成，該進程在接收到信號后可以采用四種方式處理信號。忽略信號：丟棄或忽略信號，但SIGSTOP和SIGKILL信號不能忽略。阻塞信號：暫時不處理該信號，推遲該信號的處理。默認處理信號：該信號沒有指定的信號處理程序，由內(nèi)核的默認處理程序處理。進程處理信號：有進程制定的處理程序處理該信號4.4.6Linux的進程通信Linux常用的信號SIGHUP 終端掛起或控制進程的信號SIGINT/SIGQUIT 鍵盤的中斷/退出信號SIGABRT 由abort（）函數(shù)發(fā)出的退出信號SIGILL

非法指令信號SIGKILL 終止進程的信號SIGPIPE 管道破裂信號：寫一個沒有讀端口的管道SIGSTOP 進程掛起信號SIGCHLD 子進程結(jié)束信號SIGUSR1 用戶自定義信號14.5死鎖死鎖的概念死鎖產(chǎn)生的原因和必要條件死鎖的描述-資源分配圖處理死鎖的方法4.5.1死鎖的概念所謂死鎖是指在一個進程集合中的所有進程都在等待只能由該集合中的其它一個進程才能引發(fā)的事件而無限期地僵持下去的局面。陷入僵持狀態(tài)的死鎖進程所占用的資源或者需要與它們進行某種合作的其它進程就會相繼陷入死鎖，最終可能導(dǎo)致整個系統(tǒng)處于癱瘓狀態(tài)。死鎖是進程并發(fā)執(zhí)行帶來的一個嚴重問題，是操作系統(tǒng)乃至并發(fā)程序設(shè)計中需要小心處理的難題。4.5.2死鎖產(chǎn)生的原因和必要條件死鎖產(chǎn)生的原因可以總結(jié)為如下兩點：（1）競爭資源當(dāng)系統(tǒng)中多個進程共享資源如打印機、公共隊列等，其數(shù)目不足以同時滿足各進程的需要時，會引起各進程對資源的競爭而產(chǎn)生死鎖。（2）各進程之間的推進順序不當(dāng)進程在運行過程中，請求和釋放資源的順序不當(dāng)，也可能會導(dǎo)致產(chǎn)生進程死鎖。4.5.3死鎖的描述—資源分配圖死鎖問題可以用系統(tǒng)資源分配圖精確地描述。系統(tǒng)資源分配圖是一個有向圖，它由一個節(jié)點集合V和一個邊集合E組成。節(jié)點集合V中包含兩種類型的節(jié)點子集，一個子集P由系統(tǒng)中所有的活動進程組成；另一個子集R由系統(tǒng)中的所有類別的資源組成。

如果資源分配圖中沒有環(huán)路，那么系統(tǒng)就不會陷入死鎖狀態(tài)。如果存在環(huán)路，那么系統(tǒng)就有可能出現(xiàn)死鎖，但不一定。在處理死鎖問題時，這一點很重要。4.5.4處理死鎖的方法處理死鎖的三種方法：(1)預(yù)防死鎖：這是最為簡單和直觀的一種方法，它采用事先預(yù)防策略，為系統(tǒng)和進程設(shè)置某些限定條件，從根本上破除產(chǎn)生死鎖的四個必要條件中的一個或多個，以達到預(yù)防效果。重要數(shù)據(jù)可放在受到嚴密保護的服務(wù)器所在的局域網(wǎng)內(nèi)，便于集中管理，以保證數(shù)據(jù)安全。(2)避免死鎖：該方法也屬于事先預(yù)防策略，但它無需在系統(tǒng)中設(shè)定嚴格的限定條件，而是允許系統(tǒng)運行，但在為進程分配資源之前，先采用特殊算法檢查并防止系統(tǒng)進入不安全狀態(tài)，從而避免死鎖產(chǎn)生。(3)檢測和解除死鎖：該方法事先不采取任何限定措施，在分配資源時也不檢查是否會導(dǎo)致系統(tǒng)不安全，它允許系統(tǒng)產(chǎn)生死鎖，但需要在系統(tǒng)中設(shè)置特定的檢測機構(gòu)，及時檢測出死鎖的發(fā)生，并精確地確定與死鎖有關(guān)的進程和資源，以便及時采取措施將死鎖狀態(tài)解除。4.6死鎖的預(yù)防和避免死鎖的預(yù)防擯棄“請求和保持條件”摒棄“不剝奪條件”摒棄“環(huán)路等待條件”死鎖的避免系統(tǒng)的安全狀態(tài)與不安全狀態(tài)銀行家算法銀行家算法實例4.6.1死鎖的預(yù)防死鎖的預(yù)防是在系統(tǒng)運行之前就采取措施，即在系統(tǒng)設(shè)計時確定資源分配算法，通過破除死鎖產(chǎn)生的四個必要條件中的一個或幾個的方法來消除發(fā)生死鎖的任何可能性。這種方法雖然比較保守、資源利用率低，但因簡單明了并且安全可靠，仍被廣泛采用。4.6.1死鎖的預(yù)防摒棄“請求和保持條件”為摒棄請求和保持條件，系統(tǒng)中需要使用靜態(tài)資源分配法，該方法規(guī)定每一個進程在開始運行前都必須一次性地申請其在整個運行過程中所需的全部資源。若系統(tǒng)有足夠的資源，就把進程需要的全部資源一次性地分配給它；若不能全部滿足進程的資源請求，則一個資源也不分給它，即使有部分資源處于空閑狀態(tài)也不分配給該進程。4.6.1死鎖的預(yù)防摒棄“不剝奪條件”進程在需要資源時才提出請求，并且進程是逐個地申請所需資源，如果一個進程已經(jīng)擁有了部分資源，然后又申請另一個資源而不可得時，其現(xiàn)有資源必須全部釋放。在這種方法中，進程只能在獲得其原有資源和所申請的新資源時才能繼續(xù)執(zhí)行。這種策略缺點是需要反復(fù)地申請和釋放資源，延緩了進程推進速度，延長了進程的周轉(zhuǎn)時間，同時增加了系統(tǒng)開銷，降低了系統(tǒng)的吞吐量。4.6.1死鎖的預(yù)防摒棄“環(huán)路等待條件”為確保環(huán)路等待條件不成立，可以在系統(tǒng)中實行資源有序分配策略，即系統(tǒng)中的所有資源按類型被賦予一個唯一的編號，每個進程只能按編號的升序申請資源。即對同一個進程而言，它一旦申請了一個編號為i的資源，就不允許再申請編號比i小的資源了。這種策略成功破除了環(huán)路等待條件，具有安全有效的優(yōu)點，且其資源利用率和系統(tǒng)吞吐量都要優(yōu)于前兩種策略。但是其實現(xiàn)較困難，因為難以給出合適的資源編號，使其能符合所有進程對資源使用的內(nèi)在順序要求，同時該方法還不便于系統(tǒng)增添新設(shè)備，不便于用戶編程，對于部分需要大量不同類型資源的進程而言，資源浪費現(xiàn)象仍然是存在的。4.6.2死鎖的避免死鎖的避免方法所設(shè)置的限定條件比較弱，可以使進程在寬松的環(huán)境中獲得更好的系統(tǒng)性能。系統(tǒng)在運行過程中采取動態(tài)的資源分配策略，保證系統(tǒng)不進入可能導(dǎo)致系統(tǒng)陷入死鎖的所謂不安全狀態(tài)，以達到避免死鎖發(fā)生的目的。4.6.2死鎖的避免系統(tǒng)的安全狀態(tài)與不安全狀態(tài)若在某一時刻，系統(tǒng)能按照某種進程順序來為每個進程Pi分配其所需的資源，直至滿足每個進程對各類資源的最大需求，使得每個進程均可順利完成，則稱此時的系統(tǒng)狀態(tài)為安全狀態(tài)。這種保障安全狀態(tài)出現(xiàn)的進程推進序列(P1，P2，…，Pn)則稱為安全序列。若在指定時刻，系統(tǒng)中找不到這樣的進程順序，那么就說該時刻的系統(tǒng)處于不安全狀態(tài)。4.6.2

死鎖的避免系統(tǒng)的安全狀態(tài)與不安全狀態(tài)示例eg：某系統(tǒng)有3個進程P1、P2、P3，共有12臺外部存儲設(shè)備。進程P1總共需要使用10臺存儲設(shè)備，P2和P3分別要求4臺和9臺。設(shè)在T0時刻，進程P1、P2和P3分別已經(jīng)獲得5臺、2臺和2臺，還有3臺空閑沒有分配，如下表所示進程最大需求量已分配資源量仍需申請的資源量系統(tǒng)當(dāng)前空閑資源量P110553P2422P39274.6.2

死鎖的避免在T0時刻，系統(tǒng)處于安全狀態(tài)。此時可以找到一個安全序列(P2，P1，P3)，只要系統(tǒng)按照該順序為各進程分配資源，系統(tǒng)中就總有一個進程能正確執(zhí)行直至完成任務(wù)后終止。在這個例子中，系統(tǒng)當(dāng)前空閑資源數(shù)量為3，按照安全序列要求，系統(tǒng)先從空閑資源中選取兩個交給進程P2，此時P2獲得了所有必要資源，可以順利執(zhí)行并終止。P2終止后釋放出其所占用的全部4臺存儲器，此時系統(tǒng)中的空閑資源數(shù)量變?yōu)?臺。系統(tǒng)接下來查看安全序列，下一個可以獲得資源的進程為P1，此時系統(tǒng)中所有的5臺存儲器都交給進程P1。P1完成后立即釋放所占用的全部10臺存儲器，系統(tǒng)再從中選取7臺交給進程P3，使其能夠順利完成。4.6.2

死鎖的避免只要系統(tǒng)在分配資源時按照安全序列來響應(yīng)進程申請，就可以保證所有進程都能正常結(jié)束。但若不按照安全序列進行資源分配，系統(tǒng)很有可能進入不安全狀態(tài)，甚至產(chǎn)生死鎖。eg：在進程P2完成后，系統(tǒng)沒有按照安全序列要求將所有5臺空閑資源交給P1，而是將其全部給了P3，那么P1和P3都將因為資源不足而阻塞，即此時P1和P3成為死鎖進程。4.6.2

死鎖的避免系統(tǒng)的安全狀態(tài)與不安全狀態(tài)安全狀態(tài)不是死鎖狀態(tài)，死鎖狀態(tài)卻是不安全狀態(tài)，但是并非所有不安全狀態(tài)都表示系統(tǒng)死鎖。安全狀態(tài)是非死鎖狀態(tài)，而不安全狀態(tài)并不一定是死鎖狀態(tài)，因此系統(tǒng)處于安全狀態(tài)一定可以避免死鎖，而系統(tǒng)處于不安全狀態(tài)則僅僅是可能進入死鎖狀態(tài)。安全、不安全和死鎖狀態(tài)的關(guān)系4.6.2

死鎖的避免系統(tǒng)的安全狀態(tài)與不安全狀態(tài)如果某時刻一個進程的資源申請是可以滿足的，但為其分配了資源后會導(dǎo)致系統(tǒng)進入不安全狀態(tài)，則為了避免死鎖，該進程必須等待，此時資源利用率會下降。系統(tǒng)在某時刻的安全序列可能有多個，但這不影響對系統(tǒng)安全性的判斷，只要有一個安全序列存在，就可以稱該時刻處于安全狀態(tài)。4.6.2

死鎖的避免銀行家算法的提出銀行家算法(Banker`sAlgorithm)是最有代表性的死鎖避免策略，該策略是根據(jù)在銀行系統(tǒng)所采用的借貸策略建立的模型，由Dijkstra于1965年提出。

4.6.2

死鎖的避免銀行家算法描述該模型描述了銀行和借貸客戶之間的互動情況。一個銀行只有有限數(shù)目的資金—資源，可貸給不同的貸款人—進程，為了滿足貸款人的請求，銀行可能對客戶設(shè)置信用底線，該底線就是所謂的貸款限額，即各客戶可以貸出的最高數(shù)額。在此模型中，有一個很重要的默認設(shè)定，即若一個客戶所貸金額達到貸款限額后，再申請新的資源時，必須先將以前所欠款項歸還銀行后才可以得到新的資金。銀行家算法模型中是不存在剝奪的。4.6.2

死鎖的避免在銀行家算法模型中，銀行總資金額就相當(dāng)于操作系統(tǒng)中的空閑資源總量；客戶相當(dāng)于進程，每個進程對資源都有一個最高要求，滿足該要求后，進程才能順利運行。4.6.2

死鎖的避免銀行家算法的實質(zhì)要設(shè)法保證系統(tǒng)動態(tài)分配資源后不會進入不安全狀態(tài)，以避免可能發(fā)生的死鎖。每當(dāng)進程提出資源請求且系統(tǒng)的資源能夠滿足該請求時，系統(tǒng)嘗試著滿足此次資源請求，然后檢查分配后系統(tǒng)狀態(tài)是否還處于安全狀態(tài)。若處于安全狀態(tài)，才真正為該進程分配資源，否則不分配資源，申請資源的進程將阻塞，直到其他進程釋放出足夠的資源為止。銀行家算法執(zhí)行的前提條件：進程必須預(yù)先提出自己的最大資源請求數(shù)量，這一數(shù)量不能超過系統(tǒng)資源的總量。4.6.2

死鎖的避免銀行家算法中的數(shù)據(jù)結(jié)構(gòu)可用資源向量Available：一個含有m個元素的數(shù)組，其中的每個元素的值表示一類可用資源的數(shù)目，其初值為系統(tǒng)中此類資源的總數(shù)量，且該值將隨著此資源的分配和回收動態(tài)變化。如果Available[j]=k，表示系統(tǒng)中現(xiàn)有Rj類資源k個。最大需求矩陣Max：這是一個n×m的矩陣，用來定義系統(tǒng)中n個進程對m類資源的最大需求量。如果Max[i,j]=k，則表示進程Pi需要Rj類資源k個。已分配資源矩陣Allocation：這也是一個n×m的矩陣，用來定義每個進程現(xiàn)在所獲得的各類資源的數(shù)量。如果Allocation[i,j]=k，則表示進程Pi當(dāng)前分配到k個Rj類資源。需求矩陣Need：這也是一個n×m的矩陣，用來表示每個進程還需要的各類資源的數(shù)目。如果Need[i,j]=k，則表示進程Pi尚需k個Rj類資源才能完成其任務(wù)。

矩陣Need[i,j]、Max[i,j]、Allocation[i,j]存在如下關(guān)系Need[i,j]=Max[i,j]-Allocation[i,j]4.6.2

死鎖的避免銀行家算法

設(shè)Requesti是進程Pi的請求向量，若Requesti[j]=K，表示進程Pi需要K個Rj類資源。當(dāng)Pi發(fā)出資源請求后，系統(tǒng)將按下列步驟進行檢查：1)若Requesti[j]≤Need[i,j]，繼續(xù)執(zhí)行步驟2)，否則表示進程Pi所申請的資源數(shù)量已超出其可獲取的最大限額而無法滿足，因此要拒絕申請并阻塞進程。2)若Requesti[j]≤Available[j]，繼續(xù)執(zhí)行步驟3)，否則表示系統(tǒng)中沒有足夠資源，Pi被阻塞。3)系統(tǒng)嘗試著把指定類型、指定數(shù)量的資源交給進程Pi，并對上述數(shù)據(jù)結(jié)構(gòu)的值做如下修改： Available[j]=Availabe[j]-Requesti[j]； Allocation[i,j]=Allocation[i,j]+Requesti[j]； Need[i,j]=Need[i,j]-Requesti[j]；4)執(zhí)行安全性算法，檢查完成此次分配后，系統(tǒng)是否仍處于安全狀態(tài)。若安全，才正式將資源分配給進程Pi，否則本次嘗試失敗，將各數(shù)據(jù)結(jié)構(gòu)恢復(fù)為嘗試分配前的狀態(tài)，最后阻塞進程Pi。4.6.2

死鎖的避免安全性算法

1）設(shè)置兩個向量Work和Finish。工作向量Work表示系統(tǒng)可提供給進程繼續(xù)運行所需的各類資源數(shù)目，它含有m個元素，初始化為Work[i]=Available[i]，i=1,2,…,m。結(jié)束向量Finish表示系統(tǒng)中是否有足夠的資源分配給進程，初始化為Finish[i]=false，i=1,2,…,n。在分配過程中，若有足夠資源分配給進程Pi時，令Finish[i]=true。2)在進程集合中搜索滿足下列條件的進程： Finish[i]=false，且Need[i,j]≤Work[j]。 若找到就繼續(xù)執(zhí)行下一個步驟，否則轉(zhuǎn)向步驟4)。3)進程Pi獲得資源后，可以順利執(zhí)行，直至完成，并釋放出分配給它的所有資源，因此應(yīng)將各數(shù)據(jù)結(jié)構(gòu)修改如下： Work[j]=Work[j]+Allocation[i,j]；Finish[i]=true 修改后轉(zhuǎn)向步驟2)。4)若所有進程Finish[i]=true都成立，即此時所有進程都可以順利完成，系統(tǒng)處于安全狀態(tài)；否則，系統(tǒng)處于不安全狀態(tài)。

4.6.2

死鎖的避免銀行家算法實例

假設(shè)系統(tǒng)中有5個進程{P1、P2、P3、P4、P5}和4種類型的資源{R1，R2，R3、R4}，資源的數(shù)量分別為8、5、9、7，在T0時刻的資源分配情況如下表所示資源進程AllocationR1R2R3R4MaxR1R2R3R4NeedR1R2R3R4AvailableR1R2R3R4P12011321412031222P2012102520131P3400351051102P4021015301320P51030303320034.6.2

死鎖的避免銀行家算法實例（續(xù)）T0時刻是安全的。因為在T0時刻存在一個安全序列{P3,P1,P2,P4,P5}，如下表所示資源進程WorkR1R2R3R4NeedR1R2R3R4AllocationR1R2R3R4Work+AllocationR1R2R3R4FinishP31222110240035225trueP15225120320117236trueP27236013101217357trueP47357132002107567trueP57567200310308597true4.6.2

死鎖的避免銀行家算法實例（續(xù)）T1時刻，進程P3提出資源請求Request3(1,0,0,1)，系統(tǒng)按銀行家算法進行檢查： ①Request3(1,0,0,1)≦Need3(1,1,0,2) ②Request1(1,0,0,1)≦Available(1,2,2,2) ③假設(shè)滿足進程P3的要求，為其分配所申請的資源，并且修改Available、Allocation3和Need3，得到如下表所示的資源分配表。

資源進程AllocationR1R2R3R4MaxR1R2R3R4NeedR1R2R3R4AvailableR1R2R3R4P12011321412030221P2012102520131P3500451050101P4021015301320P51030303320034.6.2

死鎖的避免銀行家算法實例（續(xù)）④利用安全性檢查算法，檢查此時的系統(tǒng)是否安全。得到如下表所示的安全序列，因此系統(tǒng)是安全的，此次P3要求的資源可以真正分配給它使用。

資源進程WorkR1R2R3R4NeedR1R2R3R4AllocationR1R2R3R4Work+AllocationR1R2R3R4FinishP30221010150045225trueP15225120320117236trueP27236013101217357trueP57357200310308387trueP48387132002108597true4.6.2

死鎖的避免銀行家算法實例（續(xù)）完成上述資源分配后，若在其后的T2時刻，進程P1提出資源申請Request1(1，2，0，1)，系統(tǒng)仍要使用銀行家算法進行檢查，從T1時刻的資源分配表可以看出，可用資源Request1(1，2，0，1)＞Available(0,2,2,1)，即系統(tǒng)不能滿足進程P1的申請，因此要阻塞P1。4.7死鎖的檢測和解除死鎖的檢測和恢復(fù)技術(shù)