進程同步問題實例

1、1操作系統(tǒng)概念進程同步問題實例進程同步問題實例2本章主要內(nèi)容n經(jīng)典同步問題經(jīng)典同步問題n生產(chǎn)者生產(chǎn)者-消費者問題：緩沖區(qū)問題消費者問題：緩沖區(qū)問題n嗜睡理發(fā)師問題嗜睡理發(fā)師問題n吸煙者問題吸煙者問題n吃水果問題吃水果問題 31 經(jīng)典同步問題n有限緩沖問題有限緩沖問題n讀者作者問題讀者作者問題n哲學(xué)家進餐問題哲學(xué)家進餐問題4有限緩沖問題(生產(chǎn)者-消費者問題)do produce an item in nextpwait(empty);wait(mutex);add nextp to buffersignal(mutex);signal(full); while (1);do wait(full)

2、;wait(mutex);remove an item from buffer to nextcsignal(mutex);signal(empty);consume the item in nextc while (1);5讀者作者問題n一個數(shù)據(jù)對象可以為多個并發(fā)進程所共享。其一個數(shù)據(jù)對象可以為多個并發(fā)進程所共享。其中有的進程可能只需要讀共享對象的內(nèi)容，而中有的進程可能只需要讀共享對象的內(nèi)容，而其他進程可能要更新共享對象（即讀和寫）。其他進程可能要更新共享對象（即讀和寫）。n將只對讀感興趣的進程稱為讀者將只對讀感興趣的進程稱為讀者n其他則稱為作者其他則稱為作者n第一讀者作者問題第一讀者作者問

3、題n僅當(dāng)無讀者等待時，才允許寫者執(zhí)行僅當(dāng)無讀者等待時，才允許寫者執(zhí)行n第二讀者作者問題第二讀者作者問題n在讀者與作者同時申請資源的時候，寫者優(yōu)先。在讀者與作者同時申請資源的時候，寫者優(yōu)先。6第一讀者作者問題wait(wrt);writing is performedsignal(wrt);wait(mutex);readcount +;if (readcount = 1)wait(wrt);signal(mutex);reading is performedwait(mutex);readcount -;if (readcount = 0)signal(wrt);signal(mutex);7

4、哲學(xué)家就餐問題8 n共享數(shù)據(jù)共享數(shù)據(jù)nsemaphore chopstick5;n哲學(xué)家哲學(xué)家i結(jié)構(gòu)結(jié)構(gòu)do wait(chopsticki);wait(chopstick(I + 1) % 5);eatsignal(chopsticki);signal(chopstick(I + 1) % 5);think while (1);92 緩沖區(qū)問題(生產(chǎn)者-消費者問題)n三個進程三個進程P1、P2、P3 互斥使用一個包含互斥使用一個包含N(N0)個單個單元的緩沖區(qū)。元的緩沖區(qū)。P1 每次用每次用produce()生成一個正整數(shù)并生成一個正整數(shù)并用用put()送入緩沖區(qū)某一個空單元中；送入緩沖區(qū)某

5、一個空單元中；P2 每次用每次用getodd()從該緩沖區(qū)中取出一個奇數(shù)并用從該緩沖區(qū)中取出一個奇數(shù)并用countodd()統(tǒng)計奇數(shù)個數(shù)；統(tǒng)計奇數(shù)個數(shù)；P3 每次用每次用geteven()從該緩沖區(qū)中取從該緩沖區(qū)中取出一個偶數(shù)并用出一個偶數(shù)并用counteven()統(tǒng)計偶數(shù)個數(shù)。請用信號統(tǒng)計偶數(shù)個數(shù)。請用信號量機制實現(xiàn)這三個進程的同步與互斥活動，并說明所量機制實現(xiàn)這三個進程的同步與互斥活動，并說明所定義的信號量的含義。要求用偽代碼描述。定義的信號量的含義。要求用偽代碼描述。10緩沖區(qū)問題求解n(1) 緩沖區(qū)是一互斥資源，因此設(shè)互斥信號量緩沖區(qū)是一互斥資源，因此設(shè)互斥信號量mutex。n(2)

6、同步問題：同步問題：P1、P2 因為奇數(shù)的放置與取用而同步，設(shè)同步信號量因為奇數(shù)的放置與取用而同步，設(shè)同步信號量odd；P1、P3 因為偶數(shù)的放置于取用而同步，設(shè)同步信號量因為偶數(shù)的放置于取用而同步，設(shè)同步信號量even；P1、P2、P3 因為共享因為共享緩沖區(qū)，設(shè)同步信號量緩沖區(qū)，設(shè)同步信號量empty。nsemaphore mutex = 1,odd = 0,even = 0,empty = N;nProcess P1: nwhile(true)n number = produce();n P(empty);P(mutex);n put();n V(mutex);n If number %

7、 2 = 0n V(even);n elsen V(odd);n11緩沖區(qū)問題求解nProcess P2:nwhile(true)n P(odd); P(mutex);n getodd();n V(mutex);V(empty);n countodd();nnProcess P3:nwhile(true)n P(even); P(mutex);n geteven();n V(mutex);V(empty);n counteven();n123 嗜睡理發(fā)師問題n一個理發(fā)店里有一個理發(fā)師，一張理發(fā)椅子，一個理發(fā)店里有一個理發(fā)師，一張理發(fā)椅子，多張等候的椅子，當(dāng)沒有顧客的時候，理發(fā)師多張等候的椅子，

8、當(dāng)沒有顧客的時候，理發(fā)師就睡覺。當(dāng)一個顧客來到店里時，如果理發(fā)師就睡覺。當(dāng)一個顧客來到店里時，如果理發(fā)師在睡覺，則叫醒理發(fā)師；否則便坐著等；如果在睡覺，則叫醒理發(fā)師；否則便坐著等；如果等待的椅子都滿了就離開。等待的椅子都滿了就離開。 133 嗜睡理發(fā)師問題nint waiting=0 ； /等候理發(fā)的顧客數(shù)等候理發(fā)的顧客數(shù) int chairs=5； /為顧客準(zhǔn)備的椅子數(shù)為顧客準(zhǔn)備的椅子數(shù) semaphore customers=0, barbers=0,mutex=1; Barber進程：進程：while(TRUE) P(cutomers); /若無顧客若無顧客,理發(fā)師睡眠理發(fā)師睡眠 P(m

9、utex); /進程互斥進程互斥,要求顧客等候要求顧客等候 waiting = waiting 1;/等候顧客數(shù)少一個等候顧客數(shù)少一個 V(barbers); /理發(fā)師去為一個顧客理發(fā)理發(fā)師去為一個顧客理發(fā) V(mutex); /開放臨界區(qū)開放臨界區(qū) cut-hair( ); /正在理發(fā)（非臨界區(qū)操作）正在理發(fā)（非臨界區(qū)操作）Customer進程：進程：P(mutex); /進入臨界區(qū)進入臨界區(qū)if (waitingchairs) waiting = waiting+1; /等候顧客數(shù)加等候顧客數(shù)加1 V(customers); /必要的話喚醒理發(fā)師必要的話喚醒理發(fā)師 V(mutex); /開

10、放臨界區(qū)開放臨界區(qū) P(barbers); /無理發(fā)師無理發(fā)師, 顧客坐著養(yǎng)神顧客坐著養(yǎng)神 get-haircut( ); /一個顧客坐下等候服務(wù)一個顧客坐下等候服務(wù)else V(mutex); /人滿了，上自習(xí)去！人滿了，上自習(xí)去！144 吸煙者問題三個吸煙者在一間房間內(nèi)，還有一個香煙供應(yīng)者。三個吸煙者在一間房間內(nèi)，還有一個香煙供應(yīng)者。(1)(1)為了制造并抽掉香煙，每個吸煙者需要三樣?xùn)|西：煙草、紙和火為了制造并抽掉香煙，每個吸煙者需要三樣?xùn)|西：煙草、紙和火柴。柴。(2)(2)供應(yīng)者有豐富的貨物提供。供應(yīng)者有豐富的貨物提供。(3)(3)三個吸煙者中，第一個有自己的煙草，第二個有自己的紙，第三

11、三個吸煙者中，第一個有自己的煙草，第二個有自己的紙，第三個有自己的火柴。個有自己的火柴。(4)(4)供應(yīng)者將兩樣?xùn)|西放在桌子上，允許一個吸煙者進行對健康不利供應(yīng)者將兩樣?xùn)|西放在桌子上，允許一個吸煙者進行對健康不利的吸煙。當(dāng)吸煙者完成吸煙后喚醒供應(yīng)者，供應(yīng)者再放兩樣?xùn)|西的吸煙。當(dāng)吸煙者完成吸煙后喚醒供應(yīng)者，供應(yīng)者再放兩樣?xùn)|西（隨機地）在桌面上，然后喚醒另一個吸煙者。（隨機地）在桌面上，然后喚醒另一個吸煙者。試為吸煙者和供應(yīng)者用同步法解決問題。試為吸煙者和供應(yīng)者用同步法解決問題。154 吸煙者問題供應(yīng)者需要供應(yīng)者需要3個進程個進程 X：提供：提供tobacco和和match Y：提供：提供matc

12、h和和wrapper Z：提供：提供wrapper和和tobacco3個吸煙者進程個吸煙者進程 A：只有：只有tobacco B：只有：只有match C：只有：只有wrapper則則 一次只能有一次只能有X,Y,Z中的一個執(zhí)行中的一個執(zhí)行(供應(yīng)供應(yīng))；X,Y,Z只能在只能在消耗完一個后才能供應(yīng)下一個消耗完一個后才能供應(yīng)下一個164 吸煙者問題Semaphore tobacco=0, match=0, wrapper=0, mutex=1;Process X:P(mutex);V(tobacco);V(match);Process Y:P(mutex);V(match);V(wrapper);

13、Process Z:P(mutex);V(wrapper);V(tobacco);Process A:P(match);P(wrapper);Smoke;V(mutex);Process B:P(wrapper);P(tobacco);Smoke;V(mutex);Process C:P(tobacco);P(match);Smoke;V(mutex);17 桌上有一空盤，允許存放一只水果。爸爸向盤中放蘋桌上有一空盤，允許存放一只水果。爸爸向盤中放蘋果，媽媽向盤中放桔子，兒子專等吃盤中的桔子，女果，媽媽向盤中放桔子，兒子專等吃盤中的桔子，女兒專等吃盤中的蘋果。規(guī)定當(dāng)盤空時一次只能放一只兒專等吃盤中的蘋果。規(guī)定當(dāng)盤空時一次只能放一只水果供吃者取用，請用水果供吃者取用，請用P P、V V原語實現(xiàn)爸爸、媽媽、兒原語實現(xiàn)爸爸、媽媽、兒子、女兒三個并發(fā)進程的同步。子、女兒三個并發(fā)進程的同步。5 吃水果問題plate爸爸爸爸媽媽媽媽兒子兒子女兒女兒185 吃水果問題n應(yīng)設(shè)置三個信號量應(yīng)設(shè)置三個信號量S、So、Sa，信號量，信號量S表示盤子是否為空，其初值表示盤子是否為空，其初值為為1；信號量；信號量So表示盤中是否有桔子，其初值為表示盤中是否有桔子，其初值為0；信號量；信號量Sa表示盤表示盤中是否有蘋果，其初值為中是否有蘋果，其初值為0。同步描述