2022年進程同步典型例題

1、學習必備歡迎下載進程同步練習題1. 在公共汽車上，司機和售票員的工作流程如圖所示。為保證乘客的安全，司機和售票員應(yīng)密切配合協(xié)調(diào)工作。請用信號量來實現(xiàn)司機與售票員之間的同步。司機啟動車輛正常行車到站停車售票員關(guān)車門售票開車門圖司機和售票員工作流程圖 約束：怎么密切配合協(xié)調(diào)工作才能保證安全呢？a)關(guān)車門 之后再 啟動車輛 ；利用前驅(qū)圖解釋b)到站停車 之后再 開車門 ； 根據(jù)約束定義信號量；關(guān)車門 和啟動車輛需要一個信號量進行同步s1； 到站停車 和開車門之間需要一個信號量進行同步 s2； 建立幾個進程呢？a)為司機 建立一個進程 driver；b)為售票員 建立一個進程 conductor；dr

2、iver：repeat 啟動車輛；正常行駛；到站停車；until false; conductor：repeat 關(guān)車門；售票；開車門；until false; 加入同步關(guān)系：var s1,s2:semorphore=0,0; 精品學習資料 可選擇p d f - - - - - - - - - - - - - - 第 1 頁，共 20 頁 - - - - - - - - -學習必備歡迎下載driver：repeat wait (s1); 啟動車輛；正常行駛；到站停車；signal(s2) until false; conductor：repeat 關(guān)車門；signal(s1); 售票；wait

3、(s2) 開車門；until false; main() driver(); conductor (); 2. 桌子上有一只盤子，盤子中只能放一只水果。爸爸專向盤子中放蘋果，媽媽專向盤子中放橘子，一個兒子專等吃盤子中的橘子，一個女兒專等吃盤子中的蘋果。用pv 操作實現(xiàn)他們之間的同步機制。分析：約束：a)爸爸和媽媽競爭盤子，往盤子放水果，爸爸在放時，媽媽等待，或者相反；b)爸爸和女兒要同步，即爸爸放完蘋果之后通知女兒來吃；同時女兒吃完之后要通知盤子可用；c)媽媽和兒子要同步，即媽媽放完橘子之后通知兒子來吃；同時兒子吃完之后要通知盤子可用； 經(jīng)上述分析可知：需要 3 個信號量：s1表示臨界資源盤子

4、， 初值 1； 爸爸和女兒需要一個信號量進行同步s2=0 媽媽和兒子需要一個信號量進行同步s3=0; 建立進程？爸爸：媽媽：女兒：兒子：repeat repeat repeat repeat 精品學習資料 可選擇p d f - - - - - - - - - - - - - - 第 2 頁，共 20 頁 - - - - - - - - -學習必備歡迎下載取一個蘋果；取一個橘子；從盤子取一個蘋果；從盤子取一個橘子；放入盤子；放入盤子吃蘋果；吃橘子；until false; until false; until false; until false; 加入同步關(guān)系。爸爸：媽媽：女兒：兒子：repe

5、at repeat repeat repeat wait(s2); wait(s3); 取一個蘋果；取一個橘子；從盤子取一個蘋果；從盤子取一個橘子；wait(s1); wait(s1); signal(s1); signal(s1); 放入盤子；放入盤子吃蘋果；吃橘子；signal(s2); signal(s3); until false; until false; until false; until false; 3. a，b 兩點之間是一段東西向的單行車道，現(xiàn)要設(shè)計一個自動管理系統(tǒng)，管理規(guī)則如下：（1）當 ab之間有車輛在行駛時同方向的車可以同時駛?cè)隺b 段，但另一方向的車必須在ab段外

6、等待；（2）當 ab 之間無車輛在行駛時，到達a 點（或 b 點）的車輛可以進入ab 段，但不能從a點和 b 點同時駛?cè)?；?）當某方向在 ab 段行駛的車輛駛出了ab段且暫無車輛進入ab 段時，應(yīng)讓另一方向等待的車輛進入 ab段行駛。請用信號量為工具，對ab 段實現(xiàn)正確管理以保證行駛安全。分析： 約束：a)ab 兩點的單行車道是一種臨界資源；兩端的車輛對該資源進行競爭；b)同步關(guān)系：（1） ， （3） ； 經(jīng)上述分析可知：首先，設(shè)置互斥信號量sab=1，用于 a、b 點的車輛互斥進入ab 段；然后，分別設(shè)置 共享變量 ab=0 用于記錄當前 ab 段上由 a 點進入的車輛數(shù)量； 共享變量ba

7、=0 用于記錄當前 ab=段上由 b 點進入車輛的數(shù)量；最后，設(shè)置互斥信號量s1=1 用于 ab 段的車輛互斥訪問共享變量ab；設(shè)置互斥信號量s2=1用于 ba 段的車輛互斥訪問共享變量ba建立進程？semaphore s1=1,s2=1,sab=1; int ab=ba=0; pab：pba：repeat repeat wait(s1) wait(s2) 精品學習資料 可選擇p d f - - - - - - - - - - - - - - 第 3 頁，共 20 頁 - - - - - - - - -學習必備歡迎下載abcount=abcount+1; bacount=bacount+1;

8、if abcount=1 then wait(sab) if bacount=1 then wait(sab) signal(s1) signal(s2) 進入車道行駛；進入車道行駛；wait(s1) wait(s2) abcount=abcount-1; bacount=bacount-1; if abcount=0 then signal(sab) if bacount=0 then signal(sab) signal(s1) signal(s2); until false; until false; main() pab(); pba(); 5一條河上架設(shè)了由若干個橋墩組成的一座橋。若

9、一個橋墩只能站一個人， 過河的人只能沿著橋向前走而不能向后退。過河時，只要對岸無人過，就可以過。但不允許河對岸的兩個人同時過，以防止出現(xiàn)死鎖。請給出兩個方向的人順利過河的同步算法。分析： 約束：a)橋?qū)儆谂R界資源，兩岸的人對該資源進行競爭；b)橋上的人數(shù)是有限制的，設(shè)這個橋由n 個橋墩構(gòu)成，橋上同時只能有n 個人過橋，其它人要進行等待。相當于共享資源數(shù)。 設(shè)置信號量信號量 s：互斥使用橋，初值為1 變量 count1：方向 1 上過河人計數(shù)器變量 count2：方向 2 上過河人計數(shù)器信號量 scount1 ：對方向 1 上過河人計數(shù)器count1的互斥使用，初值為1 信號量 scount2

10、：對方向 2 上過河人計數(shù)器count2的互斥使用，初值為1 信號量 scount ：代表橋上過河人的計數(shù)信號量，初值為橋墩個數(shù)n 建立進程semaphore s, scount1, scount2, scount; int count1, count2; s=1; scount1=1; scount2=1; scount=n; count1=0; count2=0; 精品學習資料 可選擇p d f - - - - - - - - - - - - - - 第 4 頁，共 20 頁 - - - - - - - - -學習必備歡迎下載void direct1(int i) wait(scount1

11、); count1+; if(count1=1) wait(s); signal(scount1); wait(scount); 上橋，過橋，下橋；signal(scount); wait(scount1); count1-; if(count1=0) signal(s); signal(scount1); void direct2(int i) wait(scount2); count2+; if(count2=1) wait(s); signal(scount2); wait(scount); 上橋，過橋，下橋；signal(scount); wait(scount2); count2-;

12、 if(count2=0) signal(s); signal(scount2); 精品學習資料 可選擇p d f - - - - - - - - - - - - - - 第 5 頁，共 20 頁 - - - - - - - - -學習必備歡迎下載main() cobegin direct1(1); direct1(n); direct2(1); direct2(m); 6有一個倉庫，可以存放a 和 b 兩種產(chǎn)品，但要求：（1）每次只能存入一種產(chǎn)品（a 或 b） ；（2）-na 產(chǎn)品數(shù)量 b 產(chǎn)品數(shù)量 m 。其中， n 和 m 是正整數(shù)。試用同步算法描述產(chǎn)品a 與產(chǎn)品 b 的入庫過程。分析：

13、約束：a)倉庫是一種臨界資源，兩種產(chǎn)品為之競爭；b)a 產(chǎn)品數(shù)量不能比b 產(chǎn)品數(shù)量多m 個以上即a 產(chǎn)品數(shù)量比b 產(chǎn)品數(shù)量最多多m-1 個； a 產(chǎn)品數(shù)量不能比b 產(chǎn)品數(shù)量少n 個以上即b 產(chǎn)品數(shù)量比a 產(chǎn)品最多多 n-1 個。 設(shè)置信號量設(shè)置互斥信號量 mutex 互斥使用倉庫；設(shè)置兩個信號量來控制a、b 產(chǎn)品的存放數(shù)量，sa表示當前允許 a 產(chǎn)品比 b 產(chǎn)品多入庫的數(shù)量（當前允許a 產(chǎn)品入庫數(shù)量）；sb表示當前允許 b 產(chǎn)品比 a 產(chǎn)品多入庫的數(shù)量（當前允許b 產(chǎn)品入庫數(shù)量）。初始時， sa為 m 一 1，sb為 n 一 1。當往庫中存放入一個a 產(chǎn)品時，則允許存入b 產(chǎn)品的數(shù)量也增加 1

14、;當往庫中存放入一個b 產(chǎn)品時，則允許存入a 產(chǎn)品的數(shù)量也增加1。 建立進程semaphore mutex=1 ，sa=m-1， sb=n-1; process puta() while(1) 取一個產(chǎn)品；wait(sa); wait(mutex); 將產(chǎn)品入庫；精品學習資料 可選擇p d f - - - - - - - - - - - - - - 第 6 頁，共 20 頁 - - - - - - - - -學習必備歡迎下載signal(mutex); signal(sb); process putb() while(1) 取一個產(chǎn)品；wait(sb); wait(mutex); 將產(chǎn)品入庫；

15、signal(mutex); signal(sa); main() cobegin puta(); putb(); 4將只讀數(shù)據(jù)的進程稱為“讀者”進程，而寫或修改數(shù)據(jù)的進程稱為“寫者”進程。允許多個“讀者”同時讀數(shù)據(jù)，但不允許“寫者”與其他“讀者”或“寫者”同時訪問數(shù)據(jù)。另外，要保證： 一旦有“寫者”等待時，新到達的“讀者”必須等待，直到該“寫者”完成數(shù)據(jù)訪問為止。 試用 p、v 操作正確實現(xiàn)“讀者”與“寫者”的同步。 （第二類讀者寫者問題，信號量解決方法）精品學習資料 可選擇p d f - - - - - - - - - - - - - - 第 7 頁，共 20 頁 - - - - - -

16、- - -學習必備歡迎下載分析： 約束：a)寫者與寫者之間需要互斥訪問；b)讀者與寫者之間需要互斥； （有一個讀者在讀就讓寫者等待） ，因此，此時需要一個計數(shù)變量記錄讀者的數(shù)量。c)允許多個讀者同時讀數(shù)據(jù)；d)一旦有“寫者”等待時，新到達的“讀者”必須等待，直到該“寫者”完成數(shù)據(jù)訪問為止。 建立進程write: repeat 執(zhí)行讀操作until false; read: repeat 執(zhí)行寫操作；until false; 設(shè)置信號量a)設(shè)置互斥信號量 mutex=1 實現(xiàn)寫者與寫者之間的互斥訪問；write: repeat wait(mutex) 執(zhí)行讀操作；signal(mutex); u

17、ntil false; b)實現(xiàn)讀者與寫者之間的互斥， 設(shè)置整型變量 readcount=0記錄讀者數(shù)量， if readcount=1 then wait(mutex) read：repeat readcount+; if(readcount=1) wait(mutex); 執(zhí)行讀操作；readcount- -; if(readcount=0) signal(mutex);精品學習資料 可選擇p d f - - - - - - - - - - - - - - 第 8 頁，共 20 頁 - - - - - - - - -學習必備歡迎下載until false; 由于 readcount 是共享

18、變量，所以讀者之間要互斥訪問， 因此設(shè)置一個互斥信號量rmutex=1. read：repeat wait(rmutex) readcount+; if(readcount=1) wait(mutex); signal(rmutex) 執(zhí)行讀操作；wait(rmutex) readcount- -; if(readcount=0) signal(mutex); signal(rmutex) until false; c)要想實現(xiàn) d） 的互斥，需讓讀者和寫者再共享一個互斥信號量s， 因此設(shè)置 互斥信號量 s=1，一旦有寫者等待時，就wait（s）讓讀者等待。write: repeat wait

19、(wmutex); writecount+; if(writecount=1) wait(s); signal(wmutex); wait(mutex) 執(zhí)行讀操作；signal(mutex); wait(wmutex); writecount- -; if(writecount=0)signal(s); signal(wmutex); until false; read：repeat 精品學習資料 可選擇p d f - - - - - - - - - - - - - - 第 9 頁，共 20 頁 - - - - - - - - -學習必備歡迎下載wait(s); wait(rmutex) r

20、eadcount+; if(readcount=1) wait(mutex); signal(rmutex) signal(s); 執(zhí)行讀操作；wait(rmutex) readcount- -; if(readcount=0) signal(mutex); signal(rmutex) until false; 完整代碼process reader() while(1) wait(s); wait(rmutex); if(readcount=0)wait(mutex); readcount+; signal(rmutex); signal(s); perform read operation

21、; wait(rmutex); readcount- -; if(readcount=0)signal(mutex); signal(rmutex); process writer() while(1) wait(wmutex); writecount+; 精品學習資料 可選擇p d f - - - - - - - - - - - - - - 第 10 頁，共 20 頁 - - - - - - - - -學習必備歡迎下載if(writecount=1) wait(s); signal(wmutex); wait(mutex); perform write operation; signal(m

22、utex); wait(wmutex); writecount- -; if(writecount=0)signal(s); signal(wmutex); main( ) cobegin reader(); writer(); 精品學習資料 可選擇p d f - - - - - - - - - - - - - - 第 11 頁，共 20 頁 - - - - - - - - -學習必備歡迎下載1、在公共汽車上，司機和售票員的工作流程如圖所示。為保證乘客的安全，司機和售票員應(yīng)密切配合協(xié)調(diào)工作。請用信號量來實現(xiàn)司機與售票員之間的同步。司機啟動車輛正常行車到站停車售票員關(guān)車門售票開車門圖司機和售票員

23、工作流程圖【答案】設(shè)置兩個 資源信號量： s1、s2。 s1表示是否允許司機啟動汽車，其初值為0；s2表示是否允許售票員開門，其初值為0. semaphoere s1=s2=0; void driver() while(1) wait(s1); 啟動車輛；正常行車；到站停車；signal(s2); void busman() while(1) 關(guān)車門；signal(s1)；售票；wait(s2)；開車門； 精品學習資料 可選擇p d f - - - - - - - - - - - - - - 第 12 頁，共 20 頁 - - - - - - - - -學習必備歡迎下載 main() cobe

24、gin driver(); busman(); 2. 桌子上有一只盤子，盤子中只能放一只水果。爸爸專向盤子中放蘋果，媽媽專向盤子中放橘子，一個兒子專等吃盤子中的橘子，一個女兒專等吃盤子中的蘋果。用pv 操作實現(xiàn)他們之間的同步機制?！敬鸢浮啃盘柫?s 用來實現(xiàn)盤子的互斥訪問，s1 表示盤子中蘋果個數(shù)， s2表示盤子中橘子的個數(shù)。semaphore s=1,s1=s2=0; void father() while(1) 準備蘋果 ; wait(s); 將蘋果放在盤子內(nèi)；signal(s1); void mother() while(1) 準備橘子 ; wait(s); 將橘子放在盤子內(nèi)；signa

25、l(s2); void daughter() 精品學習資料 可選擇p d f - - - - - - - - - - - - - - 第 13 頁，共 20 頁 - - - - - - - - -學習必備歡迎下載while(1) wait(sl); 從盤子里拿走蘋果；signal(s); 吃蘋果 ; void son() while(1) wait(s2); 從盤子里拿走橘子；signal(s); 吃橘子 ; main() cobegin father(); mother(); daughter(); son(); 3. a，b 兩點之間是一段東西向的單行車道，現(xiàn)要設(shè)計一個自動管理系統(tǒng)，管理規(guī)

26、則如下：（1）當 ab之間有車輛在行駛時同方向的車可以同時駛?cè)隺b 段，但另一方向的車必須在ab段外等待；（2）當 ab 之間無車輛在行駛時，到達a 點（或 b 點）的車輛可以進入ab 段，但不能從a點和 b 點同時駛?cè)耄唬?）當某方向在 ab 段行駛的車輛駛出了ab段且暫無車輛進入ab 段時，應(yīng)讓另一方向等待的車輛進入 ab段行駛。請用信號量為工具，對ab 段實現(xiàn)正確管理以保證行駛安全。【答案】精品學習資料 可選擇p d f - - - - - - - - - - - - - - 第 14 頁，共 20 頁 - - - - - - - - -學習必備歡迎下載此題是讀者 -寫者問題的變形。設(shè)置

27、3 個信號量 s1、s2 和 sab，分別用于從 a 點進入的車互斥訪問 共享變量 ab （用于記錄當前 ab 段上由 a點進入車輛的數(shù)量） ，從 b 點進入的車互斥訪問 共享變量 ba （用于記錄當前ab 段上由 b 點進入車輛的數(shù)量） 和 a、b 點的車輛互斥進入 ab 段。3 個信號量的初值分別為1、1 和 1，兩個共享變量ab 和 ba 的初值分別為 0、0。semaphore s1=1,s2=1,sab=1; int ab=ba=0; void pab() while(1) wait(s1); if(ab=0) wait(sab); ab=ab+1; signal(s1); 車輛從

28、a 點駛向 b 點; wait(s1); ab=ab-1; if(ab=0) signal(sab); signal(s1); void pba() while(1) wait(s2); if(ba=0) wait(sab); ba=ba+1; signal(s2); 車輛從 b 點駛向 a 點; wait(s2); ba=ba-1; if(ba=0) signal(sab); 精品學習資料 可選擇p d f - - - - - - - - - - - - - - 第 15 頁，共 20 頁 - - - - - - - - -學習必備歡迎下載signal(s2); main() cobegin

29、 pab(); pba(); 4. 將只讀數(shù)據(jù)的進程稱為“讀者”進程，而寫或修改數(shù)據(jù)的進程稱為“寫者”進程。允許多個“讀者”同時讀數(shù)據(jù)，但不允許“寫者”與其他“讀者”或“寫者”同時訪問數(shù)據(jù)。另外，要保證：一旦有“寫者”等待時，新到達的“讀者”必須等待，直到該“寫者”完成數(shù)據(jù)訪問為止。試用p、v 操作正確實現(xiàn)“讀者”與“寫者”的同步。（第二類讀者寫者問題，信號量解決方法）【答案】為了使寫者優(yōu)先， 可在原來的讀優(yōu)先算法的基礎(chǔ)上增加一個互斥信號量 s，初值為 1，使得當至少有一個寫者準備訪問共享對象時，它可以使后續(xù)的 讀者進程等待；整型變量 writecount，初值為 0，用來對寫者進行計數(shù)；互斥

30、信號量 wmutex，初值為 1，用來實現(xiàn)多個寫者對writecount進行互斥訪問。process reader() while(1) wait(s); wait(rmutex); if(readcount=0)wait(mutex); readcount+; signal(rmutex); signal(s); perform read operation; wait(rmutex); readcount-; if(readcount=0)signal(mutex); signal(rmutex); 精品學習資料 可選擇p d f - - - - - - - - - - - - - - 第

31、 16 頁，共 20 頁 - - - - - - - - -學習必備歡迎下載 process writer() while(1) wait(wmutex); if(writecount=0)wait(s); writecount+; signal(wmutex); wait(mutex); perform write operation; signal(mutex); wait(wmutex); writecount-; if(writecount=0)signal(s); signal(wmutex); main( ) cobegin reader(); writer(); 5. 一條河上架

32、設(shè)了由若干個橋墩組成的一座橋。若一個橋墩只能站一個人，過河的人只能沿著橋向前走而不能向后退。過河時，只要對岸無人過，就可以過。但不允許河對岸的兩個人同時過，以防止出現(xiàn)死鎖。請給出兩個方向的人順利過河的同步算法。【答案】信號量 s：互斥使用橋，初值為1 信號量 scount1 ：對方向 1 上過河人計數(shù)器count1的互斥使用，初值為1 信號量 scount2 ：對方向 2 上過河人計數(shù)器count2的互斥使用，初值為1 信號量 scount ：代表橋上過河人的計數(shù)信號量，初值為橋墩個數(shù)n 變量 count1：方向 1 上過河人計數(shù)器精品學習資料 可選擇p d f - - - - - - - -

33、 - - - - - - 第 17 頁，共 20 頁 - - - - - - - - -學習必備歡迎下載變量 count2：方向 2 上過河人計數(shù)器semaphore s, scount1, scount2, scount; int count1, count2; s=1; scount1=1; scount2=1; scount=n; count1=0; count2=0; void direct1(int i) wait(scount1); if(count1=0) wait(s); count1+; signal(scount1); wait(scount); 上橋，過橋，下橋；signal(scount); wait(scount1); count1-; if(count1=0) signal(s); signal(scount1); void direct2(int i) wait(scount2); if(count2=0)