進程同步典型例題操作系統(tǒng)

1、進程同步練習題1. 在公共汽車上，司機和售票員的工作流程如圖所示。為保證乘客的安全，司機和售票員應密切配合協(xié)調工作。請用信號量來實現司機與售票員之間的同步。圖 司機和售票員工作流程圖 約束：怎么密切配合協(xié)調工作才能保證安全呢？a) 關車門之后再啟動車輛；利用前驅圖解釋b) 到站停車之后再開車門； 根據約束定義信號量；關車門和啟動車輛需要一個信號量進行同步S1；到站停車和開車門之間需要一個信號量進行同步S2； 建立幾個進程呢？a) 為司機建立一個進程Driver；b) 為售票員建立一個進程Conductor；Driver： Repeat 啟動車輛；正常行駛； 到站停車； Until false;

2、Conductor： Repeat關車門； 售票； 開車門； Until false; 加入同步關系：Var s1,s2:semorphore=0,0; Driver： Repeat Wait (s1); 啟動車輛；正常行駛； 到站停車； Signal(s2) Until false;Conductor： Repeat關車門； Signal(s1); 售票；Wait(s2) 開車門； Until false;main() Driver(); Conductor ();2. 桌子上有一只盤子，盤子中只能放一只水果。爸爸專向盤子中放蘋果，媽媽專向盤子中放橘子，一個兒子專等吃盤子中的橘子，一個女兒專

3、等吃盤子中的蘋果。用PV操作實現他們之間的同步機制。分析：約束：a) 爸爸和媽媽競爭盤子，往盤子放水果，爸爸在放時，媽媽等待，或者相反；b) 爸爸和女兒要同步，即爸爸放完蘋果之后通知女兒來吃；同時女兒吃完之后要通知盤子可用；c) 媽媽和兒子要同步，即媽媽放完橘子之后通知兒子來吃；同時兒子吃完之后要通知盤子可用； 經上述分析可知： 需要3個信號量：S1表示臨界資源盤子，初值1；爸爸和女兒需要一個信號量進行同步S2=0媽媽和兒子需要一個信號量進行同步S3=0; 建立進程？爸爸： 媽媽： 女兒： 兒子： Repeat repeat repeat repeat 取一個蘋果； 取一個橘子； 從盤子取一個

4、蘋果； 從盤子取一個橘子； 放入盤子； 放入盤子 吃蘋果； 吃橘子； Until false; Until false; Until false; Until false; 加入同步關系。爸爸： 媽媽： 女兒： 兒子： Repeat repeat repeat repeat wait(S2); wait(S3); 取一個蘋果； 取一個橘子； 從盤子取一個蘋果； 從盤子取一個橘子； Wait(S1); Wait(S1); signal(S1); signal(S1); 放入盤子； 放入盤子 吃蘋果； 吃橘子； Signal(S2); Signal(S3); Until false; Until

5、false; Until false; Until false;3. a，b兩點之間是一段東西向的單行車道，現要設計一個自動管理系統(tǒng)，管理規(guī)則如下：（1）當ab之間有車輛在行駛時同方向的車可以同時駛入ab段，但另一方向的車必須在ab段外等待；（2）當ab之間無車輛在行駛時，到達a點（或b點）的車輛可以進入ab段，但不能從a點和b點同時駛入；（3）當某方向在ab段行駛的車輛駛出了ab段且暫無車輛進入ab段時，應讓另一方向等待的車輛進入ab段行駛。請用信號量為工具，對ab段實現正確管理以保證行駛安全。分析： 約束：a) ab兩點的單行車道是一種臨界資源；兩端的車輛對該資源進行競爭；b) 同步關系：

6、（1），（3）； 經上述分析可知：首先，設置互斥信號量Sab=1，用于a、b點的車輛互斥進入ab段；然后，分別設置共享變量ab=0用于記錄當前ab段上由a點進入的車輛數量；共享變量ba=0用于記錄當前ab=段上由b點進入車輛的數量；最后，設置互斥信號量S1=1用于ab段的車輛互斥訪問共享變量ab；設置互斥信號量S2=1用于ba段的車輛互斥訪問共享變量ba建立進程？semaphore S1=1,S2=1,Sab=1;int ab=ba=0;Pab： pba：Repeat repeatWait(S1) Wait(s2)abcount=abcount+1; bacount=bacount+1;if

7、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一條河上架設了由若干個橋墩組成的一座橋。若一個橋墩只能站一

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

9、初值為1信號量scount：代表橋上過河人的計數信號量，初值為橋墩個數N 建立進程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);count1+;if(count1=1) wait(s);signal(scount1);wait(scount); 上橋，過橋，下橋；signal(scount);wait(scount1);count1-;if(count1

10、=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-;if(count2=0) signal(s);signal(scount2);main() cobegin direct1(1); direct1(n); direct2(1); direct2(m); 6有一個倉庫，可以存放A和B兩種產品，但要求：（1）每次只能存

11、入一種產品（A或B）；（2）-NA產品數量B產品數量M。其中，N和M是正整數。試用同步算法描述產品A與產品B的入庫過程。分析： 約束：a) 倉庫是一種臨界資源，兩種產品為之競爭；b) A產品數量不能比B產品數量多M個以上即A產品數量比B產品數量最多多M-1個；A產品數量不能比B產品數量少N個以上即B產品數量比A產品最多多N-1個。 設置信號量設置互斥信號量mutex互斥使用倉庫；設置兩個信號量來控制A、B產品的存放數量，sa表示當前允許A產品比B產品多入庫的數量（當前允許A產品入庫數量）；sb表示當前允許B產品比A產品多入庫的數量（當前允許B產品入庫數量）。初始時，sa為M一1，sb為N一1。

12、當往庫中存放入一個A產品時，則允許存入B產品的數量也增加1;當往庫中存放入一個B產品時，則允許存入A產品的數量也增加1。 建立進程semaphore mutex=1，sa=M-1， sb=N-1;process puta() while(1) 取一個產品； wait(sa); wait(mutex); 將產品入庫； signal(mutex); signal(sb); process putb() while(1) 取一個產品； wait(sb); wait(mutex); 將產品入庫； signal(mutex); signal(sa); main() cobegin puta(); put

13、b();4將只讀數據的進程稱為“讀者”進程，而寫或修改數據的進程稱為“寫者”進程。允許多個“讀者”同時讀數據，但不允許“寫者”與其他“讀者”或“寫者”同時訪問數據。另外，要保證：一旦有“寫者”等待時，新到達的“讀者”必須等待，直到該“寫者”完成數據訪問為止。試用P、V操作正確實現“讀者”與“寫者”的同步。（第二類讀者寫者問題，信號量解決方法）分析： 約束：a) 寫者與寫者之間需要互斥訪問；b) 讀者與寫者之間需要互斥；（有一個讀者在讀就讓寫者等待），因此，此時需要一個計數變量記錄讀者的數量。c) 允許多個讀者同時讀數據；d) 一旦有“寫者”等待時，新到達的“讀者”必須等待，直到該“寫者”完成數

14、據訪問為止。 建立進程Write:Repeat 執(zhí)行讀操作Until false;Read:Repeat 執(zhí)行寫操作；Until false; 設置信號量a) 設置互斥信號量mutex=1實現寫者與寫者之間的互斥訪問；Write:Repeat Wait(mutex) 執(zhí)行讀操作； Signal(mutex);Until false;b) 實現讀者與寫者之間的互斥，設置整型變量readcount=0記錄讀者數量，if readcount=1 then wait(mutex)Read：Repeatreadcount+;if(readcount=1) wait(mutex);執(zhí)行讀操作；readco

15、unt- -;if(readcount=0) signal(mutex); until false; 由于readcount 是共享變量，所以讀者之間要互斥訪問，因此設置一個互斥信號量rmutex=1.Read：RepeatWait(rmutex)readcount+;if(readcount=1) wait(mutex);signal(rmutex)執(zhí)行讀操作；Wait(rmutex)readcount- -;if(readcount=0) signal(mutex);signal(rmutex) until false;c) 要想實現d）的互斥，需讓讀者和寫者再共享一個互斥信號量s，因此設

16、置互斥信號量s=1，一旦有寫者等待時，就wait（s）讓讀者等待。Write:Repeatwait(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：RepeatWait(s);Wait(rmutex)readcount+;if(readcount=1) wait(mutex);signal

17、(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;wait(rmutex);readcount- -;if(readcount=0)signal(mutex);s

18、ignal(rmutex); Process writer() while(1) wait(wmutex);writecount+;if(writecount=1) wait(s);signal(wmutex); wait(mutex);perform write operation;signal(mutex);wait(wmutex);writecount- -;if(writecount=0)signal(s);signal(wmutex);Main( )cobegin reader(); writer(); 1、在公共汽車上，司機和售票員的工作流程如圖所示。為保證乘客的安全，司機和售票員

19、應密切配合協(xié)調工作。請用信號量來實現司機與售票員之間的同步。圖 司機和售票員工作流程圖【答案】設置兩個資源信號量：S1、S2。 S1表示是否允許司機啟動汽車，其初值為0；S2表示是否允許售票員開門，其初值為0.semaphoere S1=S2=0;void Driver() while(1) wait(S1); 啟動車輛； 正常行車； 到站停車； signal(S2); void Busman() while(1) 關車門； signal(S1)； 售票； wait(S2)； 開車門； main() cobegin Driver(); Busman(); 2. 桌子上有一只盤子，盤子中只能放一

20、只水果。爸爸專向盤子中放蘋果，媽媽專向盤子中放橘子，一個兒子專等吃盤子中的橘子，一個女兒專等吃盤子中的蘋果。用PV操作實現他們之間的同步機制?！敬鸢浮啃盘柫縎用來實現盤子的互斥訪問，S1表示盤子中蘋果個數，S2表示盤子中橘子的個數。semaphore S=1,S1=S2=0;void father() while(1) 準備蘋果; wait(S); 將蘋果放在盤子內； signal(S1); void mother() while(1) 準備橘子; wait(S); 將橘子放在盤子內； signal(S2); void daughter() while(1) wait(Sl); 從盤子里拿走蘋

21、果； signal(S); 吃蘋果; void son() while(1) wait(S2); 從盤子里拿走橘子； signal(S); 吃橘子; main() cobegin father(); mother(); daughter(); son(); 3. a，b兩點之間是一段東西向的單行車道，現要設計一個自動管理系統(tǒng)，管理規(guī)則如下：（1）當ab之間有車輛在行駛時同方向的車可以同時駛入ab段，但另一方向的車必須在ab段外等待；（2）當ab之間無車輛在行駛時，到達a點（或b點）的車輛可以進入ab段，但不能從a點和b點同時駛入；（3）當某方向在ab段行駛的車輛駛出了ab段且暫無車輛進入ab段

22、時，應讓另一方向等待的車輛進入ab段行駛。請用信號量為工具，對ab段實現正確管理以保證行駛安全?！敬鸢浮看祟}是讀者-寫者問題的變形。設置3個信號量S1、S2和Sab，分別用于從a點進入的車互斥訪問共享變量ab（用于記錄當前ab段上由a點進入車輛的數量），從b點進入的車互斥訪問共享變量ba（用于記錄當前ab段上由b點進入車輛的數量）和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) wai

23、t(Sab); ab=ab+1; signal(S1); 車輛從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); signal(S2); main() cobegin Pab(); Pba(); 4. 將只讀數據的進程稱為“讀者”進程，而寫或修改數據的進程稱為“寫者”進程。允許多個

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

25、) 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); Process writer() while(1) wait(wmutex);if(writecount=0)wait(s);writecount+;signal(wmutex);wait(mutex);perform write operat

26、ion;signal(mutex);wait(wmutex);writecount-;if(writecount=0)signal(s);signal(wmutex);Main( )cobegin reader(); writer(); 5. 一條河上架設了由若干個橋墩組成的一座橋。若一個橋墩只能站一個人，過河的人只能沿著橋向前走而不能向后退。過河時，只要對岸無人過，就可以過。但不允許河對岸的兩個人同時過，以防止出現死鎖。請給出兩個方向的人順利過河的同步算法?！敬鸢浮啃盘柫縮：互斥使用橋，初值為1信號量scount1：對方向1上過河人計數器count1的互斥使用，初值為1信號量scount2：

27、對方向2上過河人計數器count2的互斥使用，初值為1信號量scount：代表橋上過河人的計數信號量，初值為橋墩個數N變量count1：方向1上過河人計數器變量count2：方向2上過河人計數器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(scou