操作系統(tǒng) 作業(yè)答案

第九題 設有兩個生產(chǎn)者進程A、B和一個銷售者進程C，他們共享一個無限大的倉庫，生產(chǎn)者每次循環(huán)生產(chǎn)一個產(chǎn)品，然后入庫供銷售；銷售者每次循環(huán)從倉庫中取出一個產(chǎn)品進行銷售。如果不允許同時入庫，也不允許邊入庫邊出庫；而且要求生產(chǎn)和消費A產(chǎn)品和B產(chǎn)品的件數(shù)都滿足以下關系：-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，如練習5中，同樣的方法管理，分別使用了信號量SAB和SBA；倉庫的管理只要求出入庫互斥，由于倉庫無限大入庫只需操作互斥就可以完成，出庫要考慮有無產(chǎn)品，SA對應于倉庫中的A產(chǎn)品量，SB對應于倉庫中的B產(chǎn)品量；銷售要滿足：-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；-n<difference<m，即可以取產(chǎn)品A也可以取產(chǎn)品B；答：為了互斥地入庫和出庫，需為倉庫設置一初值為1的互斥信號量mutex；為了使生產(chǎn)的產(chǎn)品件數(shù)滿足-nA的件數(shù)B的件數(shù)m，須設置兩個同步的信號量，其中SAB表示當前允許A生產(chǎn)的產(chǎn)品數(shù)量，其初值為m，SBA表示當前允許B生產(chǎn)的產(chǎn)品數(shù)量，其初值為n；另外，還需設置一個整數(shù)difference表示所銷售的A、B產(chǎn)品數(shù)量之差，而為了同步生產(chǎn)者和銷售者并使銷售的A、B產(chǎn)品的件數(shù)-nA的件數(shù)B的件數(shù)m，還需要設置三個資源信號量，其中S對應于倉庫中的總的產(chǎn)品量，SA對應于倉庫中的A產(chǎn)品量，SB對應于倉庫中的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 storehouse;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)品一件，所以給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<=-n時只能取A產(chǎn)品一件，無A產(chǎn)品則需阻塞 /出庫操作，滿足出入庫操作互斥wait(mutex); take a product A from storehouse; signal(mutex); difference+; /取A產(chǎn)品一件，difference+ else if(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 /-n<difference<m，即可以取產(chǎn)品A也可以取產(chǎn)品B，隨意取一件產(chǎn)品出來，之后再根據(jù)取得產(chǎn)品是A還是B進行處理 /出庫操作，滿足出入庫操作互斥wait(mutex); take a product A 或B from storehouse; signal(mutex); if（product_type=A） /取的是產(chǎn)品A，則信號量SA減1，這里不可能發(fā)生沒有A產(chǎn)品，進程C需要阻塞的情況wait(SA); difference+;/取A產(chǎn)品一件，difference+ else /取的是產(chǎn)品B，則信號量SB減1，這里不可能發(fā)生沒有B產(chǎn)品，進程C需要阻塞的情況wait(SB); difference-;/取B產(chǎn)品一件，difference- Sell the product; main()cobeginA();B();C();例題20解答本題是一個有限緩沖區(qū)的生產(chǎn)者消費者問題，關鍵是找到緩沖區(qū)資源，以及誰是生產(chǎn)者、誰是消費者。本題中煙草、紙和火柴應該看作是產(chǎn)品，桌子是緩沖區(qū)。問題是有幾種產(chǎn)品。煙草、紙和火柴三種原料又不能簡單地看成是三種產(chǎn)品，因為它們并不是以單獨的形式被三個吸煙者進程所競爭的，而是以固定的組合被三個進程所申請的。因此可以考慮：設置三個信號量r、s和t，分別代表三種原料組合，即r表示煙草和紙，s表示紙和火柴，t表示煙草和火柴，初值均為0；桌面上一次只能放一種組合，可以看作是放一個產(chǎn)品的緩沖區(qū)，設置信號量empty初值為1，控制經(jīng)銷商往桌子上放原料；對于三個吸煙者的申請動作也要加以判斷，用三個變量smoker1、smoker2、smoker3，初值為false，當為true時，表示申請資源，得到資源后置為false。四個進程循環(huán)往復，并發(fā)執(zhí)行。經(jīng)銷商進程：吸煙者1進程： 吸煙者2進程： 吸煙者3進程：第一題44. a、b兩點之間是一段東西向的單行車道，現(xiàn)要設計一個自動管理系統(tǒng)，管理規(guī)則如下：當a、b之間有車輛在行駛時同方向的車可以同時駛?cè)隺b段，但另一方向的車必須在ab段外等待；當ab之間無車輛在行駛時，到達a點(或b點)的車輛可以進入ab段，但不能從a點和b點同時駛?cè)?；當某方向在ab段駛出了ab段且暫無車輛進入ab段時，應讓另一方向等待的車輛進入ab段行駛?，F(xiàn)定義兩個計數(shù)器CountE和CountW分別記錄東行和西行車輛進程數(shù)。用PV操作進行管理時的三個信號量為S、SE、SW，程序結(jié)構(gòu)如下：begin S, SE, SW: semaphore; CountE, CountW: Integer; CountE := _(1)_0_; CountW := _(2)_0_; S := _(3)_1_; SE := _(4)_1_; SW := _(5)1_; cobegin Process EASTi (i=1, 2, 3, ) begin _(6)_P（SE）_; if CountE = 0 then_(7)P（S）_; CountE := CountE+1; _(8)_V（SE）_; pass(ab); _(9)_P（SE）_; CountE := CountE-1; if CountE = 0 then _(10)_V（S）_; _(11)_V（SE）_; end; Process WESTj(j=1, 2, 3, ) Begin _(12)_P（SW）_; if CountW = 0 then _(13)_P（S）_; CountW := CountW+1; _(14)_V（SW）_; pass(ba); _(15)_P(SW)_; CountW := CountW-1; if CountW = 0 then _(16)_V(S)_; _(17)_V(SW)_; end; coend;end;44. (1) 0 (2) 0 (3) 1 (4) 1 (5) 1 (6) P(SE) (7) P(S) (8) V(SE) (9) P(SE) (10) V(S)(11) V(SE) (12) P(SW) (13) P(S) (14) V(SW) (15) P(SW) (16) V(S) (17) V(SW)3、如果有三個進程R、W1、W2共享一個緩沖器B，而B中每次只能存放一個數(shù)。當緩沖器中無數(shù)時，進程R可以將從輸入設備上讀入的數(shù)存放到緩沖器中。若存放到緩沖器中的是奇數(shù)，則允許進程W1將其取出打??；若存放到緩沖器中的是偶數(shù)，則允許進程W2將其取出打印。同時規(guī)定：進程R必須等緩沖區(qū)中的數(shù)被取出打印后才能再存放一個數(shù)；進程W1或W2對每次存入緩沖器的數(shù)只能打印一次；W1和W2都不能從空緩沖中取數(shù)。寫出這三個并發(fā)進程能正確工作的程序。答：S為互斥信號量，用來對緩沖器的互斥使用；SO和SE為資源信號量，SO表示是否允許進程W1打印；SE表示是否允許進程W2打印。semaphore S=1,SO=SE=0;buffer B;process R（） int x;while(1)從輸入設備上讀一個數(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);打印y中數(shù); process W2() int z;while(1) wait(SE);z=B;signal(S);打印z中數(shù) ;main()cobegin R(); W1(); W2();