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

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

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

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

4、圖【答案】設(shè)置兩個(gè)資源信號(hào)量：S1、S2。S1表示是否允許司機(jī)啟動(dòng)汽車，其初值為0;S2表示是否允許售票員開門，其初值為0.semaphoereS1=S2=0;voidDriver()while(1)wait(S1);啟動(dòng)車輛；正常行車；到站停車；signal(S2);voidBusman()while(1)關(guān)車門；signal(S1)；wait(S2)；開車門;main()cobeginDriver();Busman();2. 桌子上有一只盤子，盤子中只能放一只水果。爸爸專向盤子中放蘋果，媽媽專向盤子中放橘子，一個(gè)兒子專等吃盤子中的橘子，一個(gè)女兒專等吃盤子中的蘋果。用PV操作實(shí)現(xiàn)他們之間的同

5、步機(jī)制?！敬鸢浮啃盘?hào)量S用來(lái)實(shí)現(xiàn)盤子的互斥訪問，S1表示盤子中蘋果個(gè)數(shù)，S2表示盤子中橘子的個(gè)數(shù)。semaphoreS=1,S1=S2=0;voidfather()while(1)準(zhǔn)備蘋果;wait(S);將蘋果放在盤子內(nèi)；signal(S1);voidmother()while(1)準(zhǔn)備橘子;wait(S);將橘子放在盤子內(nèi)；signal(S2);voiddaughter()while(1)wait(Sl);從盤子里拿走蘋果；signal(S);吃蘋果;voidson()while(1)wait(S2);從盤子里拿走橘子；signal(S);吃橘子;main()cobeginfather()

6、;mother();daughter();son();3. a，b兩點(diǎn)之間是一段東西向的單行車道，現(xiàn)要設(shè)計(jì)一個(gè)自動(dòng)管理系統(tǒng)，管理規(guī)則如下：(1)當(dāng)ab之間有車輛在行駛時(shí)同方向的車可以同時(shí)駛?cè)隺b段，但另一方向的車必須在ab段外等待；(2)當(dāng)ab之間無(wú)車輛在行駛時(shí)，到達(dá)a點(diǎn)(或b點(diǎn))的車輛可以進(jìn)入ab段，但不能從a點(diǎn)和b點(diǎn)同時(shí)駛?cè)耄?3)當(dāng)某方向在ab段行駛的車輛駛出了ab段且暫無(wú)車輛進(jìn)入ab段時(shí)，應(yīng)讓另一方向等待的車輛進(jìn)入ab段行駛。請(qǐng)用信號(hào)量為工具，對(duì)ab段實(shí)現(xiàn)正確管理以保證行駛安全。【答案】此題是讀者-寫者問題的變形。設(shè)置3個(gè)信號(hào)量S1、S2和Sab,分別用于從a點(diǎn)進(jìn)入的車互斥訪問共享變量

7、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個(gè)信號(hào)量的初值分別為1、1和1，兩個(gè)共享變量ab和ba的初值分別為0、0。semaphoreS1=1,S2=1,Sab=1;intab=ba=0;voidPab()while(1)wait(S1);if(ab=0)wait(Sab);ab=ab+1;signal(S1);車輛從a點(diǎn)駛向b點(diǎn);wait(S1);ab=ab-1;if(ab=0)signal(Sab);signal(S1);voidPba()while(1)wait(S2)

8、;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)程。允許多個(gè)“讀者”同時(shí)讀數(shù)據(jù)，但不允許“寫者”與其他“讀者”或“寫者”同時(shí)訪問數(shù)據(jù)。另外，要保證：一旦有“寫者”等待時(shí)，新到達(dá)的“讀者”必須等待，直到該“寫者”完成數(shù)據(jù)訪問為止。試用P、V操作正確實(shí)現(xiàn)“讀者”與“寫者”的同步。(第二類讀者寫者問題，信號(hào)量解決方法)【答案】為了使寫者

9、優(yōu)先，可在原來(lái)的讀優(yōu)先算法的基礎(chǔ)上增加一個(gè)互斥信號(hào)量s，初值為1，使得當(dāng)至少有一個(gè)寫者準(zhǔn)備訪問共享對(duì)象時(shí)，它可以使后續(xù)的讀者進(jìn)程等待；整型變量writecount，初值為0，用來(lái)對(duì)寫者進(jìn)行計(jì)數(shù)；互斥信號(hào)量wmutex，初值為1，用來(lái)實(shí)現(xiàn)多個(gè)寫者對(duì)writecount進(jìn)行互斥訪問。Processreader()while(1)wait(s);wait(rmutex);if(readcount=0)wait(mutex);readcount+;signal(rmutex);signal(s);performreadoperation;wait(rmutex);readcount-;if(readc

10、ount=0)signal(mutex);signal(rmutex);Processwriter()while(1)wait(wmutex);if(writecount=0)wait(s);writecount+;signal(wmutex);wait(mutex);performwriteoperation;signal(mutex);wait(wmutex);writecount-;if(writecount=0)signal(s);signal(wmutex);Main()cobeginreader();writer();5. 一條河上架設(shè)了由若干個(gè)橋墩組成的一座橋。若一個(gè)橋墩只能站一

11、個(gè)人，過河的人只能沿著橋向前走而不能向后退。過河時(shí)，只要對(duì)岸無(wú)人過，就可以過。但不允許河對(duì)岸的兩個(gè)人同時(shí)過，以防止出現(xiàn)死鎖。請(qǐng)給出兩個(gè)方向的人順利過河的同步算法?！敬鸢浮啃盘?hào)量s：互斥使用橋，初值為1信號(hào)量scountl:對(duì)方向1上過河人計(jì)數(shù)器countl的互斥使用，初值為1信號(hào)量scount2:對(duì)方向2上過河人計(jì)數(shù)器count2的互斥使用，初值為1信號(hào)量scount:代表橋上過河人的計(jì)數(shù)信號(hào)量，初值為橋墩個(gè)數(shù)N變量count1：方向1上過河人計(jì)數(shù)器變量count2：方向2上過河人計(jì)數(shù)器Semaphores,scount1,scount2,scount;intcount1,count2;s=1

12、;scount1=1;scount2=1;scount=N;count1=0;count2=0;voiddirect1(inti)wait(scount1);if(count1=0)wait(s);count1+;signal(scount1);wait(scount);上橋，過橋，下橋；signal(scount);wait(scount1);count1-;if(count1=0)signal(s);signal(scount1);voiddirect2(inti)wait(scount2);if(count2=0)wait(s);count2+;signal(scount2);wait(

13、scount);上橋，過橋，下橋；signal(scount);wait(scount2);count2-;if(count2=0)signal(s);signal(scount2);main()cobegindirect1(1);direct1(n);direct2(1);direct2(m);6、有一個(gè)倉(cāng)庫(kù)，可以存放A和B兩種產(chǎn)品，但要求：(1)每次只能存入一種產(chǎn)品(A或B)；(2)-N<A產(chǎn)品數(shù)量一B產(chǎn)品數(shù)量<M。其中，N和M是正整數(shù)。試用同步算法描述產(chǎn)品A與產(chǎn)品B的入庫(kù)過程。【答案】A產(chǎn)品的數(shù)量不能比B產(chǎn)品的數(shù)量少N個(gè)以上，A產(chǎn)品的數(shù)量不能比B產(chǎn)品的數(shù)量多M個(gè)以上設(shè)置兩個(gè)信號(hào)量來(lái)控制A、B產(chǎn)品的存放數(shù)量，sa表示當(dāng)前允許A產(chǎn)品比B產(chǎn)品多入庫(kù)的數(shù)量(當(dāng)前允許A產(chǎn)品入庫(kù)數(shù)量)，即在當(dāng)前庫(kù)存量和B產(chǎn)品不入庫(kù)的情況下，還可以允許sa個(gè)A產(chǎn)品入庫(kù)；sb表示當(dāng)前允許B產(chǎn)品比A產(chǎn)品多入庫(kù)的數(shù)量(當(dāng)前允許B產(chǎn)品入庫(kù)數(shù)量)，即在當(dāng)前庫(kù)存量和A產(chǎn)品不入庫(kù)的情況下，還可以允許sb個(gè)B產(chǎn)品入庫(kù)。初始時(shí)，sa為M1,sb為N1。當(dāng)往庫(kù)中存放入一個(gè)A產(chǎn)品時(shí)，則允許存入B產(chǎn)品的數(shù)量也增加1;當(dāng)往庫(kù)中存放入一個(gè)B產(chǎn)品時(shí)，則允許存入A產(chǎn)品的數(shù)量也增加1