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

1、文檔編碼 : CA8Q4Y4L1L3 HO6P4U4Z7S3 ZJ8E3Z6K3J8優(yōu)質資料 歡迎下載 進程同步練習題 1. 在公共汽車上,司機和售票員的工作流程如以下圖；為保證乘客的安全,司機和售票員應 親熱協(xié)作和諧工作；請用信號量來實現司機與售票員之間的同步； 司機 售票員 啟動車輛 關車門 正常行車 售票 到站停車 開車門 圖 司機和售票員工作流程圖 約束：怎么親熱協(xié)作和諧工作才能保證安全呢？ a 關車門 之后再 啟動車輛 ；利用前驅圖說明 b 到站停車 之后再 開車門 ； 依據約束定義信號量； 關車門 和啟動車輛需要一個信號量進行同步 S1；到站停車 和開車門之間需要一個信號量 進行同

2、步 S2； 建立幾個進程呢？ a 為司機 建立一個進程 Driver ； b 為售票員 建立一個進程 Conductor； Driver ： Repeat 啟動車輛； 正常行駛； 到站停車； Until false; Conductor： Repeat 關車門； 售票； 開車門； Until false; 加入同步關系： Var s1,s2:semorphore=0,0;第 1 頁,共 20 頁優(yōu)質資料 歡迎下載 Driver ： Repeat Wait s1; 啟動車輛； 正常行駛； 到站停車； Signals2 Until false; Conductor： Repeat關車門； Sign

3、als1; 售票； Waits2 開車門； Until false; main Driver; Conductor ; 2. 桌子上有一只盤子,盤子中只能放一只水果；爸爸專向盤子中放蘋果,媽媽專向盤子中放 橘子,一個兒子專等吃盤子中的橘子,一個女兒專等吃盤子中的蘋果；用 PV 操作實現他們 之間的同步機制； 分析： 約束： a 爸爸和媽媽競爭盤子,往盤子放水果,爸爸在放時,媽媽等待,或者相反； b 爸爸和女兒要同步,即爸爸放完蘋果之后通知女兒來吃；同時女兒吃完之后要通知盤 子可用； 媽媽和兒子要同步,即媽媽放完橘子之后通知兒子來吃；同時兒子吃完之c 后要通知盤 子可用； 經上述分析可知： 需要

4、 3 個信號量：S1 表示臨界資源盤子, 初值 1；爸爸和女兒需要一個信號量進行同步 S2=0媽媽和兒子需要一個信號量進行同步 S3=0; 建立進程？ 爸爸： 媽媽： 女兒： 兒子： Repeatrepeatrepeatrepeat第 2 頁,共 20 頁取一個蘋果； 優(yōu)質資料 歡迎下載 從盤子取一個橘子； 取一個橘子； 從盤子取一個蘋果； 放入盤子； 放入盤子 吃蘋果； 吃橘子； Until false;Until false;Until false;Until false; 加入同步關系； 爸爸： 媽媽： 女兒： 兒子： Repeatrepeatrepeatrepeat取一個橘子； wai

5、tS2;waitS3;取一個蘋果； 從盤子取一個蘋果； 從盤子取一個橘子； WaitS1;WaitS1;signalS1;signalS1;放入盤子； 放入盤子 吃蘋果； 吃橘子； SignalS2; SignalS3; Until false;Until false;Until false;Until false;3. a,b 兩點之間是一段東西向的單行車道,現要設計一個自動治理系統(tǒng),治理規(guī)章如下： （ 1）當 ab 之間有車輛在行駛時同方向的車可以同時駛入 段外等待； ab 段,但另一方向的車必需在 ab（ 2）當 ab 之間無車輛在行駛時,到達 a 點（或 b 點）的車輛可以進入 ab

6、段,但不能從 a點和 b 點同時駛入； （ 3）當某方向在 ab 段行駛的車輛駛出了 的車輛進入 ab 段行駛； ab 段且暫無車輛進入 ab 段時,應讓另一方向等待 請用信號量為工具,對 ab 段實現正確治理以保證行駛安全； 分析： 約束： a ab 兩點的單行車道是一種臨界資源；兩端的車輛對該資源進行競爭； b 同步關系：（ 1）,（3）； 經上述分析可知： 第一,設置互斥信號量 Sab=1,用于 a, b 點的車輛互斥進入 ab 段； 然后,分別設置 共享變量 ab=0 用于記錄當前 ab 段上由 a 點進入的車輛數量； 共享變量 ba=0 用于記錄當前 ab=段上由 b 點進入車輛的數

7、量； 最終,設置互斥信號量 S1=1 用于 ab 段的車輛互斥拜望共享變量 ab；設置互斥信號量 S2=1 用于 ba 段的車輛互斥拜望共享變量 ba建立進程？ semaphore S1=1,S2=1,Sab=1;int ab=ba=0;Pab： pba： Repeat repeatWaitS1 Waits2第 3 頁,共 20 頁優(yōu)質資料 歡迎下載 abcount=abcount+1; bacount=bacount+1;if abcount=1 then waitsab if bacount=1 then waitsab signalS1 signals2進入車道行駛； 進入車道行駛； W

8、aits1 Waits2abcount=abcount-1; bacount=bacount-1;if abcount=0 then signalsabif bacount=0 then signalsabsignals1 signals2; until false; until false;mainPab;Pba;5一條河上架設了由如干個橋墩組成的一座橋； 如一個橋墩只能站一個人, 過河的人只能沿 著橋向前走而不能向后退；過河時,只要對岸無人過,就可以過；但不答應河對岸的兩個人 同時過,以防止顯現死鎖；請給出兩個方向的人順當過河的同步算法； 分析： 約束： a 橋屬于臨界資源,兩岸的人對該資

9、源進行競爭； b 橋上的人數是有限制的,設這個橋由 N 個橋墩構成,橋上同時只能有 N 個人過橋, 其它人要進行等待；相當于共享資源數； 設置信號量 信號量 s：互斥使用橋,初值為 1 變量 count1：方向 1 上過河人計數器 變量 count2：方向 2 上過河人計數器 信號量 scount1：對方向 1 上過河人計數器 count1 的互斥使用,初值為 1信號量 scount2：對方向 2 上過河人計數器 count2 的互斥使用,初值為 1信號量 scoun：t 代表橋上過河人的計數信號量,初值為橋墩個數 N 建立進程 Semaphore s, scount1, scount2, s

10、count; int count1, count2; s=1; scount1=1; scount2=1; scount=N; count1=0; count2=0;第 4 頁,共 20 頁優(yōu)質資料 歡迎下載 void direct1int i waitscount1; count1+; ifcount1=1waits; signalscount1;waitscount; 上橋,過橋,下橋； signalscount;waitscount1; count1-; ifcount1=0 signals; signalscount1;void direct2int i waitscount2; co

11、unt2+; ifcount2=1 waits; signalscount2;waitscount; 上橋,過橋,下橋； signalscount;waitscount2; count2-; ifcount2=0 signals; signalscount2; 第 5 頁,共 20 頁優(yōu)質資料 歡迎下載 main cobegin direct11;direct1n; direct21;direct2m; 6 有一個倉庫,可以存放 A 和 B 兩種產品,但要求： （ 1）每次只能存入一種產品（ A或 B）； （ 2）-N A 產品數量 B 產品數量 M ；其中, N 和 M 是正整數； 試用同步

12、算法描述產品 A 與產品 B 的入庫過程； 分析： 約束： B 產品數量最多多 a倉庫是一種臨界資源,兩種產品為之競爭； bA 產品數量不能比 B 產品數量多 M 個以上即 A 產品數量比 M-1 個； A 產品數量不能比 B 產品數量少 N 個以上即 B 產品數量比 A 產品最多 多 N-1 個； 設置信號量 設置互斥信號量 mutex 互斥使用倉庫； 設置兩個信號量來把握 A, B 產品的存放數量, sa 表示當前答應 A 產品比 B 產品多入庫的數量（當前答應 A 產品入庫數量）； sb 表示當前答應 B 產品比 A 產品多入庫的數量（當前答應 B 產品入庫數量）； A 產品時,就答應存

13、入 B 產品 初始時, sa 為 一 1,sb 為 N 一 1；當往庫中存放入一個 的數量也增加 M 1;當往庫中存放入一個 B 產品時,就答應存入 A 產品的數量也增加 1； 建立進程 semaphore mutex=1,sa=M-1, sb=N-1;process puta while1 取一個產品； waitsa; waitmutex;將產品入庫； 第 6 頁,共 20 頁優(yōu)質資料 歡迎下載 signalmutex;signalsb; process putb while1 取一個產品； waitsb; waitmutex; 將產品入庫； signalmutex; signalsa; m

14、ain cob egin puta;putb; 4將只讀數據的進程稱為“讀者”進程,而寫或修改數據的進程稱為“寫者”進程；答應多 個“讀者”同時讀數據,但不答應“寫者”與其他“讀者”或“寫者”同時拜望數據；另外, 要保證： 一旦有“寫者”等待時,新到達的“讀者”必需等待,直到該“寫者”完成數據訪 問為止； 試用 P,V操作正的確現“讀者”與“寫者”的同步； （其次類讀者寫者問題,信號 量解決方法） 第 7 頁,共 20 頁優(yōu)質資料 歡迎下載 分析 ： 約束： a 寫者與寫者之間需要互斥拜望； b 讀者與寫者之間需要互斥； （有一個讀者在讀就讓寫者等待） ,因此,此時需要一個計 數變量記錄讀者的

15、數量； c 答應多個讀者同時讀數據； d 一旦有“寫者”等待時,新到達的“讀者”必需等待,直到該“寫者”完成數據拜望 為止； 建立進程 Write: Repeat執(zhí) 行讀操作 Until false; Read: Repeat 執(zhí)行寫操作； Until false;設 置信號量 設置mutex=1 實現寫者與寫者之間的互斥拜望； a互斥信號量 Write: Repeat Waitmutex 執(zhí)行讀操作； Signalmutex; Until false;b實現讀者與寫者之間的互斥, then waitmutex Read： Repeat readcount+;設置整型變量 readcount=

16、0 記錄讀者數量, if readcount=1ifreadcount=1 waitmutex;執(zhí)行讀操作； readcount- -;ifreadcount=0 signalmutex;第 8 頁,共 20 頁優(yōu)質資料 歡迎下載 until false; 由于 readcount 是共享變量,所以讀者之間要互斥拜望, 因此設置一個互斥信號量 rmutex=1.Read： Repeat Waitrmutex readcount+; ifreadcount=1 waitmutex; signalrmutex執(zhí)行讀操作； Waitrmutex readcount- -; ifreadcount=0

17、 signalmutex; signalrmutexuntil false;c要想實現 d）的互斥,需讓讀者和寫者再共享一個互斥信號量 s,因此設置 互斥信號量 s=1, 一旦有寫者等待時,就 wait（ s）讓讀者等待； Write: Repeat waitwmutex; writecount+;ifwritecount=1 waits; signalwmutex;Waitmutex執(zhí)行讀操作； Signalmutex;waitwmutex; writecount- -; ifwritecount=0signals; signalwmutex;Until false;Read： Repeat

18、第 9 頁,共 20 頁優(yōu)質資料 歡迎下載 Waits; Waitrmutex readcount+; ifreadcount=1 waitmutex; signalrmutexsignals; 執(zhí)行讀操作； Waitrmutex readcount- -;ifreadcount=0 signalmutex; signalrmutex until false; 完整代碼 Process reader while1 waits; waitrmutex;ifreadcount=0waitmutex; readcount+; signalrmutex; signals;perform read op

19、eration;waitrmutex; readcount- -; ifreadcount=0signalmutex; signalrmutex; Process writer while1 waitwmutex; writecount+;第 10 頁,共 20 頁ifwritecount=1優(yōu)質資料 歡迎下載 waits;signalwmutex; waitmutex; perform write operation; signalmutex;waitwmutex; writecount- -; ifwritecount=0signals; signalwmutex; Main cobegi

20、n reader; writer; 第 11 頁,共 20 頁優(yōu)質資料 歡迎下載 1,在公共汽車上,司機和售票員的工作流程如以下圖；為保證乘客的安全,司機和售票員應 親熱協(xié)作和諧工作；請用信號量來實現司機與售票員之間的同步； 司機 售票員 啟動車輛 關車門 正常行車 售票 到站停車 開車門 圖 司機和售票員工作流程圖 【答案】 設置兩個 資源信號量： S1,S2； S1 表示是否答應司機啟動汽車,其初值為 0；S2 表示 是否答應售票員開門,其初值為 0.semaphoere S1=S2=0; void Driverwhile1waitS1; 啟動車輛； 正常行車； 到站停車； signalS

21、2;void Busmanwhile1關車門； signalS1； 售票； waitS2； 開車門； 第 12 頁,共 20 頁優(yōu)質資料 歡迎下載 main cobegin Driver;Busman; 2. 桌子上有一只盤子,盤子中只能放一只水果；爸爸專向盤子中放蘋果,媽媽專向盤子中放 橘子,一個兒子專等吃盤子中的橘子,一個女兒專等吃盤子中的蘋果；用 PV 操作實現他們 之間的同步機制； 【答案】 信號量 S 用來實現盤子的互斥拜望, S1 表示盤子中蘋果個數, S2 表示盤子中橘子的個 數； semaphore S=1,S1=S2=0; void father while1 預備蘋果 ;

22、waitS;將蘋果放在盤子內； signalS1; void mother while1 預備橘子 ; waitS;將橘子放在盤子內； signalS2; void daughter 第 13 頁,共 20 頁優(yōu)質資料 歡迎下載 while1 waitSl; 從盤子里拿走蘋果； signalS; 吃蘋果 ; void son while1 waitS2; 從盤子里拿走橘子； signalS; 吃橘子 ; main cobegin f ather; mother; daughter; son; 3. a,b 兩點之間是一段東西向的單行車道,現要設計一個自動治理系統(tǒng),治理規(guī)章如下： （ 1）當 a

23、b 之間有車輛在行駛時同方向的車可以同時駛入 段外等待； ab 段,但另一方向的車必需在 ab（ 2）當 ab 之間無車輛在行駛時,到達 a 點（或 b 點）的車輛可以進入 ab 段,但不能從 a點和 b 點同時駛入； （ 3）當某方向在 ab 段行駛的車輛駛出了 的車輛進入 ab 段行駛； ab 段且暫無車輛進入 ab 段時,應讓另一方向等待 請用信號量為工具,對 ab 段實現正確治理以保證行駛安全； 【答案】 第 14 頁,共 20 頁優(yōu)質資料 歡迎下載 此題是讀者 -寫者問題的變形；設置 車互斥拜望 共享變量 ab（用于記錄當前 3 個信號量 S1,S2 和 Sab,分別用于從 a 點進

24、入的 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 while1 waitS1; ifab=0 waitSab; ab=ab+1; signalS1;車輛從 a 點駛向 b 點 ; waitS1; ab=ab-1; ifab=0 signalSab; signalS1;

25、 void Pba while1 waitS2; ifba=0 waitSab; ba=ba+1; signalS2; 車輛從 b 點駛向 a 點 ;waitS2; ba=ba-1; ifba=0 signalSab;第 15 頁,共 20 頁優(yōu)質資料 歡迎下載 signalS2; main cobegin Pab; Pba; 4. 將只讀數據的進程稱為“讀者”進程,而寫或修改數據的進程稱為“寫者”進程；答應 多個“讀者”同時讀數據,但不答應“寫者”與其他“讀者”或“寫者”同時拜望數據；另 外,要保證：一旦有“寫者”等待時,新到達的“讀者”必需等待,直到該“寫者”完成數 據拜望為止；試用 P,

26、 V 操作正的確現“讀者”與“寫者”的同步； （其次類讀者寫者問題, 信號量解決方法） 【答案】 為了使寫者優(yōu)先, 可在原先的讀優(yōu)先算法的基礎上增加一個 互斥信號量 s,初值為 1,使 得當至少有一個寫者預備拜望共享對象時,它可以 使后續(xù)的 讀者進程等待； 整型變量 writecount,初值為 0,用來對寫者進行計數； 互斥信號量 wmutex,初值為 Process reader while1 waits; waitrmutex; ifreadcount=0waitmutex; readcount+; signalrmutex;signals;perform read operation;

27、waitrmutex; readcount-;1,用來實現多個寫者對 writecount 進行互斥拜望； ifreadcount=0signalmutex; signalrmutex;第 16 頁,共 20 頁優(yōu)質資料 歡迎下載 Process writer while1 waitwmutex; ifwritecount=0waits; writecount+; signalwmutex;waitmutex; perform write operation; signalmutex;waitwmutex; writecount-; ifwritecount=0signals; signalw

28、mutex; Main cobegin reader; writer; 5. 一條河上架設了由如干個橋墩組成的一座橋；如一個橋墩只能站一個人,過河的人只能沿 著橋向前走而不能向后退；過河時,只要對岸無人過,就可以過；但不答應河對岸的兩個人 同時過,以防止顯現死鎖；請給出兩個方向的人順當過河的同步算法； 【答案】 信號量 s：互斥使用橋,初值為 11信號量 scount1：對方向 1 上過河人計數器 count1 的互斥使用,初值為 信號量 scount2：對方向 2 上過河人計數器 count2 的互斥使用,初值為 1信號量 scoun：t 代表橋上過河人的計數信號量,初值為橋墩個數 N變量

29、count1：方向 1 上過河人計數器 第 17 頁,共 20 頁優(yōu)質資料 歡迎下載 變量 count2：方向 2 上過河人計數器 Semaphore s, scount1, scount2, scount; int count1, count2; s=1; scount1=1; scount2=1; scount=N; count1=0; count2=0;void direct1int i waitscount1; ifcount1=0 waits; count1+; signalscount1;waitscount; 上橋,過橋,下橋； signalscount;waitscount1; count1-; ifcount1=0si