第二、三章 進程、死鎖

第三章進程進程的同步和互斥并發(fā)性一個進程的順序性是指每個進程在順序處理器上的執(zhí)行是嚴(yán)格按序的，即只有當(dāng)一個操作結(jié)束后，才能開始后續(xù)操作。一組進程的并發(fā)性是指進程的執(zhí)行在時間上是重疊的，把這些可交叉執(zhí)行的進程稱為并發(fā)進程所謂進程的執(zhí)行在時間上是重疊的，是指一個進程的第一個操作是在另一個進程的最后一個操作完成之前開始。例：有兩個進程A和B，他們分別執(zhí)行操作a1，a2，a3和b1，b2，b3。在一個單處理器上，進程A和B的執(zhí)行順序分別為a1，a2，a3和b1，b2，b3，這是進程的順序性。如果這兩個進程在單處理器上交叉執(zhí)行，如執(zhí)行序列為a1，b1，a2，b2，a3，b3或a1，b1，a2，b2，b3，a3等，則說進程A和進程B是并發(fā)的。并發(fā)的進程可能是無關(guān)的，也可能是交往的。無關(guān)的并發(fā)進程是指他們分別在不同的變量集合上操作，所以一個進程的執(zhí)行與其他并發(fā)進程的進展無關(guān)，即一個并發(fā)進程不會改變另一個并發(fā)進程的變量值。交往的并發(fā)進程，它們共享某些變量，所以一個進程的執(zhí)行可能影響其他進程的結(jié)果，因此，這種交往必須是有控制的，否則會出現(xiàn)不正確的結(jié)果。兩個交往的并發(fā)進程，其中一個進程對另一個進程的影響常常是不可預(yù)期的，甚至無法再現(xiàn)。因為兩個并發(fā)進程執(zhí)行的相對速度無法相互控制，交往進程的速度不僅受到處理器調(diào)度的響應(yīng)，而且還受到與這兩個交往的并發(fā)進程無關(guān)的其他進程的影響，所以一個進程的速度通常無法為另一個進程所知。與時間有關(guān)的錯誤例假設(shè)一個飛機訂票系統(tǒng)有兩個終端，分別運行進程T1和T2。該系統(tǒng)的公共數(shù)據(jù)區(qū)中的一些單元Aj（j=1,2…）分別存放某月某日某次航班的余票數(shù)，而x1和x2表示進程T1和T2執(zhí)行時所用的工作單元。procedureT1(x1)begin

按旅客訂票要求找到Ajx1:=Aj;ifx1>=1thenbeginx1:=x1-1;Aj:=x1;procedureT2(x2)begin

按旅游訂票要求找到Ajx2:=Aj;ifx2>=1thenbegin

輸出一張票

endelse輸出“票售完”

end;x2:=x2-1;Aj:=x2;

輸出一張票

endelse輸出“票售完”

end;進程的定義cobeginrepeatT1(x1)repeatT2(x2)Coend進程的執(zhí)行t1t2t3t4t5t6t7T1x1:=Ajx1:=x1-1Aj:=x1輸出一張票T2x2:=Ajx2:=x2-1Aj:=x2輸出一張票t1t2t3t4t5t6t7T1x1:=Ajx1:=x1-1Aj:=x1輸出一張票T2x2:=Ajx2:=x2-1Aj:=x2輸出一張票按照第一個表的序列執(zhí)行時，即使兩個終端的旅客都要求購買同天同次航班的機票，其結(jié)構(gòu)是正確的。但如果按照第二個表的順序執(zhí)行，則兩個旅客可能各自都買到同一張同天同次航班的機票，可Aj的值實際上只減去了1，造成余票數(shù)的不正確。特別是，余票只有一張時，就可能一張票賣給了兩個旅客。例假設(shè)有兩個并發(fā)進程borrow和return分別負(fù)責(zé)申請和歸還主存資源。x表示現(xiàn)有的空閑主存量，B表示申請或歸還的主存量。cobegin

repeatborrow(...B,x,...)

repeatreturn(...B,x,...)

coend

procedureborrow(...B,x,...)

varB,x:integer;

begin

ifB>xthen{等待主存資源}

x:=x-B;

{修改主存分配表}

end;

procedurereturn(...B,x,...)

varB,x:integer;

begin

x:=x+B;

{釋放等待主存資源者}

{修改主存分配表}

end;若進程borrow在執(zhí)行了比較B和x指令后，發(fā)現(xiàn)B〉x，但在執(zhí)行{等待主存資源}前，進程return執(zhí)行，歸還了全部主存。這時，由于進程borrow還未成為等待狀態(tài)，因此，進程return中的{釋放等待主存資源者}相當(dāng)于空操作。以后當(dāng)borrow被置成等待主存資源狀態(tài)時，可能已經(jīng)沒有進程來歸還主存資源了，從而borrow可能永遠(yuǎn)等待下去。進程互斥售票管理系統(tǒng)之所以會產(chǎn)生錯誤，原因在于兩個進程交叉訪問了共享變量Aj。并發(fā)進程中與共享變量有關(guān)的程序段稱為“臨界區(qū)”。進程T1的臨界區(qū)進程T2的臨界區(qū)procedureT1(x1)begin

按旅客訂票要求找到Aj

x1:=Aj;ifx1>=1thenbeginx1:=x1-1;Aj:=x1;procedureT2(x2)begin

按旅游訂票要求找到Aj

x2:=Aj;ifx2>=1thenbegin

輸出一張票

endelse輸出“票售完”

end;

x2:=x2-1;Aj:=x2;

輸出一張票

endelse輸出“票售完”

end;進程的定義cobeginrepeatT1(x1)repeatT2(x2)Coend進程的執(zhí)行臨界區(qū)訪問結(jié)構(gòu)入口區(qū)臨界區(qū)退出區(qū)進入準(zhǔn)則一次僅允許一個進程進入任何時候，處于臨界區(qū)的進程不可多于一個限時退出不能進入，則讓出cpu互斥實現(xiàn)硬件禁止中斷用戶進程權(quán)利過大多處理機無效專用機器指令TestandSetLock,TSL忙式等待操作系統(tǒng)級原語用戶級Dekker算法1-5，Peterson算法，置鎖算法（例），嚴(yán)格“輪流坐莊”法等不能完全解決多進程互斥，過于復(fù)雜，應(yīng)用困難置鎖變量法為每個臨界區(qū)設(shè)置一把鎖，開和閉兩個狀態(tài)。關(guān)鎖，lock(W)執(zhí)行臨界區(qū)開鎖,unlock(W)問題：忙等信號量E.W.Dijkstra,1965.THE操作系統(tǒng)P、V操作整形信號量P、V操作—整型信號量P(s){ while(s<=0) ;//不執(zhí)行任何操作

s--;}P操作V(s){ s++;}V操作mutex=1do{ P(mutex);

臨界區(qū)

V(mutex);

其他代碼區(qū)}while(1);信號量P、V操作整形信號量忙等，單CPU的多道程序系統(tǒng)中結(jié)構(gòu)型信號量P、V操作—結(jié)構(gòu)型信號量typedefstruct{ intvalue; structPCB*list;};semaphore;Remarks:sispre-defineddatatype,semaphorecanbedeclaredasneeded,eg.vars1,s2:semaphore;信號燈變量S.valueS.listS.valueS.listPCBPCBPCBSemaphores;FIFO信號量可以賦初值，且初值為非負(fù)信號量的值可以修改，但只能由P和V操作來訪問P操作定義voidP(semaphoreS){ S.value--; if(S.value<0){

把這個進程加到S.list對列；

block(); }}V操作定義voidV(semaphoreS){ S.value++; if(S.value<0){

從S.list對列中移走進程Q；

wakeup(Q); }}信號量P、V操作整形信號量忙等，單CPU的多道程序系統(tǒng)中結(jié)構(gòu)型信號量二值信號量結(jié)構(gòu)型信號量的特例依賴底層硬件體系結(jié)構(gòu)，0、1P、V操作—二值信號量typedefstruct{ enum{false,true}value;//枚舉量

structPCB*list;}B_semaphore;定義voidP_B(B_sempaphoreS){ if(S.value==true) S.value=false; else{

把該進程放入S.list對列；

block(); }}P操作voidV_B(B_semaphoreS){ if(S.list==NULL) S.value=true; else{

從S.list對列中移走進程Q；

wakeup(Q); }}V操作實現(xiàn)B_semaphoreS1,S2;intc;//c為信號量S1.value=true;S2.value=false;P_B(S1);c--;if(c<0){ V_B(S1); P_B(S2);}elseV_B(S1);信號量上的P操作P_B(S1);c++;if(c<=0) V_B(S2);elseV_B(S1)信號量上的V操作應(yīng)用1—用信號量實現(xiàn)進程互斥對打印機的互斥使用使用、空閑信號量mutex用于互斥，初值為1P（mutex）、V(mutex)成對出現(xiàn)，先P，臨界區(qū)，后V……P（mutex）分配打印機V(mutex)……應(yīng)用2—用信號量實現(xiàn)進程同步供者和用者對緩沖區(qū)的使用供者：空、不空；用者：滿、不滿

Buffer供者用者供者進程L1:P(S1)

啟動讀卡機

……

收到輸入結(jié)果

V(S2);gotoL1;用者進程L2:……

P(S2)

從緩沖區(qū)取出信息

V(S1);

加工并且存盤

gotoL2;同步注意事項分析進程的制約關(guān)系，確定信號量種類信號量的初值與相應(yīng)資源的數(shù)量有關(guān)，也與P，V操作的在程序代碼中出現(xiàn)的位置有關(guān)同一信號量的P，V操作要“成對”出現(xiàn)，但可分別出現(xiàn)在不同進程代碼中。利用信號量機制解經(jīng)典進程同步問題

經(jīng)典進程同步問題是從進程并發(fā)執(zhí)行中歸納的典型例子，這些問題常用來測試新的進程同步機制可行性。主要的經(jīng)典同步問題有生產(chǎn)者-消費者問題、讀者-寫者問題、哲學(xué)家進餐問題等。（1）生產(chǎn)者-消費者問題（producer-consumerProblem）生產(chǎn)者-消費者問題是最著名的同步問題，它描述一組生產(chǎn)者（P1

……Pm）向一組消費者（C1……Cq）提供消息。它們共享一個有界緩沖池（boundedbufferpool）,生產(chǎn)者向其中投放消息，消費者從中取得消息，如下圖所示。生產(chǎn)者-消費者問題是許多相互合作進程的一種抽象。利用信號量機制解經(jīng)典進程同步問題-1

假定緩沖池中有n個緩沖區(qū)，每個緩沖區(qū)存放一個消息。由于緩沖池是臨界資源，它只允許一個生產(chǎn)者投入消息，或者一個消費者從中取出消息。即生產(chǎn)者之間、生產(chǎn)者與消費者之間、消費者之間都必須互斥使用緩沖池。所以必須設(shè)置互斥信號量mutex，它代表緩沖池資源，它的數(shù)值為1。P1PmC1CqB0B1….…...………Bn-1

利用信號量機制解經(jīng)典進程同步問題-2

與計算打印兩進程同步關(guān)系相同，生產(chǎn)者和消費者二類進程P和C之間應(yīng)滿足下列二個同步條件：只有在緩沖池中至少有一個緩沖區(qū)已存入消息后，消費者才能從中提取消息，否則消費者必須等待。只有緩沖池中至少有一個緩沖區(qū)是空時，生產(chǎn)者才能把消息放入緩沖區(qū)，否則生產(chǎn)者必須等待。為了滿足第一個同步條件，設(shè)置一個同步信號量full，它代表的資源是緩沖區(qū)滿，它的初始值為0，它的值為n時整個緩沖池滿。這個資源是消費者類進程C所擁有，C進程可以申請該資源，對它施加P操作，而C進程的合作進程生產(chǎn)者進程P對它施加V操作。同樣為了滿足第二個同步條件，設(shè)置另一個同步信號量empty，它代表的資源是緩沖區(qū)空，它的初始值為n，表示緩沖池中所有緩沖區(qū)空。用類并行語言和信號量機制解生產(chǎn)者-消費者問題程序：利用信號量機制解生產(chǎn)者-消費者互斥問題生產(chǎn)者進程Producer：while(TRUE){ P(empty);/*使用一個可用緩沖區(qū)

P(mutex);/*互斥進入臨界區(qū) 產(chǎn)品送往buffer(in); in=(in+1)modN;/*以N為模*/V(mutex);/*退出臨界區(qū)

V(full);/*多出一個放有產(chǎn)品的 }緩沖區(qū) 消費者進程Consumer：while(TRUE){P(full);/*使用一個放產(chǎn)品的緩沖區(qū)

P(mutex);/*互斥進入臨界區(qū)從buffer(out)中取出產(chǎn)品；

out=(out+1)modN;/*以N為模*/V(mutex);/*退出臨界區(qū)

V(empty);/*多出一個空的}緩沖區(qū)(2)哲學(xué)家就餐問題Dining-PhilosophersProblemShareddatasemaphorechopstick[5];

ThestructureofPhilosophersiPhilosopher[i]:while(TURE){

思考問題

P(chopstick[i]);P(chopstick[(i+1)mod5]);

進餐

V(chopstick[i]);V(chopstick[(i+1)mod5];}哲學(xué)家就餐問題-1此解雖然可以保證互斥使用筷子，但有可能發(fā)生死鎖。假如五位哲學(xué)家同時饑餓而各自拿起左邊的筷子時，就會使五個信號量chopstick均為o；當(dāng)他們再試圖去拿右邊的筷子時，都將因無筷子可拿而無限期地等待。為防止死鎖發(fā)生可采取的措施：1.最多允許4個哲學(xué)家同時去拿左邊的筷子，最終能保證至少有一位哲學(xué)家能夠進餐，并在用畢時能釋放出他用過的兩只筷子，從而使更多的哲學(xué)家能夠進餐。哲學(xué)家就餐問題-22.給所有哲學(xué)家編號，奇數(shù)號的哲學(xué)家必須首先拿左邊的筷子，偶數(shù)號的哲學(xué)家則反之，首先拿右邊的筷子。按此規(guī)定，將是0、1號哲學(xué)家競爭1號筷子；2、3號哲學(xué)家競爭3號筷子。即五位哲學(xué)家都先競爭奇數(shù)號筷子，獲得后，再去競爭偶數(shù)號筷子，最后總會有一位哲學(xué)家能獲得兩只筷子而進餐。3.僅當(dāng)一個哲學(xué)家左右兩邊的筷子都可用時，才允許他拿筷子。前二個措施讀者可用P、V編程解，第三個措施要使用AND型信號量集機制。#defineN5#defineLEFT(i-1)%N#defineRIGHT(i+1)%N#defineTHINKING0#defineHUNGRY1#defineEATING2typedefstruct{/*定義結(jié)構(gòu)型信號量*/intvalue;structPCB*list;}semaphore;intstate[N];semaphoremutex=1;/*互斥進入臨界區(qū)*/semaphores[N];/*每位哲學(xué)家一個信號量*/voidphilosopher(inti){while(TRUE){think(); /*哲學(xué)家在思考問題*/take_chopstick(i);/*拿到兩根筷子或者等待*/eat(); /*進餐*/put_chopstick(i);/*把筷子放回原處*/}}voidtake_chopstick(inti){P(mutex);state[i]=HUNGRY;test(i);/*試圖拿兩根筷子*/V(mutex);P(s[i]);}voidput_chopstick(inti){P(mutex);state[i]=THINKING;test(LEFT);//看左鄰,現(xiàn)在能否進餐

test(RIGHT);//看右鄰,現(xiàn)在能否進餐

V(mutex);}voidtest(inti){if(state[i]==HUNGRY&&state[LEFT]!=EATING&&state[RIGHT]!=EATING){state[i]=EATING;V(s[i]);}}（3）讀者-寫者問題（Readers/WritersProblem）

一個數(shù)據(jù)集（如文件）如果被幾個并行進程所共享，有些進程只要求讀數(shù)據(jù)集內(nèi)容，它稱讀者，而另一些進程則要求修改數(shù)據(jù)集內(nèi)容，它稱寫者，幾個讀者可以同時讀些數(shù)據(jù)集，而不需要互斥，但一個寫者不能和其它進程（不管是寫者或讀者）同時訪問些數(shù)據(jù)集，它們之間必須互斥，這是讀者-寫者問題。這里讀者和寫者之間的互斥是指一群先后讀的讀者作為一個整體和寫者間要互斥，讀者群的第一個讀者到時就要禁止任何一個寫者寫，讀者群最后一個讀者離開后能允許一個寫者寫。

設(shè)置兩個信號量：讀互斥信號量rmutex和寫互斥信號量wmutex。另外設(shè)立一個讀計數(shù)器readcount，它是一個整型變量，初值為0。rmutex：用于讀者互斥地訪問readcount，初值為1。wmutex：用于保證一個寫者與其他讀者/寫者互斥地訪問共享資源，初值為1。讀者-寫者問題-1讀者Readers:while(TRUE){P(rmutex);readcount=readcount+1;if(readcount==1)P(wmutex);V(rmutex);

執(zhí)行讀操作

P(rmutex);readcount=readcount-1;if(readcount==0)V(wmutex);V(rmutex);

使用讀取的數(shù)據(jù)

}寫者Writers：while(TRUE){P(wmutex);

執(zhí)行寫操作

V(wmutex);}（4）進程同步的分析

用信號量機制解決進程同步問題需在程序中正確設(shè)置信號量和在適當(dāng)位置安排P、V操作。例如生產(chǎn)者-消費者問題中，用于互斥進入臨界區(qū)的P（mutex）、V(mutex)語句需緊靠著臨界區(qū)前和后，而生產(chǎn)者用于同步的P（empty）和V（full）(消費者為P（full）和V(empty))語句相對臨界區(qū)就在外面一層，格式如上程序所述。如在以上問題中生產(chǎn)者的P（empty）和P(mutex)先后位置對調(diào)，相應(yīng)消費者的P（full）和P（mutex）先后位置也對調(diào)，則生產(chǎn)者和消費者在并發(fā)執(zhí)行時，在某個執(zhí)行序列會出現(xiàn)問題。下面介紹如何尋找會發(fā)生問題的那個執(zhí)行序列，分析方法用下表表示。表左邊是生產(chǎn)者和消費者二進程推進序列，此推進序列需用戶尋找；表中間是該操作執(zhí)行后信號量的變化值，表中信號量有mutex、empty和full；表的右邊是該操作執(zhí)行后引起進程PCB的隊列變化。表中隊列有就緒隊列RL，因分別等待mutex、empty、full信號量而阻塞的隊列QmL、QeL、和QfL。進程同步的分析-1在表中已找到一個推進序列。該序列先執(zhí)行消費者進程，由于消費者進程交換了P操作，消費者進程在先后執(zhí)行P（muyex）和P（full）后阻塞在等待full信號量的隊列中。這時只能執(zhí)行生產(chǎn)者進程，由于生產(chǎn)者進程也交換了P操作，在生產(chǎn)者進程執(zhí)行了P（mutex）操作后，生產(chǎn)者進程阻塞在等待mutex信號量的隊列中。這樣生產(chǎn)者和消費者兩進程分別阻塞在等待mutex和full信號量的隊列，沒有進程可以向前推進，系統(tǒng)進入死鎖狀態(tài)。這說明在生產(chǎn)者-消費者問題中對同步信號量和互斥信號量的二個P操作的是不能顛倒，而對互斥信號量和同步信號量的二個V操作的順序交換影響不大。生產(chǎn)者、消費者交換P操作后發(fā)生問題的那個執(zhí)行序列：進程同步的分析-24．打瞌睡的理發(fā)師問題

voidbarber(void){while(TRUE){P(customers);/*如果沒有顧客，則理發(fā)師打瞌睡*/P(mutex);/*互斥進入臨界區(qū)*/waiting--;V(barbers);/*一個理發(fā)師準(zhǔn)備理發(fā)*/V(mutex);/*退出臨界區(qū)*/cut_hair();/*理發(fā)（在臨界區(qū)之外）*/}}4．打瞌睡的理發(fā)師問題

voidcustomer(void){P(mutex); /*互斥進入臨界區(qū)*/if(waiting﹤CHAIRS){waiting++;V(customers); /*若有必要，喚醒理發(fā)師*/V(mutex);/*退出臨界區(qū)*/P(barbers); /*如果理發(fā)師正忙著，則顧客打瞌睡*/get_haircut();}elseV(mutex); /*店里人滿了，不等了*/}2.7管程管程概念的定義是：一個管程定義一個數(shù)據(jù)結(jié)構(gòu)和能為并發(fā)進程在其上執(zhí)行的一組操作，這組操作能使進程同步和改變管程中的數(shù)據(jù)。一個管程由管程名稱、局部于管程的共享數(shù)據(jù)的說明、對數(shù)據(jù)進行操作的一組過程和對該共享數(shù)據(jù)賦初值的語句四部分組成。2.7管程2.7管程管程具有以下三個特性：①管程內(nèi)部的局部數(shù)據(jù)變量只能被管程內(nèi)定義的過程所訪問，不能被管程外面聲明的過程直接訪問。②進程要想進入管程，必須調(diào)用管程內(nèi)的某個過程。③一次只能有一個進程在管程內(nèi)執(zhí)行，而其余調(diào)用該管程的進程都被掛起，等待該管程成為可用的。即管程能有效地實現(xiàn)互斥。2.7管程定義兩個條件變量x和y：

conditionx,y;操作wait(x)：掛起等待條件x的調(diào)用進程，釋放相應(yīng)的管程，以便供其他進程使用。操作signal(x)：恢復(fù)執(zhí)行先前因在條件x上執(zhí)行wait而掛起的那個進程。管程的職責(zé)與信號量的職責(zé)不同。2.8進程通信

進程通信是指進程間的信息交換。各進程在執(zhí)行過程中為合作完成一項共同的任務(wù)，需要協(xié)調(diào)步伐，交流信息。前面介紹的進程的互斥和同步機構(gòu)因交換的信息量少，被稱為低級進程通信。高級進程通信方式有很多種，大致可歸并為共享存儲器、消息傳遞和管道文件三類。2.8進程通信1．共享存儲器方式共享存儲器方式是在內(nèi)存中分配一片空間作為共享存儲區(qū)。需要進行通信的各個進程把共享存儲區(qū)附加到自己的地址空間中，然后，就像正常操作一樣對共享區(qū)中的數(shù)據(jù)進行讀或?qū)?。通過對共享存儲區(qū)的訪問，相關(guān)進程間就可以傳輸大量的數(shù)據(jù)。2.8進程通信

2．消息傳遞方式消息傳遞方式以消息（Message）為單位在進程間進行數(shù)據(jù)交換。有兩種實現(xiàn)方式：①直接通信方式：發(fā)送進程直接將消息掛在接收進程的消息緩沖隊列上，接收進程從消息緩沖隊列中得到消息。②間接通信方式：發(fā)送進程將消息送到稱為信箱的中間設(shè)施中，接收進程從信箱中得到消息。2.8進程通信

3．管道文件方式管道文件也稱管道線，它是連接兩個命令的一個打開文件。一個命令向該文件中寫入數(shù)據(jù)，稱做寫者；另一個命令從該文件中讀出數(shù)據(jù)，稱做讀者。

$>who|wc-l$>ls–l|wc-l2.8進程通信

2.8.1消息傳遞系統(tǒng)send和receive的一般格式是：send(destination,message)receive(source,message)2.8.2客戶-服務(wù)器系統(tǒng)中的通信

常用的進程通信方式有socket和遠(yuǎn)程過程調(diào)用。

1．socketsocket好像一條通信線兩端的接插口——

只要通信雙方都有插口，并且中間有通信線路相連，就可以互相通信了。一對進程通過網(wǎng)絡(luò)進行通信要用一對socket，每個進程一個。一個socket在邏輯上有網(wǎng)絡(luò)地址、連接類型和網(wǎng)絡(luò)規(guī)程三個要素。2.8.2客戶-服務(wù)器系統(tǒng)中的通信網(wǎng)絡(luò)地址表明一個socket用于哪種網(wǎng)絡(luò)連接類型表明網(wǎng)絡(luò)通信所遵循的模式，主要分為“有連接”和“無連接”模式。網(wǎng)絡(luò)規(guī)程表明具體網(wǎng)絡(luò)的規(guī)程。一般來說，網(wǎng)絡(luò)地址和連接類型結(jié)合在一起就基本上確定了適用的規(guī)程。2.8.2客戶-服務(wù)器系統(tǒng)中的通信2．遠(yuǎn)程過程調(diào)用遠(yuǎn)程過程調(diào)用（RemoteProcedureCall,RPC）是遠(yuǎn)程服務(wù)的一種最常見的形式。第3章死鎖內(nèi)容提要：3.1資源3.2死鎖概念3.3死鎖的預(yù)防3.4死鎖的避免3.5死鎖的檢測和恢復(fù)3.6處理死鎖的綜合方式3.1資源資源是在任何時刻都只能被一個進程使用的任何對象。3.1.1資源使用模式

1．申請

2．使用

3．釋放3.1.2可剝奪資源與不可剝奪資源1．可剝奪資源其他進程可以從擁有它的進程那里把它剝奪過去為己所用，并且不會產(chǎn)生任何不良影響。例如，內(nèi)存就是可剝奪資源。2．不可剝奪資源不能從當(dāng)前占有它的進程那里強行搶占的資源，必須由擁有者自動釋放，否則會引起相關(guān)計算的失效。3.1.2可剝奪資源與不可剝奪資源死鎖和不可剝奪資源有關(guān)。硬件資源軟件資源可再用資源（SR）：一次僅供一個進程使用，且可由多個進程重復(fù)使用的資源。消耗性資源（CR）：可以被動態(tài)創(chuàng)建和毀壞的資源。3.2死鎖概念3.2.1什么是死鎖1．死鎖示例圖3-1汽車過窄橋時的沖突3.2.1什么是死鎖在計算機系統(tǒng)中，涉及軟件、硬件資源的進程都可能發(fā)生死鎖。生產(chǎn)者進程Producer：消費者進程consumer：

while(TRUE){while(TRUE){P(mutex);P(mutex);P(empty);P(full);

…

…}}3.2.1什么是死鎖2．死鎖定義死鎖是指在多道程序系統(tǒng)中，一組進程中的每一個進程都無限期地等待該組進程中的另一個進程所占有且永遠(yuǎn)不會釋放的資源，這種現(xiàn)象稱系統(tǒng)處于死鎖狀態(tài)，簡稱死鎖。處于死鎖狀態(tài)的進程稱為死鎖進程。計算機系統(tǒng)產(chǎn)生死鎖的根本原因就是資源有限且操作不當(dāng)。一種原因是系統(tǒng)提供的資源太少，另一種原因是進程推進順序不合適。3.2.1什么是死鎖有兩個進程A和B，競爭兩個資源R和S，這兩個資源都是不可剝奪資源。

進程A

進程B

……

……

申請并占用R申請并占用S

申請并占用S申請并占用R

……

……

釋放R釋放S

釋放S釋放R

……

……3.2.1什么是死鎖

圖3-2進程推進順序?qū)σl(fā)死鎖的影響3.2.2死鎖的條件

當(dāng)計算機系統(tǒng)同時具備下面4個必要條件時，會發(fā)生死鎖。1．互斥條件：某個資源在一段時間內(nèi)只能由一個進程占有，不能同時被兩個及以上的進程占有。2．占有且等待條件：進程至少已經(jīng)占有一個資源，但又申請新的資源。3．不可搶占條件：一個進程所占有的資源在用完之前，其他進程不能強行奪走，只能由該進程主動釋放。4．循環(huán)等待條件：存在一個進程循環(huán)等待環(huán)。只要有一個必要條件不滿足，則死鎖就可以排除。3.2.3資源分配圖

1．資源分配圖的構(gòu)成該圖由結(jié)對組成：G=(V,E)。式中，V是頂點的集合，E是邊的集合。頂點集合可分為兩部分：P={p1,p2,…,pn}，它由系統(tǒng)中所有活動進程組成；R={r1,r2,…,rm}，它由系統(tǒng)中全部資源類型組成。有向邊pi

→rj稱為申請邊，而有向邊rj

→pi稱為賦給邊。在資源分配圖中，通常用圓圈表示每個進程，用方框表示每種資源類型，方框中的圓點表示各個資源單位。3.2.3資源分配圖

2．資源分配圖示例（如果圖中有環(huán)路，則有可能存在死鎖）圖3－3資源分配圖示例3.2.3資源分配圖

3．環(huán)路與死鎖①如果每類資源的實體都只有一個，那么圖中出現(xiàn)環(huán)路就說明死鎖了。②如果每類資源的實體不止一個，那么資源分配圖中出現(xiàn)環(huán)路并不表明一定出現(xiàn)死鎖。資源分配圖中存在環(huán)路是死鎖存在的必要條件，但不是充分條件。3.2.3資源分配圖

如果資源分配圖中沒有環(huán)路，那么系統(tǒng)不會陷入死鎖狀態(tài)。如果存在環(huán)路，那么系統(tǒng)有可能出現(xiàn)死鎖，但不確定。

圖3-4有死鎖的資源分配圖圖3-5有環(huán)路但無死鎖的資源分配圖3.2.4處理死鎖的方法

①利用某些協(xié)議預(yù)防或避免死鎖，保證系統(tǒng)不會進入死鎖狀態(tài)。②允許系統(tǒng)進入死鎖狀態(tài)，然后設(shè)法發(fā)現(xiàn)并克服它。③完全忽略這個問題，好像系統(tǒng)中從來也不會出現(xiàn)死鎖。3.3死鎖的預(yù)防

基本思想是限制進程對資源的申請，以保證死鎖不會發(fā)生。3.3.1破壞互斥條件用否定互斥條件的辦法是不能預(yù)防死鎖的，因為某些資源具有不可共享的固有屬性。3.3.2破壞占有且等待條件保證一個進程無論什么時候都可申請它沒有占有的任何資源。一種辦法是預(yù)分資源策略靜態(tài)分配。另一種辦法是“空手”申請資源策略。3.3.3破壞非搶占條件

進程當(dāng)前所占有的全部資源可被搶占。另一種方法是搶占等待者的資源。3.3.4破壞循環(huán)等待條件

1.一種方法是實行資源有序分配策略設(shè)R={r1,r2,…,rm}，表示一組資源定義一對一的函數(shù)F：R→N，式中N是一組自然數(shù)。例如，F(xiàn)（磁帶機）=1，F(xiàn)（磁盤機）=5，F(xiàn)（打印機）=12做如下約定：所有進程對資源的申請嚴(yán)格按照序號遞增的次序進行。2.另一種申請辦法也很簡單：先棄大，再取小。3.4死鎖的避免排除死鎖的動態(tài)策略—死鎖的避免。該方法不限制進程有關(guān)申請資源的命令，而是對每個命令進行檢查，根據(jù)檢查結(jié)果決定是否進行資源分配。若預(yù)測有發(fā)生死鎖的可能性，則加以避免。3.4.1安全狀態(tài)在當(dāng)前分配狀態(tài)下，進程的安全序列{P1,P2,…,Pn}是這樣組成的：若對于每一個進程Pi（1≤i≤n），它需要的附加資源可被系統(tǒng)中當(dāng)前可用資源與所有進程Pj（j＜i）當(dāng)前占有資源之和所滿足，則{P1,P2,…,Pn}為一個安全序列。這時系統(tǒng)處于安全狀態(tài)，不會進入死鎖狀態(tài)。3.4死鎖的避免死鎖是不安全狀態(tài)中的特例

時刻已占有臺數(shù)最大需求臺數(shù)當(dāng)前可用臺數(shù)進程P1進程P2進程P3進程P1進程P2進程P3T03229473T13429471T23029—75T33079—70T43009——7T5900———1T6000———10表3-1安全狀態(tài)示意3.4死鎖的避免

表3-2不安全狀態(tài)示意時刻已占有臺數(shù)最大需求臺數(shù)當(dāng)前可用臺數(shù)進程P1進程P2進程P3進程P1進程P2進程P3T0′3229473T1′4229472T2′4429470T3′4029—743.4死鎖的避免給出安全狀態(tài)的概念，就可以定義避免死鎖或防止進入不安全狀態(tài)的算法。①死鎖狀態(tài)是不安全狀態(tài)。②如果系統(tǒng)處于不安全狀態(tài)，并不意味著它就在死鎖狀態(tài)，而是表示存在導(dǎo)致死鎖的危機。③如果一個進程申請的資源當(dāng)前是可用的，但為了避免死鎖，該進程也可能必須等待。此時資源利用率會下降。3.4.2資源分配圖算法

單體資源類：某類資源只有一個單位。多體資源類：某類資源有多個單位。如果系統(tǒng)中的資源都是單體資源類，就可以利用資源分配圖算法來避免死鎖。除申請邊和賦給邊之外，還要有一種稱為“要求邊”的新邊。要求邊pi

rj表示進程pi能夠申請資源rj，有時用虛線表示。3.4.2資源分配圖算法圖3-6資源分配圖示例

圖3-7處于不安全狀態(tài)的資源分配圖3.4.3銀行家算法

針對多體資源類的情況，最著名的避免死鎖的算法叫做“銀行家算法”（Banker’sAlgorithm）。銀行家算法的設(shè)計思想是：當(dāng)用戶申請一組資源時，系統(tǒng)必須做出判斷；如果把這些資源分出去，系統(tǒng)是否還處于安全狀態(tài)。若是，就可以分出這些資源；否則，該申請暫不予滿足。實現(xiàn)銀行家算法的數(shù)據(jù)結(jié)構(gòu)：

令n表示系統(tǒng)中進程的數(shù)目，m表示資源分類數(shù)。①Available是一個長度為m的向量，它表示每類資源可用的數(shù)量。Available[j]=k，表示rj類資源可用的數(shù)量是k。②Max是一個n×m矩陣，它表示每個進程對資源的最大需求。Max[i,j]=k，表示進程pi至多可申請k個rj類資源單位。③Allocation是一個n×m矩陣，它表示當(dāng)前分給每個進程的資源數(shù)目。Allocation[i,j]=k，表示進程pi當(dāng)前分到k個rj類資源。④Need是一個n×m矩陣，它表示每個進程還缺少多少資源。Need[i,j]=k，表示進程pi尚需k個rj類資源才能完成其任務(wù)?？梢园丫仃嘇llocation和Need中的每一行當(dāng)做一個向量，并分別寫成Allocationi和Needi。Allocationi表示當(dāng)前分給進程pi的資源。1．資源分配算法令Requesti表示進程pi的申請向量。Requesti[j]=k，表示進程pi需要申請k個rj類資源。當(dāng)進程pi申請資源時，就執(zhí)行下列動作：①若Requesti＞Needi，表示出錯，因為進程對資源的申請大于需求量。②如果Requesti＞Available，則pi等待。③假設(shè)系統(tǒng)把申請的資源分給進程pi，則應(yīng)對有關(guān)數(shù)據(jù)結(jié)構(gòu)進行修改：

Available：=Available–RequestiAllocationi：=Allocationi+RequestiNeedi：=Needi

–Requesti④系統(tǒng)執(zhí)行安全性算法，查看此時系統(tǒng)狀態(tài)是否安全。如果是安全的，就實際分配資源，滿足進程pi的此次申請；否則，若新狀態(tài)是不安全的，則pi等待，對所申請資源暫不予分配，并且把資源分配狀態(tài)恢復(fù)成③之前的情況。2．安全性算法①令Work和Finish分別表示長度為m和n的向量，最初，置Work：=Available，F(xiàn)inish[i]：=false，i=1,2,…,n。②搜尋滿足下列條件的i值：

Finish[i]=false，且Needi≤Work。若沒有找到，則轉(zhuǎn)向④。③修改數(shù)據(jù)值：

Work：=Work+Allocationi（pi釋放所占的全部資源）

Finish[i]=true

轉(zhuǎn)向②。④若Finish[i]=true對所有i都成立（任一進程都可能是pi），則系統(tǒng)處于安全狀態(tài)；否則，系統(tǒng)處于不安全狀態(tài)。3．算法應(yīng)用示例假定系統(tǒng)中有4個進程{A,B,C,D}和三類資源R1,R2和R3，各自的數(shù)量分別為9,3和6個單位。

進程AllocationMaxNeedAvailableR1R2R3R1R2R3R1R2R3R1R2R3A100322222112B511613102C211314103D002422420表3-3T0時刻資源分配表資源情況（1）T0時刻是安全的存在一個安全序列{B,A,C,D}

資源情況WorkNeedAllocationWork+AllocationFinishR1R2R3R1R2R3R1R2R3R1R2R3B112102511623trueA623222100723trueC723103211934trueD934420002936true進程表7-4T0時刻的安全序列（2）進程A請求資源進程A發(fā)出請求Request（1,0,1）

資源情況進程MaxAllocationNeedAvailableR1R2R3R1R2R3R1R2R3R1R2R3A322201121011B613511102C314211103011D422002420系統(tǒng)進入不安全的狀態(tài)為了避免發(fā)生死鎖，即使當(dāng)前可用資源能滿足某個進程的申請，也有可能不實施分配，讓該進程阻塞。表3-5為進程A分配資源后的有關(guān)數(shù)據(jù)3.5死鎖的檢測和恢復(fù)

在實際情況下，通過預(yù)防和避免的手段達到排除死鎖的目的是很難的。一般提供死鎖檢測與恢復(fù)的方法。死鎖檢測與恢復(fù)是指系統(tǒng)設(shè)有專門的機構(gòu)，當(dāng)死鎖發(fā)生時，該機構(gòu)能夠檢測到死鎖發(fā)生的位置和原因，且能通過外力破壞死鎖發(fā)生的必要條件，從而使并發(fā)進程從死鎖狀態(tài)中解脫出來。3.5.1對單體資源類的死鎖檢測等待圖。它是從資源分配圖中去掉表示資源類的節(jié)點，且把相應(yīng)邊折疊在一起得到的。當(dāng)且僅當(dāng)?shù)却龍D中有環(huán)路，系統(tǒng)存在死鎖。圖3-8資源分配圖和對應(yīng)的等待圖3.5.2對多體資源類的死鎖檢測

等待圖不適用于多體資源類的資源分配系統(tǒng)。下面介紹檢測算法采用若干隨時間變化的數(shù)據(jù)結(jié)構(gòu)，與銀行家算法中所用的結(jié)構(gòu)相似。①Available是一個長度為m的向量，表示每類資源的可用數(shù)目。②Allocation是一個n×m的矩陣，表示當(dāng)前分給每個進程的每類資源的數(shù)目。③Request是一個n×m的矩陣，表示當(dāng)前每個進程對資源的申請情況。檢測算法只是簡單地調(diào)查尚待完成的各個進程所有可能的分配序列。3.5.2對多體資源類的死鎖檢測

①令Work和Finish分別表示長度為m和n的向量，初始化Work：=Available；對于i=1,2,…,n，如果Allocationi≠0，則Finish