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

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

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

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

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

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

7、量； 最終,設(shè)置互斥信號量 S1=1 用于 ab 段的車輛互斥拜望共享變量 ab；設(shè)置互斥信號量 S2=1 用于 ba 段的車輛互斥拜望共享變量 ba建立進(jìn)程？ semaphore S1=1,S2=1,Sab=1;int ab=ba=0;Pab： pba： Repeat repeatWaitS1 Waits2第 3 頁,共 20 頁優(yōu)質(zhì)資料 歡迎下載 abcount=abcount+1; bacount=bacount+1;if abcount=1 then waitsab if bacount=1 then waitsab signalS1 signals2進(jìn)入車道行駛； 進(jìn)入車道行駛； 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一條河上架設(shè)了由如干個(gè)橋墩組成的一座橋； 如一個(gè)橋墩只能站一個(gè)人, 過河的人只能沿 著橋向前走而不能向后退；過河時(shí),只要對岸無人過,就可以過；但不答應(yīng)河對岸的兩個(gè)人 同時(shí)過,以防止顯現(xiàn)死鎖；請給出兩個(gè)方向的人順當(dāng)過河的同步算法； 分析： 約束： a 橋?qū)儆谂R界資源,兩岸的人對該資

9、源進(jìn)行競爭； b 橋上的人數(shù)是有限制的,設(shè)這個(gè)橋由 N 個(gè)橋墩構(gòu)成,橋上同時(shí)只能有 N 個(gè)人過橋, 其它人要進(jìn)行等待；相當(dāng)于共享資源數(shù)； 設(shè)置信號量 信號量 s：互斥使用橋,初值為 1 變量 count1：方向 1 上過河人計(jì)數(shù)器 變量 count2：方向 2 上過河人計(jì)數(shù)器 信號量 scount1：對方向 1 上過河人計(jì)數(shù)器 count1 的互斥使用,初值為 1信號量 scount2：對方向 2 上過河人計(jì)數(shù)器 count2 的互斥使用,初值為 1信號量 scoun：t 代表橋上過河人的計(jì)數(shù)信號量,初值為橋墩個(gè)數(shù) N 建立進(jì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)質(zhì)資料 歡迎下載 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)質(zhì)資料 歡迎下載 main cobegin direct11;direct1n; direct21;direct2m; 6 有一個(gè)倉庫,可以存放 A 和 B 兩種產(chǎn)品,但要求： （ 1）每次只能存入一種產(chǎn)品（ A或 B）； （ 2）-N A 產(chǎn)品數(shù)量 B 產(chǎn)品數(shù)量 M ；其中, N 和 M 是正整數(shù)； 試用同步

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

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

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

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

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

17、 signalmutex; signalrmutexuntil false;c要想實(shí)現(xiàn) d）的互斥,需讓讀者和寫者再共享一個(gè)互斥信號量 s,因此設(shè)置 互斥信號量 s=1, 一旦有寫者等待時(shí),就 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)質(zhì)資料 歡迎下載 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)質(zhì)資料 歡迎下載 waits;signalwmutex; waitmutex; perform write operation; signalmutex;waitwmutex; writecount- -; ifwritecount=0signals; signalwmutex; Main cobegi

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

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

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

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

24、入的 ab 段上由 a 點(diǎn)進(jìn)入車輛的數(shù)量） ,從 b 點(diǎn)進(jìn)入的車互 斥拜望 共享變量 ba（用于記錄當(dāng)前 ab 段上由 b 點(diǎn)進(jìn)入車輛的數(shù)量） 和 a,b 點(diǎn)的車輛互斥進(jìn) 入 ab 段； 3 個(gè)信號量的初值分別為 1,1 和 1,兩個(gè)共享變量 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 點(diǎn)駛向 b 點(diǎn) ; waitS1; ab=ab-1; ifab=0 signalSab; signalS1;

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

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

27、waitrmutex; readcount-;1,用來實(shí)現(xiàn)多個(gè)寫者對 writecount 進(jìn)行互斥拜望； ifreadcount=0signalmutex; signalrmutex;第 16 頁,共 20 頁優(yōu)質(zhì)資料 歡迎下載 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. 一條河上架設(shè)了由如干個(gè)橋墩組成的一座橋；如一個(gè)橋墩只能站一個(gè)人,過河的人只能沿 著橋向前走而不能向后退；過河時(shí),只要對岸無人過,就可以過；但不答應(yīng)河對岸的兩個(gè)人 同時(shí)過,以防止顯現(xiàn)死鎖；請給出兩個(gè)方向的人順當(dāng)過河的同步算法； 【答案】 信號量 s：互斥使用橋,初值為 11信號量 scount1：對方向 1 上過河人計(jì)數(shù)器 count1 的互斥使用,初值為 信號量 scount2：對方向 2 上過河人計(jì)數(shù)器 count2 的互斥使用,初值為 1信號量 scoun：t 代表橋上過河人的計(jì)數(shù)信號量,初值為橋墩個(gè)數(shù) N變量

29、count1：方向 1 上過河人計(jì)數(shù)器 第 17 頁,共 20 頁優(yōu)質(zhì)資料 歡迎下載 變量 count2：方向 2 上過河人計(jì)數(shù)器 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