第三章進(jìn)程進(jìn)程的同步和互斥并發(fā)性一個(gè)進(jìn)程的順序性是指每個(gè)進(jìn)程在順序處理器上的執(zhí)行是嚴(yán)格按序的，即只有當(dāng)一個(gè)操作結(jié)束后，才能開(kāi)始后續(xù)操作。一組進(jìn)程的并發(fā)性是指進(jìn)程的執(zhí)行在時(shí)間上是重疊的，把這些可交叉執(zhí)行的進(jìn)程稱為并發(fā)進(jìn)程所謂進(jìn)程的執(zhí)行在時(shí)間上是重疊的，是指一個(gè)進(jìn)程的第一個(gè)操作是在另一個(gè)進(jìn)程的最后一個(gè)操作完成之前開(kāi)始。例：有兩個(gè)進(jìn)程A和B，他們分別執(zhí)行操作a1，a2，a3和b1，b2，b3。在一個(gè)單處理器上，進(jìn)程A和B的執(zhí)行順序分別為a1，a2，a3和b1，b2，b3，這是進(jìn)程的順序性。如果這兩個(gè)進(jìn)程在單處理器上交叉執(zhí)行，如執(zhí)行序列為a1，b1，a2，b2，a3，b3或a1，b1，a2，b2，b3，a3等，則說(shuō)進(jìn)程A和進(jìn)程B是并發(fā)的。并發(fā)的進(jìn)程可能是無(wú)關(guān)的，也可能是交往的。無(wú)關(guān)的并發(fā)進(jìn)程是指他們分別在不同的變量集合上操作，所以一個(gè)進(jìn)程的執(zhí)行與其他并發(fā)進(jìn)程的進(jìn)展無(wú)關(guān)，即一個(gè)并發(fā)進(jìn)程不會(huì)改變另一個(gè)并發(fā)進(jìn)程的變量值。交往的并發(fā)進(jìn)程，它們共享某些變量，所以一個(gè)進(jìn)程的執(zhí)行可能影響其他進(jìn)程的結(jié)果，因此，這種交往必須是有控制的，否則會(huì)出現(xiàn)不正確的結(jié)果。兩個(gè)交往的并發(fā)進(jìn)程，其中一個(gè)進(jìn)程對(duì)另一個(gè)進(jìn)程的影響常常是不可預(yù)期的，甚至無(wú)法再現(xiàn)。因?yàn)閮蓚€(gè)并發(fā)進(jìn)程執(zhí)行的相對(duì)速度無(wú)法相互控制，交往進(jìn)程的速度不僅受到處理器調(diào)度的響應(yīng)，而且還受到與這兩個(gè)交往的并發(fā)進(jìn)程無(wú)關(guān)的其他進(jìn)程的影響，所以一個(gè)進(jìn)程的速度通常無(wú)法為另一個(gè)進(jìn)程所知。與時(shí)間有關(guān)的錯(cuò)誤例假設(shè)一個(gè)飛機(jī)訂票系統(tǒng)有兩個(gè)終端，分別運(yùn)行進(jìn)程T1和T2。該系統(tǒng)的公共數(shù)據(jù)區(qū)中的一些單元Aj（j=1,2…）分別存放某月某日某次航班的余票數(shù)，而x1和x2表示進(jìn)程T1和T2執(zhí)行時(shí)所用的工作單元。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;進(jìn)程的定義cobeginrepeatT1(x1)repeatT2(x2)Coend進(jìn)程的執(zhí)行t1t2t3t4t5t6t7T1x1:=Ajx1:=x1-1Aj:=x1輸出一張票T2x2:=Ajx2:=x2-1Aj:=x2輸出一張票t1t2t3t4t5t6t7T1x1:=Ajx1:=x1-1Aj:=x1輸出一張票T2x2:=Ajx2:=x2-1Aj:=x2輸出一張票按照第一個(gè)表的序列執(zhí)行時(shí)，即使兩個(gè)終端的旅客都要求購(gòu)買同天同次航班的機(jī)票，其結(jié)構(gòu)是正確的。但如果按照第二個(gè)表的順序執(zhí)行，則兩個(gè)旅客可能各自都買到同一張同天同次航班的機(jī)票，可Aj的值實(shí)際上只減去了1，造成余票數(shù)的不正確。特別是，余票只有一張時(shí)，就可能一張票賣給了兩個(gè)旅客。例假設(shè)有兩個(gè)并發(fā)進(jìn)程borrow和return分別負(fù)責(zé)申請(qǐng)和歸還主存資源。x表示現(xiàn)有的空閑主存量，B表示申請(qǐng)或歸還的主存量。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;若進(jìn)程borrow在執(zhí)行了比較B和x指令后，發(fā)現(xiàn)B〉x，但在執(zhí)行{等待主存資源}前，進(jìn)程return執(zhí)行，歸還了全部主存。這時(shí)，由于進(jìn)程borrow還未成為等待狀態(tài)，因此，進(jìn)程return中的{釋放等待主存資源者}相當(dāng)于空操作。以后當(dāng)borrow被置成等待主存資源狀態(tài)時(shí)，可能已經(jīng)沒(méi)有進(jìn)程來(lái)歸還主存資源了，從而borrow可能永遠(yuǎn)等待下去。進(jìn)程互斥售票管理系統(tǒng)之所以會(huì)產(chǎn)生錯(cuò)誤，原因在于兩個(gè)進(jìn)程交叉訪問(wèn)了共享變量Aj。并發(fā)進(jìn)程中與共享變量有關(guān)的程序段稱為“臨界區(qū)”。進(jìn)程T1的臨界區(qū)進(jìn)程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;進(jìn)程的定義cobeginrepeatT1(x1)repeatT2(x2)Coend進(jìn)程的執(zhí)行臨界區(qū)訪問(wèn)結(jié)構(gòu)入口區(qū)臨界區(qū)退出區(qū)進(jìn)入準(zhǔn)則一次僅允許一個(gè)進(jìn)程進(jìn)入任何時(shí)候，處于臨界區(qū)的進(jìn)程不可多于一個(gè)限時(shí)退出不能進(jìn)入，則讓出cpu互斥實(shí)現(xiàn)硬件禁止中斷用戶進(jìn)程權(quán)利過(guò)大多處理機(jī)無(wú)效專用機(jī)器指令TestandSetLock,TSL忙式等待操作系統(tǒng)級(jí)原語(yǔ)用戶級(jí)Dekker算法1-5，Peterson算法，置鎖算法（例），嚴(yán)格“輪流坐莊”法等不能完全解決多進(jìn)程互斥，過(guò)于復(fù)雜，應(yīng)用困難置鎖變量法為每個(gè)臨界區(qū)設(shè)置一把鎖，開(kāi)和閉兩個(gè)狀態(tài)。關(guān)鎖，lock(W)執(zhí)行臨界區(qū)開(kāi)鎖,unlock(W)問(wèn)題：忙等信號(hào)量E.W.Dijkstra,1965.THE操作系統(tǒng)P、V操作整形信號(hào)量P、V操作—整型信號(hào)量P(s){ while(s<=0) ;//不執(zhí)行任何操作

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

臨界區(qū)

V(mutex);

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

把這個(gè)進(jìn)程加到S.list對(duì)列；

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

從S.list對(duì)列中移走進(jìn)程Q；

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

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

把該進(jìn)程放入S.list對(duì)列；

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

從S.list對(duì)列中移走進(jìn)程Q；

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

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

啟動(dòng)讀卡機(jī)

……

收到輸入結(jié)果

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

P(S2)

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

V(S1);

加工并且存盤(pán)

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

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

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

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

利用信號(hào)量機(jī)制解經(jīng)典進(jìn)程同步問(wèn)題-2

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

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

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

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

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

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

ThestructureofPhilosophersiPhilosopher[i]:while(TURE){

思考問(wèn)題

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

進(jìn)餐

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

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

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

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

設(shè)置兩個(gè)信號(hào)量：讀互斥信號(hào)量rmutex和寫(xiě)互斥信號(hào)量wmutex。另外設(shè)立一個(gè)讀計(jì)數(shù)器readcount，它是一個(gè)整型變量，初值為0。rmutex：用于讀者互斥地訪問(wèn)readcount，初值為1。wmutex：用于保證一個(gè)寫(xiě)者與其他讀者/寫(xiě)者互斥地訪問(wèn)共享資源，初值為1。讀者-寫(xiě)者問(wèn)題-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ù)

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

執(zhí)行寫(xiě)操作

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

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

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

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

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

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

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

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

$>who|wc-l$>ls–l|wc-l2.8進(jìn)程通信

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

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

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

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

1．申請(qǐng)

2．使用

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

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

…

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

進(jìn)程A

進(jìn)程B

……

……

申請(qǐng)并占用R申請(qǐng)并占用S

申請(qǐng)并占用S申請(qǐng)并占用R

……

……

釋放R釋放S

釋放S釋放R

……

……3.2.1什么是死鎖

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

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

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

→rj稱為申請(qǐng)邊，而有向邊rj

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

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

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

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

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

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

基本思想是限制進(jìn)程對(duì)資源的申請(qǐng)，以保證死鎖不會(huì)發(fā)生。3.3.1破壞互斥條件用否定互斥條件的辦法是不能預(yù)防死鎖的，因?yàn)槟承┵Y源具有不可共享的固有屬性。3.3.2破壞占有且等待條件保證一個(gè)進(jìn)程無(wú)論什么時(shí)候都可申請(qǐng)它沒(méi)有占有的任何資源。一種辦法是預(yù)分資源策略靜態(tài)分配。另一種辦法是“空手”申請(qǐng)資源策略。3.3.3破壞非搶占條件

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

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

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

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

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

rj表示進(jìn)程pi能夠申請(qǐng)資源rj，有時(shí)用虛線表示。3.4.2資源分配圖算法圖3-6資源分配圖示例

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

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

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

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

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

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

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

Finish[i]=true

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

進(jìn)程AllocationMaxNeedAvailableR1R2R3R1R2R3R1R2R3R1R2R3A100322222112B511613102C211314103D002422420表3-3T0時(shí)刻資源分配表資源情況（1）T0時(shí)刻是安全的存在一個(gè)安全序列{B,A,C,D}

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

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

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

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

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