操作系統(tǒng)-第二章部分答案

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

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

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

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

5、/ 退出臨界區(qū)過橋；B方向上的行人通過獨(dú)木橋P(MB);II實(shí)現(xiàn)對(duì)臨界資源 countB的互斥訪問countB=countB-1; II當(dāng)B方向上的行人已經(jīng)通過了獨(dú)木橋時(shí)，則B方向上在獨(dú)木橋上的行人數(shù)需要減少1個(gè)if(countB=0)II如果B方向上在獨(dú)木橋上的行人數(shù)減少到0，則V(mutex); II需要釋放獨(dú)木橋臨界資源，喚醒第一個(gè)由于在等待獨(dú)木橋而處于等待狀態(tài)的A方向上過獨(dú)木橋的行人進(jìn)程(如果此進(jìn)程存在)V(MB);II退出臨界區(qū)coend27有7個(gè)并發(fā)執(zhí)行的進(jìn)程Pi (i=1,2,7 )，若希望它們按照如下圖所示的次序執(zhí)行， 試寫出進(jìn)程并發(fā)執(zhí)行的算法。Semaphore S8; II

6、定義一個(gè)大小等于8的結(jié)構(gòu)型信號(hào)量數(shù)組for(int i=0;i8;i+)Si.V alue=0;process PP() cobegin II偽代碼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.在公共汽車上，司機(jī)的活動(dòng)描述為：啟動(dòng)汽車、正常行車、到站停車；售票員的活 動(dòng)描述為：關(guān)車門、售票、開車門；試寫

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

8、ore S1,S2; /首先定義兩個(gè)信 號(hào)量 S1 和 S2S1.value=0; S2.value=0; cobegin process driver()while(1)P(S1); 啟動(dòng)汽車 ; 正常行車 ; 到站停車 ;V(S2);coendprocess conductor()while(1)關(guān)車門 ;V(S1);P(S2); 開車門 ; 上下乘客 ;我們來分析這個(gè)過程，首先將信號(hào)量 S1 和 S2 的初值都設(shè)為 0.然后進(jìn)行以下分析：1. P(S1) ： S 1 .value = S1.value - 1 = -1 0 ，那么司機(jī)進(jìn)程就自己阻塞起來，等待售票員進(jìn)程，售票 員關(guān)車門。2

9、. V(S1) ： S 1 .value = S1.value + 1 = 0 = 0 ，喚醒司機(jī)進(jìn)程，那么司機(jī)就開始啟動(dòng)汽車、正常行車； 在此期間，售票員也可以同時(shí)進(jìn)行售票。3. P(S2) ：S2.value = S2.value - 1 = -1 0 ，那么售票員在售完票后，售票員進(jìn)程就會(huì)自己阻塞起來， 等待司機(jī)進(jìn)程。這樣就能避免當(dāng)司機(jī)還沒到站停車時(shí)，售票員就已經(jīng)將車門打開了。而這是不允許 的。4. V(S2) ：S2.value = S2.value + 1 = 0 = 0 ，司機(jī)到站停車之后，就喚醒售票員進(jìn)程，那么售票員就 開啟車門讓乘客上下車。那么這個(gè)進(jìn)程就完成了。30一個(gè)閱覽室共

10、有 100 個(gè)座位，用一張表來管理，每個(gè)表目記錄座位號(hào)和讀者姓名。 讀者進(jìn)入時(shí)要先在表上登記，離開時(shí)要注銷登記。試寫出讀者“進(jìn)入”和“注銷”之 間的同步算法。答：讀者的動(dòng)作有兩個(gè)，一是填表進(jìn)入閱覽室讀書，這時(shí)要考慮閱覽室里是否有座位；二是讀者閱 讀完畢，需要注銷登記再離開閱覽室，這時(shí)的操作要考慮閱覽室里是否有讀者存在。讀者在閱覽室 讀書時(shí)，由于沒有引起資源的變動(dòng)，不算動(dòng)作變化。因此，設(shè)置算法所涉及的三個(gè)信號(hào)量： empty 資源信號(hào)量表示閱覽室里的空座位的數(shù)目， 初值為 100；full 資源信號(hào)量表示閱覽室里有人的座位的數(shù)目 (或表示閱覽室里的讀者的數(shù)目) 初值為 0； mutex 互斥信號(hào)

11、量表示對(duì)登記表這個(gè)臨界資源的互斥訪問，初值設(shè)為1。使用信號(hào)量機(jī)制對(duì)讀者“進(jìn)入”閱覽室和“注銷”登記之間的同步算法描述如下：Semaphore empty,full,mutex; / 首先定義兩個(gè)資源信號(hào)量 empty 、 full 和一個(gè)互斥信 號(hào)量 mutex empty.value=100; full.value=0;mutex.value=1;cobeginprocess getin() / 讀者“進(jìn)入”閱覽室的進(jìn)程while(1)/沒有座位則離開/進(jìn)入臨界區(qū)/離開臨界區(qū)/釋放一個(gè)讀者資源P (empty);P (mutex); 填寫登記表 ; 進(jìn)入閱覽室讀書V (mutex);V (f

12、ull);process getout () / 讀者“注銷”登記、離開閱覽室的進(jìn)程while(1)P(full);/ 閱覽室是否有人在讀書 (是否存在有人的座位)P(mutex);/ 進(jìn)入臨界區(qū)注銷登記； 離開閱覽室；V(mutex);/ 離開臨界區(qū)V(empty);/ 釋放一個(gè)座位資源coend32.假定有3個(gè)進(jìn)程R、W1 W2共享一個(gè)緩沖區(qū)B, B中每次只能存放一個(gè)整數(shù)。進(jìn)程 R 從輸入設(shè)備讀入一個(gè)數(shù)進(jìn)緩沖區(qū) B。若讀入的是奇數(shù)，則由進(jìn)程 W1取出打??；若讀入 的是偶數(shù)，則由進(jìn)程 W2取出打印。規(guī)定不能重復(fù)從 B中取數(shù)打印。試寫出同步算法。 答：需要設(shè)置 3 個(gè)信 號(hào)量：(1) 信號(hào)量e

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