【正文】 0 C 經(jīng)典進(jìn)程同步問(wèn)題(P、V操作解決進(jìn)程同步問(wèn)題)``020450012101101有三個(gè)進(jìn)程，Reader進(jìn)程讀入數(shù)據(jù)number1，將其放入緩沖器B1，Executor進(jìn)程將B1中數(shù)據(jù)取出，處理成數(shù)據(jù)number2，將其放入緩沖器B2，Printer進(jìn)程將number2數(shù)據(jù)取出打印，假設(shè)B1 和B2只能存放一個(gè)數(shù)據(jù)，用P、V操作管理這三個(gè)進(jìn)程的執(zhí)行。 = = 1 。 4分PARBEGINReader：BEGINL1：read number1 。B1=number1 。goto L1；END 6分Executor：BEGINL2：P(full1) 。V(empty1) 。P(empty2) 。V(full2) 。V(empty2) 。goto L3；END 10分PARENDEND``020450023101101若一只盤子一次只能放一個(gè)水果，A只往盤中放蘋果，B只往盤中放梨子，C只從盤中取蘋果，D只從盤中取梨子。``020450023101100semaphore SAB=1。 //C的資源信號(hào)量(用于與A同步)semaphore SD=0。 //測(cè)試盤子是否為空將一蘋果放入盤中；signal(SC) //通知C盤中已有蘋果(可能喚醒C) 4分}}process C:{while(true) {wait(SC)。signal(SAB)。 6分}}process B: //進(jìn)程B的算法描述{while(true) {取一個(gè)梨子；wait(SAB)。 //測(cè)試盤子是否有梨子從盤中取出梨子。 //通知A(或B)盤子一空(可能喚醒A或B)消費(fèi)該梨子。試用PV操作實(shí)現(xiàn)四個(gè)工人的合作。為了防止積壓，倉(cāng)庫(kù)滿時(shí)就停止生產(chǎn)。``020450043101200semaphore mutex, empty, full 。 //互斥信號(hào)量empty=8。 //消費(fèi)者進(jìn)程的同步信號(hào)量 4分parbeginprocess Pi //生產(chǎn)者進(jìn)程{while (1) {生產(chǎn)一個(gè)成品x。 //互斥使用搬運(yùn)設(shè)備用搬運(yùn)設(shè)備將成品放入倉(cāng)庫(kù)。 //倉(cāng)庫(kù)中成品數(shù)增1(可能喚醒一個(gè)消費(fèi)者)V(mutex)。 //互斥使用搬運(yùn)設(shè)備用搬運(yùn)設(shè)備將成品從倉(cāng)庫(kù)取出。 //倉(cāng)庫(kù)中可放成品數(shù)增1(可能喚醒一個(gè)生產(chǎn)者)V(mutex)。當(dāng)B中無(wú)數(shù)時(shí)，進(jìn)程R可將從輸入設(shè)備上讀入的數(shù)存放到緩沖器B中；若存放到B中的是奇數(shù)，則允許進(jìn)程W1將其取出打??；若存放到B中的是偶數(shù)，則允許進(jìn)程Ｗ2將其取出打??；同時(shí)規(guī)定：進(jìn)程R必須等緩沖器中的數(shù)被取出后才能再存放下一個(gè)數(shù)；進(jìn)程W1或W2對(duì)每次存入緩沖器的數(shù)只能打印一次；Ｗ1和Ｗ2都不能從空的緩沖器中取數(shù)。(動(dòng)作部分可用文字描述)``020450053101200semaphore S,S1,S2。 S1=S2=0。P(S)。if (x%2==1) V(S1)。 //若是偶數(shù)，則通知W2 6分}}Process W1{while (1) {P(S1)。 //從緩沖器B中取奇數(shù)存于yV(S)。 //打印 8分}}Process W2{while (1) {P(S2)。 //從緩沖器B中取偶數(shù)存于yV(S)。 10分}}parend``020450064101201進(jìn)程P1使用緩沖區(qū)buffer向進(jìn)程P2，P3，P4發(fā)送消息，要求每當(dāng)Pl向buffer中發(fā)消息時(shí)，只有當(dāng)P2，P3，P4進(jìn)程都讀取這條消息后P1才可向buffer中發(fā)送新的消息。``020450064101200解法一：semaphore S1,S2,S3,S4。===0。for (i=0。i++) { S1[i]=1。}parbeginprocess P1{while (1) {P1生成一個(gè)消息；for (i=0。i++) P(S1[i])。i3。 //通知P2～P4緩沖區(qū)buffer中已有消息}}Process P2{while(1) {P(S[0])。V(S1[0])。}}Process P3{while(1) {P(S[1])。V(S1[1])。}}Process P4{while(1) {P(S[2])。V(S1[2])。}}parend``020450073101201三個(gè)進(jìn)程PPP3互斥使用一個(gè)包含N(N0)個(gè)單元的緩沖區(qū)。請(qǐng)用信號(hào)量機(jī)制實(shí)現(xiàn)這三個(gè)進(jìn)程的同步與互斥活動(dòng)，并說(shuō)明所定義的信號(hào)量的含義。``020450073101200定義P1的資源信號(hào)量empty來(lái)表示緩沖區(qū)中空單元個(gè)數(shù)，用于P1與PP3的同步；定義P2的資源信號(hào)量S1來(lái)表示緩沖區(qū)中奇數(shù)的個(gè)數(shù)，用于P2和P1的同步；定義P3的資源信號(hào)量S2來(lái)表示緩沖區(qū)中偶數(shù)的個(gè)數(shù)，用于P3和P1的同步；定義互斥信號(hào)量mutex，用于三個(gè)進(jìn)程互斥訪問(wèn)緩沖區(qū)。 4分ParbeginP1: beginx := produce( )。 /* 判斷緩沖區(qū)是否有空單元 */P(mutex)。 /* 將生成的數(shù)送入緩沖區(qū)的某個(gè)單元 */if x mod 2=0 then V(S2)。 /*如果是奇數(shù)，向P2發(fā)出信號(hào) */V(mutex)。 /* 緩沖區(qū)中是否有奇數(shù) */P(mutex)。V(empty)。countodd( )。P(mutex)。V(empty)。counteven( )。寫(xiě)進(jìn)程Writer把整數(shù)逐個(gè)存入緩沖區(qū)，讀進(jìn)程Reader則逐個(gè)從緩沖區(qū)中讀出并打印輸出，要求打印的與輸入的完全一樣，即個(gè)數(shù)、次序、數(shù)值一樣。``020450082101200解：(1) 寫(xiě)進(jìn)程與讀進(jìn)程間具體的制約關(guān)系是同步和互斥關(guān)系。mutex=1。 //同步信號(hào)量，表示空閑緩沖區(qū)的數(shù)量full=0。P(empty)。write_an_integer_to_buffer( )。V(full)。P(mutex)。V(mutex)。print_an_integer( )。有一水井和一個(gè)水缸，由小和尚提水入缸供老和尚飲用。水井很窄，每次只能容一個(gè)水桶打水。每次入水、取水僅為1桶水，且不可同時(shí)進(jìn)行。``020450094101200semaphore mutex, empty, full, S。 //互斥信號(hào)量empty=10。 //老和尚的資源信號(hào)量，用于與小和尚同步S=3。 //取一水桶，準(zhǔn)備入水P(empty)。 //互斥從水井取水，倒入水缸中。V(full)。 //釋放水桶 7分}}老和尚j (J1, 2, ... , n) //n個(gè)老和尚進(jìn)程{while (1) {P(S)。 //看看水缸中是否有水P(mutex)。V(mutex)。 //水缸增加一個(gè)桶空間V(S)。 10分}}parend``020450104101501現(xiàn)有3個(gè)生產(chǎn)者PPP3，他們都要生產(chǎn)桔子水，每個(gè)生產(chǎn)者都已分別購(gòu)得兩種不同原料，待購(gòu)得第三種原料后就可配制成桔子水，裝瓶出售。當(dāng)容器中有原料時(shí)需要該原料的生產(chǎn)者可取走，當(dāng)容器空時(shí)供應(yīng)商又可以放入一種原料。試用信號(hào)量和P、V操作，寫(xiě)出供應(yīng)商和3個(gè)生產(chǎn)者之間能正確同步的算法。empty=1。 //開(kāi)始時(shí)容器中無(wú)桔子精，用于阻塞P1fullb=0。 //開(kāi)始時(shí)容器中無(wú)水，用于阻塞P3 2分parbeginprocess 供應(yīng)商{while (true) {隨機(jī)地取一種原料x(chóng)。 //看看容器是否空，不空則等待將x放入容器中。 //通知（或喚醒）P1else if (x是糖) V(fullb)。 //通知（或喚醒）P3 4分}}process P1{while (true) {P(fulla)。V(empty)。若供應(yīng)商因容器不空而阻塞，則喚醒之用三種原料配制成桔子水，裝瓶出售。 //看看容器中是否有糖，若無(wú)則阻塞從容器中取出糖。 //通知供應(yīng)商，容器空了。 8分}}process P3{while (true) {P(fullc)。V(empty)。若供應(yīng)商因容器不空而阻塞，則喚醒之用三種原料配制成桔子水，裝瓶出售。兩個(gè)生產(chǎn)車間每生產(chǎn)一個(gè)零件后都要分別把它們送到裝配車間的貨架FF2上，F(xiàn)1存放零件A，F(xiàn)2存放零件B，F(xiàn)1與F2的容量均為可以存放10個(gè)零件。請(qǐng)用信號(hào)量和P、V操作進(jìn)行正確的管理。mutex=1。 //同步信號(hào)量，表示貨架F1可容納的零件數(shù)empty2=10。 //同步信號(hào)量，表示貨架F1已放的零件數(shù)full2=0。P(empty1)。將一個(gè)零件A放到貨架F1上。V(full1)。P(empty2)。將一個(gè)零件B放到貨架F2上V(mutex)。 8分}}process workerCi ( ) //裝配車間的工人進(jìn)程，i=1, 2, ... , k{while (1) {P(full1)。從貨架F1上取一個(gè)零件AV(mutex)。P(full2)。從貨架F2上取一個(gè)零件BV(mutex)。用零件A、B組裝成一個(gè)產(chǎn)品。F中每次只能存放一個(gè)數(shù)。若存放到F中的數(shù)是5的倍數(shù)，則由進(jìn)程B將其取出并打印，否則由進(jìn)程C將被5除后的余數(shù)打印出來(lái)。``020450123101200begin S1,S2,S3:semaphore。S1:=1。 S3:=0。 P(S1) 。 if R mod 5=0 then V(S2)。 6分 goto L1。process Bbegin L2: P(S2)。 V(S1)。 8分 goto L2。process Cbegin L3: P(S3)。 V(S1) 。 print y。end。end。試用P、V操作來(lái)進(jìn)行管理。進(jìn)程可同時(shí)讀F，但有進(jìn)程寫(xiě)時(shí)，其他進(jìn)程不能讀和寫(xiě)。``020450144101500semaphore Rmutex, mutex。 //前者用于互斥訪問(wèn)共享變量Rcount，后者用于寫(xiě)互斥int Rcount=0。 //互斥訪問(wèn)共享變量RcountRcount=Rcount+1。 //第一個(gè)讀者應(yīng)與寫(xiě)者互斥V(Rmutex)。P(Rmutex)。 //讀者離開(kāi)，讀者數(shù)減1if (Rcount==0) V(mutex)。 6分}process P2{P(mutex)。V(mutex)。 //前半部分與P1相同Rcount=Rcount+1。V(Rmutex)。P(Rmutex)。if (Rcount==0) V(mutex)。P(mutex)。V(mutex)。讀者進(jìn)入和離開(kāi)閱覽室時(shí)都必須在閱覽室入口處的一個(gè)登記表上登記，閱覽室有50個(gè)座位，規(guī)定每次只允許一個(gè)人登記或注銷登記。``020450153101500解：（1）用PV操作描述讀者進(jìn)程的同步算法如下：semaphore mutex=1, seat=50。P(seat)。 //登記需互斥在登記表上登記。 6分在閱覽室閱覽資料。在登記表上注銷。V(seat)。endparend（2）互斥信號(hào)量mutex，其初值為1，用于互斥使用登記表；資源信號(hào)量seat，其初值為50，用于表示閱覽室空座位的數(shù)量?，F(xiàn)在用自動(dòng)分揀系統(tǒng)把黑子、白子分開(kāi)，設(shè)分揀系統(tǒng)有兩個(gè)進(jìn)程P1和P2，其中P1揀白子，P2揀黑子。假設(shè)從揀白子開(kāi)始。``020450162101500semaphore mutex, S1, S2。 //互斥信號(hào)量S1=1。 // P2的同步信號(hào)量，用于與P1同步 4分parbeginProcess P1{while (1) {P(S1)。 //揀子必須互斥揀一白子。V(S2)。 //看看P1是否已撿完一個(gè)白子P(mutex)。V(mutex)。 //通知P1可以揀一白子了 10分}}parend``020450175101501僅有k個(gè)進(jìn)程，它們的標(biāo)號(hào)依次為1，2，…，k，允許它們同時(shí)讀文件file，但必須滿足條件：參加同時(shí)讀文件的進(jìn)程的標(biāo)號(hào)之和需小于或等于k，請(qǐng)使用：(1) 信號(hào)量與P、V操作，編寫(xiě)協(xié)調(diào)多進(jìn)程讀文件的算法程序。 //互斥信號(hào)量，用于互斥訪問(wèn)共享變量sumsemaphore S=0。 //用于記錄和的值，若和大于k，則在S上阻塞int count=0。if (i+sumk) {count ++。 //允許其它進(jìn)程讀P(S)。 //進(jìn)程被喚醒后從L1重新開(kāi)始執(zhí)行}else{sum=sum+i。}Read File。sum=sumi。 //喚醒所有在S上阻塞的進(jìn)程count 。 10分}Parend``020450182