進程管理習題

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

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

3、一個車輪；又設有三個工人，其活動分別為：又設有三個工人，其活動分別為：工人工人1活動：活動：Do 加工一個車架；加工一個車架； 車架放入箱中；車架放入箱中； while(1);工人工人2活動：活動：Do 加工一個車輪；加工一個車輪； 車輪放入箱中；車輪放入箱中； while(1);工人工人3活動：活動：Do 箱中取一車架；箱中取一車架； 箱中取二車輪；箱中取二車輪； 組裝為一臺車；組裝為一臺車； while(1);試用信號量與試用信號量與P、V操作實現三個工人的合作操作實現三個工人的合作首先不考慮死鎖問題，工人首先不考慮死鎖問題，工人1與工人與工人3、工人、工人2與工人與工人3構成生產者與消費

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

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

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

7、： 加工一個車輪；加工一個車輪； 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)； 組裝為一臺車；組裝為一臺車；一座小橋（最多只能承重兩個人）橫跨南一座小橋（最多只能承重兩個人）橫跨南北兩岸，任意時刻同一方向只允許一人過北兩岸，任意時刻同一方向只允許一人過橋，南側橋段和北側橋段較窄只能通過一橋，南側橋段和北側橋段較窄只能通過一人，

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

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

10、個記錄。緩沖區(qū)的大小等于一個記錄大??；一個記錄。緩沖區(qū)的大小等于一個記錄大?。徽堄谜堄肞，V操作來保證文件的正確打印操作來保證文件的正確打印設置設置4個信號量：個信號量：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復制復制PC打印打印PA() 從磁盤讀一從磁盤讀一 個記錄；個記錄； 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 取一個記錄；取一個記錄； V(empty2); 打印記錄打印記錄;緩沖區(qū)緩沖區(qū)1緩沖區(qū)緩沖區(qū)2PA從磁盤讀入從磁盤讀入PB復制復制PC打印打印公共汽車上，司機和售票員的活動分別為：公共汽車上，司機和售票員的活動分別為：司機：司機：啟動車輛；啟動車輛；正常行駛，正常行駛，到站停車到站停車售票員：售票員： 關車

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

13、放一只水果。爸爸桌上有一空盤，允許存放一只水果。爸爸可向盤中放蘋果，也可向盤中放桔子，兒可向盤中放蘋果，也可向盤中放桔子，兒子專等吃盤中的桔子，女兒專等吃盤中的子專等吃盤中的桔子，女兒專等吃盤中的蘋果。規(guī)定當盤空時一次只能放一只水果蘋果。規(guī)定當盤空時一次只能放一只水果供吃者取用，請用供吃者取用，請用P，V原語實現爸爸，兒原語實現爸爸，兒子女兒三個進程的同步。子女兒三個進程的同步。設三個信號量：設三個信號量： 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個座位，有一張登記表，要求：個座位，

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

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

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

18、設因偶數的放與取而同步，設 置信號量置信號量even；P1、P2、P3因共享緩沖因共享緩沖 區(qū)而同步，設置信號量區(qū)而同步，設置信號量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();某銀行提供一個服務窗口和某銀行提供一個服務窗口和

19、10個個供顧客等待的座位。顧客到達銀供顧客等待的座位。顧客到達銀行時，若有空座位，則到取號機行時，若有空座位，則到取號機上領取一個號。等待叫號。取號上領取一個號。等待叫號。取號機每次僅允許一位顧客使用。當機每次僅允許一位顧客使用。當營業(yè)員空閑時，通過叫號選取一營業(yè)員空閑時，通過叫號選取一位顧客，并為其服務。顧客和營位顧客，并為其服務。顧客和營業(yè)員的活動過程描述為：業(yè)員的活動過程描述為：請?zhí)砑颖匾男盘柫亢驼執(zhí)砑颖匾男盘柫亢蚉、V（或（或wait()、signal()）操作，實現上述）操作，實現上述過程的的互斥與同步。要求寫出過程的的互斥與同步。要求寫出完整的過程，說明信號量的含義完整的過程，

20、說明信號量的含義并賦初值。并賦初值。Cobegin process 顧客顧客 從取號機獲得一個號碼從取號機獲得一個號碼; 等待叫號等待叫號; 獲得服務獲得服務; process 營業(yè)員營業(yè)員 while (TRUE) 叫號；叫號； 為顧客服務；為顧客服務； coend互斥資源：取號機（一次只允許一位顧客互斥資源：取號機（一次只允許一位顧客領號），因此，設一個互斥信號量領號），因此，設一個互斥信號量mutex；同步問題同步問題顧客需要獲得空座位等待叫號，當營業(yè)員空閑顧客需要獲得空座位等待叫號，當營業(yè)員空閑時，將選取一位顧客并為其服務。空座位的有、時，將選取一位顧客并為其服務。空座位的有、無影響等

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

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

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