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

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

2、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方向上過(guò)獨(dú)木橋的行人進(jìn)程P(MA); /實(shí)現(xiàn)對(duì)臨界資源countA的互斥訪問(wèn)/當(dāng)A方向上沒(méi)有行人過(guò)獨(dú)木橋時(shí)，這時(shí)有可能存在B方向上的行人在過(guò)獨(dú)木橋。 if (countA = 0) P(mutex); /如果當(dāng)前獨(dú)木橋正在被使用，說(shuō)明B方向上的行人正在過(guò)橋，則A方向上的行人必須等待。 countA=count

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

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

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

6、t i=0;i8;i+) Si.Value=0;process PP()cobegin /偽代碼cobegin和coend表示夾在它們之間的語(yǔ)句可以并發(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.在公共汽車(chē)上，司機(jī)的活動(dòng)描述為：?jiǎn)?dòng)汽車(chē)、正常行車(chē)、到站停車(chē)；售票員的活動(dòng)描述為：關(guān)車(chē)門(mén)、售票、開(kāi)車(chē)門(mén)；試寫(xiě)出司機(jī)與售票員之間的同步算法。答：在汽車(chē)行駛過(guò)程中，司

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

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

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

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

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

12、在有人的座位）P(mutex); /進(jìn)入臨界區(qū)注銷(xiāo)登記；離開(kāi)閱覽室； V(mutex); /離開(kāi)臨界區(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取出打?。蝗糇x入的是偶數(shù)，則由進(jìn)程W2取出打印。規(guī)定不能重復(fù)從B中取數(shù)打印。試寫(xiě)出同步算法。答：需要設(shè)置3個(gè)信號(hào)量：（1）信號(hào)量empty用于表示進(jìn)程R可向緩沖區(qū)B中讀入的整數(shù)個(gè)數(shù)，初值為1，表示進(jìn)程R能讀入一個(gè)整數(shù)到緩沖區(qū)B中。（2）信號(hào)量SW1的初值為0，表示開(kāi)始時(shí)緩沖區(qū)B中沒(méi)有奇數(shù)可供進(jìn)程W1讀取

13、。SW1控制R與W1之間的同步。（3）信號(hào)量SW2的初值為0，表示開(kāi)始時(shí)緩沖區(qū)B中沒(méi)有偶數(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)程阻塞起來(lái)等待。否則，繼續(xù)向下執(zhí)行。B=x; /把讀入到變量x中的整數(shù)賦值給緩沖區(qū)Bif(x%2=1) V(SW1); /如果讀入的是奇數(shù)，則向進(jìn)程W1發(fā)出信號(hào)else V(SW2); /如果讀入的是偶數(shù)，則向進(jìn)程W2發(fā)出信號(hào) process W1()int y;while(1)P(S