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

1、進(jìn)程同步練習(xí)題1. 在公共汽車上，司機(jī)和售票員的工作流程如圖所示。為保證乘客的安全，司機(jī)和售票員應(yīng) 密切配合協(xié)調(diào)工作。請用信號量來實現(xiàn)司機(jī)與售票員之間的同步。司機(jī)啟動車輛售票員關(guān)車門售票開車門正常行車到站停車圖司機(jī)和售票員工作流程圖2. 桌子上有一只盤子，盤子中只能放一只水果。爸爸專向盤子中放蘋果，媽媽專向盤子中放 橘子，一個兒子專等吃盤子中的橘子，一個女兒專等吃盤子中的蘋果。用PV操作實現(xiàn)他們之間的同步機(jī)制。3. a，b兩點(diǎn)之間是一段東西向的單行車道，現(xiàn)要設(shè)計一個自動管理系統(tǒng)，管理規(guī)則如下：（1） 當(dāng)ab之間有車輛在行駛時同方向的車可以同時駛?cè)隺b段，但另一方向的車必須在 ab 段外等待；（

2、2） 當(dāng)ab之間無車輛在行駛時，到達(dá) a點(diǎn)（或b點(diǎn)）的車輛可以進(jìn)入ab段，但不能從a 點(diǎn)和b點(diǎn)同時駛?cè)?；?）當(dāng)某方向在ab段行駛的車輛駛出了 ab段且暫無車輛進(jìn)入ab段時，應(yīng)讓另一方向等待 的車輛進(jìn)入ab段行駛。請用信號量為工具，對ab段實現(xiàn)正確管理以保證行駛安全。4將只讀數(shù)據(jù)的進(jìn)程稱為“讀者”進(jìn)程，而寫或修改數(shù)據(jù)的進(jìn)程稱為“寫者”進(jìn)程。允許多 個“讀者”同時讀數(shù)據(jù)，但不允許“寫者”與其他“讀者”或“寫者”同時訪問數(shù)據(jù)。另外， 要保證：一旦有“寫者”等待時，新到達(dá)的“讀者”必須等待，直到該“寫者”完成數(shù)據(jù)訪 問為止。試用P、V操作正確實現(xiàn)“讀者”與“寫者”的同步。（第二類讀者寫者問題，信號

3、量解決方法）5. 條河上架設(shè)了由若干個橋墩組成的一座橋。若一個橋墩只能站一個人，過河的人只能沿著橋向前走而不能向后退。過河時，只要對岸無人過，就可以過。但不允許河對岸的兩個人 同時過，以防止出現(xiàn)死鎖。請給出兩個方向的人順利過河的同步算法。6有一個倉庫，可以存放 A 和 B 兩種產(chǎn)品，但要求：（ 1）每次只能存入一種產(chǎn)品（ A 或 B）；（2） -N v A產(chǎn)品數(shù)量一B產(chǎn)品數(shù)量v M。其中，N和M是正整數(shù)。 試用同步算法描述產(chǎn)品 A 與產(chǎn)品 B 的入庫過程。1在公共汽車上，司機(jī)和售票員的工作流程如圖所示。為保證乘客的安全，司機(jī)和售票員應(yīng) 密切配合協(xié)調(diào)工作。請用信號量來實現(xiàn)司機(jī)與售票員之間的同步。

4、司機(jī)售票員啟動車輛正常行車到站停車關(guān)車門售票開車門圖司機(jī)和售票員工作流程圖【答案】設(shè)置兩個資源信號量：S1 S2。S1表示是否允許司機(jī)啟動汽車，其初值為 是否允許售票員開門，其初值為 0.semaphoere S1=S2=0;void Driver()while(1)wait(S1);啟動車輛；正常行車；到站停車；sig nal(S2);void Busma n()while(1)關(guān)車門；signal(S1)；0； S2表示wait(S2)；開車門；main()cobeginDriver();Busman();2. 桌子上有一只盤子，盤子中只能放一只水果。爸爸專向盤子中放蘋果，媽媽專向盤子中放

5、 橘子，一個兒子專等吃盤子中的橘子，一個女兒專等吃盤子中的蘋果。用 PV 操作實現(xiàn)他們 之間的同步機(jī)制?！敬鸢浮啃盘柫縎用來實現(xiàn)盤子的互斥訪問，S1表示盤子中蘋果個數(shù)，S2表示盤子中橘子的個 數(shù)。semaphore S=1,S1=S2=0;void father()while(1)準(zhǔn)備蘋果 ;wait(S);將蘋果放在盤子內(nèi)；signal(S1);void mother()while(1)準(zhǔn)備橘子 ;wait(S);將橘子放在盤子內(nèi)；signal(S2);void daughter()while(1)wait(Sl);從盤子里拿走蘋果； signal(S); 吃蘋果 ;void son()wh

6、ile(1)wait(S2);從盤子里拿走橘子；signal(S);吃橘子 ;main()cobeginfather();mother();daughter();son();3. a，b 兩點(diǎn)之間是一段東西向的單行車道，現(xiàn)要設(shè)計一個自動管理系統(tǒng)，管理規(guī)則如下：(1)當(dāng)ab之間有車輛在行駛時同方向的車可以同時駛?cè)隺b段，但另一方向的車必須在 ab段外等待；( 2)當(dāng) ab 之間無車輛在行駛時，到達(dá) a 點(diǎn)(或 b 點(diǎn))的車輛可以進(jìn)入 ab 段，但不能從 a 點(diǎn)和 b 點(diǎn)同時駛?cè)耄?3)當(dāng)某方向在ab段行駛的車輛駛出了 ab段且暫無車輛進(jìn)入ab段時，應(yīng)讓另一方向等待 的車輛進(jìn)入ab段行駛。請用信號

7、量為工具，對 ab 段實現(xiàn)正確管理以保證行駛安全。【答案】此題是讀者-寫者問題的變形。設(shè)置3個信號量S1、S2和Sab,分別用于從a點(diǎn)進(jìn)入的 車互斥訪問共享變量ab (用于記錄當(dāng)前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個信號量的初值分別為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(

8、S1);車輛從 a 點(diǎn)駛向 b 點(diǎn);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 點(diǎn)駛向 a 點(diǎn);wait(S2);ba=ba-1;if(ba=0)signal(Sab);signal(S2);main()cobeginPab();Pba();4. 將只讀數(shù)據(jù)的進(jìn)程稱為“讀者”進(jìn)程，而寫或修改數(shù)據(jù)的進(jìn)程稱為“寫者”進(jìn)程。允許 多個“讀者”同時讀數(shù)據(jù)，但不允許“寫者”與其他“讀者”或“寫者”同時訪問數(shù)據(jù)。另

9、外，要保證：一旦有“寫者”等待時，新到達(dá)的“讀者”必須等待，直到該“寫者”完成數(shù) 據(jù)訪問為止。試用 P、 V 操作正確實現(xiàn)“讀者”與“寫者”的同步。 (第二類讀者寫者問題， 信號量解決方法)【答案】為了使寫者優(yōu)先，可在原來的讀優(yōu)先算法的基礎(chǔ)上增加一個互斥信號量S,初值為1,使 得當(dāng)至少有一個寫者準(zhǔn)備訪問共享對象時，它可以 使后續(xù)的 讀者進(jìn)程等待；整型變量 writecount ，初值為 0，用來對寫者進(jìn)行計數(shù)；互斥信號量 wmutex ，初值為 1 ，用來實現(xiàn)多個寫者對 writecount 進(jìn)行互斥訪問。ProceSS reader() while(1)wait(S);wait(rmutex

10、);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 operation;signal(mutex);wait(

11、wmutex);writecount-;if(writecount=0)signal(s);signal(wmutex);Main( )cobegin reader();writer();5. 一條河上架設(shè)了由若干個橋墩組成的一座橋。若一個橋墩只能站一個人，過河的人只能沿 著橋向前走而不能向后退。過河時，只要對岸無人過，就可以過。但不允許河對岸的兩個人 同時過，以防止出現(xiàn)死鎖。請給出兩個方向的人順利過河的同步算法。【答案】信號量S：互斥使用橋，初值為1信號量scount1:對方向1上過河人計數(shù)器count1的互斥使用，初值為1信號量scount2:對方向2上過河人計數(shù)器count2的互斥使用，

12、初值為1信號量scount:代表橋上過河人的計數(shù)信號量，初值為橋墩個數(shù)N變量 count1 ：方向 1 上過河人計數(shù)器變量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

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

14、(m);6、有一個倉庫，可以存放A和B兩種產(chǎn)品，但要求：（1）每次只能存入一種產(chǎn)品（A或B）; （2）-N v A產(chǎn)品數(shù)量一B產(chǎn)品數(shù)量v M。其中，N和M是正整數(shù)。試用同步算法描述產(chǎn)品A 與產(chǎn)品 B 的入庫過程?！敬鸢浮緼 產(chǎn)品的數(shù)量不能比 B 產(chǎn)品的數(shù)量少 N 個以上， A 產(chǎn)品的數(shù)量不能比 B 產(chǎn)品的 數(shù)量多 M 個以上設(shè)置兩個信號量來控制 A、B產(chǎn)品的存放數(shù)量，sa表示當(dāng)前允許A產(chǎn)品比B產(chǎn)品多入庫 的數(shù)量（當(dāng)前允許 A 產(chǎn)品入庫數(shù)量），即在當(dāng)前庫存量和 B 產(chǎn)品不入庫的情況下，還可以允 許 sa 個 A 產(chǎn)品入庫；sb表示當(dāng)前允許B產(chǎn)品比A產(chǎn)品多入庫的數(shù)量（當(dāng)前允許 B產(chǎn)品入庫數(shù)量），即在當(dāng)前 庫存量和A產(chǎn)品不入庫的情況下，還可以允許 sb個B產(chǎn)品入庫。初始時，sa為M 一 1, sb為N 1。當(dāng)往庫中存放入一個 A產(chǎn)品時，則允許存入B產(chǎn) 品的數(shù)量也增加1;當(dāng)往庫中存放入一個B產(chǎn)品時，則允許存入 A產(chǎn)品的數(shù)量也增加1。semaphore m