操作系統(tǒng)2002-進(jìn)程同步與互斥

進(jìn)程同步與互斥一、進(jìn)程的并發(fā)性二、進(jìn)程的互斥三、進(jìn)程的同步四、同步與互斥的混合問題一、進(jìn)程的并發(fā)性

程序并行性的表示：CobeginS1；S2；…；SnCoend

在多道系統(tǒng)中，假如有兩個(gè)進(jìn)程A和B，它們要求順序執(zhí)行的操作如下：進(jìn)程A：a1,a2,a3,a4,…,an進(jìn)程B：b1,b2,b3,b4,…,bm這兩個(gè)進(jìn)程是在處理器上交替執(zhí)行的，可能出現(xiàn)的執(zhí)行序列有：a1,b1,a2,b2,…和a1,a2,b1,b2,…,等等，它們的執(zhí)行在時(shí)間上是重疊的，這被稱為“可同時(shí)執(zhí)行的”。在多道程序環(huán)境下，進(jìn)程之間存在以下關(guān)系資源共享關(guān)系相互合作關(guān)系觀察者beginL：observealorry；count:=count+1；gotoLend；報(bào)告者beginprintcount；count:=0；end；樣例1：假定某一時(shí)刻，觀察者已記錄了N輛車，又在記錄下一輛車，此時(shí)，報(bào)告者也開始工作。與時(shí)間有關(guān)的錯(cuò)誤執(zhí)行順序1：（觀察者）count:=count+1;（報(bào)告者）report;（報(bào)告者）count:=0;這是正確的結(jié)果。執(zhí)行順序2：（報(bào)告者）reportcount;（觀察者）count:=count+1;（報(bào)告者）count:=0;觀察者剛剛記錄的一輛車的信息丟失了

造成不正確的因素是與進(jìn)程占用處理器的時(shí)間、執(zhí)行的速度以及外界的影響有關(guān)。這些因素都與時(shí)間有關(guān)，所以，稱它們?yōu)椤芭c時(shí)間有關(guān)的錯(cuò)誤”樣例2：飛機(jī)航班有N個(gè)售票處，每個(gè)售票處通過(guò)終端訪問系統(tǒng)的公共數(shù)據(jù)區(qū)。

售票處1begin從數(shù)據(jù)單元中取出現(xiàn)有余票；做減1操作；把結(jié)果送回到數(shù)據(jù)單元end;售票處2begin從數(shù)據(jù)單元中取出現(xiàn)有余票；做減1操作；把結(jié)果送回到數(shù)據(jù)單元end;假定現(xiàn)有余票為1執(zhí)行順序：（售票處1）從數(shù)據(jù)單元中取出現(xiàn)有余票；（售票處2）從數(shù)據(jù)單元中取出現(xiàn)有余票；（售票處1）做減1操作；（售票處1）把結(jié)果送回到數(shù)據(jù)單元；（售票處2）做減1操作；（售票處2）把結(jié)果送回到數(shù)據(jù)單元；結(jié)果是把一張票賣給了兩個(gè)顧客。

與時(shí)間有關(guān)的錯(cuò)誤產(chǎn)生的原因：多個(gè)進(jìn)程不受限制的對(duì)同一數(shù)據(jù)對(duì)象進(jìn)行存取操作。二、進(jìn)程的互斥

有共享資源的進(jìn)程執(zhí)行時(shí)出現(xiàn)與時(shí)間有關(guān)的錯(cuò)誤，其根本原因是對(duì)共享資源的使用不受限制。進(jìn)程交叉使用了共享資源從而造成了錯(cuò)誤。幾個(gè)基本概念

1、臨界資源一次僅允許一個(gè)進(jìn)程訪問的資源被稱為臨界資源

2、臨界區(qū)臨界區(qū)的定義：把在進(jìn)程中那段訪問臨界區(qū)的代碼稱為臨界區(qū)。對(duì)臨界區(qū)管理的要求：一次最多讓一個(gè)進(jìn)程進(jìn)入臨界區(qū)任何一個(gè)進(jìn)入臨界區(qū)的進(jìn)程必須在一個(gè)有限的時(shí)間內(nèi)退出臨界區(qū)。若有多個(gè)進(jìn)程同時(shí)要求進(jìn)入它們的臨界區(qū)，則應(yīng)在有限的時(shí)間內(nèi)讓其中之一進(jìn)入。處理臨界區(qū)的原則：1、當(dāng)無(wú)進(jìn)程處于臨界區(qū)時(shí)，允許一進(jìn)程立即進(jìn)入臨界區(qū)2、當(dāng)某一進(jìn)程已進(jìn)入臨界區(qū)時(shí)，其它試圖進(jìn)入臨界區(qū)進(jìn)程必須等待3、當(dāng)某已進(jìn)程離開臨界區(qū)時(shí)，若有進(jìn)程等待，則允許其中之一進(jìn)入臨界區(qū)4、當(dāng)進(jìn)程不能進(jìn)入臨界區(qū)時(shí)，應(yīng)立即釋放處理機(jī)，避免忙等。對(duì)臨界資源同時(shí)提出訪問請(qǐng)求的諸進(jìn)程的執(zhí)行要加以限制，以防止上述“與時(shí)間有關(guān)的錯(cuò)誤”。這種對(duì)臨界資源的排它訪問稱為互斥。

早期的研究結(jié)果表明，互斥問題的解決并不是一件很簡(jiǎn)單的事情。解決互斥問題的軟件方法假設(shè)有兩個(gè)進(jìn)程Pi和Pj，共享一個(gè)臨界資源R。方法一：設(shè)置一公用整型變量turn，用于指示被允許進(jìn)入臨界區(qū)的進(jìn)程的編號(hào)。repeatwhiletern<>idonoop;進(jìn)入臨界區(qū)turn=j;untilfalse;repeatwhiletern<>jdonoop;進(jìn)入臨界區(qū)turn=i;untilfalse;該方法可以確保每次只允許一個(gè)進(jìn)程進(jìn)入臨界區(qū)，但不符合處理臨界區(qū)的原則1，易造成資源利用不充分。方法二：基本思想：在每一個(gè)進(jìn)程訪問臨界資源之前，先查看一下臨界資源是否正被訪問。若正被訪問，則進(jìn)程等待；否則進(jìn)入自己的臨界區(qū)。為此，設(shè)置一個(gè)數(shù)組flag，每個(gè)元素的初值為false，表示進(jìn)程未進(jìn)入臨界區(qū)，進(jìn)程進(jìn)入臨界區(qū)后，相應(yīng)標(biāo)志位置為true。repeatwhileflag[j]donoop;flag[i]=true；進(jìn)入臨界區(qū)flag[i]=false;untilfalse;repeatwhileflag[i]donoop;flag[j]=true；進(jìn)入臨界區(qū)flag[j]=false;untilfalse;方法二可以滿足原則1，但又出現(xiàn)了新的問題。比如，當(dāng)Pi和Pj幾乎在同時(shí)都要求進(jìn)入臨界區(qū)，因而都發(fā)現(xiàn)對(duì)方的訪問標(biāo)志為false，于是兩進(jìn)程都先后進(jìn)入臨界區(qū)，顯然，這不符合臨界區(qū)處理的原則2。為了解決這個(gè)問題，把標(biāo)志位的含義改變?yōu)椋簍rue表示進(jìn)程希望進(jìn)入臨界區(qū)，即當(dāng)進(jìn)程要進(jìn)入臨界區(qū)前，先將標(biāo)志位flag置為true，表示進(jìn)程已要求進(jìn)入臨界區(qū)，然后再去查看另一進(jìn)程的標(biāo)志，若另一進(jìn)程的flag標(biāo)志也為true，則本進(jìn)程等待，否則，本進(jìn)程進(jìn)入臨界區(qū)。換句話說(shuō)，進(jìn)程要進(jìn)入臨界區(qū)，首先設(shè)置其要求進(jìn)入的標(biāo)志，然后，再去查看其他進(jìn)程的標(biāo)志。方法三：repeatflag[i]=true；whileflag[j]donoop;進(jìn)入臨界區(qū)flag[i]=false;untilfalse;repeatflag[j]=true；whileflag[i]donoop;進(jìn)入臨界區(qū)flag[j]=false;untilfalse;該方法可以有效地防止兩個(gè)進(jìn)程同時(shí)進(jìn)入臨界區(qū)，但仔細(xì)分析又可看出，該方法可能會(huì)造成兩個(gè)進(jìn)程都不能進(jìn)入臨界區(qū)的后果。例如，當(dāng)兩個(gè)進(jìn)程同時(shí)要求進(jìn)入臨界區(qū)，分別將自己的標(biāo)志位置為true，再去查看另一進(jìn)程的標(biāo)志，發(fā)現(xiàn)也為true，于是都等待，誰(shuí)也無(wú)法進(jìn)入臨界區(qū)。方法四：repeatflag[i]=true；turn=j;while[flag[j]andturn=jdonoop;進(jìn)入臨界區(qū)flag[i]=false;untilfalse;假如進(jìn)程Pi和Pj幾乎同時(shí)要求進(jìn)入臨界區(qū)，它們分別將flag[i}]和flag[j]置為true。Pi先將turn置為j，當(dāng)它執(zhí)行while語(yǔ)句時(shí)，條件成立，故等待。但Pj會(huì)立即將turn置為i，這樣Pi就可以進(jìn)入臨界區(qū)。Pi退出臨界區(qū)時(shí)會(huì)將flag[i]置為false，從而可以使Pj進(jìn)入臨界區(qū)。利用軟件方法解決互斥問題有一定難度，在使用同一資源的進(jìn)程數(shù)量較大時(shí)，有很大的局限性。另外一種解決互斥問題的方法是鎖機(jī)制。為臨界資源設(shè)置一個(gè)鎖w，當(dāng)進(jìn)程在進(jìn)入臨界區(qū)之前，首先測(cè)試w的狀態(tài)。w等于1表示上鎖，該資源已被占用；w等于0表示開鎖，該資源已空閑，未被占用。Lockw:L:ifw=1thengotoLelsew:=1Unlockw:w:=0;軟件的解決方法四和鎖機(jī)制雖然可以在一定程度上解決互斥問題，但進(jìn)程在等待時(shí)都需要不停地進(jìn)行測(cè)試。這不滿足處理臨界區(qū)的原則4，降低了系統(tǒng)工作效率。信號(hào)量同步機(jī)制

一個(gè)信號(hào)量可以看成由兩個(gè)部分組成：一個(gè)是整型變量，另一個(gè)是隊(duì)列。整型變量隊(duì)列ProcedureP(VarS:Semaphore)beginS:=S–1;ifS<0thenW(S)end;ProcedureV(VarS:Semaphore)beginS:=S+1;ifS<=0thenR(S)end;P、V操作是原語(yǔ)操作，即它們的執(zhí)行是不可中斷的。

相應(yīng)地，信號(hào)量的P、V操作可以被描述如下：W(S)：將當(dāng)前進(jìn)程掛起在信號(hào)量等待隊(duì)列上R(S)：從信號(hào)量等待隊(duì)列上喚醒一個(gè)等待進(jìn)程臨界區(qū)的管理一般形式：

進(jìn)程Abegin…P（S）;臨界區(qū)；V（S）…end;進(jìn)程Bbegin…P（S）;臨界區(qū)；V（S）…end;P、V操作必須合理使用，否則可能造成由于交叉使用資源而引發(fā)的錯(cuò)誤。用P、V操作實(shí)現(xiàn)進(jìn)程的互斥①用P、V操作實(shí)現(xiàn)車輛觀察系統(tǒng)的互斥將S定義為一個(gè)信號(hào)量，初值為1ProcessObserverbeginL:observealorry;P(S);count:=count+1;V(S);gotoLend;ProcessReportbeginP(S);printcount;count:=0;V(S)end;錯(cuò)誤方式1：ProcessObserverbeginL:P(S);

observealorry;count:=count+1;V(S);gotoLend;降低了進(jìn)程的并發(fā)程度錯(cuò)誤方式2：ProcessObserverbeginL:observealorry;P(S);count:=count+1;

gotoL；V(S)end;將造成系統(tǒng)癱瘓。②用P、V操作實(shí)現(xiàn)售票系統(tǒng)的互斥

將S定義為信號(hào)量，初值為1，余票的數(shù)量值放在整型變量A中。PROCESSPir:integer;beginP(S);r:=A;ifr>=1thenbeginr:=r–1;A:=r;V(S);{售出一張票};endelse{售出票已售完};end；PROCESSPir:integer;beginP(S);r:=A;ifr>=1thenbeginr:=r–1;A:=r;V(S);{售出一張票};endelsebeginV(S);{售出票已售完}endend；無(wú)法退出臨界區(qū)③讀者寫者問題：規(guī)定：允許多個(gè)進(jìn)程同時(shí)讀；只允許一個(gè)進(jìn)程寫；當(dāng)有進(jìn)程讀時(shí)不允許其它進(jìn)程寫。第一種方案：定義信號(hào)量：S:semaphore；初值1；定義一個(gè)整數(shù)：rs，初值0；

讀者：PROCESSReaderibeginrs:=rs+1;ifrs=1thenP(S);readfileF;rs:=rs–1;ifrs=0thenV(S);end;寫者：PROCESSWriterjbeginP(S);writefileF;V(S);end;問題：對(duì)共享變量rs訪問的程序段也是臨界區(qū)。

改進(jìn)的方案：定義信號(hào)量：S,Sr:semaphore；分別為互斥訪問文件和計(jì)數(shù)變量的信號(hào)量，初值均為1；定義一個(gè)整數(shù)：rs，初值0；讀者：PROCESSReaderbeginP(Sr);rs:=rs+1;ifrs=1thenP(S);V(Sr);readfileF;P(Sr);rs:=rs–1;ifrs=0thenV(S);V(Sr);end;寫者：PROCESSWriterbeginP(S);writefileF;V(S);end;例題：試用P、V操作寫出讀者優(yōu)先的同步算法。解答：定義兩個(gè)變量RC和WC，分別用于對(duì)進(jìn)入臨界區(qū)的讀者和寫者進(jìn)程計(jì)數(shù)。為了互斥的操作這兩個(gè)變量，需設(shè)置兩個(gè)相應(yīng)的信號(hào)量RCS和WCS。為了使讀者-寫者之間和寫者-寫者之間互斥的訪問緩沖區(qū)，設(shè)置信號(hào)量S。為了阻止讀者進(jìn)程和鏈接等待的寫者進(jìn)程，設(shè)置信號(hào)量W。為了鏈接等待的讀者進(jìn)程，設(shè)置信號(hào)量R。這樣，當(dāng)有第一個(gè)寫者進(jìn)程進(jìn)入臨界區(qū)后，所有的試圖進(jìn)入臨界區(qū)的讀者進(jìn)程將被阻塞在信號(hào)量R上，而寫者進(jìn)程將優(yōu)先進(jìn)入臨界區(qū)。讀者：PROCESSReaderbeginP(R);P(W);P(RCS);ifRC=0thenP(S);RC:=RC+1;V(RCS);V(W);V(R);readfileF;P(RCS);RC:=RC–1;ifRC=0thenV(S);V(RCS);end;寫者：PROCESSWriterbeginP(WCS);ifWC:=0thenP(W);WC:=WC+1;V(WCS);P(S);writefileF;V(S);P(WCS);WC:=WC–1;ifWC=0thenV(W);V(WCS);end;R:=W:=RCS:=WCS:=S:=1;RC:=WC:=0;例題：舉例說(shuō)明P、V操作為什么要被設(shè)計(jì)成原語(yǔ)（即對(duì)同一信號(hào)量上的操作必須互斥）。解答：對(duì)于P操作，過(guò)程為：ProcedureP(VarS:Semaphore)beginS:=S–1;ifS<0thenW(S)end;假如有兩個(gè)進(jìn)程P1、P2幾乎在同時(shí)作P操作，信號(hào)量S的初值為1。如果進(jìn)程P1先作P操作，則S的值為0，P1進(jìn)程不應(yīng)被阻塞（或掛起）。但是，如果P操作不是原語(yǔ)操作，則可能有如下執(zhí)行順序：P1：S:=S-1P2：S:=S-1P1：ifS<0thenW(S)由于此時(shí)S為–1，P1將被阻塞，這樣，P操作就不符合原來(lái)的語(yǔ)義了。同樣，對(duì)于V操作，過(guò)程為：ProcedureV(VarS:Semaphore)beginS:=S+1;ifS<=0thenR(S)end;假如有兩個(gè)進(jìn)程P1、P2幾乎在同時(shí)作V操作，信號(hào)量S的初值為-1。如果進(jìn)程P1先作V操作，則S的值為0，該V操作應(yīng)該喚醒一個(gè)被P操作阻塞的進(jìn)程。但是，如果V操作不是原語(yǔ)操作，則可能有如下執(zhí)行順序：P1：S:=S+1P2：S:=S+1P1：ifS<=0thenR(S)由于此時(shí)S為1，P1所作的V操作將不再去喚醒被阻塞的進(jìn)程，這樣，V操作就不符合原來(lái)的語(yǔ)義了。

另外，如果在P操作過(guò)程中插入了V操作，也會(huì)出現(xiàn)不符合語(yǔ)義的情況。例如，假定S的值為0，按照P操作的語(yǔ)義，作P操作的進(jìn)程應(yīng)該被阻塞，但是，如果有如下執(zhí)行順序：A進(jìn)程的P操作語(yǔ)句：S:=S-1B進(jìn)程的V操作語(yǔ)句：S:=S+1A進(jìn)程的P操作語(yǔ)句：ifS<0thenW(S)

則作P操作的進(jìn)程將不會(huì)被阻塞，這不符合語(yǔ)義。三、進(jìn)程的同步

協(xié)作

buffer1buffer2輸入設(shè)備打印設(shè)備輸入進(jìn)程計(jì)算進(jìn)程打印進(jìn)程P1P2P3這里，計(jì)算進(jìn)程C和打印進(jìn)程P的工作必須相互協(xié)作：計(jì)算進(jìn)程只有在緩沖區(qū)中無(wú)數(shù)據(jù)時(shí)才能向其寫入數(shù)據(jù)；打印進(jìn)程只有在緩沖區(qū)中已有數(shù)據(jù)時(shí)才能將從中取出并打印。兩個(gè)進(jìn)程應(yīng)做如下協(xié)作1、進(jìn)程C把一個(gè)記錄存入緩沖區(qū)后，應(yīng)向進(jìn)程P發(fā)送“緩沖區(qū)中有等待處理的記錄”的消息；2、進(jìn)程P從緩沖區(qū)取出記錄后，應(yīng)向進(jìn)程C發(fā)送“緩沖區(qū)中的記錄已取走”的消息；3、進(jìn)程C只有在得到進(jìn)程P發(fā)送來(lái)的“緩沖區(qū)中的記錄已取走”的消息后，才能把下一個(gè)記錄存入緩沖區(qū)，否則，進(jìn)程C等待，直到消息到達(dá)；4、進(jìn)程P只有在得到進(jìn)程C發(fā)送來(lái)的“緩沖區(qū)中有等待處理的記錄”的消息后，才能從緩沖區(qū)取出記錄，否則，進(jìn)程P等待，直到消息到達(dá)。buffer1buffer2輸入設(shè)備打印設(shè)備輸入進(jìn)程計(jì)算進(jìn)程打印進(jìn)程P1P2P3PROCESScalculatorbeginL1:P(SB);計(jì)算下一個(gè)數(shù)據(jù)并送入緩沖區(qū);V(SA);gotoL1;end;PROCESSprinterbeginL2:P(SA);從緩沖區(qū)中取出數(shù)據(jù)并打印;V(SB);gotoL2;end;同步機(jī)制調(diào)用P操作測(cè)試消息是否到達(dá)調(diào)用V操作發(fā)送消息生產(chǎn)者-消費(fèi)者問題簡(jiǎn)單的生產(chǎn)者、消費(fèi)者問題（單緩沖區(qū)）定義：整型變量：Buffer，信號(hào)量：SP=1,SG=0

PROCESSProducerbeginL1:produceaproduct;P(SP);Buffer:=product;V(SG);gotoL1endPROCESSConsumerbeginL2:P(SG);TakeaproductformBuffer;V(SP);gotoL2end多緩沖區(qū)生產(chǎn)者、消費(fèi)者問題PROCESSProducerbeginL1:produceaproduct;P(SP);B[k]:=product;k:=(k+1)modn;V(SG);gotoL1endPROCESSConsumerbeginL2:P(SG);TakeaproductformB[t];t:=(t+1)modnV(SP);consumer;gotoL2end定義：整型變量：k=0,t=0整型數(shù)組：B[0…n-1]信號(hào)量：SP=n,SG=0例子：三個(gè)進(jìn)程R、W1、W2，共享一個(gè)緩沖區(qū)B，B中最多只能存放一個(gè)數(shù)。進(jìn)程R負(fù)責(zé)不斷地向B中存入整數(shù)，進(jìn)程W1、W2分別負(fù)責(zé)取出B中的奇數(shù)和偶數(shù)并進(jìn)行打印。PROCESSRx:integer;beginL1:{從輸入設(shè)備中讀入一個(gè)數(shù)};x:=讀入的數(shù)；P(S);B:=x;ifB=奇數(shù)thenV(SO)elseV(SE)gotoL1;endPROCESSW1y:integer;beginL2:P(SO);y:=B；V(S);{打印y中數(shù)}；gotoL2;endPROCESSW2z:integer;beginL3:P(SE);z:=B；V(S);{打印z中數(shù)}；gotoL3;end定義信號(hào)量：S初值為1表示初始時(shí)緩沖區(qū)可用SO初值為0用于向打印奇數(shù)的進(jìn)程發(fā)消息SE初值為0用于向打印偶數(shù)的進(jìn)程發(fā)消息四、同步與互斥的混合問題

例子：有m個(gè)生產(chǎn)者和r個(gè)消費(fèi)者共享容量為n的緩沖器（m、r、n均大于1）。每個(gè)生產(chǎn)者把自己生產(chǎn)的物品存入緩沖區(qū)，每個(gè)消費(fèi)者從緩沖區(qū)中取出物品去消費(fèi)。要求用P、V操作對(duì)這些生產(chǎn)者和消費(fèi)者進(jìn)行正確管理。定義：整型數(shù)組：B[0…n-1]整型變量：k，t初值均為0信號(hào)量：S1：初值1用于生產(chǎn)者放入物品S2：初值1用于消費(fèi)者取出物品SP：初值n緩沖區(qū)是否可用SG：初值0緩沖區(qū)里是否有物品PROCESSPibeginL1:produceaproduct;P(SP);P(S1);B[k]:=product;k:=(k+1)modn;V(S1);V(SG);gotoL1endPROCESSCjbeginL2:P(SG);P(S2);takeaproductfromB[t];t:=(t+1)modn;V(S2);V(SP);consume;gotoL1end生產(chǎn)者分別向緩沖區(qū)送產(chǎn)品，由S1控制互斥訪問。消費(fèi)者分別從緩沖區(qū)中取出產(chǎn)品，由S2控制互斥訪問。例子：現(xiàn)有四個(gè)進(jìn)程R1、R2、W1、W2，它們共享一個(gè)可以存放一個(gè)數(shù)的緩沖器B，R1、R2從鍵盤和磁盤上讀入數(shù)據(jù)，放到緩沖器B中，W1、W2從緩沖器中分別讀取R1，R2寫入的數(shù)據(jù)并輸出打印。怎樣用P、V操作來(lái)協(xié)調(diào)四個(gè)進(jìn)程的并發(fā)執(zhí)行？定義：信號(hào)量S初值為1用于寫入進(jìn)程的互斥S1初值為0R1向W1發(fā)送消息S2初值為0R2向W2發(fā)送消息整型變量BPROCESSR1x:integerbeginL1:{接受來(lái)自鍵盤的數(shù)}；x:=接受的數(shù);P(S);B:=x;V(S1);gotoL1endPROCESSR2y:integerbeginL2:{從磁盤上讀一個(gè)數(shù)}；y:=讀入的數(shù);P(S);B:=y;V(S2);gotoL2endPROCESSW1k:integerbeginL4:P(S1);k:=B;V(S);{打印k中的數(shù)}；gotoL3endPROCESSW2j:integerbeginL4:P(S2);j:=B;V(S);{打印k中的數(shù)}；gotoL3end例題：假定一個(gè)閱覽室最多可以同時(shí)容納100個(gè)人閱讀，，讀者進(jìn)入和離開閱覽室時(shí)，都必須在閱覽室門口的一個(gè)登記表上登記或去掉登記。試用P、V操作編寫讀者進(jìn)程的同步算法。分析：設(shè)讀者有任意多個(gè)，但能同時(shí)閱覽的只能100人，所以，設(shè)一個(gè)信號(hào)量S代表空座位數(shù)目，初值為100，用它來(lái)控制進(jìn)入閱覽室的讀者進(jìn)程不超過(guò)100。另設(shè)信號(hào)量m，用于控制對(duì)登記表這一共享資源的互斥使用，其初值為1。Process第i個(gè)讀者進(jìn)程beginP(S);P(m);填寫登記表；V(m);坐下閱覽;P(m);在登記表上去掉登記；V(m);V(S);gotoL1;end例題：有一個(gè)倉(cāng)庫(kù)存放兩種零件A和B，最大庫(kù)容量各為M個(gè)。有一車間不斷的取A和B進(jìn)行裝配，每次各取一個(gè)。有兩組供應(yīng)商分別不斷的供應(yīng)A和B（每次供應(yīng)一個(gè)）。為保證配套和合理庫(kù)存，當(dāng)某種零件的數(shù)量比另一種的數(shù)量超過(guò)n（n<M）個(gè)時(shí)，暫停對(duì)數(shù)量大的零件的進(jìn)貨，只補(bǔ)充數(shù)量少的零件。試用P、V操作正確地實(shí)現(xiàn)之。分析：這里除了生產(chǎn)者-消費(fèi)者這一對(duì)控制關(guān)系外，還增加了生產(chǎn)者之間的相互制約關(guān)系。這種相互制約關(guān)系需要另外設(shè)置信號(hào)量來(lái)實(shí)現(xiàn)。解答：信號(hào)量初值S1實(shí)現(xiàn)存取零件的互斥aval_am零件A的庫(kù)存容量aval_bm零件B的庫(kù)存容量full_a0零件A的可用數(shù)量full_b0零件B的可用數(shù)量san控制零件B是否超過(guò)零件An個(gè)sbn控制零件A是否超過(guò)零件Bn個(gè)A零件供應(yīng)商的進(jìn)程B零件供應(yīng)商的進(jìn)程生產(chǎn)車間的進(jìn)程beginL1:P(aval_a);P(sa);P(S);storeA;V(full_a);V(sb);V(S);gotoL1:endbeginL2:P(aval_b);P(sb);P(S);storeB;V(full_b);V(sa);V(S);gotoL2:endbeginL3:P(full_a);P(full_b);P(S);takeAandB;V(aval_a);V(aval_b);V(S);gotoL3:end例題：當(dāng)進(jìn)程X和進(jìn)程Y共享某個(gè)資源r，進(jìn)程并發(fā)執(zhí)行時(shí)的程序如下(信號(hào)量S的初值為1)：請(qǐng)回答：1、兩個(gè)進(jìn)程并發(fā)執(zhí)行時(shí)，能否保證互斥使用資源，為什么？2、如果要使兩個(gè)進(jìn)程交替使用資源，若仍使用P、V操作來(lái)進(jìn)行管理，寫出應(yīng)定義的信號(hào)量及其初值；3、修改上述程序，使兩個(gè)進(jìn)程能交替使用資源；ProcessXbeginL1:P(S);使用資源r;V(S);gotoL1;endProcessYbeginL2:P(S);使用資源r;V(S);gotoL2;end1、能保證互斥使用資源。因?yàn)樵趦蓚€(gè)進(jìn)程中“使用資源r”都作為臨界區(qū)，由P(S)和V(S)操作保證了互斥執(zhí)行，S的初值定義為1，符合要求；2、要使兩個(gè)進(jìn)程交替使用資源，僅僅保證互斥使用資源是不夠的，必須使兩個(gè)進(jìn)程互相等待、互相通知。為此，必須定義新的信號(hào)量來(lái)實(shí)現(xiàn)進(jìn)程的同步通信。這里定義信號(hào)量S1和S2，假定進(jìn)程X先使用資源，那么S1的初值定義為1，S2的初值定義為0。S1和S2的使用可以保證互斥，所以原來(lái)的信號(hào)量S可以不要；3、兩個(gè)進(jìn)程可以改寫為：ProcessXbeginL1:P(S1);使用資源r;V(S2);gotoL1;endProcessYbeginL2:P(S2);使用資源r;V(S1);gotoL2;endS1:semaphore:=1;S2:semaphore:=0;例題：假定三個(gè)進(jìn)程間的同步算法如下，其中S1、S2、S3的初值都是1。問：算法在什么情況下會(huì)發(fā)生死鎖。ProcessAbeginP(S1);P(S2);......V(S2);V(S1);endProcessBbeginP(S2);P(S3);......V(S3);V(S2);endProcessCbeginP(S3);P(S1);......V(S1);V(S3);end假定出現(xiàn)了如下的進(jìn)程執(zhí)行順序：進(jìn)程A執(zhí)行P(S1)，進(jìn)程B執(zhí)行P(S2)，進(jìn)程C執(zhí)行P(S3)，進(jìn)程A執(zhí)行P(S2)，進(jìn)程B執(zhí)行P(S3)，進(jìn)程C執(zhí)行P(S1)，即A、B、C都在試圖執(zhí)行各自第二個(gè)P操作。此時(shí)，A阻塞在S2，B阻塞在S3，C阻塞在S1，它們都等待其它進(jìn)程釋放相應(yīng)的信號(hào)量，處于相互等待和循環(huán)等待的狀態(tài)，此時(shí)就是死鎖。其它控制同步與互斥的機(jī)制1、信號(hào)量集在某些應(yīng)用場(chǎng)合，一個(gè)進(jìn)程可能要訪問多個(gè)臨界資源，比如同時(shí)申請(qǐng)輸入和打印設(shè)備。相應(yīng)的描述如下：ProcessAbeginP(Si);P(So);......V(Si);V(So);endProcessBbeginP(So);P(Si);......V(So);V(Si);end仔細(xì)分析一下可以看出，這樣互斥使用臨界資源可能造成死鎖。另外，在前述的信號(hào)量機(jī)制中，P、V操作僅能對(duì)信號(hào)量施以加1或減1操作，即每次只能獲得或釋放一個(gè)單位的臨界資源。當(dāng)一次需要N個(gè)某類資源時(shí)，便需要進(jìn)行N次操作。顯然這是低效的。信號(hào)量集機(jī)制的基本思想是：將進(jìn)程在整個(gè)運(yùn)行過(guò)程中所需要的所有臨界資源一次性地全部分配給進(jìn)程，待該進(jìn)程使用完后一次性的釋放。亦即，對(duì)若干個(gè)臨界資源的分配，采取原子操作方式。所謂“and信號(hào)量集”的思想是：將進(jìn)程所需要的所有臨界共享資源一次全部分配給它，待其使用完后再一起釋放。只要有一個(gè)資源不能獲得，其他資源也都不分配給它。這種同步機(jī)制稱為“同時(shí)P操作”（SP）同時(shí)P操作定義如下：ProcedureSP(S1,…，Sn)Beginif(S1>=1and...andSn>=1)fori:=1tondoSi:=Si–1;else將當(dāng)前執(zhí)行進(jìn)程插入到Si的等待隊(duì)列，Si是第一個(gè)滿足Si<1的信號(hào)量，程序計(jì)數(shù)器設(shè)為P操作的開始；end;同時(shí)V操作定義如下：ProcedureV(S1,...,Sn)beginfori:=1tondoSi:=Si+1;喚醒Si等待隊(duì)列上的所有等待進(jìn)程，將它們插入到就緒隊(duì)列中。end;采用同步信號(hào)量集描述同時(shí)申請(qǐng)輸入和打印設(shè)備的進(jìn)程如下：ProcessAbeginSP(Si，So);......SV(Si，So);endProcessBbeginSP(So，Si);......SV(So，Si);end

此外，在有些情況下，當(dāng)資源數(shù)量低于某一下限值時(shí)，便不予分配。因而在每次分配前都必須測(cè)試資源的數(shù)量是否滿足要求?；谏鲜鰞牲c(diǎn)，可以對(duì)信號(hào)量機(jī)制作進(jìn)一步擴(kuò)充，形成一般的信號(hào)量集機(jī)制。滿足最低要求的資源數(shù)量為ti，請(qǐng)求分配的資源數(shù)量為di。ProcedureP(S1,t1,d1,...,Sn,tn,dn)beginif(S1>=t1and...andSn>=tn)fori:=1tondoSi:=Si–di;else將當(dāng)前執(zhí)行進(jìn)程插入到Si的等待隊(duì)列，Si是第一個(gè)滿足Si<ti的信號(hào)量，程序計(jì)數(shù)器設(shè)為P操作的開始；end;ProcedureV(S1,d1,...,Sn,dn)beginfori:=1tondoSi:=Si+di;喚醒Si等待隊(duì)列上的所有等待進(jìn)程，將它們插入到就緒隊(duì)列中。end;信號(hào)量集幾種特殊情況的討論：(1)P(S,d,d)，此時(shí)在信號(hào)量集中只有一個(gè)信號(hào)量，但它允許每次申請(qǐng)d個(gè)資源，當(dāng)現(xiàn)有資源數(shù)少于d時(shí)，不予分配；(2)P(S,1,1)，此時(shí)的信號(hào)量集已蛻化為一般的信號(hào)量（S>1）或互斥信號(hào)量（S=1）;(3)P(S,1,0)，這是一種很特殊且很有用的信號(hào)量。當(dāng)S>=1時(shí)，允許多個(gè)進(jìn)程進(jìn)入某特定區(qū)，當(dāng)S變?yōu)?后，將阻止任何進(jìn)程進(jìn)入特定區(qū)。換言之，它相當(dāng)于一個(gè)可控開關(guān)。2、管程信號(hào)量機(jī)制的一個(gè)特點(diǎn)是：在每個(gè)并發(fā)進(jìn)程中都要設(shè)置大量的同步操作原語(yǔ)，同步控制部分分散在各個(gè)進(jìn)程中。這不僅給編程帶來(lái)了麻煩，而且如果P、V操作不當(dāng)還可能會(huì)導(dǎo)致數(shù)據(jù)的不確定性和系統(tǒng)的死鎖。Dijkstra認(rèn)為應(yīng)把各進(jìn)程中與同一共享數(shù)據(jù)有關(guān)的同步控制和同步處理集中起來(lái)，構(gòu)成獨(dú)立于進(jìn)程的實(shí)體。系統(tǒng)中的各種硬件資源和軟件資源均可用數(shù)據(jù)結(jié)構(gòu)抽象地描述，既用少量信息和對(duì)該資源所執(zhí)行的操作來(lái)表征該資源，而忽略它們的內(nèi)部結(jié)構(gòu)和實(shí)現(xiàn)細(xì)節(jié)。當(dāng)共享資源用共享數(shù)據(jù)來(lái)表示時(shí)，資源管理程序可以用對(duì)該數(shù)據(jù)結(jié)構(gòu)進(jìn)行操作的一組過(guò)程來(lái)表示。我們把這樣一組相關(guān)的數(shù)據(jù)結(jié)構(gòu)和過(guò)程稱為管程。Hansen為管程下的定義是：一個(gè)管程定義了一個(gè)數(shù)據(jù)結(jié)構(gòu)和能為并發(fā)進(jìn)程所執(zhí)行的（在該數(shù)據(jù)結(jié)構(gòu)上的）一組操作，這種操作能同步進(jìn)程和改變管程中的數(shù)據(jù)。管程的組成：局部于管程的共享數(shù)據(jù)說(shuō)明對(duì)該數(shù)據(jù)結(jié)構(gòu)進(jìn)行操作的一組過(guò)程對(duì)局部于管程的數(shù)據(jù)的初始化語(yǔ)句在管程的實(shí)現(xiàn)中必須考慮：互斥：當(dāng)幾個(gè)進(jìn)程調(diào)用管程時(shí)，僅允許一個(gè)進(jìn)程進(jìn)入管程，其它調(diào)用者必須等待。同步：在管程中必須設(shè)置兩個(gè)同步操作原語(yǔ)wait和signal。當(dāng)進(jìn)程通過(guò)管程請(qǐng)求訪問某共享數(shù)據(jù)而未能滿足時(shí)，管程便調(diào)用wait原語(yǔ)使該進(jìn)程等待，并將它排在等待隊(duì)列上。僅當(dāng)另一進(jìn)程訪