進程同步問題實例

操作系統概念進程同步問題實例1本章主要內容經典同步問題生產者-消費者問題：緩沖區問題嗜睡理發師問題吸煙者問題吃水果問題21經典同步問題有限緩沖問題讀者－作者問題哲學家進餐問題3有限緩沖問題(生產者-消費者問題)do{ … produceaniteminnextp … wait(empty); wait(mutex); … addnextptobuffer … signal(mutex); signal(full);}while(1);do{ wait(full); wait(mutex); … removeanitemfrombuffertonextc … signal(mutex); signal(empty); … consumetheiteminnextc …}while(1);4讀者－作者問題一個數據對象可以為多個并發進程所共享。其中有的進程可能只需要讀共享對象的內容，而其他進程可能要更新共享對象（即讀和寫）。將只對讀感興趣的進程稱為讀者其他則稱為作者第一讀者－作者問題僅當無讀者等待時，才允許寫者執行第二讀者－作者問題在讀者與作者同時申請資源的時候，寫者優先。5第一讀者－作者問題wait(wrt);…writingisperformed…signal(wrt);wait(mutex);readcount++;if(readcount==1) wait(wrt);signal(mutex);…readingisperformed…wait(mutex);readcount--;if(readcount==0) signal(wrt);signal(mutex);6哲學家就餐問題7

共享數據semaphorechopstick[5];哲學家i結構do{ wait(chopstick[i]); wait(chopstick[(I+1)%5]); … eat … signal(chopstick[i]); signal(chopstick[(I+1)%5]); … think …}while(1);82緩沖區問題(生產者-消費者問題)三個進程P1、P2、P3互斥使用一個包含N(N>0)個單元的緩沖區。P1每次用produce()生成一個正整數并用put()送入緩沖區某一個空單元中；P2每次用getodd()從該緩沖區中取出一個奇數并用countodd()統計奇數個數；P3每次用geteven()從該緩沖區中取出一個偶數并用counteven()統計偶數個數。請用信號量機制實現這三個進程的同步與互斥活動，并說明所定義的信號量的含義。要求用偽代碼描述。9緩沖區問題求解(1)緩沖區是一互斥資源，因此設互斥信號量mutex。(2)同步問題：P1、P2因為奇數的放置與取用而同步，設同步信號量odd；P1、P3因為偶數的放置于取用而同步，設同步信號量even；P1、P2、P3因為共享緩沖區，設同步信號量empty。semaphoremutex=1,odd=0,even=0,empty=N;ProcessP1:while(true){number=produce();P(empty);P(mutex);put();V(mutex);Ifnumber%2==0V(even);elseV(odd);}10緩沖區問題求解ProcessP2:while(true){P(odd);P(mutex);getodd();V(mutex);V(empty);countodd();}ProcessP3:while(true){P(even);P(mutex);geteven();V(mutex);V(empty);counteven();}113嗜睡理發師問題一個理發店里有一個理發師，一張理發椅子，多張等候的椅子，當沒有顧客的時候，理發師就睡覺。當一個顧客來到店里時，如果理發師在睡覺，則叫醒理發師；否則便坐著等；如果等待的椅子都滿了就離開。

123嗜睡理發師問題int

waiting=0；//等候理發的顧客數

int

chairs=5；

//為顧客準備的椅子數

semaphore

customers=0,barbers=0,mutex=1;

Barber進程：while(TRUE){P(cutomers);//若無顧客,理發師睡眠P(mutex);//進程互斥,要求顧客等候

waiting=waiting–1;//等候顧客數少一個V(barbers);//理發師去為一個顧客理發V(mutex);//開放臨界區cut-hair();//正在理發（非臨界區操作）}Customer進程：P(mutex);//進入臨界區if(waiting<chairs){waiting=waiting+1;//等候顧客數加1V(customers);//必要的話喚醒理發師V(mutex);//開放臨界區P(barbers);//無理發師,顧客坐著養神get-haircut();//一個顧客坐下等候服務}elseV(mutex);//人滿了，上自習去！134吸煙者問題三個吸煙者在一間房間內，還有一個香煙供應者。(1)為了制造并抽掉香煙，每個吸煙者需要三樣東西：煙草、紙和火柴。(2)供應者有豐富的貨物提供。(3)三個吸煙者中，第一個有自己的煙草，第二個有自己的紙，第三個有自己的火柴。(4)供應者將兩樣東西放在桌子上，允許一個吸煙者進行對健康不利的吸煙。當吸煙者完成吸煙后喚醒供應者，供應者再放兩樣東西（隨機地）在桌面上，然后喚醒另一個吸煙者。試為吸煙者和供應者用同步法解決問題。144吸煙者問題供應者需要3個進程X：提供tobacco和matchY：提供match和wrapperZ：提供wrapper和tobacco3個吸煙者進程A：只有tobaccoB：只有matchC：只有wrapper則一次只能有X,Y,Z中的一個執行(供應)；X,Y,Z只能在消耗完一個后才能供應下一個154吸煙者問題Semaphoretobacco=0,match=0,wrapper=0,mutex=1;ProcessX:P(mutex);V(tobacco);V(match);ProcessY:P(mutex);V(match);V(wrapper);ProcessZ:P(mutex);V(wrapper);V(tobacco);ProcessA:P(match);P(wrapper);Smoke;V(mutex);ProcessB:P(wrapper);P(tobacco);Smoke;V(mutex);ProcessC:P(tobacco);P(match);Smoke;V(mutex);16桌上有一空盤，允許存放一只水果。爸爸向盤中放蘋果，媽媽向盤中放桔子，兒子專等吃盤中的桔子，女兒專等吃盤中的蘋果。規定當盤空時一次只能放一只水果供吃者取用，請用P、V原語實現爸爸、媽媽、兒子、女兒三個并發進程的同步。5吃水果問題plate爸爸媽媽兒子女兒175吃水果問題應設置三個信號量S、So、Sa，信號量S表示盤子是否為空，其初值為1；信號量So表示盤中是否有桔子，其初值為0；信號量Sa表示盤中是否有蘋果，其初值為0。同步描述如下：SemaphorS=1,