進(jìn)程管理習(xí)題

1、設(shè)有一個(gè)可以裝設(shè)有一個(gè)可以裝A、B兩種物品的倉庫，其兩種物品的倉庫，其容量無限大，但要求倉庫中容量無限大，但要求倉庫中A、B兩種物品兩種物品的數(shù)量滿足下述不等式：的數(shù)量滿足下述不等式： -M A物品數(shù)量物品數(shù)量-B物品數(shù)量物品數(shù)量N 其中，其中，M和和N為正整數(shù)。試用信號(hào)量和為正整數(shù)。試用信號(hào)量和P、V操作描述操作描述A、B兩種物品的入庫過程。兩種物品的入庫過程。已知條件已知條件 -M A物品數(shù)量物品數(shù)量-B物品數(shù)量物品數(shù)量N可以拆分成兩個(gè)不等式，即：可以拆分成兩個(gè)不等式，即： A物品數(shù)量物品數(shù)量-B物品數(shù)量物品數(shù)量N B物品數(shù)量物品數(shù)量-A物品數(shù)量物品數(shù)量M 這兩個(gè)不等式的含義是：倉庫中這兩

2、個(gè)不等式的含義是：倉庫中A物品可物品可以比以比B物品多，但不能超過物品多，但不能超過N個(gè)；個(gè)； B物品可物品可以比以比A物品多，但不能超過物品多，但不能超過M個(gè)。個(gè)。A物品入庫：物品入庫： P(a); A物品入庫；物品入庫； V(b);B物品入庫：物品入庫： P(b); B物品入庫；物品入庫； V(a); 設(shè)兩個(gè)信號(hào)量：設(shè)兩個(gè)信號(hào)量：a=N；b=M如果沒有如果沒有B，A最多只能最多只能N個(gè)；個(gè)；如果沒有如果沒有A，B最多只能最多只能M個(gè)。個(gè)。設(shè)自行車生產(chǎn)線上有一支箱子，其中有設(shè)自行車生產(chǎn)線上有一支箱子，其中有N個(gè)位置個(gè)位置（N3），每個(gè)位置可存放一個(gè)車架或一個(gè)車輪；），每個(gè)位置可存放一個(gè)車架或

3、一個(gè)車輪；又設(shè)有三個(gè)工人，其活動(dòng)分別為：又設(shè)有三個(gè)工人，其活動(dòng)分別為：工人工人1活動(dòng)：活動(dòng)：Do 加工一個(gè)車架；加工一個(gè)車架； 車架放入箱中；車架放入箱中； while(1);工人工人2活動(dòng)：活動(dòng)：Do 加工一個(gè)車輪；加工一個(gè)車輪； 車輪放入箱中；車輪放入箱中； while(1);工人工人3活動(dòng)：活動(dòng)：Do 箱中取一車架；箱中取一車架； 箱中取二車輪；箱中取二車輪； 組裝為一臺(tái)車；組裝為一臺(tái)車； while(1);試用信號(hào)量與試用信號(hào)量與P、V操作實(shí)現(xiàn)三個(gè)工人的合作操作實(shí)現(xiàn)三個(gè)工人的合作首先不考慮死鎖問題，工人首先不考慮死鎖問題，工人1與工人與工人3、工人、工人2與工人與工人3構(gòu)成生產(chǎn)者與消費(fèi)

4、者關(guān)系，通過共構(gòu)成生產(chǎn)者與消費(fèi)者關(guān)系，通過共同的緩沖區(qū)相聯(lián)系。從資源的角度看，箱子同的緩沖區(qū)相聯(lián)系。從資源的角度看，箱子中的空位置相當(dāng)于工人中的空位置相當(dāng)于工人1和工人和工人2的資源，而的資源，而車架和車輪相當(dāng)于工人車架和車輪相當(dāng)于工人3的資源。的資源。定義定義3個(gè)信號(hào)量：個(gè)信號(hào)量： empty=N；（空位置）；（空位置） wheel=0；（車輪）；（車輪） frame=0；（車架）；（車架） empty=N；wheel=0；frame=0；工人工人1： 加工一個(gè)車架；加工一個(gè)車架； P(empy)； 車架放入箱中；車架放入箱中； V(frame)；工人工人2： 加工一個(gè)車輪；加工一個(gè)車輪；

5、P(empy)； 車輪放入箱中；車輪放入箱中； V(wheel)；工人工人3： P(frame)； 箱中取一車架；箱中取一車架； P(wheel)； P(wheel)； 箱中取二車輪；箱中取二車輪； V(empty)； V(empty)； V(empty)； 組裝為一臺(tái)車；組裝為一臺(tái)車；為防止死鎖，箱中車架的為防止死鎖，箱中車架的數(shù)量不能超過數(shù)量不能超過N-2，車輪的，車輪的數(shù)量不能超過數(shù)量不能超過N-1，所以設(shè)，所以設(shè)置：置： s1=N-2，s2=N-1工人工人1： 加工一個(gè)車架；加工一個(gè)車架； P(s1)； 車架放入箱中；車架放入箱中； V(frame)；工人工人2： 加工一個(gè)車輪；加工一

6、個(gè)車輪； P(s2)； 車輪放入箱中；車輪放入箱中； V(wheel)；工人工人3： P(frame)； 箱中取一車架；箱中取一車架； V(s1)； P(wheel)； P(wheel)； 箱中取二車輪；箱中取二車輪； V(s2)； V(s2)； 組裝為一臺(tái)車；組裝為一臺(tái)車；為防止死鎖，箱中車架的為防止死鎖，箱中車架的數(shù)量不能超過數(shù)量不能超過N-2，車輪的，車輪的數(shù)量不能超過數(shù)量不能超過N-1，所以設(shè)，所以設(shè)置：置： s1=N-2，s2=N-1，empty=N工人工人1： 加工一個(gè)車架；加工一個(gè)車架； P(s1)； P(empty)； 車架放入箱中；車架放入箱中； V(frame)；工人工人2

7、： 加工一個(gè)車輪；加工一個(gè)車輪； P(s2)； P(empty)； 車輪放入箱中；車輪放入箱中； V(wheel)；工人工人3： P(frame)； 箱中取一車架；箱中取一車架； V(empty)； V(s1)； P(wheel)； P(wheel)； 箱中取二車輪；箱中取二車輪； V(empty); V(empty); V(s2)； V(s2)； 組裝為一臺(tái)車；組裝為一臺(tái)車；一座小橋（最多只能承重兩個(gè)人）橫跨南一座小橋（最多只能承重兩個(gè)人）橫跨南北兩岸，任意時(shí)刻同一方向只允許一人過北兩岸，任意時(shí)刻同一方向只允許一人過橋，南側(cè)橋段和北側(cè)橋段較窄只能通過一橋，南側(cè)橋段和北側(cè)橋段較窄只能通過一人，

8、橋中央一處寬敞，允許兩個(gè)人通過或人，橋中央一處寬敞，允許兩個(gè)人通過或歇息。試用信號(hào)量和歇息。試用信號(hào)量和P、V操作寫出南、北操作寫出南、北兩岸過橋的同步算法。兩岸過橋的同步算法。load控制橋上人控制橋上人數(shù)，數(shù)，north控制北控制北段的互斥使用，段的互斥使用，south控制南段互控制南段互斥使用斥使用初始值：初始值：load=2, north=1, south=1To 南：南： P(load)； P(north)； 過北橋段；過北橋段； 到橋中間；到橋中間； V(north)； P(south)； 過南橋段；過南橋段； 到達(dá)南岸；到達(dá)南岸； V(south)； V(load)；To 北：北

9、： P(load)； P(south)； 過南橋段；過南橋段； 到橋中間；到橋中間； V(south)； P(north)； 過北橋段；過北橋段； 到達(dá)北岸；到達(dá)北岸； V(north)； V(load)；有有3個(gè)進(jìn)程個(gè)進(jìn)程PA，PB和和PC合作解決文件打印問合作解決文件打印問題：題：PA將文件記錄從磁盤讀入主存的緩沖區(qū)將文件記錄從磁盤讀入主存的緩沖區(qū)1，每執(zhí)，每執(zhí)行一次讀一個(gè)記錄；行一次讀一個(gè)記錄；PB將緩沖區(qū)將緩沖區(qū)1的內(nèi)容復(fù)制到緩沖區(qū)的內(nèi)容復(fù)制到緩沖區(qū)2，每執(zhí)行一，每執(zhí)行一次復(fù)制一個(gè)記錄；次復(fù)制一個(gè)記錄；PC將緩沖區(qū)將緩沖區(qū)2的內(nèi)容打印出來，每執(zhí)行一次打印的內(nèi)容打印出來，每執(zhí)行一次打印一

10、個(gè)記錄。緩沖區(qū)的大小等于一個(gè)記錄大?。灰粋€(gè)記錄。緩沖區(qū)的大小等于一個(gè)記錄大?。徽?qǐng)用請(qǐng)用P，V操作來保證文件的正確打印操作來保證文件的正確打印設(shè)置設(shè)置4個(gè)信號(hào)量：個(gè)信號(hào)量：empty1、empty2、full1、full2empty1及及empty2分別表示緩沖區(qū)分別表示緩沖區(qū)1及緩沖區(qū)及緩沖區(qū)2是否為空，初值為是否為空，初值為1full1，full2分別表示緩沖區(qū)分別表示緩沖區(qū)1及緩沖區(qū)及緩沖區(qū)2是否是否有記錄可供處理，其初值為有記錄可供處理，其初值為0緩沖區(qū)緩沖區(qū)1緩沖區(qū)緩沖區(qū)2PA從磁盤讀入從磁盤讀入PB復(fù)制復(fù)制PC打印打印PA() 從磁盤讀一從磁盤讀一 個(gè)記錄；個(gè)記錄； P(empty1

11、)； 將記錄存入將記錄存入 緩沖區(qū)緩沖區(qū)1； V(full1)；PB() P(full1)； 從緩沖區(qū)從緩沖區(qū)1中中 取出記錄；取出記錄； V(empty1)； P(empty2)； 將記錄存入緩將記錄存入緩 沖區(qū)沖區(qū)2； V(full2);PC() P(full2); 從緩沖區(qū)從緩沖區(qū)2 取一個(gè)記錄；取一個(gè)記錄； V(empty2); 打印記錄打印記錄;緩沖區(qū)緩沖區(qū)1緩沖區(qū)緩沖區(qū)2PA從磁盤讀入從磁盤讀入PB復(fù)制復(fù)制PC打印打印公共汽車上，司機(jī)和售票員的活動(dòng)分別為：公共汽車上，司機(jī)和售票員的活動(dòng)分別為：司機(jī)：司機(jī)：啟動(dòng)車輛；啟動(dòng)車輛；正常行駛，正常行駛，到站停車到站停車售票員：售票員： 關(guān)車

12、門；關(guān)車門； 售票；售票； 開車門；開車門；設(shè)信號(hào)量設(shè)信號(hào)量S1：是否允許司機(jī)啟動(dòng)汽車，初值為：是否允許司機(jī)啟動(dòng)汽車，初值為0， S2：是否允許售票員開門，初值為：是否允許售票員開門，初值為0Driver() While (1) P(S1); 啟動(dòng)汽車；啟動(dòng)汽車； 正常行車；正常行車； 到站停車；到站停車； V(S2); Busman() While (1) 關(guān)車門關(guān)車門; V(S1)； 售票；售票； P(S2)； 開車門；開車門； 上下乘客；上下乘客； Int s1=0;Int s2=0;Main( ) Cobegin Driver(); Busman(); Coend 桌上有一空盤，允許存

13、放一只水果。爸爸桌上有一空盤，允許存放一只水果。爸爸可向盤中放蘋果，也可向盤中放桔子，兒可向盤中放蘋果，也可向盤中放桔子，兒子專等吃盤中的桔子，女兒專等吃盤中的子專等吃盤中的桔子，女兒專等吃盤中的蘋果。規(guī)定當(dāng)盤空時(shí)一次只能放一只水果蘋果。規(guī)定當(dāng)盤空時(shí)一次只能放一只水果供吃者取用，請(qǐng)用供吃者取用，請(qǐng)用P，V原語實(shí)現(xiàn)爸爸，兒原語實(shí)現(xiàn)爸爸，兒子女兒三個(gè)進(jìn)程的同步。子女兒三個(gè)進(jìn)程的同步。設(shè)三個(gè)信號(hào)量：設(shè)三個(gè)信號(hào)量： S：表示盤子是否：表示盤子是否為空，初值為為空，初值為1； So：表示盤中是：表示盤中是否有桔子，初值否有桔子，初值為為0 ； Sa：表示盤中是：表示盤中是否有蘋果，初值否有蘋果，初值為為

14、0。int s=1;int sa=0;int so=0;main() cobegin father(); son(); daughter(); coend father() While (1) P(s); 將水果放入盤中；將水果放入盤中； if (放入的是桔子放入的是桔子) v(so) else v(sa); son() While (1) P(so); 從盤中取出桔子；從盤中取出桔子； v(s); 吃桔子；吃桔子； daughter() While (1) P(sa); 從盤中取出蘋果；從盤中取出蘋果； v(s); 吃蘋果；吃蘋果； 圖書館有圖書館有100個(gè)座位，有一張登記表，要求：個(gè)座位，

15、有一張登記表，要求：閱讀者進(jìn)入時(shí)登記，取得座位號(hào)；閱讀者進(jìn)入時(shí)登記，取得座位號(hào)；出來時(shí)，注銷；出來時(shí)，注銷；登記表同時(shí)只能由一個(gè)人使用；登記表同時(shí)只能由一個(gè)人使用；用用P、V原語描述一個(gè)讀者的使用過程原語描述一個(gè)讀者的使用過程信號(hào)量信號(hào)量SN，表示可用座位數(shù)，初值為，表示可用座位數(shù)，初值為100；信號(hào)量信號(hào)量sb, 表示登記表是否正在使用，初值表示登記表是否正在使用，初值為為1；reader(int i) enter()； 閱讀閱讀; outer()enter( ) P(SN) P(sb) 登記；登記； V(sb)；outer( ) P(sb); 注銷；注銷； V(sb); V(SN);三個(gè)進(jìn)

16、程三個(gè)進(jìn)程P1、P2、P3互斥使用一個(gè)包含互斥使用一個(gè)包含N（N0）個(gè)單元的緩沖區(qū)。）個(gè)單元的緩沖區(qū)。P1每次用每次用produce()生成一個(gè)正整數(shù)并用生成一個(gè)正整數(shù)并用put()送入緩送入緩沖區(qū)某已空單元中；沖區(qū)某已空單元中；P2每次用每次用getodd()從該從該緩沖區(qū)中取出一個(gè)奇數(shù)并用緩沖區(qū)中取出一個(gè)奇數(shù)并用countodd()統(tǒng)計(jì)統(tǒng)計(jì)奇數(shù)個(gè)數(shù)；奇數(shù)個(gè)數(shù)；P3每次用每次用geteven()從該緩沖區(qū)從該緩沖區(qū)中取出一個(gè)偶數(shù)并用中取出一個(gè)偶數(shù)并用counteven()統(tǒng)計(jì)偶數(shù)統(tǒng)計(jì)偶數(shù)個(gè)數(shù)。請(qǐng)用信號(hào)量機(jī)制實(shí)現(xiàn)這三個(gè)進(jìn)程的個(gè)數(shù)。請(qǐng)用信號(hào)量機(jī)制實(shí)現(xiàn)這三個(gè)進(jìn)程的同步和互斥活動(dòng)，并說明所定義信號(hào)量

17、的同步和互斥活動(dòng)，并說明所定義信號(hào)量的含義。要求用偽碼描述。含義。要求用偽碼描述。互斥信號(hào)量：互斥信號(hào)量：mutex初值為初值為1；同步信號(hào)量：同步信號(hào)量：P1、P2因奇數(shù)的放與取而同因奇數(shù)的放與取而同步，設(shè)置信號(hào)量步，設(shè)置信號(hào)量odd；P1、P3因偶數(shù)的放與因偶數(shù)的放與取而同步，設(shè)置信號(hào)量取而同步，設(shè)置信號(hào)量even；P1、P2、P3因共享緩沖區(qū)而同步，設(shè)置信號(hào)量因共享緩沖區(qū)而同步，設(shè)置信號(hào)量empty?；コ庑盘?hào)量：互斥信號(hào)量：mutex初值為初值為1；同步信號(hào)量：同步信號(hào)量：P1、P2因奇數(shù)的放與取而同步，設(shè)置信號(hào)量因奇數(shù)的放與取而同步，設(shè)置信號(hào)量 odd；P1、P3因偶數(shù)的放與取而同步，

18、設(shè)因偶數(shù)的放與取而同步，設(shè) 置信號(hào)量置信號(hào)量even；P1、P2、P3因共享緩沖因共享緩沖 區(qū)而同步，設(shè)置信號(hào)量區(qū)而同步，設(shè)置信號(hào)量empty。P1： P(empty); P(mutex); put(); V(mutex); If number%2=0 V(even) Else V(odd);P2： P(odd); P(mutex); getodd(); V(mutex); V(empty); countodd();P3： P(even); P(mutex); geteven(); V(mutex); V(empty); counteven();某銀行提供一個(gè)服務(wù)窗口和某銀行提供一個(gè)服務(wù)窗口和

19、10個(gè)個(gè)供顧客等待的座位。顧客到達(dá)銀供顧客等待的座位。顧客到達(dá)銀行時(shí)，若有空座位，則到取號(hào)機(jī)行時(shí)，若有空座位，則到取號(hào)機(jī)上領(lǐng)取一個(gè)號(hào)。等待叫號(hào)。取號(hào)上領(lǐng)取一個(gè)號(hào)。等待叫號(hào)。取號(hào)機(jī)每次僅允許一位顧客使用。當(dāng)機(jī)每次僅允許一位顧客使用。當(dāng)營業(yè)員空閑時(shí)，通過叫號(hào)選取一營業(yè)員空閑時(shí)，通過叫號(hào)選取一位顧客，并為其服務(wù)。顧客和營位顧客，并為其服務(wù)。顧客和營業(yè)員的活動(dòng)過程描述為：業(yè)員的活動(dòng)過程描述為：請(qǐng)?zhí)砑颖匾男盘?hào)量和請(qǐng)?zhí)砑颖匾男盘?hào)量和P、V（或（或wait()、signal()）操作，實(shí)現(xiàn)上述）操作，實(shí)現(xiàn)上述過程的的互斥與同步。要求寫出過程的的互斥與同步。要求寫出完整的過程，說明信號(hào)量的含義完整的過程，

20、說明信號(hào)量的含義并賦初值。并賦初值。Cobegin process 顧客顧客 從取號(hào)機(jī)獲得一個(gè)號(hào)碼從取號(hào)機(jī)獲得一個(gè)號(hào)碼; 等待叫號(hào)等待叫號(hào); 獲得服務(wù)獲得服務(wù); process 營業(yè)員營業(yè)員 while (TRUE) 叫號(hào)；叫號(hào)； 為顧客服務(wù)；為顧客服務(wù)； coend互斥資源：取號(hào)機(jī)（一次只允許一位顧客互斥資源：取號(hào)機(jī)（一次只允許一位顧客領(lǐng)號(hào)），因此，設(shè)一個(gè)互斥信號(hào)量領(lǐng)號(hào)），因此，設(shè)一個(gè)互斥信號(hào)量mutex；同步問題同步問題顧客需要獲得空座位等待叫號(hào)，當(dāng)營業(yè)員空閑顧客需要獲得空座位等待叫號(hào)，當(dāng)營業(yè)員空閑時(shí)，將選取一位顧客并為其服務(wù)。空座位的有、時(shí)，將選取一位顧客并為其服務(wù)?？兆坏挠小o影響等

21、待顧客數(shù)量，顧客的有、無決定了營無影響等待顧客數(shù)量，顧客的有、無決定了營業(yè)員是否能開始服務(wù)，故分別設(shè)置信號(hào)量業(yè)員是否能開始服務(wù)，故分別設(shè)置信號(hào)量empty和和full來實(shí)現(xiàn)這一同步關(guān)系；來實(shí)現(xiàn)這一同步關(guān)系；顧客獲得空座位后，需要等待叫號(hào)和被服務(wù)。顧客獲得空座位后，需要等待叫號(hào)和被服務(wù)。這樣，顧客與營業(yè)員就服務(wù)何時(shí)開始又構(gòu)成了這樣，顧客與營業(yè)員就服務(wù)何時(shí)開始又構(gòu)成了一個(gè)同步關(guān)系，定義信號(hào)量一個(gè)同步關(guān)系，定義信號(hào)量service來完成這一來完成這一同步過程。同步過程。semaphore mutex=1; /互斥使用取號(hào)機(jī)互斥使用取號(hào)機(jī)semaphore empty=10; /空座位的數(shù)量空座位的數(shù)

22、量semaphore full=0; /已占座位的數(shù)量已占座位的數(shù)量semaphore service=0; /等待叫號(hào)等待叫號(hào)cobegin process 顧客顧客 process 營業(yè)員營業(yè)員 P(empty); while(TRUE) P(mutex); 從取號(hào)機(jī)獲得一個(gè)號(hào)；從取號(hào)機(jī)獲得一個(gè)號(hào)； P(full); V(mutex); V(empty); V(full); V(service); /叫號(hào)叫號(hào) P(service); /等待叫號(hào)等待叫號(hào) 為顧客服務(wù)；為顧客服務(wù)； 獲得服務(wù)；獲得服務(wù)； coend評(píng)分說明評(píng)分說明能正確給出互斥信號(hào)量定義、含義及初值，能正確給出互斥信號(hào)量定義、

23、含義及初值，給給1分。分。能正確給出能正確給出3個(gè)同步信號(hào)量定義、含義及初個(gè)同步信號(hào)量定義、含義及初值，給值，給2分。分。營業(yè)員進(jìn)程描述正確的，給營業(yè)員進(jìn)程描述正確的，給2分。分。顧客進(jìn)程描述中，互斥描述正確的，給顧客進(jìn)程描述中，互斥描述正確的，給1分；分；同步描述正確的，給同步描述正確的，給2分；共分；共3分。分。其他正確解答，參照其他正確解答，參照- 的標(biāo)準(zhǔn)給分。的標(biāo)準(zhǔn)給分。某系統(tǒng)有某系統(tǒng)有R1、R2和和R3共共3種資源，在種資源，在T0時(shí)刻時(shí)刻P1、P2、P3和和P4這這4個(gè)進(jìn)程對(duì)資源的個(gè)進(jìn)程對(duì)資源的占用和需求情況見下頁表，此時(shí)系統(tǒng)的可占用和需求情況見下頁表，此時(shí)系統(tǒng)的可用資源向量為用資源向量為 (2, 1, 2)，問題：，問題： 將系統(tǒng)各種資源總數(shù)和此刻各進(jìn)程對(duì)資將系統(tǒng)各種資源總數(shù)和此刻各進(jìn)程對(duì)資源的需求數(shù)目用向量或矩陣表示出來；源的需求數(shù)目用向量或矩陣表示出來； 如果此時(shí)如果此時(shí)P1和和P2均發(fā)出資源請(qǐng)求向量均發(fā)出資源請(qǐng)求向量Request (1,0,1)，為保證系統(tǒng)的安全性，為保證系統(tǒng)的安全性，應(yīng)如何分配資源給這兩個(gè)進(jìn)程？說明采應(yīng)如何分配資源給這兩個(gè)進(jìn)程？說明采用策略的原因。用策略的原因。MaxUsed (Allocation) R1 R2 R3 R1 R2 R3P1 3 2 2