操作系統(tǒng)死鎖同步互斥CH6c5

進(jìn)程間的制約關(guān)系

第6章

計(jì)算機(jī)學(xué)院柴忠良6.1進(jìn)程間的制約關(guān)系16.3死鎖、高級(jí)進(jìn)程通信3本章講述內(nèi)容6.2信號(hào)量與P、V操作1

本章將引入操作系統(tǒng)中的重要概念：信號(hào)量以及在信號(hào)量上的P、V操作。利用信號(hào)量以及在信號(hào)量上的P、V操作，可以很好地解決進(jìn)程間的互斥與同步關(guān)系，保證進(jìn)程程序的正確執(zhí)行。

本章著重講述四個(gè)方面的內(nèi)容：（1）進(jìn)程間的兩種制約關(guān)系—互斥與同步。（2）正確處理互斥與同步的方法—信號(hào)量以及在信號(hào)量上的P、V操作。（3）死鎖以及解決死鎖的途徑。（4）進(jìn)程間的高級(jí)通信。進(jìn)程的順序性馮·諾依曼結(jié)構(gòu)的基本特性是處理器順序執(zhí)行命令。當(dāng)一個(gè)進(jìn)程獨(dú)占CPU時(shí)具有以下特性：順序性：處理機(jī)的操作嚴(yán)格按照程序所規(guī)定的順序執(zhí)行。封閉性：進(jìn)程執(zhí)行的結(jié)果取決于進(jìn)程本身，不受外界影響。可再現(xiàn)性：當(dāng)進(jìn)程再次重復(fù)執(zhí)行時(shí)，必定獲得相同的結(jié)果。進(jìn)程的并發(fā)性如果系統(tǒng)中存在一組可同時(shí)執(zhí)行的進(jìn)程。并發(fā)進(jìn)程之間可能是無(wú)關(guān)的，也可能是有關(guān)的—相互依賴。當(dāng)多個(gè)進(jìn)程共享CPU時(shí)具有以下特性：間斷性：不再是一口氣運(yùn)行下去，出現(xiàn)走走停?，F(xiàn)象，停的次數(shù)和地方不再相同。封閉性被打破：不同的時(shí)間運(yùn)行的進(jìn)程個(gè)數(shù)、是誰(shuí)以及它們的執(zhí)行時(shí)間不同，受外界影響。不可再現(xiàn)性：當(dāng)進(jìn)程再次重復(fù)執(zhí)行時(shí)，運(yùn)行的過(guò)程和運(yùn)行的結(jié)果不一定相同。6.1進(jìn)程間的制約關(guān)系

6.1.1與時(shí)間有關(guān)的錯(cuò)誤在相同的前提條件下，兩次執(zhí)行的結(jié)果有可能不相同。在操作系統(tǒng)里，把這種由于時(shí)間因素的影響而產(chǎn)生的錯(cuò)誤，稱為“與時(shí)間有關(guān)的錯(cuò)誤”。例：游樂(lè)場(chǎng)自動(dòng)計(jì)數(shù)系統(tǒng)。Begin Count:integer; Count:=0;Cobegin

Coend;End;ProcessPIN R1:integer;Begin R1:=count; R1:=R1+1; count:=R1;End;ProcessPOUT R2:integer;Begin R2:=count; R2:=R2-1; count:=R2;End;例：飛機(jī)航班售票系統(tǒng)。Aj:j次航班余票數(shù)

j=1,2,3…mPi:i航班處理進(jìn)程i=1,2,3…nRi:各進(jìn)程工作單元售票處1售票處5售票處4售票處3售票處2例：飛機(jī)航班售票系統(tǒng)。ProcessPi(i=1,2,3…n) Ri:integer;Begin

按旅客要求找到Aj; Ri:=Aj; ifRi>=1then else輸出“票已售完”End;Begin Ri:=Ri-1; Aj:=Ri;

輸出一張票End;圖6-1對(duì)輸出井文件目錄的管理圖6-2通過(guò)雙緩沖區(qū)復(fù)制文件圖6-3GET→PUT→COPY導(dǎo)致錯(cuò)誤6.1.2競(jìng)爭(zhēng)資源—互斥在操作系統(tǒng)中，凡是牽扯到數(shù)據(jù)、隊(duì)列、緩沖區(qū)、表格和變量等任何形式的共享資源時(shí)，都很容易出現(xiàn)類似的這種“與時(shí)間有關(guān)的錯(cuò)誤”。

為了避免錯(cuò)誤的發(fā)生，關(guān)鍵是要找到一種途徑，來(lái)阻止多于一個(gè)進(jìn)程同時(shí)使用它們。也就是說(shuō)，保證對(duì)它們的使用是互斥進(jìn)行的。

與一個(gè)共享變量（或臨界資源）交往的多個(gè)進(jìn)程，為了保證它們各自運(yùn)行結(jié)果的正確性，當(dāng)其中的一個(gè)進(jìn)程正在對(duì)該變量（或臨界資源）進(jìn)行操作時(shí)，就不允許其他進(jìn)程同時(shí)對(duì)它進(jìn)行操作。進(jìn)程間的這種制約關(guān)系被稱為“互斥”。

進(jìn)程A進(jìn)程B共享變量COUNT對(duì)具有互斥關(guān)系的進(jìn)程，要注意以下四點(diǎn)：（1）只有涉及共享變量的那一部分程序，才真正需要保證互斥地執(zhí)行。通常，把進(jìn)程程序中“真正需要保證互斥執(zhí)行”的那一段程序，稱為該進(jìn)程的“臨界區(qū)（或臨界段）”。

進(jìn)程A進(jìn)程B共享變量COUNT例：游樂(lè)場(chǎng)自動(dòng)計(jì)數(shù)系統(tǒng)。Begin Count:integer; Count:=0;Cobegin

Coend;End;ProcessPIN R1:integer;Begin

R1:=count; R1:=R1+1; count:=R1;End;ProcessPOUT R2:integer;Begin

R2:=count; R2:=R2-1; count:=R2;End;（2）具有互斥關(guān)系的進(jìn)程，并不關(guān)心對(duì)方的存在性。即使對(duì)方不存在，自己也能夠正確的運(yùn)行，不會(huì)受到它存在與否的影響。（3）具有互斥關(guān)系進(jìn)程的臨界區(qū)，雖然都是針對(duì)同一個(gè)共享變量的程序段，但在其上的操作可以相同也可以不相同。相關(guān)臨界區(qū)（4）進(jìn)程的臨界區(qū)是相對(duì)于某個(gè)共享變量而言的，不同共享變量的臨界區(qū)之間，不存在互斥關(guān)系。XY相關(guān)臨界區(qū)執(zhí)行時(shí)必須遵循以下準(zhǔn)則：（1）每次只允許一個(gè)進(jìn)程進(jìn)入臨界區(qū)。（2）一個(gè)進(jìn)程在臨界區(qū)內(nèi)逗留有限時(shí)間后，就應(yīng)該退出，以便給其他進(jìn)程創(chuàng)造進(jìn)入臨界區(qū)的機(jī)會(huì)。（3）不能強(qiáng)迫一個(gè)進(jìn)程在臨界區(qū)外無(wú)限期逗留。相關(guān)臨界區(qū)三原則

有限時(shí)間進(jìn)一次一個(gè)有限時(shí)間出16.1.3協(xié)同工作—同步這里所描述的進(jìn)程間的關(guān)系有如下特點(diǎn)：（1）具有這種關(guān)系的進(jìn)程，需要在某些點(diǎn)上協(xié)調(diào)相互的動(dòng)作，誰(shuí)先到達(dá)誰(shuí)后到達(dá)是有順序要求的。圖6-4GET和COPY協(xié)調(diào)一致地工作（2）這些進(jìn)程都應(yīng)該了解對(duì)方的工作，對(duì)方不存在，或任何一方單獨(dú)運(yùn)行，就會(huì)出現(xiàn)差錯(cuò)。（3）一方或雙方的運(yùn)行會(huì)直接地依賴于對(duì)方所產(chǎn)生的信息或發(fā)出的消息。

一個(gè)進(jìn)程運(yùn)行到某一點(diǎn)時(shí)，除非合作進(jìn)程已經(jīng)完成了某種操作或發(fā)來(lái)了信息，否則就必須暫時(shí)等待那些操作的完成或信息的到來(lái)。握手和均值

進(jìn)程間的這種關(guān)系被稱為“同步”。暫停等待以取得同步的那一點(diǎn)，稱為“同步點(diǎn)”，需要等待一個(gè)進(jìn)程完成的操作或發(fā)送的信息，稱為“同步條件”。6.2信號(hào)量與P、V操作

通過(guò)信號(hào)量取不同的初值以及在其上做P、V操作，就能夠?qū)崿F(xiàn)進(jìn)程間的互斥、同步，甚至用來(lái)管理資源的分配。6.2.1信號(hào)量與P、V操作的定義所謂“信號(hào)量”，是一個(gè)具有非負(fù)初值的整型變量，并且有一個(gè)隊(duì)列與它關(guān)聯(lián)。

在一個(gè)信號(hào)量S上，只能做規(guī)定的兩種操作：P操作，記為P（S）；和V操作，記為V（S）。P、V操作的具體定義如下。（1）信號(hào)量S上的P操作定義:當(dāng)一個(gè)進(jìn)程調(diào)用P（S）時(shí)，應(yīng)該順序做下面不可分割的兩個(gè)動(dòng)作。Vs

=

Vs

?

1，即把當(dāng)前信號(hào)量S的取值減1。若Vs

>=

0，則調(diào)用進(jìn)程繼續(xù)運(yùn)行；若Vs<0，則調(diào)用進(jìn)程由運(yùn)行狀態(tài)變?yōu)樽枞麪顟B(tài)，到與該信號(hào)量有關(guān)的隊(duì)列Vq上排隊(duì)等待，直到其他進(jìn)程在S上執(zhí)行V操作將其釋放為止。P(S)V(S)ProcedureP(VarS:semaphore)Begin S:=S-1; ifS<0thenW(S)End;{P}ProcedureV(VarS:semaphore)Begin S:=S+1; ifS<=0thenR(S)End;{V}（2）信號(hào)量S上的V操作定義:當(dāng)一個(gè)進(jìn)程調(diào)用V（S）時(shí)，應(yīng)該順序做下面不可分割的兩個(gè)動(dòng)作。Vs

=

Vs

+

1，即把當(dāng)前信號(hào)量S的取值加1。若Vs

>

0，則調(diào)用進(jìn)程繼續(xù)運(yùn)行；若Vs<=

0，則先從與該信號(hào)量有關(guān)的隊(duì)列Vq上摘下一個(gè)等待進(jìn)程，讓它從阻塞狀態(tài)變?yōu)榫途w狀態(tài)，到就緒隊(duì)列里排隊(duì)，然后調(diào)用進(jìn)程繼續(xù)運(yùn)行。6.2.2用P、V操作實(shí)現(xiàn)互斥Begin PROCESSPi … s:semaphore; begin coend; s:=1; … end; … P(S);Cobegin {臨界區(qū)Ci}; … V(S);

… end;例：游樂(lè)場(chǎng)自動(dòng)計(jì)數(shù)系統(tǒng)。Begin Count:integer; Count:=0;Cobegin

Coend;End;ProcessPIN R1:integer;Begin

R1:=count; R1:=R1+1; count:=R1;End;ProcessPOUT R2:integer;Begin

R2:=count; R2:=R2-1; count:=R2;End;例：游樂(lè)場(chǎng)自動(dòng)計(jì)數(shù)系統(tǒng)。Begin Count:integer;

S:semaphore; Count:=0;

S:=1;Cobegin

Coend;End;ProcessPIN R1:integer;Begin

P(S);

R1:=count; R1:=R1+1; count:=R1;

V(S);End;ProcessPOUT R2:integer;Begin P(S);

R2:=count; R2:=R2-1; count:=R2; V(S);End;S的范圍例：飛機(jī)航班售票系統(tǒng)。ProcessPi(i=1,2,3…n) Ri:integer;Begin

按旅客要求找到Aj;

P(S)；

Ri:=Aj; ifRi>=1then else輸出“票已售完”End;Begin Ri:=Ri-1; Aj:=Ri;

V(S);

輸出一張票End;Begin

S:semaphore;

S:=1;Cobegin

Coend;End;例：飛機(jī)航班售票系統(tǒng)。ProcessPi(i=1,2,3…n) Ri:integer;Begin

按旅客要求找到Aj;

P(S)；

Ri:=Aj; ifRi>=1then else輸出“票已售完”End;Begin Ri:=Ri-1; Aj:=Ri;

V(S);

輸出一張票End;Begin

S:semaphore;

S:=1;Cobegin

Coend;End;例：飛機(jī)航班售票系統(tǒng)。ProcessPi(i=1,2,3…n) Ri:integer;Begin

按旅客要求找到Aj;

P(S)；

Ri:=Aj; ifRi>=1then elsebeginV(S);

輸出“票已售完”

end;End;Begin Ri:=Ri-1; Aj:=Ri;

V(S);

輸出一張票End;Begin

S:semaphore;

S:=1;Cobegin

Coend;End;序調(diào)用進(jìn)程PV操作臨界區(qū)內(nèi)被S阻塞S的值112AP(S)A03AV(S)14BP(S)B05CP(S)BC-16DP(S)BCD-27EP(S)BCDE-38BV(S)DCE-29FP(S)DCEF-310DV(S)ECF-211非A-FECF-212EV(S)FC-113FV(S)C014CV(S)1圖6-5P、V操作用于進(jìn)程互斥

設(shè)置一個(gè)初值為1的信號(hào)量S，在進(jìn)程A和B的進(jìn)入點(diǎn)處安排關(guān)于信號(hào)量S的P操作，在進(jìn)程A和B的退出點(diǎn)處安排關(guān)于信號(hào)量S的V操作。這樣，就能夠確保CSa和CSb互斥地執(zhí)行。

例6-1在第2章的圖2-2中，給出了一個(gè)“觀察者-報(bào)告者”的例子。試用信號(hào)量上的P、V操作來(lái)保證它們正確地配合工作。圖6-6“觀察者-報(bào)告者”問(wèn)題的P、V操作解法6.2.3用P、V操作實(shí)現(xiàn)同步互斥是特殊的同步：空間限制協(xié)調(diào)同步：時(shí)間限制記錄和均值圖6-7P、V操作用于進(jìn)程同步

為了保證做到這一點(diǎn)，設(shè)置一個(gè)初值為0的信號(hào)量S，在進(jìn)程A的X點(diǎn)處（即同步點(diǎn)），安排一個(gè)關(guān)于信號(hào)量S的P操作，在進(jìn)程B的Y點(diǎn)處安排關(guān)于信號(hào)量S的V操作。

這樣，就能夠確保進(jìn)程A在X點(diǎn)處與進(jìn)程B取得同步了。

例6-2試用信號(hào)量上的P、V操作，來(lái)保證如圖6-4所示的GET和COPY兩者之間協(xié)調(diào)地工作。圖6-8用P、V操作保證GET和COPY間的協(xié)作關(guān)系6.2.4用P、V操作實(shí)現(xiàn)資源分配如果把信號(hào)量的初始值，比如n，理解為是系統(tǒng)中某種資源的數(shù)目，那么，在它的上面做P操作，即是申請(qǐng)一個(gè)資源；在它的上面做V操作，即是釋放一個(gè)用完的資源。

與該信號(hào)量有關(guān)的隊(duì)列，是資源等待隊(duì)列。

在用P、V操作實(shí)現(xiàn)資源分配時(shí)，把所設(shè)置的信號(hào)量初值設(shè)為資源的個(gè)數(shù)n。在進(jìn)行資源分配的進(jìn)程中對(duì)信號(hào)量做P操作。每做一次P操作，就分配一個(gè)資源。

在進(jìn)行資源回收的進(jìn)程里對(duì)信號(hào)量做V操作。每做一次V操作，就收回一個(gè)資源。

由于資源初啟時(shí)共有n個(gè)，如果對(duì)資源進(jìn)行連續(xù)n次申請(qǐng)，都能夠立即得到滿足。但第n+1個(gè)提出申請(qǐng)的進(jìn)程就不得不在資源等待隊(duì)列中等待了。

例“生產(chǎn)者-消費(fèi)者”問(wèn)題）假定有m個(gè)生產(chǎn)者和r個(gè)消費(fèi)者，他們共享n個(gè)緩沖區(qū)。生產(chǎn)者容器消費(fèi)者

1:1:11:n:1m:n:r

生產(chǎn)者容器消費(fèi)者

1:1:11Begin buffer:integer; SP,SG:semaphore; SP:=1;SG:=0;Cobegin

生產(chǎn)者、消費(fèi)者進(jìn)程Coend;End;生產(chǎn)者、消費(fèi)者進(jìn)程ProcessproducerBegin L1: produceaproduct; P(SP); buffer:=product; V(SG); gotoL1;End;ProcessconsumerBegin L2: P(SG); takeaproduct; V(SP); consume; gotoL1;End;

例6-3（簡(jiǎn)單的“生產(chǎn)者-消費(fèi)者”問(wèn)題）假定有一個(gè)生產(chǎn)者和一個(gè)消費(fèi)者，他們共享10個(gè)緩沖區(qū)。生產(chǎn)者不斷地生產(chǎn)物品，將每個(gè)物品依次放入緩沖區(qū)中（一個(gè)緩沖區(qū)正好放一個(gè)物品）。

消費(fèi)者依次從緩沖區(qū)中取出物品進(jìn)行消費(fèi)。只有在緩沖區(qū)中有空位時(shí)，生產(chǎn)者生產(chǎn)出來(lái)的物品才能往里面放；只有在緩沖區(qū)有物品時(shí)，消費(fèi)者才能從它的里面取出物品。試用P、V操作來(lái)協(xié)調(diào)生產(chǎn)者和消費(fèi)者之間的工作。圖6-9P、V操作用于“簡(jiǎn)單生產(chǎn)者-消費(fèi)者”問(wèn)題

生產(chǎn)者容器消費(fèi)者

1:n:1 k tB[0]B[1]…B[t]…B[k]…B[n-1]Begin

B:array[0…(n-1)]ofinteger; k,t:integer;k:=0;t:=0; SP,SG:semaphore; SP:=n;SG:=0;Cobegin

生產(chǎn)者、消費(fèi)者進(jìn)程Coend;End;生產(chǎn)者、消費(fèi)者進(jìn)程ProcessproducerBegin L1: produceaproduct; P(SP);

B(k):=product; k:=k+1; V(SG); gotoL1;End;ProcessconsumerBegin L2: P(SG);

takeaproductfromB(t); t:=t+1; V(SP); consume; gotoL1;End;生產(chǎn)者、消費(fèi)者進(jìn)程ProcessproducerBegin L1: produceaproduct; P(SP);

B(k):=product; k:=(k+1)modn; V(SG); gotoL1;End;ProcessconsumerBegin L2: P(SG);

takeaproductfromB(t); t:=(t+1)modn; V(SP); consume; gotoL1;End;6.2.5互斥/同步的樣例分析

例6-4（“生產(chǎn)者-消費(fèi)者”問(wèn)題）假定有i個(gè)生產(chǎn)者和j個(gè)消費(fèi)者，他們共享k個(gè)緩沖區(qū)。生產(chǎn)者不斷地生產(chǎn)物品，將每個(gè)物品依次放入緩沖區(qū)中（一個(gè)緩沖區(qū)正好放一個(gè)物品）。

消費(fèi)者依次從緩沖區(qū)中取出物品進(jìn)行消費(fèi)。只有在緩沖區(qū)中有空位時(shí)，生產(chǎn)者生產(chǎn)出來(lái)的物品才能往里面放；只有在緩沖區(qū)有物品時(shí)，消費(fèi)者才能從它的里面取出物品。試用P、V操作來(lái)協(xié)調(diào)生產(chǎn)者和消費(fèi)者之間的工作。圖6-10P、V操作用于“生產(chǎn)者-消費(fèi)者”問(wèn)題

生產(chǎn)者容器消費(fèi)者

m:n:r k tS1 S2 B[0]B[1]…B[t]…B[k]…B[n-1]Begin

B:array[0…(n-1)ofinteger; k,t:integer;k:=0;t:=0;

S1,S2,SP,SG:semaphore;

S1=1;S2:=1;SP:=n;SG:=0;Cobegin

生產(chǎn)者、消費(fèi)者進(jìn)程Coend;End;生產(chǎn)者、消費(fèi)者進(jìn)程Processproduceri(i=1,2…m)Begin L1: produceaproduct; P(SP);

P(S1);

B(k):=product; k:=(k+1)modn; V(S1); V(SG); gotoL1;End;Processconsumerj(j=1,2…r)Begin L2: P(SG);

P(S2);

takeaproductfromB(t); t:=:=(t+1)modn;

V(S2); V(SP); consume; gotoL1;End;

互斥、資源分配，只是同步的不同表現(xiàn)形式罷了?；コ馐翘厥獾耐剑嚎臻g限制協(xié)調(diào)同步：時(shí)間限制

例6-5（“讀者-寫(xiě)者”問(wèn)題）若一批數(shù)據(jù)被多個(gè)并發(fā)進(jìn)程共享使用。其中一些進(jìn)程只要求讀數(shù)據(jù)，稱為“讀者”；另一些會(huì)對(duì)數(shù)據(jù)進(jìn)行修改，稱為“寫(xiě)者”。

多個(gè)讀者同時(shí)工作時(shí)，訪問(wèn)不會(huì)有問(wèn)題。但是讀者和寫(xiě)者或?qū)懻吆蛯?xiě)者同時(shí)工作時(shí)，就可能導(dǎo)致錯(cuò)誤的訪問(wèn)結(jié)果。

假定在有讀者訪問(wèn)時(shí)，又來(lái)寫(xiě)者要求訪問(wèn)，那么寫(xiě)者只能等待，而后續(xù)到來(lái)的讀者則可以進(jìn)行訪問(wèn)（這就是隱含讀者比寫(xiě)者有更高的訪問(wèn)權(quán)）。試用P、V操作來(lái)協(xié)調(diào)讀者和寫(xiě)者之間的工作。圖6-11P、V操作用于“讀者-寫(xiě)者”問(wèn)題過(guò)鐵橋、過(guò)隧道Begin

E,W,Flag:Semaphore; E=1;W:=1;Flag:=1; CE,CW:integer; CE:=0;CW:=0;Cobegin

過(guò)鐵橋或過(guò)隧道進(jìn)程Coend;End;過(guò)鐵橋、過(guò)隧道進(jìn)程ProcessEastBegin L1:P(E); ifCE=0ThenP(Flag); CE:=CE+1; V(E);

過(guò)橋或過(guò)隧道；

P(E); ifCE=1ThenV(Flag); CE:=CE-1; V(E); gotoL1;End;ProcessWestBegin L2:P(W); ifCW=0ThenP(Flag); CW:=CW+1; V(W);

過(guò)橋或過(guò)隧道；

P(W); ifCW=1ThenV(Flag); CW:=CW-1; V(W); gotoL2;End;過(guò)鐵橋、過(guò)隧道進(jìn)程ProcessEastBegin

P(E); ifCE=0ThenP(Flag); CE:=CE+1; V(E);

過(guò)橋或過(guò)隧道；

P(E); ifCE=1ThenV(Flag); CE:=CE-1; V(E);End;ProcessWestBegin

P(W); ifCW=0ThenP(Flag); CW:=CW+1; V(W);

過(guò)橋或過(guò)隧道；

P(W); ifCW=1ThenV(Flag); CW:=CW-1; V(W); End;過(guò)鐵橋、過(guò)隧道進(jìn)程ProcessEastBegin

P(E); CE:=CE+1;

ifCE=1ThenP(Flag); V(E);

過(guò)橋或過(guò)隧道；

P(E); CE:=CE-1; ifCE=0ThenV(Flag); V(E);End;ProcessWestBegin

P(W); ifCW=0ThenP(Flag); CW:=CW+1; V(W);

過(guò)橋或過(guò)隧道；

P(W); ifCW=1ThenV(Flag); CW:=CW-1; V(W); End;圖6-12不正確的解法圖6-13又一個(gè)不正確的解法補(bǔ)充：水果問(wèn)題看似2:1:2

父 兒母 女盤(pán)子Begin S,SP,SO:semaphore; S:=1;SP:=0;SO:=0;Cobegin

生產(chǎn)者父母、消費(fèi)者兒女進(jìn)程Coend;End;ProcessfatherBegin L1: haveanapple; P(S); putanappleintoplate; V(SP); gotoL1;End;ProcessmotherBegin L2: haveanorange; P(S); putanorangeintoplate; V(SO); gotoL2;End;ProcesssonBegin L3:P(SO); getanorangefromplate; V(S); eatanorange; gotoL3;End;ProcessdaughtBegin L4: P(SP); getanapple; V(S); eattheapplefromplate; gotoL4;End;作業(yè)：分奇偶數(shù)

W1R W2

緩沖區(qū)B輸入設(shè)備輸出設(shè)備輸出設(shè)備Begin B:integer; S,SE,SO:semaphore; S:=1;SE:=0;SO:=0;Cobegin

一輸入二輸出進(jìn)程Coend;End;ProcessR x:integer;Begin L1: 讀數(shù)；

X:=所讀的數(shù)；

P(S)；

B:=x;

ifB=奇數(shù)thenV(SO);

elseV(SE); gotoL1;End;ProcessW1 y:integer;Begin L2: P(SO)；

y:=B;

V(S);

輸出y; gotoL2;End;ProcessW2 z:integer;Begin L3: P(SE)；

z:=B;

V(S);

輸出z; gotoL3;End;司機(jī)與票員的同步進(jìn)程ProcessBus-DriverBegin L1:P(Run);

啟動(dòng)車輛;

正常行駛;

到站停車；

V(Open); gotoL1;End;ProcessCondctorBegin L2:售票；

P(Open);

開(kāi)啟車門(mén);

服務(wù)乘客上車;

關(guān)閉車門(mén)；

V(Run); gotoL2;End;請(qǐng)用PV操作來(lái)實(shí)現(xiàn)司機(jī)與票員的同步Begin

Open,Run:Semaphore; Open=0;Run:=1;Cobegin

司機(jī)、售票員進(jìn)程Coend;End;司機(jī)與票員的同步進(jìn)程ProcessBus-DriverBegin L1:P(Run);

啟動(dòng)車輛;

正常行駛;

到站停車；

V(Open); gotoL1;End;ProcessCondctorBegin L2:售票；

P(Open);

開(kāi)啟車門(mén);

服務(wù)乘客上車;

關(guān)閉車門(mén)；

V(Run); gotoL2;End;6.3死鎖、高級(jí)進(jìn)程通信

6.3.1死鎖與產(chǎn)生死鎖的必要條件常用方框代表資源，圓圈代表進(jìn)程，如果畫(huà)一條由資源到進(jìn)程的有向邊，則表示把該資源分配給了這個(gè)進(jìn)程。

如果畫(huà)一條由進(jìn)程到資源的有向邊，則表示該進(jìn)程申請(qǐng)這個(gè)資源，這樣的圖就是所謂的“資源分配圖”。圖6-14資源分配圖

例6-6現(xiàn)在有進(jìn)程A對(duì)資源的需求序列是申請(qǐng)R，申請(qǐng)S，釋放R，釋放S；進(jìn)程B對(duì)資源的需求序列是申請(qǐng)S，申請(qǐng)T，釋放S，釋放T；進(jìn)程C對(duì)資源的需求序列是申請(qǐng)T，申請(qǐng)R，釋放T，釋放R。

請(qǐng)對(duì)序列：（1）“A申請(qǐng)R、B申請(qǐng)S、C申請(qǐng)T、A申請(qǐng)S、B申請(qǐng)T、C申請(qǐng)R”；（2）“A申請(qǐng)R、C申請(qǐng)T、A申請(qǐng)S、C申請(qǐng)R、A釋放R、A釋放S”分別畫(huà)出對(duì)應(yīng)的資源分配圖，說(shuō)明誰(shuí)能夠運(yùn)行，誰(shuí)無(wú)法運(yùn)行。圖6-15第1個(gè)序列的資源分配圖圖6-16第2個(gè)序列的資源分配圖

所謂“死鎖”，即指系統(tǒng)中若存在一組（至少兩個(gè)或以上）進(jìn)程，它們中的每一個(gè)都占用了某種資源而又都在等待其中另一個(gè)所占用的資源，這種等待永遠(yuǎn)不會(huì)結(jié)束，這就是“死鎖”，或說(shuō)這一組進(jìn)程處于“死鎖”狀態(tài)。

一個(gè)系統(tǒng)出現(xiàn)死鎖，會(huì)存在四個(gè)必要條件：（1）互斥條件（2）部分分配（占用并等待）條件（3）非剝奪條件（4）循環(huán)等待條件死機(jī)不一定死鎖出現(xiàn)環(huán)路也不一定死鎖

R1R2P1P4P3P2

解決系統(tǒng)中的死鎖問(wèn)題，有下面幾種對(duì)策：（1）忽略死鎖（2）預(yù)防死鎖（3）避免死鎖（4）檢測(cè)死鎖并恢復(fù)（解除）6.3.2死鎖的預(yù)防所謂“死鎖的預(yù)防”，是指破壞產(chǎn)生死鎖四個(gè)必要條件中的一條或幾條，以使系統(tǒng)不會(huì)產(chǎn)生死鎖。（1）破壞“互斥條件”。（2）破壞“部分分配（占用并等待）條件”。（3）破壞“非剝奪條件”。（4）破壞“循環(huán)等待條件”。圖6-17用順序編號(hào)破壞“循環(huán)等待條件”哲學(xué)家吃面Begin S1,S2,S3,S4,S5:semaphore; S1:=1;S2:=1;S3:=1;S4:=1;S5:=1;Cobegin

進(jìn)程Coend;End;f1f4f5f3f2人1人3人2人4人5ProcessP1Begin L1: 思考; P(S1);

取F1; P(S2);

取F2;

吃面； 放下F1和F2; V(S2); V(S1); gotoL1;End;ProcessP2Begin L2: 思考; P(S2);

取F2; P(S3);

取F3;

吃面； 放下F2和F3; V(S3); V(S2); gotoL2;End;ProcessP3Begin L3: 思考; P(S3);

取F3; P(S4);

取F4;

吃面； 放下F3和F4; V(S4); V(S3); gotoL3;End;ProcessP4Begin L4: 思考; P(S4);

取F4; P(S5);

取F5;

吃面； 放下F4和F5; V(S5); V(S4); gotoL4;End;ProcessP5Begin L5: 思考; P(S5);

取F5; P(S1);

取F1;

吃面； 放下F1和F5; V(S1); V(S5); gotoL5;End;ProcessP5Begin L5: 思考; P(S1);

取F1; P(S5);

取F5;

吃面； 放下F1和F5; V(S5); V(S1); gotoL5;End;按序分配6.3.3死鎖的避免死鎖的防止是在運(yùn)行前采取的措施，相當(dāng)于小孩打防疫針，不會(huì)死鎖。但這些措施會(huì)大大影響系統(tǒng)的速度。死鎖的避免就是如果能夠找到一個(gè)執(zhí)行次序，那么也不會(huì)死鎖。死鎖的避免是指雖然系統(tǒng)中存在有產(chǎn)生死鎖的條件，但小心對(duì)待進(jìn)程提出的每一個(gè)資源請(qǐng)求。

在接到一個(gè)資源請(qǐng)求時(shí)，不是立即進(jìn)行分配，而是根據(jù)當(dāng)時(shí)資源的使用情況，按照一定的算法去模擬分配，探測(cè)出模擬分配的結(jié)果。共12個(gè)資源，剩余3個(gè)

只有在探測(cè)結(jié)果表明絕對(duì)不會(huì)出現(xiàn)死鎖時(shí)，才真正接受這次資源請(qǐng)求。進(jìn)程最大需求數(shù)已占資源尚缺資源P1P2P39104252752共12個(gè)資源，剩余2個(gè)進(jìn)程最大需求數(shù)已占資源尚缺資源P1P2P391042+1=352652

如果能在有限的時(shí)間內(nèi)，保證所有進(jìn)程得到自己需要的全部資源，那么稱系統(tǒng)處于“安全狀態(tài)”；否則稱系統(tǒng)處于“不安全狀態(tài)”。安全狀態(tài)不安全狀態(tài)死鎖銀行家算法的基本思想當(dāng)一個(gè)用戶對(duì)資金的最大需求量不超過(guò)銀行家現(xiàn)有的資金時(shí)就接納該用戶。用戶可以分期貸款，但貸款總數(shù)不能超過(guò)最大需求量。當(dāng)銀行家現(xiàn)有資金不夠時(shí)可推遲支付，但時(shí)間有限。當(dāng)用戶得到全部貸款后，必須按時(shí)歸還所有貸款。圖6-18銀行家算法的基本思想銀行家算法之例

假定系統(tǒng)中有五個(gè)進(jìn)程｛P0,P1,P2,P3,P4｝和三類資源｛A,B,C｝，各種資源的數(shù)量分別為10、5、7，在T0時(shí)刻的資源分配情況如圖3-15所示。圖3-15T0時(shí)刻的資源分配表(1)T0時(shí)刻的安全性：圖3-16T0時(shí)刻的安全序列Max最大ABC1057Allacation已分ABCNeed尚需ABCWork工作區(qū)ABC332Sort執(zhí)行次序Finish完成p075401074410575Tp13222001221221Tp290230260010474Tp32222110117432Tp44330024317453TT0時(shí)刻存在安全序列{p1,p3,p4,p2,p0}，因此不會(huì)死鎖Max最大ABC1057Allacation已分ABC221Need尚需ABCWork工作區(qū)ABC111Sort執(zhí)行次序Finish完成p0754010231744523Fp13222001225222Tp2902302600Fp32222110113221Tp4433002431FT1時(shí)刻找不到安全序列，在不安全狀態(tài)，系統(tǒng)不分配圖6-19一個(gè)導(dǎo)致安全狀態(tài)的請(qǐng)求圖6-20一個(gè)導(dǎo)致不安全狀態(tài)的請(qǐng)求

銀行家算法可以推廣用于處理多種資源。此時(shí)，系統(tǒng)要為算法設(shè)置兩張表，一張記錄已分配給各進(jìn)程的資源數(shù)，一張記錄各進(jìn)程還需要的資源數(shù)。

另外還要有3個(gè)向量：向量E記錄各種資源的總數(shù)，向量P記錄各種資源已分配數(shù)，向量A記錄各種資源的剩余數(shù)。圖6-21多種資源的銀行家算法

多種資源銀行家算法的執(zhí)行步驟如下：（1）假定接受一個(gè)進(jìn)程提出的資源請(qǐng)求，修改向量P和A。（2）檢查還需資源表中是否有一個(gè)進(jìn)程的行向量小于或等于向量A。如果沒(méi)有，那么系統(tǒng)就可能會(huì)死鎖，因?yàn)楝F(xiàn)在任何進(jìn)程都無(wú)法完成了。（3）如果存在這種進(jìn)程，那么假定它已獲得需要的所有資源，并完成工作，把它的“能執(zhí)行完”標(biāo)志