進(jìn)程同步練習(xí)題

1、進(jìn)程同步練習(xí)題1第二類讀者寫者問題，信號量解決方法2復(fù)印室里有一個操作員為顧客復(fù)印資料，有5把椅子供顧客休息等待復(fù)印。如果沒有顧客，則操作員休息。當(dāng)顧客來到復(fù)印室時，如果有空椅子則坐下來，并喚醒復(fù)印操作員；如果沒有空椅子則必須離開復(fù)印室。3如果有三個進(jìn)程R、W1、W2共享一個緩沖器B，而B中每次只能存放一個數(shù)。當(dāng)緩沖器中無數(shù)時，進(jìn)程R可以將從輸入設(shè)備上讀入的數(shù)存放到緩沖器中。若存放到緩沖器中的是奇數(shù)，則允許進(jìn)程W1將其取出打??；若存放到緩沖器中的是偶數(shù)，則允許進(jìn)程W2將其取出打印。同時規(guī)定：進(jìn)程R必須等緩沖區(qū)中的數(shù)被取出打印后才能再存放一個數(shù)；進(jìn)程W1或W2對每次存入緩沖器的數(shù)只能打印一次；W

2、1和W2都不能從空緩沖中取數(shù)。寫出這三個并發(fā)進(jìn)程能正確工作的程序。4現(xiàn)有四個進(jìn)程R1、R2、W1、W2，它們共享可以存放一個數(shù)的緩沖器B。進(jìn)程R1每次把來自鍵盤的一個數(shù)存入緩沖器B中，供進(jìn)程W1打印輸出；進(jìn)程R2每次從磁盤上讀一個數(shù)存放到緩沖器B中，供進(jìn)程W2打印輸出。為防止數(shù)據(jù)的丟失和重復(fù)打印，問怎樣用信號量操作來協(xié)調(diào)這四個進(jìn)程的并發(fā)執(zhí)行。5有一個倉庫，可以存放A和B兩種產(chǎn)品，但要求：（1）每次只能存入一種產(chǎn)品（A或B）；（2）-NA產(chǎn)品數(shù)量B產(chǎn)品數(shù)量M。其中，N和M是正整數(shù)。試用同步算法描述產(chǎn)品A與產(chǎn)品B的入庫過程。6設(shè)有兩個生產(chǎn)者進(jìn)程A、B和一個銷售者進(jìn)程C，他們共享一個無限大的倉庫，生

3、產(chǎn)者每次循環(huán)生產(chǎn)一個產(chǎn)品，然后入庫供銷售；銷售者每次循環(huán)從倉庫中取出一個產(chǎn)品進(jìn)行銷售。如果不允許同時入庫，也不允許邊入庫邊出庫；而且要求生產(chǎn)和消費A產(chǎn)品和B產(chǎn)品的件數(shù)都滿足以下關(guān)系：-nA的件數(shù)B的件數(shù)m，其中n、m是正整數(shù)。1. 第二類讀者寫者問題，信號量解決方法答：為了使寫者優(yōu)先，可在原來的讀優(yōu)先算法的基礎(chǔ)上增加一個互斥信號量s，初值為1，使得當(dāng)至少有一個寫者準(zhǔn)備訪問共享對象時，它可以使后續(xù)的讀者進(jìn)程等待完成；整型變量writecount，初值為0，用來對寫者進(jìn)行計數(shù)；互斥信號量mutex，初值為1，用來實現(xiàn)多個讀者對寫者writecount進(jìn)行互斥訪問。Process reader()

4、while(1) wait(s);wait(rmutex);if(readcount=0)wait(wmutex);readcount+;signal(rmutex);signal(s);perform read operation;wait(rmutex);readcount-;if(readcount=0)signal(wmutex);signal(rmutex); Process writer() while(1) wait(mutex);if(writecount=0)wait(s);writecount+;signal(mutex);wait(wmutex);perform writ

5、e operation;signal(wmutex);wait(mutex);writecount-;if(writecount=0)signal(s);signal(mutex);Main( )cobegin reader(); writer(); 2. 復(fù)印室里有一個操作員為顧客復(fù)印資料，有5把椅子供顧客休息等待復(fù)印。如果沒有顧客，則操作員休息。當(dāng)顧客來到復(fù)印室時，如果有空椅子則坐下來，并喚醒復(fù)印操作員；如果沒有空椅子則必須離開復(fù)印室。答：信號量：customers表示正在等待復(fù)印的顧客數(shù)量（不包括正在復(fù)印的顧客）operator記錄正在等候顧客的操作員數(shù)，只有1和0mutex用于對wai

6、ting的訪問; 變量：waiting表示等待的顧客數(shù)量。它實際上是customers的一個副本。之所以使用waiting是因為無法讀取信號量的當(dāng)前值。semaphore customers=0,operator=0,mutex=1;waiting=0；process operator( )/操作員進(jìn)程 while(1) wait(customers); /等待顧客到來 復(fù)?。?signal(operator); /通知顧客已經(jīng)完成復(fù)印 process cusotmeri( )/顧客進(jìn)程i wait(mutex); if(waiting5) waiting+; signal(customers

7、); signal(mutex); wait(operator); wait(mutex); waiting-; signal(mutex); elsesignal(mutex); 離開復(fù)印室； main( )cobegin operator( ); customeri( ); 3、如果有三個進(jìn)程R、W1、W2共享一個緩沖器B，而B中每次只能存放一個數(shù)。當(dāng)緩沖器中無數(shù)時，進(jìn)程R可以將從輸入設(shè)備上讀入的數(shù)存放到緩沖器中。若存放到緩沖器中的是奇數(shù)，則允許進(jìn)程W1將其取出打?。蝗舸娣诺骄彌_器中的是偶數(shù)，則允許進(jìn)程W2將其取出打印。同時規(guī)定：進(jìn)程R必須等緩沖區(qū)中的數(shù)被取出打印后才能再存放一個數(shù)；進(jìn)程W

8、1或W2對每次存入緩沖器的數(shù)只能打印一次；W1和W2都不能從空緩沖中取數(shù)。寫出這三個并發(fā)進(jìn)程能正確工作的程序。答：S為互斥信號量，用來對緩沖器的互斥使用；SO和SE為資源信號量，SO表示是否允許進(jìn)程W1打??；SE表示是否允許進(jìn)程W2打印。semaphore S=1,SO=SE=0;buffer B;process R（） int x;while(1)從輸入設(shè)備上讀一個數(shù);x=接收的數(shù);wait(S);B=x;if B=奇數(shù) then signal(SO);else signal(SE); process W1() int y;while(1) wait(SO);y=B;signal(S);打印

9、y中數(shù); process W2() int z;while(1) wait(SE);z=B;signal(S);打印z中數(shù) ; main() cobegin R(); W1(); W2(); 4. 現(xiàn)有四個進(jìn)程R1、R2、W1、W2，它們共享可以存放一個數(shù)的緩沖器B。進(jìn)程R1每次把來自鍵盤的一個數(shù)存入緩沖器B中，供進(jìn)程W1打印輸出；進(jìn)程R2每次從磁盤上讀一個數(shù)存放到緩沖器B中，供進(jìn)程W2打印輸出。為防止數(shù)據(jù)的丟失和重復(fù)打印，問怎樣用信號量操作來協(xié)調(diào)這四個進(jìn)程的并發(fā)執(zhí)行。答：S：互斥訪問緩沖器S1：是否可以供進(jìn)程W1打印輸出S2：是否可以供進(jìn)程W2打印輸出semaphore S=1,S1=S2=

10、0;buffer B;process R1（） int x;while(1)接收來自鍵盤的數(shù);x=接收的數(shù);wait(S);B=x;signal(S1); process R2() int y;while(1) 從磁盤上讀一個數(shù);y=接收的數(shù);wait(S);B=y;signal(S2); process W1() int k;while(1)wait(Sl);k=B;signal(S);打印k中數(shù); process W2() int j;while(1)wait(S2);j=B;signal(S);打印j中數(shù); main() cobegin R1(); R2(); W1(); W2();5、

11、有一個倉庫，可以存放A和B兩種產(chǎn)品，但要求：（1）每次只能存入一種產(chǎn)品（A或B）；（2）-NA產(chǎn)品數(shù)量B產(chǎn)品數(shù)量M。其中，N和M是正整數(shù)。試用同步算法描述產(chǎn)品A與產(chǎn)品B的入庫過程。分析：A產(chǎn)品的數(shù)量不能比B產(chǎn)品的數(shù)量少N個以上，A產(chǎn)品的數(shù)量不能比B產(chǎn)品的數(shù)量多M個以上設(shè)置兩個信號量來控制A、B產(chǎn)品的存放數(shù)量，sa表示當(dāng)前允許A產(chǎn)品比B產(chǎn)品多入庫的數(shù)量，即在當(dāng)前庫存量和B產(chǎn)品不入庫的情況下，還可以允許sa個A產(chǎn)品入庫；sb表示當(dāng)前允許B產(chǎn)品比A產(chǎn)品多入庫的數(shù)量，即在當(dāng)前庫存量和A產(chǎn)品不入庫的情況下，還可以允許sb個B產(chǎn)品入庫。初始時，sa為M一1，sb為N一1。當(dāng)往庫中存放入一個A產(chǎn)品時，則允許

12、存入B產(chǎn)品的數(shù)量也增加1;當(dāng)往庫中存放入一個B產(chǎn)品時，則允許存入A產(chǎn)品的數(shù)量也增加1。 semaphore mutex=1，sa=M-1， sb=N-1;process puta() while(1) 取一個產(chǎn)品； wait(sa); wait(mutex); 將產(chǎn)品入庫； signal(mutex); signal(sb); process putb() while(1) 取一個產(chǎn)品； wait(sb); wait(mutex); 將產(chǎn)品入庫； signal(mutex); signal(sa); main() cobegin puta(); putb();6、設(shè)有兩個生產(chǎn)者進(jìn)程A、B和一個

13、銷售者進(jìn)程C，他們共享一個無限大的倉庫，生產(chǎn)者每次循環(huán)生產(chǎn)一個產(chǎn)品，然后入庫供銷售；銷售者每次循環(huán)從倉庫中取出一個產(chǎn)品進(jìn)行銷售。如果不允許同時入庫，也不允許邊入庫邊出庫；而且要求生產(chǎn)和消費A產(chǎn)品和B產(chǎn)品的件數(shù)都滿足以下關(guān)系：-nA的件數(shù)B的件數(shù)m，其中n、m是正整數(shù)。分析：生產(chǎn)者A、B和消費者之間不能同時將產(chǎn)品入庫和出庫，故倉庫是一個臨界資源。生產(chǎn)的A、B產(chǎn)品必須滿足：-nA的件數(shù)B的件數(shù)m，如練習(xí)5中，同樣的方法管理，分別使用了信號量SAB和SBA；倉庫的管理只要求出入庫互斥，由于倉庫無限大入庫只需操作互斥就可以完成，出庫要考慮有無產(chǎn)品，SA對應(yīng)于倉庫中的A產(chǎn)品量，SB對應(yīng)于倉庫中的B產(chǎn)品量

14、；銷售要滿足：-nA的件數(shù)B的件數(shù)m，用difference表示A的件數(shù)B的件數(shù)，即difference= A的件數(shù)B的件數(shù);difference=-n的時候，不能取產(chǎn)品B，只能取A；difference=m的時候，不能取產(chǎn)品A，只能取B；-ndifferencem，即可以取產(chǎn)品A也可以取產(chǎn)品B；答：為了互斥地入庫和出庫，需為倉庫設(shè)置一初值為1的互斥信號量mutex；為了使生產(chǎn)的產(chǎn)品件數(shù)滿足-nA的件數(shù)B的件數(shù)m，須設(shè)置兩個同步的信號量，其中SAB表示當(dāng)前允許A生產(chǎn)的產(chǎn)品數(shù)量，其初值為m，SBA表示當(dāng)前允許B生產(chǎn)的產(chǎn)品數(shù)量，其初值為n；另外，還需設(shè)置一個整數(shù)difference表示所銷售的A、

15、B產(chǎn)品數(shù)量之差，而為了同步生產(chǎn)者和銷售者并使銷售的A、B產(chǎn)品的件數(shù)-nA的件數(shù)B的件數(shù)m，還需要設(shè)置三個資源信號量，其中S對應(yīng)于倉庫中的總的產(chǎn)品量，SA對應(yīng)于倉庫中的A產(chǎn)品量，SB對應(yīng)于倉庫中的B產(chǎn)品量，它們的初值都為0.Semaphore SAB=m,SBA=n,S=0,SA=0,SB=0,mutex=1;process A( ) while(1)/生產(chǎn)產(chǎn)品，-nA的件數(shù)B的件數(shù)m，方法同第4題wait(SAB);Produce a product A;signal(SBA);/入庫操作，滿足出入庫操作互斥即可wait(mutex);add the product A to the stor

16、ehouse;signal(mutex);signal(SA); /入庫產(chǎn)品A一件，所以給SA增值signal(S); /入庫產(chǎn)品一件，所以給S增值，S是倉庫中全部產(chǎn)品的數(shù)量 process B( ) while(1)/生產(chǎn)產(chǎn)品，-nA的件數(shù)B的件數(shù)m，方法同第4題wait(SBA);Produce a product B;signal(SAB);/入庫操作，滿足出入庫操作互斥即可wait(mutex);add the product A to the storehouse;signal(mutex);signal(SB); /入庫產(chǎn)品A一件，所以給SA增值signal(S); /入庫產(chǎn)品一件

17、，所以給S增值，S是倉庫中全部產(chǎn)品的數(shù)量 process C( ) while(1) wait(S); /首先檢查有無產(chǎn)品，無產(chǎn)品阻塞，有產(chǎn)品，下面操作將會取走一件產(chǎn)品，所以S減1 if(difference=-n) wait(SA); / difference=m) wait(SB); / difference=m時只能取B產(chǎn)品一件，無B產(chǎn)品則需阻塞 /出庫操作，滿足出入庫操作互斥wait(mutex); take a product B from storehouse; signal(mutex); difference-; /取B產(chǎn)品一件，difference- else /-ndifferencem，即可以取產(chǎn)品A也可以取產(chǎn)品B，隨意取一件產(chǎn)品出來，之后再根據(jù)取得產(chǎn)品是A還是B進(jìn)行處理 /出庫操作，滿足出入庫操作互斥wait(mutex); take a product A 或B from storeho