操作系統(tǒng)pv操作

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

進(jìn)程的同步和互斥互斥：是指某一資源同時(shí)只允許一個(gè)訪問者對其進(jìn)行訪問，具有唯一性和排它性。但互斥無法限制訪問者對資源的訪問順序，即訪問是無序的。同步：是指在互斥的基礎(chǔ)上(大多數(shù)情況)，通過其它機(jī)制實(shí)現(xiàn)訪問者對資源的有序訪問。在大多數(shù)情況下，同步已經(jīng)實(shí)現(xiàn)了互斥，特別是所有寫入資源的情況必定是互斥的。少數(shù)情況是指可以允許多個(gè)訪問者同時(shí)訪問資源。二SeveralTypicalExamples本節(jié)我們討論幾個(gè)利用信號量來實(shí)現(xiàn)進(jìn)程互斥和同步的經(jīng)典例子。這里的問題關(guān)鍵是如何選擇信號量和如何安排P、V原語的使用順序。依據(jù)信號量與進(jìn)程的關(guān)系，我們可把進(jìn)程中使用的信號量分成私有信號量和公用信號量。私有信號量是指只與制約進(jìn)程和被制約進(jìn)程有關(guān)的信號量；公用信號量是指與一組并發(fā)進(jìn)程有關(guān)的信號量。這里請不要和C++、JAVA等編程語言的公有、私有相混淆。這里指的是相對于共享資源來說的。1生產(chǎn)者一消費(fèi)者問題(producer-consumerproblem)生產(chǎn)者--消費(fèi)者問題(producer-consumerproblem)是指若干進(jìn)程通過有限的共享緩沖區(qū)交換數(shù)據(jù)時(shí)的緩沖區(qū)資源使用問題。問題描述：假設(shè)“生產(chǎn)者”進(jìn)程不斷向共享緩沖區(qū)寫人數(shù)據(jù)(即生產(chǎn)數(shù)據(jù))，而“消費(fèi)者”進(jìn)程不斷從共享緩沖區(qū)讀出數(shù)據(jù)(即消費(fèi)數(shù)據(jù))；共享緩沖區(qū)共有n個(gè)；任何時(shí)刻只能有一個(gè)進(jìn)程可對共享緩沖區(qū)進(jìn)行操作。所有生產(chǎn)者和消費(fèi)者之間要協(xié)調(diào)，以完成對共享緩沖區(qū)的操作。Producer:ProducerMConsutner1生產(chǎn)捋休Producer:ProducerMConsutner1生產(chǎn)捋休悄費(fèi)指針Figure1.1:producer-consumerproblem我們可把共享緩沖區(qū)中的n個(gè)緩沖塊視為共享資源，生產(chǎn)者寫人數(shù)據(jù)的緩沖塊成為消費(fèi)者可用資源，而消費(fèi)者讀出數(shù)據(jù)后的緩沖塊成為生產(chǎn)者的可用資源。為此，可設(shè)置三個(gè)信號量：full、empty和mutex。其中：full表示有數(shù)據(jù)的緩沖塊數(shù)目，初值是0；empty表示空的緩沖塊數(shù)初值是n；mutex用于訪問緩沖區(qū)時(shí)的互斥，初值是1。實(shí)際上，full和empty間存在如下關(guān)系：full+empty=NTheP,VcodeUsingPaScalbuffer:array[O..k-1]ofinteger;in,out:O..k-1;//in記錄第一個(gè)空緩沖區(qū)，out記錄第一個(gè)不空的緩沖區(qū)empty,full,mutex:semaphore;//empty控制緩沖區(qū)不滿,full控制緩沖區(qū)不空,mutex保護(hù)臨界區(qū)；〃初始化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注意：這里每個(gè)進(jìn)程中各個(gè)P操作的次序是重要的。各進(jìn)程必須先檢查自己對應(yīng)的資源數(shù)在確信有可用資源后再申請對整個(gè)緩沖區(qū)的互斥操作；否則，先申請對整個(gè)緩沖區(qū)的互斥操后申請自己對應(yīng)的緩沖塊資源，就可能死鎖。出現(xiàn)死鎖的條件是，申請到對整個(gè)緩沖區(qū)的互斥操作后，才發(fā)現(xiàn)自己對應(yīng)的緩沖塊資源，這時(shí)已不可能放棄對整個(gè)緩沖區(qū)的占用。如果采用AND信號量集，相應(yīng)的進(jìn)入?yún)^(qū)和退出區(qū)都很簡單。如生產(chǎn)者的進(jìn)入?yún)^(qū)為Swait(empty,mutex)，退出區(qū)為Ssignal(full，mutex)。2讀者--寫者問題(Readers-WritersProblem)問題描述：有一個(gè)許多進(jìn)程共享的數(shù)據(jù)區(qū)，這個(gè)數(shù)據(jù)區(qū)可以是一個(gè)文件或者主存的一塊空間；有一些只讀取這個(gè)數(shù)據(jù)區(qū)的進(jìn)程(Reader)和一些只往數(shù)據(jù)區(qū)寫數(shù)據(jù)的進(jìn)程(Writer)，此外還需要滿足以下條件：(1)任意多個(gè)讀進(jìn)程可以同時(shí)讀這個(gè)文件；(2)一次只有一個(gè)寫進(jìn)程可以往文件中寫；(3)如果一個(gè)寫進(jìn)程正在進(jìn)行操作，禁止任何讀進(jìn)程度文件。實(shí)驗(yàn)要求用信號量來實(shí)現(xiàn)讀者寫者問題的調(diào)度算法。實(shí)驗(yàn)提供了Semaphore類，該類通過P()、V()兩個(gè)方法實(shí)現(xiàn)了P、V原語的功能。實(shí)驗(yàn)的任務(wù)是修改Reader類的Read方法以及Writer類的Write方法。我們需要分兩種情況實(shí)現(xiàn)該問題：讀優(yōu)先：要求指一個(gè)讀者試圖進(jìn)行讀操作時(shí)，如果這時(shí)正有其他讀者在進(jìn)行操作，他可直接開始讀操作，而不需要等待。寫優(yōu)先：一個(gè)讀者試圖進(jìn)行讀操作時(shí)，如果有其他寫者在等待進(jìn)行寫操作或正在進(jìn)行寫操作，他要等待該寫者完成寫操作后才開始讀操作。TheP,VcodeUsingPaScal讀者優(yōu)先算法：rwmutex用于寫者與其他讀者/寫者互斥的訪問共享數(shù)據(jù)rmutex用于讀者互斥的訪問readcount讀者計(jì)數(shù)器varrwmutex,rmutex：semaphore:=1,1；intreadcount=0;cobeginprocedurereader_ibegin//i=1,2,.P(rmutex);Readcount++;if(readcount==1)P(rwmutex);V(rmutex);讀數(shù)據(jù)；P(rmutex);Readcount--;if(readcount==0)V(rwmutex);V(rmutex);endprocedureWriter_jbegin//j=1,2,….P(rwmutex);寫更新；V(rwmutex);endcoendTheP,VcodeUsingPaScal寫者優(yōu)先：多個(gè)讀者可以同時(shí)進(jìn)行讀寫者必須互斥(只允許一個(gè)寫者寫，也不能讀者寫者同時(shí)進(jìn)行)寫者優(yōu)先于讀者(一旦有寫者，則后續(xù)讀者必須等待，喚醒時(shí)優(yōu)先考慮寫者)如果讀者數(shù)是固定的，我們可采用下面的算法：rwmutex：用于寫者與其他讀者/寫者互斥的訪問共享數(shù)據(jù)rmutex：該信號量初始值設(shè)為10，表示最多允許10個(gè)讀者進(jìn)程同時(shí)進(jìn)行讀操作varrwmutex,rmutex：semaphore:=1,10；cobeginprocedurereader_ibegin//i=1,2,….P(rwmutex);//讀者、寫者互斥P(rmutex);V(rwmutex);//釋放讀寫互斥信號量，允許其它讀、寫進(jìn)程訪問資源讀數(shù)據(jù)；V(rmutex);endprocedureWriter_jbegin//j=1,2,….P(rwmutex);for(i=1;i<=10;i++)P(rmutex);//禁止新讀者，并等待已進(jìn)入的讀者退出寫更新；for(i=1;i<=10;i++)V(rmutex);//恢復(fù)允許rmutex值為10V(rwmutex);endcoend問題擴(kuò)展如果讀者寫者均是平等的即二者都不優(yōu)先，如何實(shí)現(xiàn)?哲學(xué)家進(jìn)餐問題(TheDiningPhilosophersProblem)Figure1.2:TheDiningPhilosophersProblem問題描述：(由Dijkstra首先提出并解決)5個(gè)哲學(xué)家圍繞一張圓桌而坐，桌子上放著5支筷子，每兩個(gè)哲學(xué)家之間放一支；哲學(xué)家的動(dòng)作包括思考和進(jìn)餐，進(jìn)餐時(shí)需要同時(shí)拿起他左邊和右邊的兩支筷子，思考時(shí)則同時(shí)將兩支筷子放回原處。如何保證哲學(xué)家們的動(dòng)作有序進(jìn)行？如：不出現(xiàn)相鄰者同時(shí)要求進(jìn)餐；不出現(xiàn)有人永遠(yuǎn)拿不到筷子；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理發(fā)師問題(BarberProblem)問題描述：理發(fā)店理有一位理發(fā)師、一把理發(fā)椅和n把供等候理發(fā)的顧客坐的椅子如果沒有顧客，理發(fā)師便在理發(fā)椅上睡覺一個(gè)顧客到來時(shí)，它必須叫醒理發(fā)師如果理發(fā)師正在理發(fā)時(shí)又有顧客來到，則如果有空椅子可坐，就坐下來等待，否則就離開。TheP,VcodeUsingPascal控制變量waiting用來記錄等候理發(fā)的顧客數(shù)，初值均為0；信號量customers用來記錄等候理發(fā)的顧客數(shù)，并用作阻塞理發(fā)師進(jìn)程，初值為0；信號量barbers用來記錄正在等候顧客的理發(fā)師數(shù)，并用作阻塞顧客進(jìn)程，初值為0；信號量mutex用于互斥，初值為1intwaiting=0；//等候理發(fā)的顧客數(shù)intchairs=n；//為顧客準(zhǔn)備的椅子數(shù)semaphorecustomers=0,barbers=0,mutex=1;cobeginbarber()beginwhile(TRUE);//理完一人,還有顧客嗎?P(cutomers);//若無顧客,理發(fā)師睡眠P(mutex);//進(jìn)程互斥waiting:=waiting-1;〃等候顧客數(shù)少一個(gè)V(barbers);//理發(fā)師去為一個(gè)顧客理發(fā)V(mutex);//開放臨界區(qū)cut-hair();//正在理發(fā)endcustomer()beginP(mutex);//進(jìn)程互斥if(waiting)beginwaiting:=waiting+1;//等候顧客數(shù)加1V(customers);//必要的話喚醒理發(fā)師V(mutex);//開放臨界區(qū)P(barbers);//無理發(fā)師,顧客坐著養(yǎng)神get-haircut();//一個(gè)顧客坐下等理/endelseV(mutex);//人滿了,走吧!endcoend吸煙者問題(SmokerProblem)問題描述：三個(gè)吸煙者在一間房間內(nèi)，還有一個(gè)香煙供應(yīng)者。為了制造并抽掉香煙，每個(gè)吸煙者需要三樣?xùn)|西：煙草、紙和火柴。供應(yīng)者有豐富的貨物提供。三個(gè)吸煙者中，第一個(gè)有自己的煙草，第二個(gè)有自己的紙，第三個(gè)有自己的火柴。供應(yīng)者將兩樣?xùn)|西放在桌子上，允許一個(gè)吸煙者進(jìn)行對健康不利的吸煙。當(dāng)吸煙者完成吸煙后喚醒供應(yīng)者，供應(yīng)者再放兩樣?xùn)|西(隨機(jī)地)在桌面上，然后喚醒另一個(gè)吸煙者。試為吸煙者和供應(yīng)者編寫程序解決問題。問題分析：供應(yīng)者seller隨即產(chǎn)生兩樣?xùn)|西，提供它們，這里用普通變量來表示吸煙者進(jìn)程smoker根據(jù)其排號不同，擁有不同的一件東西。假設(shè)1號吸煙者擁有煙草tobacco，2號吸煙者擁有紙paper,3號吸煙者擁有火柴match。其他號碼錯(cuò)誤返回。吸煙者的序號代表他們擁有的東西，用他們的序號和供應(yīng)者產(chǎn)生的兩樣?xùn)|西比較，如果都不相等，則說明他擁有的東西和供應(yīng)者產(chǎn)生的東西匹配，它可以吸煙。如果其中一個(gè)相等，則推出，繼續(xù)排隊(duì)。mutex信號量代表一個(gè)只能進(jìn)入的門，每次只有一個(gè)吸煙者可以進(jìn)入進(jìn)行比較和吸煙。每個(gè)吸煙者在吸煙完畢之后出門之前要叫醒供應(yīng)者，調(diào)用seller進(jìn)程。TheP,VcodeUsingPaScalvars,S1,S2,S3;semaphore;S:=1;S1:=S2:=S3:=0;fiag1,flag2,fiag3:Boolean;fiag1:=flag2:=flag3:=true;cobeginprocess供應(yīng)者beginrepeatP(S);取兩樣香煙原料放桌上，由flagi標(biāo)記；//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第二章典型練習(xí)題目一生產(chǎn)者--消費(fèi)者問題擴(kuò)展1擴(kuò)展一設(shè)有一個(gè)可以裝A、B兩種物品的倉庫，其容量無限大，但要求倉庫中A、B兩種物品的數(shù)量滿足下述不等式：-MWA物品數(shù)量一B物品數(shù)量WN其中M和N為正整數(shù).試用信號量和PV操作描述A、B兩種物品的入庫過程.問題分析：若只放入A,而不放入B,貝3產(chǎn)品最多可放入N次便被阻塞；若只放入B,而不放入A,則B產(chǎn)品最多可放入M次便被阻塞；每放入一次A,放入產(chǎn)品B的機(jī)會也多一次；同理，每放入一次B,放入產(chǎn)品A的機(jī)會也多一次.TheP,VcodeUsingPascalSemaphoremutex=1,sa=N,sb=M;cobegincoend2擴(kuò)展二procedureA：procedureA：while(TURE)beginp(sa);p(mutex);A產(chǎn)品入庫;V(mutex);V(sb);endprocedureB：while(TURE)beginp(sb);p(mutex);B產(chǎn)品入庫V(mutex);V(sa);end設(shè)有一個(gè)可以裝A、B兩種物品的倉庫，其容量有限(分別為N),但要求倉庫中A、B兩種物品的數(shù)量滿足下述不等式：-MWA物品數(shù)量一B物品數(shù)量WN其中M和N為正整數(shù)。另外，還有一個(gè)進(jìn)程消費(fèi)A,B,一次取一個(gè)A,B組裝成C。試用信號量和PV操作描述A、B兩種物品的入庫過程。問題分析：已知條件-MWA物品數(shù)量一B物品數(shù)量WN可以拆成兩個(gè)不等式，即A物品數(shù)量一B物品數(shù)量WNB物品數(shù)量一A物品數(shù)量WM這兩個(gè)不等式的含義是：倉庫中A物品可以比B物品多，但不能超過N個(gè)；B物品可以比A物品多，但不能超過M個(gè)。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擴(kuò)展三設(shè)P,Q,R共享一個(gè)緩沖區(qū)，P,Q構(gòu)成一對生產(chǎn)者-消費(fèi)者，R既為生產(chǎn)者又為消費(fèi)者。使用P,V實(shí)現(xiàn)其同步。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);消費(fèi)一個(gè)產(chǎn)品v(mutex);v(empty);endcoend二讀者--寫者問題擴(kuò)展1擴(kuò)展一如果讀者寫者均是平等的即二者都不優(yōu)先。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個(gè)讀者同時(shí)讀。為此，又引入了一個(gè)信號量L，賦予其初值為rn，通過執(zhí)行SP(L丄1)操作來控制讀者的數(shù)目，每當(dāng)一個(gè)讀者進(jìn)入時(shí)，都要做一次SP(L,1,1)操作，使L的值減1。當(dāng)有rn個(gè)讀者進(jìn)入讀后，L便減為0,而第rn+1個(gè)讀者必然會因執(zhí)行SP(L,1,1)操作失敗而被封鎖。利用一般信號量機(jī)制解決讀者-寫者問題的算法描述如下：TheP,VcodeUsingPascalvarrn:integer;/*允許同時(shí)讀的讀進(jìn)程數(shù)L:semaphore:=rn;/*控制讀進(jìn)程數(shù)信號量，最多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）語句起開關(guān)作用，只要沒有寫者進(jìn)程進(jìn)入寫，由于這時(shí)W=l,讀者進(jìn)程就都可以進(jìn)入讀文件。但一旦有寫者進(jìn)程進(jìn)入寫時(shí)，其W=0,則任何讀者進(jìn)程及其他寫者進(jìn)程就無法進(jìn)入讀寫。SP（W,1,1;L,rn,o）語句表示僅當(dāng)既無寫者進(jìn)程在寫（這時(shí)W=1）、又無讀者進(jìn)程在讀（這時(shí)L=rn）時(shí)，寫者進(jìn)程才能進(jìn)行臨界區(qū)寫文件。2擴(kuò)展二在經(jīng)典的同步問題中有一個(gè)讀者－寫者的問題。它的實(shí)現(xiàn)方法一般都是基于讀者優(yōu)先策略的，現(xiàn)在請用PV操作來實(shí)現(xiàn)基于先來先服務(wù)策略的讀者一寫者的問題，具體要求描述如下：存在m個(gè)讀者和n個(gè)一寫者，共享同一個(gè)緩沖區(qū)；當(dāng)沒有讀者在讀，寫者在寫時(shí)，讀者，寫者均可進(jìn)入讀或?qū)懏?dāng)有讀者在讀時(shí)：（1）寫者來了，則寫者等待；（2）讀者來了，分兩種情況處理：無寫者等待，則讀者可以直接進(jìn)入讀操作，如果有寫者等待，則讀者必須依次等待；當(dāng)有寫者在寫時(shí)，寫者或讀者來了，均需等待；當(dāng)寫者寫完后，如果等待隊(duì)列中第一個(gè)是寫者，則喚醒該寫者；如果等待隊(duì)列中的第一個(gè)是讀者，則喚醒該隊(duì)列中從讀者開始連續(xù)的所有讀者；當(dāng)最后一個(gè)讀者讀后，如果有寫者在等待，則喚醒第一個(gè)等待的寫者。endend三吸煙者問題擴(kuò)展1擴(kuò)展一在一間酒吧里有三個(gè)音樂愛好者隊(duì)列，第一隊(duì)的音樂愛好者只有隨身聽，第二隊(duì)的只有音樂磁帶，第三隊(duì)只有電池。而要聽音樂就必須隨身聽，音樂磁帶和電池這三種物品俱全。酒吧老板依次出售這三種物品中的任意兩種。當(dāng)一名音樂愛好者得到這三種物品并聽完一首樂曲后，酒吧老板才能再一次出售這三種物品中的任意兩種。于是第二名音樂愛好者得到這三種物品，并開始聽樂曲。全部買賣就這樣進(jìn)行下去。試用P,V操作正確解決這一買賣。問題分析：該問題與吸煙者解法相同。2擴(kuò)展二假設(shè)一個(gè)錄像廳有0,1，2三種不同的錄像片可由觀眾選擇放映，錄像廳的放映規(guī)則為:任一時(shí)刻最多只能放映一種錄像片，正在放映的錄像片是自動(dòng)循環(huán)放映的，最后一個(gè)觀眾主動(dòng)離開時(shí)結(jié)束當(dāng)前錄像片的放映；選擇當(dāng)前正在放映的錄像片的觀眾可立即進(jìn)入，允許同時(shí)有多位選擇同一種錄像片的觀眾同時(shí)觀看，同時(shí)觀看的觀眾數(shù)量不受限制；等待觀看其他錄像片的觀眾按到達(dá)順序排隊(duì)，當(dāng)一種新的錄像片開始放映時(shí)，所有等待觀看該錄像片的觀眾可依次序進(jìn)入錄像廳同時(shí)觀看。用一個(gè)進(jìn)程代表一個(gè)觀眾，要求:用信號量方法PV實(shí)現(xiàn)，并給出信號量定義和初始值。(最好也能寫出錄像廳的進(jìn)程)問題分析：電影院一次只能放映一部影片，希望觀看的觀眾可能有不同的愛好，但每次只能滿足部分觀眾的需求，即希望觀看另外兩部影片的用戶只能等待。分別為三部影片設(shè)置三個(gè)信號量s0,sl,s2,初值分別為1,1,1電影院一次只能放一部影片，因此需要互斥使用。由于觀看影片的觀眾有多個(gè)，因此必須分別設(shè)置三個(gè)計(jì)數(shù)器(初值都是0)，用來統(tǒng)計(jì)觀眾個(gè)數(shù)。當(dāng)然計(jì)數(shù)器是個(gè)共享變量，需要互斥使用。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第三章題輯一銀行排隊(duì)問題問題描述：銀行有n個(gè)柜員，每個(gè)顧客進(jìn)入銀行后先取一個(gè)號，并且等著叫號，當(dāng)一個(gè)柜員空閑后，就叫下一個(gè)號。問題分析：將顧客號碼排成一個(gè)隊(duì)列，顧客進(jìn)入銀行領(lǐng)取號碼后，將號碼由隊(duì)尾插入;柜員空閑時(shí)，從隊(duì)首取得顧客號碼，并且為這個(gè)顧客服務(wù)，由于隊(duì)列為若干進(jìn)程共享，所以需要互斥.柜員空閑時(shí)，若有顧客，就叫下一個(gè)顧客為之服務(wù).因此，需要設(shè)置一個(gè)信號量來記錄等待服務(wù)的顧客數(shù).TheP,VcodeUsingPajcalbeginvarmutex=1，customer_count=0:semaphore;cobeginprocesscustomerbeginrepeat取號碼；p(mutex);進(jìn)入隊(duì)列；v(mutex);v(customer_count);endprocessserversi(i=1，...，n)beginrepeatp(customer_count);p(mutex);從隊(duì)列中取下一個(gè)號碼；v(mutex);為該號碼持有者服務(wù)；endcoendend思考：某車站售票廳，任何時(shí)刻最多可容納20名購票者進(jìn)入，當(dāng)售票廳中少于20名購票者時(shí)，則廳外的購票者可立即進(jìn)入，否則需在外面等待。若把一個(gè)購票者看作一個(gè)進(jìn)程，請回答下列問題用PV操作管理這些并發(fā)進(jìn)程時(shí)，應(yīng)怎樣定義信號量，寫出信號量的初值以及信號量各種取值的含義。若欲購票者最多為n個(gè)人，寫出信號量可能的變化范圍(最大值和最小值)。定義信號量S,初值為20,當(dāng)s>0時(shí)，它表示可以繼續(xù)進(jìn)入購票廳的人數(shù)，當(dāng)=0時(shí)表示廳內(nèi)已有20人正在購票，當(dāng)s<0時(shí)jS?表示正等待進(jìn)入的人數(shù)。TheP,VcodeUsingPascalvarS:semaphore;S=20;cobeginprocedureP_i:beginp(s);Enterandbuyticket;v(s)endcoend(2)最大值為20,最小值為20-N。二生產(chǎn)消費(fèi)問題擴(kuò)展假設(shè)緩沖區(qū)bufl和緩沖區(qū)buf2無限大，進(jìn)程pl向bufl寫數(shù)據(jù)，進(jìn)程p2向buf2寫數(shù)據(jù)，要求bufl數(shù)據(jù)個(gè)數(shù)和buf2數(shù)據(jù)個(gè)數(shù)的差保持在(m,n)之間(mvn,m,n都是正數(shù))。問題分析：題中沒有給出兩個(gè)進(jìn)程執(zhí)行順序之間的制約關(guān)系，只給出了一個(gè)數(shù)量上的制約關(guān)系，即m?一bufl數(shù)據(jù)個(gè)數(shù)一buf2數(shù)據(jù)個(gè)數(shù)?n.不需要考慮緩沖區(qū)的大小，只需要考慮兩個(gè)進(jìn)程的同步和互斥.p2向buf2寫數(shù)據(jù)比pl向bufl寫數(shù)據(jù)的次數(shù)最少不超過m次，最多不能超過n次，反之也成立.所以是一個(gè)生產(chǎn)者和消費(fèi)者問題。將等式展開得：(l)m.(bufl數(shù)據(jù)個(gè)數(shù)一buf2數(shù)據(jù)個(gè)數(shù))?n;(2)m?(buf2數(shù)據(jù)個(gè)數(shù)一bufl數(shù)據(jù)個(gè)數(shù))?n;由于m,n都是正數(shù)，等式只有一個(gè)成立，不妨設(shè)(l)成立.在進(jìn)程pl和p2都沒有運(yùn)行時(shí)，兩個(gè)緩沖區(qū)數(shù)據(jù)個(gè)數(shù)之差為0,因此，pl必須先運(yùn)行，向bufl至少寫m+l個(gè)數(shù)據(jù)后再喚醒p2運(yùn)行.信號量sl表示pl—次寫入的最大量,初值為n,s2表示p2一次寫入的最大量,初值為-m?！睺heP,VcodeUsingPascalbeginvarmutexl=l,mutex2=l,sl=n,s2=-m:semaphore;cobeginprocessplbeginrepeatgetdata;p(sl);p(mutexl);寫數(shù)據(jù)到bufl;v(mutexl);v(s2);endprocessp2beginrepeat;getdata;p(s2);p(mutex2);寫數(shù)據(jù)至到buf2;v(mutex2);v(s1);endcoendend思考：pl和p2每次執(zhí)行時(shí)需要進(jìn)行一些額外的操作.對于p2來說，它首先必須在自己的緩沖區(qū)buf2中寫入至少m個(gè)數(shù)據(jù)，此后pl和p2的同步可簡單通過兩個(gè)信號量來控制.題目的一個(gè)變形是要求：-m?(buf2數(shù)據(jù)個(gè)數(shù)一bufl數(shù)據(jù)個(gè)數(shù))?n;那么信號量的初值就變成m和n,若只有pl向bufl放入數(shù)據(jù)而p2不放入數(shù)據(jù)至到buf2中，貝Upl最多可放m次.因此，設(shè)置信號量sl,初值為m,此外，每當(dāng)p2放入一個(gè)數(shù)據(jù)到buf2中時(shí)，則使信號量sl增1,即pl增加一次放入數(shù)據(jù)到bufl的機(jī)會.反之，若只有p2向buf2放入數(shù)據(jù)而pl不放入數(shù)據(jù)至到bufl中，則p2最多可放次.因此，設(shè)置信號量s2,初值為n,此外，每當(dāng)pl放入一個(gè)數(shù)據(jù)至到bufl中時(shí)，貝M吏信號量s2增1,即p2增加一次放入數(shù)據(jù)到bufl的機(jī)會.TheP,VcodeUsingPascalbeginvarmutexl=l,mutex2=l,sl=m,s2=n:semaphore;cobeginprocessplbeginrepeatgetdata;p(sl);p(mutexl);寫數(shù)據(jù)至bufl;v(mutexl);v(s2);//pl每放入一個(gè)數(shù)據(jù)到bufl同時(shí)使s2增加1endprocessp2beginrepeat;getdata;p(s2);p(mutex2);寫數(shù)據(jù)至buf2;v(mutex2);v(sl);//p2每放入一個(gè)數(shù)據(jù)至到buf2同時(shí)使si增加1endcoendend三輸入輸出一個(gè)從鍵盤輸入到打印機(jī)輸出的數(shù)據(jù)處理流程圖如圖所示。其中鍵盤輸入進(jìn)程通過緩沖區(qū)bufl把數(shù)絕傳送給計(jì)算進(jìn)程，計(jì)算進(jìn)程把處理結(jié)果通過buf2傳送給打印進(jìn)程。假設(shè)上述兩個(gè)緩沖區(qū)的大小分別為nl和n2，試寫出鍵盤輸入進(jìn)程、計(jì)算進(jìn)程及打印進(jìn)程間的同步算法。問題分析：本題解決的試具有多個(gè)緩沖區(qū)的生產(chǎn)者和消費(fèi)者之間的多階段同步問題。由于每個(gè)緩沖區(qū)中均有多個(gè)存儲單元，因而要護(hù)持使用。所以要為每個(gè)緩沖區(qū)設(shè)置一個(gè)互斥信號量。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生產(chǎn)者消費(fèi)者擴(kuò)展設(shè)有N個(gè)計(jì)算進(jìn)程和M個(gè)打印進(jìn)程共享同一個(gè)緩沖區(qū)，緩沖區(qū)長度為8。各計(jì)算進(jìn)程不斷地把計(jì)算得到的結(jié)果送入緩沖區(qū)，各打印進(jìn)程不斷的從緩沖區(qū)取數(shù)并打印。要求：既不漏打，也不重復(fù)打印任一個(gè)結(jié)果。并且，為了高效地工作，計(jì)算機(jī)進(jìn)程在使用緩沖區(qū)的同時(shí)允許打印進(jìn)程從緩沖區(qū)中取數(shù)，反之亦然。請用P、V操作作為同步機(jī)制，并用類PASCAL或類C，描述對應(yīng)于計(jì)算進(jìn)程和打印進(jìn)程的程序。理發(fā)師問題擴(kuò)展有一個(gè)理發(fā)師，一把理發(fā)椅和n把供等候理發(fā)的顧客坐的椅子，若沒有顧客，則理發(fā)師睡覺,當(dāng)一個(gè)顧客到來時(shí),必須喚醒理發(fā)師進(jìn)行理發(fā),若理發(fā)師正在理發(fā),又有顧客到來,則若有空椅子可坐就坐下來等，若沒有空椅子就離開。問題分析：需要設(shè)置一個(gè)信號量barber，初值為0,用于控制理發(fā)師和顧客之間的同步關(guān)系.還需要設(shè)置一個(gè)信號量customer，初值為0,用于離開顧客與等候顧客之間的同步控制，為了記錄等候的顧客數(shù)，應(yīng)該設(shè)置一個(gè)計(jì)數(shù)器count，初值為0.當(dāng)一個(gè)顧客到達(dá)時(shí),需要在count上做加1操作，并根據(jù)count值的不同分別采取不同的動(dòng)作，當(dāng)顧客離開時(shí)，要對count上做減1操作,并根據(jù)count值的不同分別采取不同的動(dòng)作;由于count是共享變量，因此要互斥使用，為此設(shè)置一個(gè)互斥信號量mutex;TheP,VcodeUsingPaScalbeginvarbarber=0，customer=0，count=0，mutex=1:semaphore;cobeginprocessbarberbeginrepeatp(customer);p(mutex);count=count-1;v(barber);v(mutex);理發(fā);untilfalseendprocesscustomerbeginrepeat;p(mutex);if(count<n){count=count+1;v(customer);p(barber);理發(fā)；}else{v(mutex);離開；}untilfalseendcoendend思考：有3個(gè)理發(fā)師,3把理發(fā)椅子,n把供等候理發(fā)的顧客坐的椅子.由于有3位理發(fā)師，所以一次同時(shí)可以為三個(gè)顧客服務(wù)，設(shè)置信號量maxcapacity,用于表示空閑椅子的數(shù)量,初值為n.信號量barberchair表示空閑理發(fā)師(椅)的數(shù)量，初值為3;信號量custready,finished,leavebchair分別表示是否有顧客到來，理發(fā)完成，離開理發(fā)椅，它們的初值都為0;TheP,VcodeUsingPajcalbeginvarmax_capacity=n,barber_chair=3,cust_ready=0,finished=0,leave_b_chair=0:semaphore;cobeginprocessbarberbeginrepeatp(cust_ready);理發(fā);untilfalseendprocesscustomerbeginrepeat;p(max_capacity);〃是否有空閑椅子；進(jìn)入店里；p(barber_chair);〃是否有空閑的理發(fā)椅；坐在理發(fā)椅上；v(cust_ready);〃喚醒理發(fā)師；p(finished);//是否完成理發(fā)；離開理發(fā)椅；v(leave_b_chair);離開店；v(max_capacity);untilfalseendcoendend讀者寫者問題擴(kuò)展問題描述：一個(gè)主修動(dòng)物行為學(xué)、輔修計(jì)算機(jī)科學(xué)的學(xué)生參加了一個(gè)課題，調(diào)查花果山的猴子是否能被教會理解死鎖。他找到一處峽谷，橫跨峽谷拉了一根繩索(假設(shè)為南北方向)，這樣猴子就可以攀著繩索越過峽谷。只要它們朝著相同的方向，同一時(shí)刻可以有多只猴子通過。但是如果在相反的方向上同時(shí)有猴子通過則會發(fā)生死鎖(這些猴子將被卡在繩索中間，假設(shè)這些猴子無法在繩索上從另一只猴子身上翻過去)。如果一只猴子相越過峽谷，它必須看當(dāng)前是否有別的猴子在逆向通過。請使用P/V操作來解決該問題。問題分析：由于不允許兩個(gè)方向的猴子同時(shí)跨越繩索，所以對繩索應(yīng)該互斥使用，但同一個(gè)方向可以允許多只猴子通過，所以臨界區(qū)可允許多個(gè)實(shí)例訪問。本題的難點(diǎn)在于位于南北方向的猴子具有相同的行為，當(dāng)一方有猴子在繩索上時(shí)，同方向的猴子可繼續(xù)通過，但此時(shí)要防止零一方的猴子跨越繩索。類比經(jīng)典的讀者/寫者問題，可以發(fā)現(xiàn)類似之處，但又不完全相同，因?yàn)闆]有類似的寫者。進(jìn)一步分析可將此題歸結(jié)為兩種讀者間的同步與互斥問題。TheP,VcodeUsingPaScalBeginvarmutex,Smutex,Nmutex,SmonkeyCount,NmonkeyCount:semaphore;SmonkeyCount:=0;〃從南向北攀越繩索的猴子數(shù)量NmonkeyCount:=0;〃從北向南攀越繩索的猴子數(shù)量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進(jìn)程互斥進(jìn)程Pl和P2通過兩個(gè)緩沖區(qū)給進(jìn)程Pll、P12、P21、P22傳遞信息，進(jìn)程Pll、P12取進(jìn)程P1的信息，進(jìn)程P2l、P22取進(jìn)程P2的信息。假定這兩個(gè)緩沖區(qū)一樣大小，所要傳遞的信息也與緩沖區(qū)一樣大，同一時(shí)刻只能由一個(gè)進(jìn)程往緩沖區(qū)中送信息或取信息。試用PV操作來實(shí)現(xiàn)這6個(gè)進(jìn)程之間的同步與互斥關(guān)系。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管道通信問題在管道通信機(jī)制中，用信號量描述讀進(jìn)程和寫進(jìn)程訪問管道文件的過程，假設(shè)管道文件大小為10KB.問題分析：UNIX系統(tǒng)中，利用一個(gè)打開的共享文件來連接兩個(gè)相互通信的進(jìn)程，這個(gè)共享文件叫管道．作為管道輸入的發(fā)送進(jìn)程，以字符流的形式將信息送入管道，而作為管道輸出的接收進(jìn)程，從管道中獲取信息．管道通信機(jī)制要提供三方面的協(xié)調(diào)能力：(1)互斥．當(dāng)一個(gè)進(jìn)程對管道進(jìn)行讀／寫操作時(shí)，另一個(gè)進(jìn)程必須等待．(2)同步．當(dāng)寫進(jìn)程把數(shù)據(jù)寫入管道后便去睡眠等待，直到輸出進(jìn)程取走數(shù)據(jù)后喚醒它．若一次寫入的數(shù)據(jù)超過緩沖區(qū)剩余空間的大小，當(dāng)緩沖區(qū)滿時(shí)，寫進(jìn)程必須阻塞，并喚醒讀進(jìn)程。(3)對方是否存在．只有確定對方存在時(shí)，才能夠進(jìn)行通信．本題只需要考慮互斥，同步問題。由于只有一對進(jìn)程訪問管道，因此不需要設(shè)置互斥信號量，只要設(shè)置兩個(gè)同步信號量empty,fu11.分別表示管道可寫和可讀.TheP,VcodeUsingPascalbeginpipe:array[09]ofkilobytes;ts=10,length,in=0,out=0:integer;empty,full:semaphore=1,0;cobeginprocessPipeWriterbeginrepeat產(chǎn)生數(shù)據(jù)；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);從緩沖區(qū)取出一件物品;out=(out+1)modn;ts=ts+1;v(empty);endcoendend吃水果問題問題描述：桌上有一空盤，允許存放一只水果。爸爸可向盤中放蘋果，也可向盤中放桔子，兒子專等吃盤中的桔子，女兒專等吃盤中的蘋果。規(guī)定當(dāng)盤空時(shí)一次只能放一只水果供吃者取用，請用P、V原語實(shí)現(xiàn)爸爸、兒子、女兒三個(gè)并發(fā)進(jìn)程的同步。問題分析：在本題中，爸爸、兒子、女兒共用一個(gè)盤子，盤中一次只能放一個(gè)水果。當(dāng)盤子為空時(shí)，爸爸可將一個(gè)水果放入果盤中。若放入果盤中的是桔子，則允許兒子吃，女兒必須等待；若放入果盤中的是蘋果，則允許女兒吃，兒子必須等待。本題實(shí)際上是生產(chǎn)者-消費(fèi)者問題的一種變形。這里，生產(chǎn)者放入緩沖區(qū)的產(chǎn)品有兩類，消費(fèi)者也有兩類，每類消費(fèi)者只消費(fèi)其中固定的一類產(chǎn)品。TheP,VcodeUsingPaScal在本題中，應(yīng)設(shè)置三個(gè)信號量S、So、Sa，信號量S表示盤子是否為空，其初值為1；信號量So表示盤中是否有桔子，其初值為0；信號量Sa表示盤中是否有蘋果，其初值為0。同步描述如下：S=1;Sa=0;So=0;cobeginProcedurefather;/*父親進(jìn)程*/Procedureson;/*兒子進(jìn)程*/Proceduredaughter;/*女兒進(jìn)程*/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十安全島問題在南開大學(xué)至天津大學(xué)間有一條彎曲的路，每次只允許一輛自行車通過，但中間有小的安全島M(同時(shí)允許兩輛車)，可供兩輛車在已進(jìn)入兩端小車錯(cuò)車，設(shè)計(jì)算法并使用P,V實(shí)現(xiàn)。問題分析：由于安全島M僅僅允許兩輛車停留，本應(yīng)該作為臨界資源而要設(shè)置信號量，但根據(jù)題意，任意時(shí)刻進(jìn)入安全島的車不會超過兩輛(兩個(gè)方向最多各有一輛)，因此，不需要為M設(shè)置信號量,在路口s和路口t都需要設(shè)置信號量，以控制來自兩個(gè)方向的車對路口資源的爭奪.這兩個(gè)信號量的初值都是1.此外，由于從s到t的一段路只允許一輛車通過，所以還需要設(shè)置另外的信號量用于控制，由于M的存在，可以為兩端的小路分別設(shè)置一個(gè)互斥信號量.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十一珍瓏棋局問題問題描述：在一個(gè)盒子里，混裝了數(shù)量相等的黑白圍棋子?現(xiàn)在用自動(dòng)分揀系統(tǒng)把黑子、白子分開,設(shè)分揀系統(tǒng)有二個(gè)進(jìn)程P1和P2，其中P1揀白子；P2揀黑子。規(guī)定每個(gè)進(jìn)程每次揀一子;當(dāng)一個(gè)進(jìn)程在揀時(shí)，不允許另一個(gè)進(jìn)程去揀；當(dāng)一個(gè)進(jìn)程揀了一子時(shí)，必須讓另一個(gè)進(jìn)程去揀.試寫出兩進(jìn)程P1和P2能并發(fā)正確執(zhí)行的程序。問題分析：大家熟悉了生產(chǎn)-消費(fèi)問題(PC),這個(gè)問題很簡單。題目較為新穎，但是本質(zhì)非常簡單即：生產(chǎn)-消費(fèi)問題的簡化或者說是兩個(gè)進(jìn)程的簡單同步問題。答案如下：TheP,VcodeUsingPaScal設(shè)信號量si和s2分別表示可揀白子和黑子；不失一般性，若令先揀白子。varS1,S2:semaphore；S1:=l；S2：=0；cobeginprocessP1beginrepeatP(S1)；pickThewhite；V(S2)；untilfalse；endprocessP2beginrepeatp(S2)；endendendendStartDrivingSelltheticketnthedoorCloseThedoorStartDrivingSelltheticketnthedoorCloseThedoorpicktheblack;v(sl);untilfalse;endcoend十二公交車問題問題描述：設(shè)公共汽車上，司機(jī)和售票員的活動(dòng)分別如下：司機(jī)的活動(dòng)：啟動(dòng)車輛：正常行車；到站停車。售票員的活動(dòng)：關(guān)車門；售票；開車門。在汽車不斷地到站、停車、行駛過程中，這兩個(gè)活動(dòng)有什么同步關(guān)系？用信號量和P、V操作實(shí)現(xiàn)它們的同步。DriverConductorDriver問題分析：在汽車行駛過程中，司機(jī)活動(dòng)與售票員活動(dòng)之間的同步關(guān)系為：售票員關(guān)車門后，向司機(jī)發(fā)開車信號，司機(jī)接到開車信號后啟動(dòng)車輛，在汽車正常行駛過程中售票員售票，到站時(shí)司機(jī)停車，售票員在車停后開門讓乘客上下車。因此，司機(jī)啟動(dòng)車輛的動(dòng)作必須與售票員關(guān)車門的動(dòng)作取得同步;售票員開車門的動(dòng)作也必須與司機(jī)停車取得同步。應(yīng)設(shè)置兩個(gè)信號量:S1、S2;S1表示是否允許司機(jī)啟動(dòng)汽車(其初值為0)S2表示是否允許售票員開門(其初值為0)用P、v原語描述如下：TheP,VcodeUsingPajcalvarS1,S2:semaphore;S1=0；S2=0；cobeginproceduredriverbeginwhileTRUEbeginP(S1);Start;Driving;Stop;v(S2);endprocedureConductorbeginwhileTRUEbegin關(guān)車門；v(sl);售票；口,P(s2);開車門；上下乘客；endendcoend十三少林寺問題問題描述：某寺廟，有小和尚、老和尚若干.廟內(nèi)有一水缸，由小和尚提水入缸，供老和尚飲用。水缸可容納10桶水，每次入水、取水僅為桶，不可同時(shí)進(jìn)行。水取自同一井中，水井徑窄,每次只能容納一個(gè)水桶取水。設(shè)水桶個(gè)數(shù)為3個(gè)，試用信號燈和PV操作給出老和尚和小和尚的活動(dòng)。問題分析：從井中取水并放入水缸是一個(gè)連續(xù)的動(dòng)作可以視為一個(gè)進(jìn)程，從缸中取水為另一個(gè)進(jìn)程。設(shè)水井和水缸為臨界資源，引入mutex1,mutex2；三個(gè)水桶無論從井中取水還是放入水缸中都一次一個(gè)，應(yīng)該給他們一個(gè)信號量count，搶不到水桶的進(jìn)程只好為等待，水缸滿了時(shí)，不可以再放水了。設(shè)empty控制入水量，水缸空了時(shí),不可取水設(shè)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十四過橋問題問題描述：一座小橋(最多只能承重兩個(gè)人)橫跨南北兩岸，任意時(shí)刻同一方向只允許一人過橋，南側(cè)橋段和北側(cè)橋段較窄只能通過一人，橋中央一處寬敞，允許兩個(gè)人通過或歇息。試用信號燈和PV操作寫出南、北兩岸過橋的同步算法。SuulliNorth*-問題分析：橋上可能沒有人，也可能有一人，也可能有兩人。兩人同時(shí)過橋兩人都到中間南(北)來者到北(南)段共需要三個(gè)信號量，load用來控制橋上人數(shù)，初值為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);過南段橋;到達(dá)南岸;V(south);V(load);GO_North()P(load);P(south);過南段橋;到橋中間V(south);P(north);過北段橋;到達(dá)北岸V(north);V(load);思考：某條河上有一獨(dú)木橋可以使行人通過，現(xiàn)在河的兩邊都有人過河，為了保障安全，依照如下規(guī)則過橋：同一方向的可連續(xù)過河，若某方向有人過河，則另一方等待。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);過獨(dú)木橋；p(Sl)；rc1:=rc1-1;ifrc1==0thenv(S);v(S1);endprocedureWest2East_i:beginp(S2);rc2:=rc2+1;ifrc2==1thenp(s);v(S2);過獨(dú)木橋；p(S2);rc2=rc2-1;ifrc2==0thenv(s);v(S2);endcoend思考：一條公路兩次橫跨運(yùn)河，兩個(gè)運(yùn)河橋相距100米，均帶有閘門，以供船只通過運(yùn)河橋。運(yùn)河和公路的交通均是單方向的。運(yùn)河上的運(yùn)輸由駁船擔(dān)負(fù)。在一駁船接近吊橋A時(shí)就拉汽笛警告，若橋上無車輛，吊橋就吊起，直到駁船尾P通過此橋?yàn)橹?。對吊橋B也按同樣次序處理。一般典型的駁船長度為200米，當(dāng)它在河上航行時(shí)是否會產(chǎn)生死鎖？若會，說明理由，請?zhí)岢鲆粋€(gè)防止死鎖的辦法，并用信號量來實(shí)現(xiàn)駁船的同步。問題分析：當(dāng)汽車或駁船未同時(shí)到達(dá)橋A時(shí)，以任何次序前進(jìn)不會產(chǎn)生死鎖。但假設(shè)汽車駛過了橋它在繼續(xù)前進(jìn)，并且在駛過橋B之前，此時(shí)有駁船并快速地通過了橋A,駁船頭到達(dá)橋這時(shí)會發(fā)生死鎖。因?yàn)槿舻跗鸬鯓駼讓駁船通過，則汽車無法通過橋B;若不吊起吊橋B讓汽車通過，則駁船無法通過橋B?？捎脙蓚€(gè)信號量同步車、船通過兩座橋的動(dòng)作。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思考：設(shè)有一個(gè)T型路口，其中A、B、C、D處各可容納一輛車，車行方向如圖所示:試找出死鎖并用有序分配法消除之，要求資源編號合理。解：（1）E方向兩輛車分別位于A和B；S方向一輛車位于C；W方向一輛車位于D。（2）S方向兩輛車分別位于B和C；E方向一輛車位于A；W方向一輛車位于D。TheP,VcodeUsingPajcal設(shè)位置資源C、B、A、D的編號從低到高依次為1、2、3、4,管理4個(gè)位置的信號量分別為S1，S2，S3，S4，信號量的初值均為1。車輛活動(dòng)如下：semaphoreS1=1，S2=1，S3=1，s4=l；cobeginprocedureW:直行beginP（S1）；P（S4）;EnterD;EnterC;v（S4）;OutofC;v（S1）;endprocedureE:左轉(zhuǎn)beginp(S2);EnterB;p(S3);EnterA;v(S2);p(S4);EnterD;v(S3);outofD;V(S4);procedureS:左轉(zhuǎn)beginp(S1);EnterC;p(S2);EnterB;v(S1);p(S3);EnterA;v(S2);outofA;v(S3);endcoend十五帳戶問題兩人公用一個(gè)賬號，每次限存或取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十六機(jī)房上機(jī)問題某高校計(jì)算機(jī)系開設(shè)網(wǎng)絡(luò)課并安排上機(jī)實(shí)習(xí)，假設(shè)機(jī)房共有2m臺機(jī)器，有2n名學(xué)生選課（m,n均大于等于1）,規(guī)定：每兩個(gè)學(xué)生組成一組，各占一臺及其協(xié)同完成上機(jī)實(shí)習(xí)；只有一組兩個(gè)學(xué)生到齊，并且此時(shí)機(jī)房有空閑機(jī)器時(shí)，該組學(xué)生才能進(jìn)入機(jī)房；上機(jī)實(shí)習(xí)由一名教師檢查，檢查完畢，一組學(xué)生同時(shí)離開機(jī)房試用P、V實(shí)現(xiàn)其過程。本題目隱含一個(gè)進(jìn)程(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進(jìn)程問題問題描述：設(shè)有A、B、C三組進(jìn)程，它們互斥地使用某一獨(dú)占型資源R,使用前申請，使用后釋放資源分配原則如下:當(dāng)只有一組申請進(jìn)程時(shí)，該組申請進(jìn)程依次獲得R;當(dāng)有兩組申請進(jìn)程時(shí)，各組申請進(jìn)程交替獲得R,組內(nèi)申請進(jìn)程交替獲得R;當(dāng)有三組申請進(jìn)程時(shí)，各組申請進(jìn)程輪流獲得R,組內(nèi)申請進(jìn)程交替獲得R.試用信號燈和PV操作分別給出各組進(jìn)程的申請活動(dòng)程序段和釋放活動(dòng)程序段TheP,VcodeUsingPaScalIntFree=l;〃設(shè)備狀態(tài)標(biāo)志semaphoremutex=1;semaphoreqa=qb=qc=0;//各組等待隊(duì)列Intcounta=countb=countc=0;//等待隊(duì)列長度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組進(jìn)程活動(dòng)可以給出B組和C組進(jìn)程活動(dòng)。思考：今有三個(gè)并發(fā)進(jìn)程R，M,P,它們共享了一個(gè)可循環(huán)使用的緩沖區(qū)B,緩沖區(qū)B共有N個(gè)單元。進(jìn)程R負(fù)責(zé)從輸入設(shè)備讀信息，每讀一個(gè)字符后，把它存放在緩沖區(qū)B的一個(gè)單元中；進(jìn)程M負(fù)責(zé)處理讀入的字符，若發(fā)現(xiàn)讀入的字符中有空格符，則把它改成“，”；進(jìn)程P負(fù)責(zé)把處理后的字符取出并打印輸出。當(dāng)緩沖區(qū)單元中的字符被進(jìn)程P取出后，則又可用來存放下一次讀入的字符。請用PV操作為同步機(jī)制寫出它們能正確并發(fā)執(zhí)行的程序。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三個(gè)進(jìn)程共享一個(gè)表格F,Pl對F只讀不寫，P2對F只寫不讀，P3對F先讀后寫。進(jìn)程可同時(shí)讀F,但有進(jìn)程寫時(shí)，其他進(jìn)程不能讀和寫。用1）信號量和P、V操作。（2）管程編寫三進(jìn)程能正確工作的程序。TheP,VcodeUsingPaScal(1)信號量和P、V操作。這是讀-寫者問題的變種。其中，P3既是讀者又是寫者。讀者與寫者之間需要互斥，寫者與寫者之間需要互斥，為提高進(jìn)程運(yùn)行的并發(fā)性，可讓讀者盡量優(yōu)先。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思考如圖所示，四個(gè)進(jìn)程PiG=0…3)和四個(gè)信箱Mj(j=0…3)，進(jìn)程間借助相鄰信箱傳遞消息，即Pi每次從Mi中取一條消息，經(jīng)加工后送入M(i+1)mod4，其中MO、M1、M2、M3分別可存放3、3、2、2個(gè)消息。初始狀態(tài)下，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思考：四個(gè)進(jìn)程A、B、C、D都要讀一個(gè)共享文件F,系統(tǒng)允許多個(gè)進(jìn)程同時(shí)讀文件F。但限制是進(jìn)程A和進(jìn)程C不能同時(shí)讀文件F,進(jìn)程B和進(jìn)程D也不能同時(shí)讀文件F。為了使這四個(gè)進(jìn)程并發(fā)執(zhí)行時(shí)能按系統(tǒng)要求使用文件，現(xiàn)用PV操作進(jìn)行管理，請回答下面的問題：(1)如何定義信號量及初值；(2)在下列的程序中填上適當(dāng)?shù)腜、V操作，以保證它們能正確并發(fā)工作：進(jìn)程A:進(jìn)程B：進(jìn)程C：進(jìn)程D：beginbeginbeginbegin????????????readeF;readeF;readeF;readeF;????????????endendendend(1)定義二個(gè)信號量SI、S2，初值均為1,即：Sl=l,S2=l。其中進(jìn)程A和C使用信號量S1，進(jìn)程B和D使用信號量S2。(2)從⑴到⑻分別為：P(S1)V(S1)P(S2)V(S2)P(S1)V(S1)P(S2)V(S2)思考今有k個(gè)進(jìn)程，它們的