操作系統PV題解第一章TheP,VTheorem在操作系統理論中有一個非常重要的概念叫做P,V原語。在我們研究進程間的互斥的時候經常會引入這個概念，將p,v操作方法與加鎖的方法相比較，來解決進程間的互斥問題。實際上，他的應用范圍很廣，他不但可以解決進程管理當中的互斥問題，而且我們還可以利用此方法解決進程同步與進程通信的問題。一IntroductionofP,VTheorem闡述P,V原語的理論不得不提到的一個人便是赫赫有名的荷蘭科學家E.W.Dijkstra。如果你對這位科學家沒有什么印象的話，提起解決圖論中最短路徑問題的Dijkstra算法應當是我們再熟悉不過的。P,V原語的概念以及P,V操作當中需要使用到的信號量的概念都是由他在1965年提出的。SomeConceptions信號量是最早出現的用來解決進程同步與互斥問題的機制，包括一個稱為信號量的變量及對它進行的兩個原語操作。信號量為一個整數，我們設這個信號量為：S。很顯然，我們規定在S大于等于零的時候代表可供并發進程使用的資源實體數，S小于零的時候，表示正在等待使用臨界區的進程的個數。根據這個原則，在給信號量附初值的時候，我們顯然就要設初值大于零。p操作和v操作是不可中斷的程序段，稱為原語。P,V原語中P是荷蘭語的Passeren，相當于英文的pass,V是荷蘭語的Verhoog,相當于英文中的incremnet。P原語操作的動作是：（1）S減1；（2）若S減1后仍大于或等于零，則進程繼續執行；（3）若S減1后小于零，則該進程被阻塞后進入與該信號相對應的隊列中，然后轉進程調度。V原語操作的動作是：（1）S加1；（2）若相加結果大于零，則進程繼續執行；（3）若相加結果小于或等于零，則從該信號的等待隊列中喚醒一等待進程，然后再返回原進程繼續執行或轉進程調度。需要提醒大家的是：P,V操作首先是一個原語操作，對于每一個進程來說，都只能進行一次。而且必須成對使用。且在P,V愿語執行期間不允許有中斷的發生。對于具體的實現，方法非常多，可以用硬件實現，也可以用軟件實現。這里不再贅述。TheMostImportantConceptions臨界資源是指每次僅允許一個進程訪問的資源。屬于臨界資源可以是硬件的打印機、磁帶機等,軟件的有消息緩沖隊列、變量、數組、緩沖區等。每個進程中訪問臨界資源的那段程序稱為臨界區（臨界資源是一次僅允許一個進程使用的共享資源）。每次只準許一個進程進入臨界區，該進程進入后不允許其他進程進入。

進程的同步和互斥互斥：是指某一資源同時只允許一個訪問者對其進行訪問，具有唯一性和排它性。但互斥無法限制訪問者對資源的訪問順序，即訪問是無序的。同步：是指在互斥的基礎上(大多數情況)，通過其它機制實現訪問者對資源的有序訪問。在大多數情況下，同步已經實現了互斥，特別是所有寫入資源的情況必定是互斥的。少數情況是指可以允許多個訪問者同時訪問資源。二SeveralTypicalExamples本節我們討論幾個利用信號量來實現進程互斥和同步的經典例子。這里的問題關鍵是如何選擇信號量和如何安排P、V原語的使用順序。依據信號量與進程的關系，我們可把進程中使用的信號量分成私有信號量和公用信號量。私有信號量是指只與制約進程和被制約進程有關的信號量；公用信號量是指與一組并發進程有關的信號量。這里請不要和C++、JAVA等編程語言的公有、私有相混淆。這里指的是相對于共享資源來說的。1生產者一消費者問題(producer-consumerproblem)生產者--消費者問題(producer-consumerproblem)是指若干進程通過有限的共享緩沖區交換數據時的緩沖區資源使用問題。問題描述：假設“生產者”進程不斷向共享緩沖區寫人數據(即生產數據)，而“消費者”進程不斷從共享緩沖區讀出數據(即消費數據)；共享緩沖區共有n個；任何時刻只能有一個進程可對共享緩沖區進行操作。所有生產者和消費者之間要協調，以完成對共享緩沖區的操作。Producer:ProducerMConsutner1生產捋休Producer:ProducerMConsutner1生產捋休悄費指針Figure1.1:producer-consumerproblem我們可把共享緩沖區中的n個緩沖塊視為共享資源，生產者寫人數據的緩沖塊成為消費者可用資源，而消費者讀出數據后的緩沖塊成為生產者的可用資源。為此，可設置三個信號量：full、empty和mutex。其中：full表示有數據的緩沖塊數目，初值是0；empty表示空的緩沖塊數初值是n；mutex用于訪問緩沖區時的互斥，初值是1。實際上，full和empty間存在如下關系：full+empty=NTheP,VcodeUsingPaScalbuffer:array[O..k-1]ofinteger;in,out:O..k-1;//in記錄第一個空緩沖區，out記錄第一個不空的緩沖區empty,full,mutex:semaphore;//empty控制緩沖區不滿,full控制緩沖區不空,mutex保護臨界區；〃初始化empty=k,full=0,mutex=1cobeginprocedureproducer:procedureconsumer:whiletruethenwhiletruethenbeginbeginproduce(&item);p(full);

p(empty);p(mutex);buffer[in]:=item;in:=(in+1)modk;p(empty);p(mutex);buffer[in]:=item;in:=(in+1)modk;v(mutex);v(full);endp(mutex);item:=buffer[out];out:=(out+1)modk;v(mutex);v(empty);consume(&item);endcoend注意：這里每個進程中各個P操作的次序是重要的。各進程必須先檢查自己對應的資源數在確信有可用資源后再申請對整個緩沖區的互斥操作；否則，先申請對整個緩沖區的互斥操后申請自己對應的緩沖塊資源，就可能死鎖。出現死鎖的條件是，申請到對整個緩沖區的互斥操作后，才發現自己對應的緩沖塊資源，這時已不可能放棄對整個緩沖區的占用。如果采用AND信號量集，相應的進入區和退出區都很簡單。如生產者的進入區為Swait(empty,mutex)，退出區為Ssignal(full，mutex)。2讀者--寫者問題(Readers-WritersProblem)問題描述：有一個許多進程共享的數據區，這個數據區可以是一個文件或者主存的一塊空間；有一些只讀取這個數據區的進程(Reader)和一些只往數據區寫數據的進程(Writer)，此外還需要滿足以下條件：(1)任意多個讀進程可以同時讀這個文件；(2)一次只有一個寫進程可以往文件中寫；(3)如果一個寫進程正在進行操作，禁止任何讀進程度文件。實驗要求用信號量來實現讀者寫者問題的調度算法。實驗提供了Semaphore類，該類通過P()、V()兩個方法實現了P、V原語的功能。實驗的任務是修改Reader類的Read方法以及Writer類的Write方法。我們需要分兩種情況實現該問題：讀優先：要求指一個讀者試圖進行讀操作時，如果這時正有其他讀者在進行操作，他可直接開始讀操作，而不需要等待。寫優先：一個讀者試圖進行讀操作時，如果有其他寫者在等待進行寫操作或正在進行寫操作，他要等待該寫者完成寫操作后才開始讀操作。TheP,VcodeUsingPaScal讀者優先算法：rwmutex用于寫者與其他讀者/寫者互斥的訪問共享數據rmutex用于讀者互斥的訪問readcount讀者計數器varrwmutex,rmutex：semaphore:=1,1；intreadcount=0;cobeginprocedurereader_ibegin//i=1,2,.P(rmutex);Readcount++;if(readcount==1)P(rwmutex);V(rmutex);讀數據；P(rmutex);Readcount--;if(readcount==0)V(rwmutex);V(rmutex);endprocedureWriter_jbegin//j=1,2,….P(rwmutex);寫更新；V(rwmutex);endcoendTheP,VcodeUsingPaScal寫者優先：多個讀者可以同時進行讀寫者必須互斥(只允許一個寫者寫，也不能讀者寫者同時進行)寫者優先于讀者(一旦有寫者，則后續讀者必須等待，喚醒時優先考慮寫者)如果讀者數是固定的，我們可采用下面的算法：rwmutex：用于寫者與其他讀者/寫者互斥的訪問共享數據rmutex：該信號量初始值設為10，表示最多允許10個讀者進程同時進行讀操作varrwmutex,rmutex：semaphore:=1,10；cobeginprocedurereader_ibegin//i=1,2,….P(rwmutex);//讀者、寫者互斥P(rmutex);V(rwmutex);//釋放讀寫互斥信號量，允許其它讀、寫進程訪問資源讀數據；V(rmutex);endprocedureWriter_jbegin//j=1,2,….P(rwmutex);for(i=1;i<=10;i++)P(rmutex);//禁止新讀者，并等待已進入的讀者退出寫更新；for(i=1;i<=10;i++)V(rmutex);//恢復允許rmutex值為10V(rwmutex);endcoend問題擴展如果讀者寫者均是平等的即二者都不優先，如何實現?哲學家進餐問題(TheDiningPhilosophersProblem)Figure1.2:TheDiningPhilosophersProblem問題描述：(由Dijkstra首先提出并解決)5個哲學家圍繞一張圓桌而坐，桌子上放著5支筷子，每兩個哲學家之間放一支；哲學家的動作包括思考和進餐，進餐時需要同時拿起他左邊和右邊的兩支筷子，思考時則同時將兩支筷子放回原處。如何保證哲學家們的動作有序進行？如：不出現相鄰者同時要求進餐；不出現有人永遠拿不到筷子；TheP,VcodeUsingPajcal解法一：semaphoreFork[i]:=1(i=0,1,2,3,4)beginThiking;Beinghangery;P(Fork[imod5]);p(Fork[(i+1)mod5]);Eating;v(Fork[imod5]);v(Fork[(i+1)mod5]);end解法二：semaphorec[0]c[4]初值均為1；Integeri=0,1,...,4;procedurephilosopher」beginifimod2==0thenbeginp(c[i]);p(c[i+1]mod5);Eating;v(c[i]);v(c[i+1]mod5);endelsebeginp(c[i+1]mod5);p(c[i]);Eating;v(c[i+1]mod5);v(c[i]);endend理發師問題(BarberProblem)問題描述：理發店理有一位理發師、一把理發椅和n把供等候理發的顧客坐的椅子如果沒有顧客，理發師便在理發椅上睡覺一個顧客到來時，它必須叫醒理發師如果理發師正在理發時又有顧客來到，則如果有空椅子可坐，就坐下來等待，否則就離開。TheP,VcodeUsingPascal控制變量waiting用來記錄等候理發的顧客數，初值均為0；信號量customers用來記錄等候理發的顧客數，并用作阻塞理發師進程，初值為0；信號量barbers用來記錄正在等候顧客的理發師數，并用作阻塞顧客進程，初值為0；信號量mutex用于互斥，初值為1intwaiting=0；//等候理發的顧客數intchairs=n；//為顧客準備的椅子數semaphorecustomers=0,barbers=0,mutex=1;cobeginbarber()beginwhile(TRUE);//理完一人,還有顧客嗎?P(cutomers);//若無顧客,理發師睡眠P(mutex);//進程互斥waiting:=waiting-1;〃等候顧客數少一個V(barbers);//理發師去為一個顧客理發V(mutex);//開放臨界區cut-hair();//正在理發endcustomer()beginP(mutex);//進程互斥if(waiting)beginwaiting:=waiting+1;//等候顧客數加1V(customers);//必要的話喚醒理發師V(mutex);//開放臨界區P(barbers);//無理發師,顧客坐著養神get-haircut();//一個顧客坐下等理/endelseV(mutex);//人滿了,走吧!endcoend吸煙者問題(SmokerProblem)問題描述：三個吸煙者在一間房間內，還有一個香煙供應者。為了制造并抽掉香煙，每個吸煙者需要三樣東西：煙草、紙和火柴。供應者有豐富的貨物提供。三個吸煙者中，第一個有自己的煙草，第二個有自己的紙，第三個有自己的火柴。供應者將兩樣東西放在桌子上，允許一個吸煙者進行對健康不利的吸煙。當吸煙者完成吸煙后喚醒供應者，供應者再放兩樣東西(隨機地)在桌面上，然后喚醒另一個吸煙者。試為吸煙者和供應者編寫程序解決問題。問題分析：供應者seller隨即產生兩樣東西，提供它們，這里用普通變量來表示吸煙者進程smoker根據其排號不同，擁有不同的一件東西。假設1號吸煙者擁有煙草tobacco，2號吸煙者擁有紙paper,3號吸煙者擁有火柴match。其他號碼錯誤返回。吸煙者的序號代表他們擁有的東西，用他們的序號和供應者產生的兩樣東西比較，如果都不相等，則說明他擁有的東西和供應者產生的東西匹配，它可以吸煙。如果其中一個相等，則推出，繼續排隊。mutex信號量代表一個只能進入的門，每次只有一個吸煙者可以進入進行比較和吸煙。每個吸煙者在吸煙完畢之后出門之前要叫醒供應者，調用seller進程。TheP,VcodeUsingPaScalvars,S1,S2,S3;semaphore;S:=1;S1:=S2:=S3:=0;fiag1,flag2,fiag3:Boolean;fiag1:=flag2:=flag3:=true;cobeginprocess供應者beginrepeatP(S);取兩樣香煙原料放桌上，由flagi標記；//nago1、nage2、nage3代表煙草、紙、火柴ifflag2&flag3thenV(S1);//供紙和火柴elseifflag1&fiag3thenV(S2);//供煙草和火柴elseV(S3);//供煙草和紙untilfalse;endprocess吸煙者1beginrepeatP(S1);取原料；做香煙；V(S);吸香煙；untilfalse;endprocess吸煙者2beginrepeatp(S2);取原料做香煙V(S);吸香煙untilfalse;endprocess吸煙者3beginrepeatP(S3);取原料；做香煙；V(S);吸香煙；untilfalse;endcoend第二章典型練習題目一生產者--消費者問題擴展1擴展一設有一個可以裝A、B兩種物品的倉庫，其容量無限大，但要求倉庫中A、B兩種物品的數量滿足下述不等式：-MWA物品數量一B物品數量WN其中M和N為正整數.試用信號量和PV操作描述A、B兩種物品的入庫過程.問題分析：若只放入A,而不放入B,貝3產品最多可放入N次便被阻塞；若只放入B,而不放入A,則B產品最多可放入M次便被阻塞；每放入一次A,放入產品B的機會也多一次；同理，每放入一次B,放入產品A的機會也多一次.TheP,VcodeUsingPascalSemaphoremutex=1,sa=N,sb=M;cobegincoend2擴展二procedureA：procedureA：while(TURE)beginp(sa);p(mutex);A產品入庫;V(mutex);V(sb);endprocedureB：while(TURE)beginp(sb);p(mutex);B產品入庫V(mutex);V(sa);end設有一個可以裝A、B兩種物品的倉庫，其容量有限(分別為N),但要求倉庫中A、B兩種物品的數量滿足下述不等式：-MWA物品數量一B物品數量WN其中M和N為正整數。另外，還有一個進程消費A,B,一次取一個A,B組裝成C。試用信號量和PV操作描述A、B兩種物品的入庫過程。問題分析：已知條件-MWA物品數量一B物品數量WN可以拆成兩個不等式，即A物品數量一B物品數量WNB物品數量一A物品數量WM這兩個不等式的含義是：倉庫中A物品可以比B物品多，但不能超過N個；B物品可以比A物品多，但不能超過M個。TheP,VcodeUsingPascalsemaphoremutex=1,a,b=m,empty1,empty2=N,full1,full2=0;cobeginprocess(A);process(B);process(C)coendA物品入庫processAbeginwhile(TRUE)beginp(empty1);P(a);p(mutex);A物品入庫;v(mutex);V(b);v(full1);endendB物品入庫：processBbeginwhile(TRUE)beginp(empty2);P(b);p(mutex);B物品入庫;v(mutex);V(a);p(full2);endendprocessCbeginwhile(TRUE)beginp(full1);p(full2);p(a);P(b);組裝;V(a);v(b);v(empty1);v(empty2);endend3擴展三設P,Q,R共享一個緩沖區，P,Q構成一對生產者-消費者，R既為生產者又為消費者。使用P,V實現其同步。TheP,VcodeUsingPaScalvarmutex,full,empty:semaphore;full:=1;empty:=0;mutex:=1;cobeginProcedurePbeginwhiletruep(empty);P(mutex);Productone；v(mutex);v(full);endProcedureQbeginwhiletruep(full);P(mutex);consumeone;v(mutex);v(empty);endProcedureRbeginifempty:=1thenbeginp(empty);P(mutex);product；v(mutex);v(full);endiffull:=1then

beginp(full);p(mutex);消費一個產品v(mutex);v(empty);endcoend二讀者--寫者問題擴展1擴展一如果讀者寫者均是平等的即二者都不優先。TheP,VcodeUsingPascalvarw,s,mutex:semaphore;RC:integer;w,s,mutex:=1;RC:=0;ProcedureWriterbeginwhileTRUEp(w);p(s);Writing;v(s);v(w);endProcedureWriterbeginwhileTRUEp(w);p(s);Writing;v(s);v(w);endProcedureReaderbeginwhileTRUEp(w);p(mutex);ifRC==0thenp(s);RC:=RC+1;v(mutex);v(w);Reading;p(mutex);RC:=RC-1;ifRC==0thenv(s);v(mutex);endcoend對讀者-寫者問題作一條限制，最多只允許rn個讀者同時讀。為此，又引入了一個信號量L，賦予其初值為rn，通過執行SP(L丄1)操作來控制讀者的數目，每當一個讀者進入時，都要做一次SP(L,1,1)操作，使L的值減1。當有rn個讀者進入讀后，L便減為0,而第rn+1個讀者必然會因執行SP(L,1,1)操作失敗而被封鎖。利用一般信號量機制解決讀者-寫者問題的算法描述如下：TheP,VcodeUsingPascalvarrn:integer;/*允許同時讀的讀進程數L:semaphore:=rn;/*控制讀進程數信號量，最多rnW:semaphore:=1;begincobeginprocessreaderbeginrepeatSP（L，1，1;W，1，0）;Readthefile;SV（L，1）;untilfalse;endprocesswriterbeginRepeatSP（W，1，1;L，rn，0）;Writethefile;SV（W，1）;untilfalse;endcoendend.上述算法中，SP（W,1,O）語句起開關作用，只要沒有寫者進程進入寫，由于這時W=l,讀者進程就都可以進入讀文件。但一旦有寫者進程進入寫時，其W=0,則任何讀者進程及其他寫者進程就無法進入讀寫。SP（W,1,1;L,rn,o）語句表示僅當既無寫者進程在寫（這時W=1）、又無讀者進程在讀（這時L=rn）時，寫者進程才能進行臨界區寫文件。2擴展二在經典的同步問題中有一個讀者－寫者的問題。它的實現方法一般都是基于讀者優先策略的，現在請用PV操作來實現基于先來先服務策略的讀者一寫者的問題，具體要求描述如下：存在m個讀者和n個一寫者，共享同一個緩沖區；當沒有讀者在讀，寫者在寫時，讀者，寫者均可進入讀或寫當有讀者在讀時：（1）寫者來了，則寫者等待；（2）讀者來了，分兩種情況處理：無寫者等待，則讀者可以直接進入讀操作，如果有寫者等待，則讀者必須依次等待；當有寫者在寫時，寫者或讀者來了，均需等待；當寫者寫完后，如果等待隊列中第一個是寫者，則喚醒該寫者；如果等待隊列中的第一個是讀者，則喚醒該隊列中從讀者開始連續的所有讀者；當最后一個讀者讀后，如果有寫者在等待，則喚醒第一個等待的寫者。endend三吸煙者問題擴展1擴展一在一間酒吧里有三個音樂愛好者隊列，第一隊的音樂愛好者只有隨身聽，第二隊的只有音樂磁帶，第三隊只有電池。而要聽音樂就必須隨身聽，音樂磁帶和電池這三種物品俱全。酒吧老板依次出售這三種物品中的任意兩種。當一名音樂愛好者得到這三種物品并聽完一首樂曲后，酒吧老板才能再一次出售這三種物品中的任意兩種。于是第二名音樂愛好者得到這三種物品，并開始聽樂曲。全部買賣就這樣進行下去。試用P,V操作正確解決這一買賣。問題分析：該問題與吸煙者解法相同。2擴展二假設一個錄像廳有0,1，2三種不同的錄像片可由觀眾選擇放映，錄像廳的放映規則為:任一時刻最多只能放映一種錄像片，正在放映的錄像片是自動循環放映的，最后一個觀眾主動離開時結束當前錄像片的放映；選擇當前正在放映的錄像片的觀眾可立即進入，允許同時有多位選擇同一種錄像片的觀眾同時觀看，同時觀看的觀眾數量不受限制；等待觀看其他錄像片的觀眾按到達順序排隊，當一種新的錄像片開始放映時，所有等待觀看該錄像片的觀眾可依次序進入錄像廳同時觀看。用一個進程代表一個觀眾，要求:用信號量方法PV實現，并給出信號量定義和初始值。(最好也能寫出錄像廳的進程)問題分析：電影院一次只能放映一部影片，希望觀看的觀眾可能有不同的愛好，但每次只能滿足部分觀眾的需求，即希望觀看另外兩部影片的用戶只能等待。分別為三部影片設置三個信號量s0,sl,s2,初值分別為1,1,1電影院一次只能放一部影片，因此需要互斥使用。由于觀看影片的觀眾有多個，因此必須分別設置三個計數器(初值都是0)，用來統計觀眾個數。當然計數器是個共享變量，需要互斥使用。TheP,VcodeUsingPaScalvars=1,s0=1,s1=1,s2=1:semaphore;varcount0=0,count1=0,count2=0;cobeginprocessvideoshow0//vcd_id=0beginrepeatp(s0);count0=count0+1;if(count0=1)p(s);v(s0);看影片；p(s0);count0=count0-1;if(count0=1)v(s);v(s0);untilfalseprocessvideoshow1//vcd_id=1beginrepeatp(s1);count1=count1+1;if(count1=1)p(s);v(s1);看影片；p(s1);count1=count1-1;if(count1=1)v(s);v(s1);untilfalseendprocessvideoshow2//vcd_id=2beginrepeatp(s2);count2=count2+1;if(count2=1)p(s);v(s2);看影片；p(s2);count1=count1-1;if(count2=1)v(s);v(s2);untilfalseendcoend第三章題輯一銀行排隊問題問題描述：銀行有n個柜員，每個顧客進入銀行后先取一個號，并且等著叫號，當一個柜員空閑后，就叫下一個號。問題分析：將顧客號碼排成一個隊列，顧客進入銀行領取號碼后，將號碼由隊尾插入;柜員空閑時，從隊首取得顧客號碼，并且為這個顧客服務，由于隊列為若干進程共享，所以需要互斥.柜員空閑時，若有顧客，就叫下一個顧客為之服務.因此，需要設置一個信號量來記錄等待服務的顧客數.TheP,VcodeUsingPajcalbeginvarmutex=1，customer_count=0:semaphore;cobeginprocesscustomerbeginrepeat取號碼；p(mutex);進入隊列；v(mutex);v(customer_count);endprocessserversi(i=1，...，n)beginrepeatp(customer_count);p(mutex);從隊列中取下一個號碼；v(mutex);為該號碼持有者服務；endcoendend思考：某車站售票廳，任何時刻最多可容納20名購票者進入，當售票廳中少于20名購票者時，則廳外的購票者可立即進入，否則需在外面等待。若把一個購票者看作一個進程，請回答下列問題用PV操作管理這些并發進程時，應怎樣定義信號量，寫出信號量的初值以及信號量各種取值的含義。若欲購票者最多為n個人，寫出信號量可能的變化范圍(最大值和最小值)。定義信號量S,初值為20,當s>0時，它表示可以繼續進入購票廳的人數，當=0時表示廳內已有20人正在購票，當s<0時jS?表示正等待進入的人數。TheP,VcodeUsingPascalvarS:semaphore;S=20;cobeginprocedureP_i:beginp(s);Enterandbuyticket;v(s)endcoend(2)最大值為20,最小值為20-N。二生產消費問題擴展假設緩沖區bufl和緩沖區buf2無限大，進程pl向bufl寫數據，進程p2向buf2寫數據，要求bufl數據個數和buf2數據個數的差保持在(m,n)之間(mvn,m,n都是正數)。問題分析：題中沒有給出兩個進程執行順序之間的制約關系，只給出了一個數量上的制約關系，即m?一bufl數據個數一buf2數據個數?n.不需要考慮緩沖區的大小，只需要考慮兩個進程的同步和互斥.p2向buf2寫數據比pl向bufl寫數據的次數最少不超過m次，最多不能超過n次，反之也成立.所以是一個生產者和消費者問題。將等式展開得：(l)m.(bufl數據個數一buf2數據個數)?n;(2)m?(buf2數據個數一bufl數據個數)?n;由于m,n都是正數，等式只有一個成立，不妨設(l)成立.在進程pl和p2都沒有運行時，兩個緩沖區數據個數之差為0,因此，pl必須先運行，向bufl至少寫m+l個數據后再喚醒p2運行.信號量sl表示pl—次寫入的最大量,初值為n,s2表示p2一次寫入的最大量,初值為-m。〔TheP,VcodeUsingPascalbeginvarmutexl=l,mutex2=l,sl=n,s2=-m:semaphore;cobeginprocessplbeginrepeatgetdata;p(sl);p(mutexl);寫數據到bufl;v(mutexl);v(s2);endprocessp2beginrepeat;getdata;p(s2);p(mutex2);寫數據至到buf2;v(mutex2);v(s1);endcoendend思考：pl和p2每次執行時需要進行一些額外的操作.對于p2來說，它首先必須在自己的緩沖區buf2中寫入至少m個數據，此后pl和p2的同步可簡單通過兩個信號量來控制.題目的一個變形是要求：-m?(buf2數據個數一bufl數據個數)?n;那么信號量的初值就變成m和n,若只有pl向bufl放入數據而p2不放入數據至到buf2中，貝Upl最多可放m次.因此，設置信號量sl,初值為m,此外，每當p2放入一個數據到buf2中時，則使信號量sl增1,即pl增加一次放入數據到bufl的機會.反之，若只有p2向buf2放入數據而pl不放入數據至到bufl中，則p2最多可放次.因此，設置信號量s2,初值為n,此外，每當pl放入一個數據至到bufl中時，貝M吏信號量s2增1,即p2增加一次放入數據到bufl的機會.TheP,VcodeUsingPascalbeginvarmutexl=l,mutex2=l,sl=m,s2=n:semaphore;cobeginprocessplbeginrepeatgetdata;p(sl);p(mutexl);寫數據至bufl;v(mutexl);v(s2);//pl每放入一個數據到bufl同時使s2增加1endprocessp2beginrepeat;getdata;p(s2);p(mutex2);寫數據至buf2;v(mutex2);v(sl);//p2每放入一個數據至到buf2同時使si增加1endcoendend三輸入輸出一個從鍵盤輸入到打印機輸出的數據處理流程圖如圖所示。其中鍵盤輸入進程通過緩沖區bufl把數絕傳送給計算進程，計算進程把處理結果通過buf2傳送給打印進程。假設上述兩個緩沖區的大小分別為nl和n2，試寫出鍵盤輸入進程、計算進程及打印進程間的同步算法。問題分析：本題解決的試具有多個緩沖區的生產者和消費者之間的多階段同步問題。由于每個緩沖區中均有多個存儲單元，因而要護持使用。所以要為每個緩沖區設置一個互斥信號量。TheP,VcodeUsingPaScalBeginvarempty1,empty2,full1,full2,mutex1,mutex2:semaphore;empty1:=n1;empty2:=n2;full1:=0;full2:=0;mutex1:=mutex2:=1;cobeginprocedureInputbeginInputadata;p(empty1);p(mutex1);Puttobuf1;v(mutex1);v(full1);endprocedureCalculatebeginP(full1)；p(mutex1);Getfrombuf1;v(mutex1);v(empty1);Calculateit;p(empty2);p(mutex2);putresulttobuf2;v(mutex2);v(full2);endprocedurePrint_Outbeginp(full2);p(mutex2);GetDatafrombuf2;v(mutex2);v(empty2);Printoutthedata;endcoendend生產者消費者擴展設有N個計算進程和M個打印進程共享同一個緩沖區，緩沖區長度為8。各計算進程不斷地把計算得到的結果送入緩沖區，各打印進程不斷的從緩沖區取數并打印。要求：既不漏打，也不重復打印任一個結果。并且，為了高效地工作，計算機進程在使用緩沖區的同時允許打印進程從緩沖區中取數，反之亦然。請用P、V操作作為同步機制，并用類PASCAL或類C，描述對應于計算進程和打印進程的程序。理發師問題擴展有一個理發師，一把理發椅和n把供等候理發的顧客坐的椅子，若沒有顧客，則理發師睡覺,當一個顧客到來時,必須喚醒理發師進行理發,若理發師正在理發,又有顧客到來,則若有空椅子可坐就坐下來等，若沒有空椅子就離開。問題分析：需要設置一個信號量barber，初值為0,用于控制理發師和顧客之間的同步關系.還需要設置一個信號量customer，初值為0,用于離開顧客與等候顧客之間的同步控制，為了記錄等候的顧客數，應該設置一個計數器count，初值為0.當一個顧客到達時,需要在count上做加1操作，并根據count值的不同分別采取不同的動作，當顧客離開時，要對count上做減1操作,并根據count值的不同分別采取不同的動作;由于count是共享變量，因此要互斥使用，為此設置一個互斥信號量mutex;TheP,VcodeUsingPaScalbeginvarbarber=0，customer=0，count=0，mutex=1:semaphore;cobeginprocessbarberbeginrepeatp(customer);p(mutex);count=count-1;v(barber);v(mutex);理發;untilfalseendprocesscustomerbeginrepeat;p(mutex);if(count<n){count=count+1;v(customer);p(barber);理發；}else{v(mutex);離開；}untilfalseendcoendend思考：有3個理發師,3把理發椅子,n把供等候理發的顧客坐的椅子.由于有3位理發師，所以一次同時可以為三個顧客服務，設置信號量maxcapacity,用于表示空閑椅子的數量,初值為n.信號量barberchair表示空閑理發師(椅)的數量，初值為3;信號量custready,finished,leavebchair分別表示是否有顧客到來，理發完成，離開理發椅，它們的初值都為0;TheP,VcodeUsingPajcalbeginvarmax_capacity=n,barber_chair=3,cust_ready=0,finished=0,leave_b_chair=0:semaphore;cobeginprocessbarberbeginrepeatp(cust_ready);理發;untilfalseendprocesscustomerbeginrepeat;p(max_capacity);〃是否有空閑椅子；進入店里；p(barber_chair);〃是否有空閑的理發椅；坐在理發椅上；v(cust_ready);〃喚醒理發師；p(finished);//是否完成理發；離開理發椅；v(leave_b_chair);離開店；v(max_capacity);untilfalseendcoendend讀者寫者問題擴展問題描述：一個主修動物行為學、輔修計算機科學的學生參加了一個課題，調查花果山的猴子是否能被教會理解死鎖。他找到一處峽谷，橫跨峽谷拉了一根繩索(假設為南北方向)，這樣猴子就可以攀著繩索越過峽谷。只要它們朝著相同的方向，同一時刻可以有多只猴子通過。但是如果在相反的方向上同時有猴子通過則會發生死鎖(這些猴子將被卡在繩索中間，假設這些猴子無法在繩索上從另一只猴子身上翻過去)。如果一只猴子相越過峽谷，它必須看當前是否有別的猴子在逆向通過。請使用P/V操作來解決該問題。問題分析：由于不允許兩個方向的猴子同時跨越繩索，所以對繩索應該互斥使用，但同一個方向可以允許多只猴子通過，所以臨界區可允許多個實例訪問。本題的難點在于位于南北方向的猴子具有相同的行為，當一方有猴子在繩索上時，同方向的猴子可繼續通過，但此時要防止零一方的猴子跨越繩索。類比經典的讀者/寫者問題，可以發現類似之處，但又不完全相同，因為沒有類似的寫者。進一步分析可將此題歸結為兩種讀者間的同步與互斥問題。TheP,VcodeUsingPaScalBeginvarmutex,Smutex,Nmutex,SmonkeyCount,NmonkeyCount:semaphore;SmonkeyCount:=0;〃從南向北攀越繩索的猴子數量NmonkeyCount:=0;〃從北向南攀越繩索的猴子數量mutex:=l;〃繩索互斥信號量Smutex:=l;〃南方向猴子間的互斥信號量Nmutex:=1;〃北方向猴子間的互斥信號量cobeginprocedureSouth_i(i=1,2,3,...)beginp(Smutex);ifSmonkeyCount==0thenp(mutex);SmonkeyCount:=SmonkeyCount+1;v(Smutex);Crossthecordage;p(Smutex);SmonkeyCount:=SmonkeyCount-1;ifSmonkeyCount==0thenv(mutex);v(Nmutex);endprocedureNorth_j(j=1,2,3,...)beginp(Nmutex);ifNmonkeyCount==0thenp(mutex);NmonkeyCount:=NmonkeyCount+1;v(Nmutex);Crossthecordage;p(Nmutex);NmonkeyCount:=NmonkeyCount-1;ifNmonkeyCount==0thenv(mutex);v(Nmutex);endcoendend進程互斥進程Pl和P2通過兩個緩沖區給進程Pll、P12、P21、P22傳遞信息，進程Pll、P12取進程P1的信息，進程P2l、P22取進程P2的信息。假定這兩個緩沖區一樣大小，所要傳遞的信息也與緩沖區一樣大，同一時刻只能由一個進程往緩沖區中送信息或取信息。試用PV操作來實現這6個進程之間的同步與互斥關系。TheP,VcodeUsingPaScalvarmutex,Sll,Sl2,S2l,S22,emptyl,empty2,fulll,full2:semaphore;emptyl=empty2=l;fulll=full2=0;sij=0;(i,j=l,2)mutex=l;cobeginProcedurePl:beginp(empty1);P(mutex);putmessageintobuff1;v(mutex);v(S11);v(S12);v(fll1);endprocedureP2:beginp(empty2);p(mutex);putmessageintobuff2;v(mutex);v(s21);v(S22);v(full2);endprocedureSij:(i=1,2,j=1,2)beginp(fulli);p(sij);p(mutex);Getmessagefrombuffi;v(mutex);v(emptyi)endcoend管道通信問題在管道通信機制中，用信號量描述讀進程和寫進程訪問管道文件的過程，假設管道文件大小為10KB.問題分析：UNIX系統中，利用一個打開的共享文件來連接兩個相互通信的進程，這個共享文件叫管道．作為管道輸入的發送進程，以字符流的形式將信息送入管道，而作為管道輸出的接收進程，從管道中獲取信息．管道通信機制要提供三方面的協調能力：(1)互斥．當一個進程對管道進行讀／寫操作時，另一個進程必須等待．(2)同步．當寫進程把數據寫入管道后便去睡眠等待，直到輸出進程取走數據后喚醒它．若一次寫入的數據超過緩沖區剩余空間的大小，當緩沖區滿時，寫進程必須阻塞，并喚醒讀進程。(3)對方是否存在．只有確定對方存在時，才能夠進行通信．本題只需要考慮互斥，同步問題。由于只有一對進程訪問管道，因此不需要設置互斥信號量，只要設置兩個同步信號量empty,fu11.分別表示管道可寫和可讀.TheP,VcodeUsingPascalbeginpipe:array[09]ofkilobytes;ts=10,length,in=0,out=0:integer;empty,full:semaphore=1,0;cobeginprocessPipeWriterbeginrepeat產生數據；p(empty);length=datalength;while(length>0andts>0)beginpipe[in]=dataof1KB;in=(in+1)modn;ts=ts-1;length=length-1;endv(full);endprocessConsumerbeginrepeat;p(full);從緩沖區取出一件物品;out=(out+1)modn;ts=ts+1;v(empty);endcoendend吃水果問題問題描述：桌上有一空盤，允許存放一只水果。爸爸可向盤中放蘋果，也可向盤中放桔子，兒子專等吃盤中的桔子，女兒專等吃盤中的蘋果。規定當盤空時一次只能放一只水果供吃者取用，請用P、V原語實現爸爸、兒子、女兒三個并發進程的同步。問題分析：在本題中，爸爸、兒子、女兒共用一個盤子，盤中一次只能放一個水果。當盤子為空時，爸爸可將一個水果放入果盤中。若放入果盤中的是桔子，則允許兒子吃，女兒必須等待；若放入果盤中的是蘋果，則允許女兒吃，兒子必須等待。本題實際上是生產者-消費者問題的一種變形。這里，生產者放入緩沖區的產品有兩類，消費者也有兩類，每類消費者只消費其中固定的一類產品。TheP,VcodeUsingPaScal在本題中，應設置三個信號量S、So、Sa，信號量S表示盤子是否為空，其初值為1；信號量So表示盤中是否有桔子，其初值為0；信號量Sa表示盤中是否有蘋果，其初值為0。同步描述如下：S=1;Sa=0;So=0;cobeginProcedurefather;/*父親進程*/Procedureson;/*兒子進程*/Proceduredaughter;/*女兒進程*/coendProcedurefather:beginwhi1e(TRUE)beginP(S);將水果放入盤中;if(放入的是桔子)V(So);e1seV(Sa);endendProcedureson:beginwhi1e(TRUE)beginP(So);從盤中取出桔子;V(S);吃桔子;endendProceduredaughter:beginwhi1e(TRUE)beginP(Sa);從盤中取出蘋果;V(S);吃蘋果吃蘋果;吃蘋果吃蘋果;endend十安全島問題在南開大學至天津大學間有一條彎曲的路，每次只允許一輛自行車通過，但中間有小的安全島M(同時允許兩輛車)，可供兩輛車在已進入兩端小車錯車，設計算法并使用P,V實現。問題分析：由于安全島M僅僅允許兩輛車停留，本應該作為臨界資源而要設置信號量，但根據題意，任意時刻進入安全島的車不會超過兩輛(兩個方向最多各有一輛)，因此，不需要為M設置信號量,在路口s和路口t都需要設置信號量，以控制來自兩個方向的車對路口資源的爭奪.這兩個信號量的初值都是1.此外，由于從s到t的一段路只允許一輛車通過，所以還需要設置另外的信號量用于控制，由于M的存在，可以為兩端的小路分別設置一個互斥信號量.TheP,VcodeUsingPajcalvarT2N，N2T，L，M，K:semaphore;T2N:=1;N2T:=1;L:=1;K:=1;M:=2;cobeginProcedureBikeT2Nbeginp(T2N);P(L);goTtoL;P(M);gointoM;V(L);P(k);goKtos;V(M);V(k);V(T2N);endProcedureBikeN2TbeginP(N2T);p(k);govtok;p(M);gointoM;V(k);P(L);goLtoT;V(M);V(L);V(N2T);endcoend十一珍瓏棋局問題問題描述：在一個盒子里，混裝了數量相等的黑白圍棋子?現在用自動分揀系統把黑子、白子分開,設分揀系統有二個進程P1和P2，其中P1揀白子；P2揀黑子。規定每個進程每次揀一子;當一個進程在揀時，不允許另一個進程去揀；當一個進程揀了一子時，必須讓另一個進程去揀.試寫出兩進程P1和P2能并發正確執行的程序。問題分析：大家熟悉了生產-消費問題(PC),這個問題很簡單。題目較為新穎，但是本質非常簡單即：生產-消費問題的簡化或者說是兩個進程的簡單同步問題。答案如下：TheP,VcodeUsingPaScal設信號量si和s2分別表示可揀白子和黑子；不失一般性，若令先揀白子。varS1,S2:semaphore；S1:=l；S2：=0；cobeginprocessP1beginrepeatP(S1)；pickThewhite；V(S2)；untilfalse；endprocessP2beginrepeatp(S2)；endendendendStartDrivingSelltheticketnthedoorCloseThedoorStartDrivingSelltheticketnthedoorCloseThedoorpicktheblack;v(sl);untilfalse;endcoend十二公交車問題問題描述：設公共汽車上，司機和售票員的活動分別如下：司機的活動：啟動車輛：正常行車；到站停車。售票員的活動：關車門；售票；開車門。在汽車不斷地到站、停車、行駛過程中，這兩個活動有什么同步關系？用信號量和P、V操作實現它們的同步。DriverConductorDriver問題分析：在汽車行駛過程中，司機活動與售票員活動之間的同步關系為：售票員關車門后，向司機發開車信號，司機接到開車信號后啟動車輛，在汽車正常行駛過程中售票員售票，到站時司機停車，售票員在車停后開門讓乘客上下車。因此，司機啟動車輛的動作必須與售票員關車門的動作取得同步;售票員開車門的動作也必須與司機停車取得同步。應設置兩個信號量:S1、S2;S1表示是否允許司機啟動汽車(其初值為0)S2表示是否允許售票員開門(其初值為0)用P、v原語描述如下：TheP,VcodeUsingPajcalvarS1,S2:semaphore;S1=0；S2=0；cobeginproceduredriverbeginwhileTRUEbeginP(S1);Start;Driving;Stop;v(S2);endprocedureConductorbeginwhileTRUEbegin關車門；v(sl);售票；口,P(s2);開車門；上下乘客；endendcoend十三少林寺問題問題描述：某寺廟，有小和尚、老和尚若干.廟內有一水缸，由小和尚提水入缸，供老和尚飲用。水缸可容納10桶水，每次入水、取水僅為桶，不可同時進行。水取自同一井中，水井徑窄,每次只能容納一個水桶取水。設水桶個數為3個，試用信號燈和PV操作給出老和尚和小和尚的活動。問題分析：從井中取水并放入水缸是一個連續的動作可以視為一個進程，從缸中取水為另一個進程。設水井和水缸為臨界資源，引入mutex1,mutex2；三個水桶無論從井中取水還是放入水缸中都一次一個，應該給他們一個信號量count，搶不到水桶的進程只好為等待，水缸滿了時，不可以再放水了。設empty控制入水量，水缸空了時,不可取水設full。TheP,VcodeUsingPascalvarmutex1,mutex2,empty,full,count:semaphore;mutex1:=mutex2:=1;empty:=10;full:=0;count:=3;cobeginprocedureFetch_Waterbeginwhiletruep(empty);P(count);P(mutexl);GetWater;v(mutexl);P(mutex2);purewaterintothejar;v(mutex2);v(count);v(full);endProcedureDrink_Waterbeginwhiletruep(full);p(count);p(mutex2);GetwaterandDrinkwater;p(mutex2);v(empty);v(count);endcoend十四過橋問題問題描述：一座小橋(最多只能承重兩個人)橫跨南北兩岸，任意時刻同一方向只允許一人過橋，南側橋段和北側橋段較窄只能通過一人，橋中央一處寬敞，允許兩個人通過或歇息。試用信號燈和PV操作寫出南、北兩岸過橋的同步算法。SuulliNorth*-問題分析：橋上可能沒有人，也可能有一人，也可能有兩人。兩人同時過橋兩人都到中間南(北)來者到北(南)段共需要三個信號量，load用來控制橋上人數，初值為2,表示橋上最多有2人；north用來控制北段橋的使用，初值為1，用于對北段橋互斥；south用來控制南段橋的使用，初值為1,用于對南段橋互斥。TheP,VcodeUsingPascalvarload,north,south:semaphore;load=2;north=1;south=1;GO_South()P(load);P(north);過北段橋;到橋中間;V(north);P(south);過南段橋;到達南岸;V(south);V(load);GO_North()P(load);P(south);過南段橋;到橋中間V(south);P(north);過北段橋;到達北岸V(north);V(load);思考：某條河上有一獨木橋可以使行人通過，現在河的兩邊都有人過河，為了保障安全，依照如下規則過橋：同一方向的可連續過河，若某方向有人過河，則另一方等待。TheP,VcodeUsingPascalvarS,S1,S2:semaphore;rc1,rc2:integer;S,S1,S2:=1;rc1=rc2=0;cobeginprocedureEast2West_i:beginp(S1);rcl:=rcl+l;ifrc1==1thenP(s);v(S1);過獨木橋；p(Sl)；rc1:=rc1-1;ifrc1==0thenv(S);v(S1);endprocedureWest2East_i:beginp(S2);rc2:=rc2+1;ifrc2==1thenp(s);v(S2);過獨木橋；p(S2);rc2=rc2-1;ifrc2==0thenv(s);v(S2);endcoend思考：一條公路兩次橫跨運河，兩個運河橋相距100米，均帶有閘門，以供船只通過運河橋。運河和公路的交通均是單方向的。運河上的運輸由駁船擔負。在一駁船接近吊橋A時就拉汽笛警告，若橋上無車輛，吊橋就吊起，直到駁船尾P通過此橋為止。對吊橋B也按同樣次序處理。一般典型的駁船長度為200米，當它在河上航行時是否會產生死鎖？若會，說明理由，請提出一個防止死鎖的辦法，并用信號量來實現駁船的同步。問題分析：當汽車或駁船未同時到達橋A時，以任何次序前進不會產生死鎖。但假設汽車駛過了橋它在繼續前進，并且在駛過橋B之前，此時有駁船并快速地通過了橋A,駁船頭到達橋這時會發生死鎖。因為若吊起吊橋B讓駁船通過，則汽車無法通過橋B;若不吊起吊橋B讓汽車通過，則駁船無法通過橋B。可用兩個信號量同步車、船通過兩座橋的動作。TheP,VcodeUsingPascal解答：varSa,Sb:semaphore;Sa:=Sb:=l;cobeginprocess駁船beginP(Sa);P(Sb);船過橋A、B;v(Sa);v(Sb);endprocess汽車beginP(Sa);P(Sb);車過橋A、B;v(Sa);v(Sb);endcoend思考如圖所示：South2BridgeNurih橋每次只能有一輛車通過。不允許兩車交會，但允許同方向的多輛車依次通過〔TheP,VcodeUsingPascalbeginmutex:semaphore=1;cobeginprocessScar//南邊來的車begincome;p(mutex);過橋；v(mutex);endendendendendendendendgo;processNear//北邊來的車begincome;p(mutex);過橋;v(mutex);go;endcoendendbeginvarSmutex=1,Nmutex=1,mutex=1:semaphore;SCarCount=0,NCarCount=0:integer;cobeginprocessScari(i=1,2)beginp(Smutex);if(SCarCount=0)thenp(mutex);SCarCount=SCarCount+1;v(Smutex);過橋；p(Smutex);SCarCount=SCarCount-1;if(SCarCount=0)thenv(mutex);v(Smutex);endprocessNcarj(j=1,2)beginp(Nmutex);if(NCarCount=0)thenp(mutex);NCarCount=NCarCount+1;v(Nmutex);過橋；p(Nmutex);NCarCount=NCarCount-1;if(NCarCount=0)thenv(mutex);v(Nmutex);coendendendendendendendend思考：設有一個T型路口，其中A、B、C、D處各可容納一輛車，車行方向如圖所示:試找出死鎖并用有序分配法消除之，要求資源編號合理。解：（1）E方向兩輛車分別位于A和B；S方向一輛車位于C；W方向一輛車位于D。（2）S方向兩輛車分別位于B和C；E方向一輛車位于A；W方向一輛車位于D。TheP,VcodeUsingPajcal設位置資源C、B、A、D的編號從低到高依次為1、2、3、4,管理4個位置的信號量分別為S1，S2，S3，S4，信號量的初值均為1。車輛活動如下：semaphoreS1=1，S2=1，S3=1，s4=l；cobeginprocedureW:直行beginP（S1）；P（S4）;EnterD;EnterC;v（S4）;OutofC;v（S1）;endprocedureE:左轉beginp(S2);EnterB;p(S3);EnterA;v(S2);p(S4);EnterD;v(S3);outofD;V(S4);procedureS:左轉beginp(S1);EnterC;p(S2);EnterB;v(S1);p(S3);EnterA;v(S2);outofA;v(S3);endcoend十五帳戶問題兩人公用一個賬號，每次限存或取10元；TheP,VcodeUsingPascalbeginvarmutex=1:semaphore;amount=0:integer;cobeginprocesssavem1:integer;beginrepeatp(mutex);m1=amount;m1=m1+10;amout=m1;v(mutex);endprocesstakem2:integer;beginrepeat;p(mutex);m2=amount;m2=m2-10;amout=m2;v(mutex);coendend十六機房上機問題某高校計算機系開設網絡課并安排上機實習，假設機房共有2m臺機器，有2n名學生選課（m,n均大于等于1）,規定：每兩個學生組成一組，各占一臺及其協同完成上機實習；只有一組兩個學生到齊，并且此時機房有空閑機器時，該組學生才能進入機房；上機實習由一名教師檢查，檢查完畢，一組學生同時離開機房試用P、V實現其過程。本題目隱含一個進程(Guard)。TheP,VcodeUsingPaScalvarstu,computer,enter,finish,test:semaphore;ste:=2N;computer:=2M;enter:=0;finish:=0;test:=0;cobeginprocedureStudentbeginp(computer);p(stu);Startcomputer;v(finish);v(test);v(computer);endprocedureTeacherbeginp(finish);Testthework;v(test);v(test);endprocedureGuardbeginp(stu);p(stu);Enter;v(enter);v(enter);endcoend十七3進程問題問題描述：設有A、B、C三組進程，它們互斥地使用某一獨占型資源R,使用前申請，使用后釋放資源分配原則如下:當只有一組申請進程時，該組申請進程依次獲得R;當有兩組申請進程時，各組申請進程交替獲得R,組內申請進程交替獲得R;當有三組申請進程時，各組申請進程輪流獲得R,組內申請進程交替獲得R.試用信號燈和PV操作分別給出各組進程的申請活動程序段和釋放活動程序段TheP,VcodeUsingPaScalIntFree=l;〃設備狀態標志semaphoremutex=1;semaphoreqa=qb=qc=0;//各組等待隊列Intcounta=countb=countc=0;//等待隊列長度A組申請：P(mutex);ifFree==lthenbeginFree=0;V(mutex);endelsebegincounta++;V(mutex);P(qa);endA組釋放：ifcountb>0thenbegincountb--;V(qb);endelsebeginifcountc>0thenbegincountc--;v(qc);endendendendelsebeginif(counta>0)begincounta--;V(qa);endelsebeginFree=1;endendendA組進程活動可以給出B組和C組進程活動。思考：今有三個并發進程R，M,P,它們共享了一個可循環使用的緩沖區B,緩沖區B共有N個單元。進程R負責從輸入設備讀信息，每讀一個字符后，把它存放在緩沖區B的一個單元中；進程M負責處理讀入的字符，若發現讀入的字符中有空格符，則把它改成“，”；進程P負責把處理后的字符取出并打印輸出。當緩沖區單元中的字符被進程P取出后，則又可用來存放下一次讀入的字符。請用PV操作為同步機制寫出它們能正確并發執行的程序。TheP,VcodeUsingPaScalvarempty,full1,full2,mutex:semaphore;charbuffer[n];intin=0,out1=0,out2=0;empty=N;full1=0;full2=0;mutex=1;cobeginprocedureR;procedureM;procedureP;coendprocedureR:beginwhileTruethenbegincharx;Readachartox;p(empty);p(mutex);buffer[in]=x;in=(in+1)%N;v(mutex);v(full1);endendprocedureM:beginwhileTruethenbegincharx;p(full1);p(mutex);x=buffer[out1];ifx==""thenbeginx=",";buffer[out1]=x;endout1=(out1+1)%N;v(mutex);v(full2);endendprocedureP:beginwhileTruethenbegincharx;p(full2);p(empty);x=buffer[out2];out2=(out2+1)%N;v(mutex);v(empty);出字符X；endend思考有Pl、P2、P3三個進程共享一個表格F,Pl對F只讀不寫，P2對F只寫不讀，P3對F先讀后寫。進程可同時讀F,但有進程寫時，其他進程不能讀和寫。用1）信號量和P、V操作。（2）管程編寫三進程能正確工作的程序。TheP,VcodeUsingPaScal(1)信號量和P、V操作。這是讀-寫者問題的變種。其中，P3既是讀者又是寫者。讀者與寫者之間需要互斥，寫者與寫者之間需要互斥，為提高進程運行的并發性，可讓讀者盡量優先。varrmutex,wmutex:semaphore;rmutex:=wmutex:=1;count:integer;count:=0;cobegin{processP1beginrepeatP(rmutex);count:=count+1;ifcount=1thenP(wmutex);V(rmutex);ReadF;P(rmutex);count:=count-1;ifcount=0thenV(wmutex);V(rmutex);untilfalse;endprocessP2beginrepeatP(wmutex);WriteF;V(wmutex);untilfalse;endprocessP3beginrepeatP(rmutex);count:=count+1;ifcount=1thenP(wmutex);V(rmutex);ReadF;P(rmutex);count:=count-l;ifcount=0thenV(wmutex);V(rmutex);P(wmutex);WriteF;V(wmutex);untilfalse;end}coend思考如圖所示，四個進程PiG=0…3)和四個信箱Mj(j=0…3)，進程間借助相鄰信箱傳遞消息，即Pi每次從Mi中取一條消息，經加工后送入M(i+1)mod4，其中MO、M1、M2、M3分別可存放3、3、2、2個消息。初始狀態下，M0裝了三條消息，其余為空。試以PV操作為工具,Mutex1=nutex2:=mutex3:=mutex0:=1;Empty0,empty1,empty2,empty3;semaphore;empty:=0;empty1:=3;empty:=2:=empty3:=2;full。,full1,full2,full3:semphore;full0:=3;fuH1:=full2:=full3:=0;in0,in1,in2,in3,out0,out2,out3,;intger;in0:=in1:=in2:=in3:=out0:=out1:=out2:=out3:=0;cobeginprocessPObeginrepeatP(fullO);P(mutexO);從M0[out0]取一條消息；out0:=(out0+1)mod3;V(mutexO);V(emptyO);加工消息；P(empty1);P(mutex1);消息已Ml[inl];In1:=(in1+1)mod3;v(mutexl);v(fulll);untilfalse;endprocessPlbeginrepeatp(full);p(mutexl);GetamessagefromM[outl];outl:=(outl+l)mod3;v(mutexl);v(emptyl);加工消息；p(empty2);p(mutex2);消息己M2[in2];In2:=(in2+l)mod2;v(mutex2);v(full2);untilfalse;endprocessP2beginrepeatP(full2);P(mutex2);從M2[out2]取一條消息；out2:=(out2+l)mod2;v(mutex2);v(empty2);加工消息；P(empty3);P(mutex3);消息己M3[in3];in3:=(in3+l)mod2;v(mutex3);v(full3);untilfalse;endprocessP3beginrepeatp(full3);P(mutex3);從M3[out3]取一條消息；out3:=(out3+1)mod2;v(mutex3)；v(empty3)；加工消息；p(empty0)；p(mutex0)；消息己MO[in0];In0:=(in0+1)mod3；v(mutex0);v(full0);untilefalse;endcoend思考：四個進程A、B、C、D都要讀一個共享文件F,系統允許多個進程同時讀文件F。但限制是進程A和進程C不能同時讀文件F,進程B和進程D也不能同時讀文件F。為了使這四個進程并發執行時能按系統要求使用文件，現用PV操作進行管理，請回答下面的問題：(1)如何定義信號量及初值；(2)在下列的程序中填上適當的P、V操作，以保證它們能正確并發工作：進程A:進程B：進程C：進程D：beginbeginbeginbegin????????????readeF;readeF;readeF;readeF;????????????endendendend(1)定義二個信號量SI、S2，初值均為1,即：Sl=l,S2=l。其中進程A和C使用信號量S1，進程B和D使用信號量S2。(2)從⑴到⑻分別為：P(S1)V(S1)P(S2)V(S2)P(S1)V(S1)P(S2)V(S2)思考今有k個進程，它們的