操作系統(tǒng)部分答案

1、26. 假定有如下獨木橋問題：過橋時，同一方向的行人可連續(xù)過橋，當(dāng)某一方向有人過橋時，另一方向的行人必須等待；當(dāng)某一方向無人過橋時，另一方向的行人可以過橋。試用信號量機制解決。答：(1) 將獨木橋的兩個方向分別標(biāo)記為A和B。用整型變量countA和countB分別表示A、B方向上已在獨木橋上的行人數(shù)，初值都設(shè)置為0。需要設(shè)置三個初值都為1的互斥信號量：MA用來實現(xiàn)對countA的互斥訪問，MB用來實現(xiàn)對countB的互斥訪問，mutex用來實現(xiàn)兩個方向的行人對獨木橋的互斥使用。(2)以下使用信號量機制對A方向上的行人過橋和B方向上的行人過橋的算法進行描述：int countA, countB;

2、countA = 0; countB = 0; Semaphore MA,MB,mutex; /定義了三個互斥信號量MA.value=1; MB.value=1; mutex.value=1;cobeginprocess A_direction_cross_bridge_person /A方向上過獨木橋的行人進程P(MA); /實現(xiàn)對臨界資源countA的互斥訪問/當(dāng)A方向上沒有行人過獨木橋時，這時有可能存在B方向上的行人在過獨木橋。 if (countA = 0) P(mutex); /如果當(dāng)前獨木橋正在被使用，說明B方向上的行人正在過橋，則A方向上的行人必須等待。 countA=count

3、A+1; /當(dāng)B方向上沒有行人過橋時，則A方向上的行人可以過獨木橋。因此A方向上已在獨木橋上的行人數(shù)增加1個V(MA); /退出臨界區(qū)過橋； /A方向上的行人通過獨木橋P(MA); /實現(xiàn)對臨界資源countA的互斥訪問 countA=countA-1; /當(dāng)A方向上的行人已經(jīng)通過了獨木橋時，則A方向上在獨木橋上的行人數(shù)需要減少1個 if(countA=0) /如果A方向上在獨木橋上的行人數(shù)減少到0，則 V(mutex); /需要釋放獨木橋臨界資源，喚醒第一個由于在等待獨木橋而處于等待狀態(tài)的B方向上過獨木橋的行人進程（如果此進程存在）V(MA); /退出臨界區(qū)process B_directi

4、on_cross_bridge_person /B方向上過獨木橋的行人進程P(MB); /實現(xiàn)對臨界資源countB的互斥訪問/當(dāng)B方向上沒有行人過獨木橋時，這時有可能存在A方向上的行人在過獨木橋。 if (countB=0) P(mutex); /如果當(dāng)前獨木橋正在被使用，說明A方向上的行人正在過橋，則B方向上的行人必須等待。 countB=countB+1; /當(dāng)A方向上沒有行人過橋時，則B方向上的行人可以過獨木橋。因此B方向上已在獨木橋上的行人數(shù)增加1個V(MB); /退出臨界區(qū)過橋；/B方向上的行人通過獨木橋P(MB); /實現(xiàn)對臨界資源countB的互斥訪問 countB=count

5、B-1; /當(dāng)B方向上的行人已經(jīng)通過了獨木橋時，則B方向上在獨木橋上的行人數(shù)需要減少1個 if(countB=0) /如果B方向上在獨木橋上的行人數(shù)減少到0，則 V(mutex); /需要釋放獨木橋臨界資源，喚醒第一個由于在等待獨木橋而處于等待狀態(tài)的A方向上過獨木橋的行人進程（如果此進程存在）V(MB); /退出臨界區(qū)coend27.有7個并發(fā)執(zhí)行的進程Pi（i=1,2, ,7），若希望它們按照如下圖所示的次序執(zhí)行，試寫出進程并發(fā)執(zhí)行的算法。S5P4 S7S0S2S3P6 P2 P3 S1P7 S4 S6P5 P1 Semaphore S8; /定義一個大小等于8的結(jié)構(gòu)型信號量數(shù)組for(in

6、t i=0;i8;i+) Si.Value=0;process PP()cobegin /偽代碼cobegin和coend表示夾在它們之間的語句可以并發(fā)執(zhí)行P1; V(S1);P2; V(S0);P(S0); P(S1); P3; V(S2); V(S3); V(S4);P(S2); P4; V(S5);P(S4); P5; V(S6);P(S5); P(S3); P6; V(S7);P(S7); P(S6); P7;coend29.在公共汽車上，司機的活動描述為：啟動汽車、正常行車、到站停車；售票員的活動描述為：關(guān)車門、售票、開車門；試寫出司機與售票員之間的同步算法。答：在汽車行駛過程中，司

7、機活動與售票員活動之間的同步關(guān)系為：售票員關(guān)車門后，向司機發(fā)開車信號，司機接到開車信號后啟動汽車，在汽車正常行駛過程中售票員售票，到站時司機停車，售票員在車停后開車門讓乘客上下車。因此司機啟動汽車的動作必須與售票員關(guān)車門的動作取得同步，而售票員開車門的動作也必須與司機到站停車的動作取得同步。在本題中，應(yīng)設(shè)置兩個信號量S1和S2。S1表示是否允許司機啟動汽車（或表示售票員是否已經(jīng)關(guān)好車門），其初值為0；S2表示是否允許售票員開門（或表示司機是否已經(jīng)到站停車了），其初值為0. 采用信號量機制描述司機與售票員之間的同步算法如下：Semaphore S1,S2; /首先定義兩個信號量S1和S2S1.v

8、alue=0; S2.value=0;cobeginprocess driver() process conductor() while(1) while(1) P(S1); 關(guān)車門; 啟動汽車; V(S1); 正常行車; 售票; 到站停車; P(S2); V(S2); 開車門; 上下乘客; coend我們來分析這個過程，首先將信號量S1和S2的初值都設(shè)為0.然后進行以下分析：1.P(S1) ：S1.value = S1.value - 1 = -1 0 ，那么司機進程就自己阻塞起來，等待售票員進程，售票員關(guān)車門。2.V(S1) ：S1.value = S1.value + 1 = 0 = 0

9、，喚醒司機進程，那么司機就開始啟動汽車、正常行車；在此期間，售票員也可以同時進行售票。3.P(S2) ：S2.value = S2.value - 1 = -1 0 ，那么售票員在售完票后，售票員進程就會自己阻塞起來，等待司機進程。這樣就能避免當(dāng)司機還沒到站停車時，售票員就已經(jīng)將車門打開了。而這是不允許的。4.V(S2) ：S2.value = S2.value + 1 = 0 = 0，司機到站停車之后，就喚醒售票員進程，那么售票員就開啟車門讓乘客上下車。那么這個進程就完成了。30一個閱覽室共有100個座位，用一張表來管理，每個表目記錄座位號和讀者姓名。讀者進入時要先在表上登記，離開時要注銷登

10、記。試寫出讀者“進入”和“注銷”之間的同步算法。答：讀者的動作有兩個，一是填表進入閱覽室讀書，這時要考慮閱覽室里是否有座位；二是讀者閱讀完畢，需要注銷登記再離開閱覽室，這時的操作要考慮閱覽室里是否有讀者存在。讀者在閱覽室讀書時，由于沒有引起資源的變動，不算動作變化。因此，設(shè)置算法所涉及的三個信號量：empty資源信號量表示閱覽室里的空座位的數(shù)目，初值為100；full資源信號量表示閱覽室里有人的座位的數(shù)目（或表示閱覽室里的讀者的數(shù)目），初值為0；mutex互斥信號量表示對登記表這個臨界資源的互斥訪問，初值設(shè)為1。使用信號量機制對讀者“進入”閱覽室和“注銷”登記之間的同步算法描述如下：Semap

11、hore empty,full,mutex; /首先定義兩個資源信號量empty、full和一個互斥信號量mutexempty.value=100; full.value=0;mutex.value=1;cobeginprocess getin() /讀者“進入”閱覽室的進程while(1)P (empty); /沒有座位則離開P (mutex); /進入臨界區(qū)填寫登記表;進入閱覽室讀書;V (mutex); /離開臨界區(qū)V (full); /釋放一個讀者資源process getout () /讀者“注銷”登記、離開閱覽室的進程while(1)P(full); /閱覽室是否有人在讀書（是否存

12、在有人的座位）P(mutex); /進入臨界區(qū)注銷登記；離開閱覽室； V(mutex); /離開臨界區(qū)V(empty); /釋放一個座位資源 coend32.假定有3個進程R、W1、W2共享一個緩沖區(qū)B，B中每次只能存放一個整數(shù)。進程R從輸入設(shè)備讀入一個數(shù)進緩沖區(qū)B。若讀入的是奇數(shù)，則由進程W1取出打??；若讀入的是偶數(shù)，則由進程W2取出打印。規(guī)定不能重復(fù)從B中取數(shù)打印。試寫出同步算法。答：需要設(shè)置3個信號量：（1）信號量empty用于表示進程R可向緩沖區(qū)B中讀入的整數(shù)個數(shù)，初值為1，表示進程R能讀入一個整數(shù)到緩沖區(qū)B中。（2）信號量SW1的初值為0，表示開始時緩沖區(qū)B中沒有奇數(shù)可供進程W1讀取

13、。SW1控制R與W1之間的同步。（3）信號量SW2的初值為0，表示開始時緩沖區(qū)B中沒有偶數(shù)可供進程W2讀取。SW2控制R與W2之間的同步。使用信號量機制對這三個進程的同步算法描述如下：Semaphore empty,SW1,SW2; /首先定義3個信號量empty.value=1;SW1.value=0;SW2.value=0;cobeginprocess R()int x;while(1)從輸入設(shè)備上讀一個整數(shù)到x；P(empty); /判斷進程R能否向緩沖區(qū)B中讀入一個整數(shù)。如果不可以，則R進程阻塞起來等待。否則，繼續(xù)向下執(zhí)行。B=x; /把讀入到變量x中的整數(shù)賦值給緩沖區(qū)Bif(x%2=1) V(SW1); /如果讀入的是奇數(shù)，則向進程W1發(fā)出信號else V(SW2); /如果讀入的是偶數(shù)，則向進程W2發(fā)出信號 process W1()int y;while(1)P(S