from http://c.biancheng.net/cpp/html/2600.html
問題描述
一組生產(chǎn)者進(jìn)程和一組消費(fèi)者進(jìn)程共享一個(gè)初始為空、大小為n的緩沖區(qū),只有緩沖區(qū)沒滿時(shí),生產(chǎn)者才能把消息放入到緩沖區(qū),否則必須等待;只有緩沖區(qū)不空時(shí),消費(fèi)者才能從中取出消息,否則必須等待。由于緩沖區(qū)是臨界資源,它只允許一個(gè)生產(chǎn)者放入消息,或者一個(gè)消費(fèi)者從中取出消息。
問題分析
1) 關(guān)系分析。生產(chǎn)者和消費(fèi)者對(duì)緩沖區(qū)互斥訪問是互斥關(guān)系,同時(shí)生產(chǎn)者和消費(fèi)者又是一個(gè)相互協(xié)作的關(guān)系,只有生產(chǎn)者生產(chǎn)之后,消費(fèi)者才能消費(fèi),他們也是同步關(guān)系。
2) 整理思路。這里比較簡(jiǎn)單,只有生產(chǎn)者和消費(fèi)者兩個(gè)進(jìn)程,正好是這兩個(gè)進(jìn)程存在著互斥關(guān)系和同步關(guān)系。那么需要解決的是互斥和同步PV操作的位置。
3) 信號(hào)量設(shè)置。信號(hào)量mutex作為互斥信號(hào)量,它用于控制互斥訪問緩沖池,互斥信號(hào)量初值為1;信號(hào)量full用于記錄當(dāng)前緩沖池中“滿”緩沖區(qū)數(shù),初值為0。信號(hào)量empty 用于記錄當(dāng)前緩沖池中“空”緩沖區(qū)數(shù),初值為n。
生產(chǎn)者-消費(fèi)者進(jìn)程的描述如下:
- semaphore mutex=1; //臨界區(qū)互斥信號(hào)量
- semaphore empty=n; //空閑緩沖區(qū)
- semaphore full=0; //緩沖區(qū)初始化為空
- producer () { //生產(chǎn)者進(jìn)程
- while(1){
- produce an item in nextp; //生產(chǎn)數(shù)據(jù)
- P(empty); //獲取空緩沖區(qū)單元
- P(mutex); //進(jìn)入臨界區(qū).
- add nextp to buffer; //將數(shù)據(jù)放入緩沖區(qū)
- V(mutex); //離開臨界區(qū),釋放互斥信號(hào)量
- V(full); //滿緩沖區(qū)數(shù)加1
- }
- }
- consumer () { //消費(fèi)者進(jìn)程
- while(1){
- P(full); //獲取滿緩沖區(qū)單元
- P(mutex); // 進(jìn)入臨界區(qū)
- remove an item from buffer; //從緩沖區(qū)中取出數(shù)據(jù)
- V (mutex); //離開臨界區(qū),釋放互斥信號(hào)量
- V (empty) ; //空緩沖區(qū)數(shù)加1
- consume the item; //消費(fèi)數(shù)據(jù)
- }
- }
該類問題要注意對(duì)緩沖區(qū)大小為n的處理,當(dāng)緩沖區(qū)中有空時(shí)便可對(duì)empty變量執(zhí)行P 操作,一旦取走一個(gè)產(chǎn)品便要執(zhí)行V操作以釋放空閑區(qū)。對(duì)empty和full變量的P操作必須放在對(duì)mutex的P操作之前。如果生產(chǎn)者進(jìn)程先執(zhí)行P(mutex),然后執(zhí)行P(empty),消費(fèi)者執(zhí)行P(mutex),然后執(zhí)行P(fall),這樣可不可以?答案是否定的。設(shè)想生產(chǎn)者進(jìn)程已經(jīng)將緩沖區(qū)放滿,消費(fèi)者進(jìn)程并沒有取產(chǎn)品,即empty = 0,當(dāng)下次仍然是生產(chǎn)者進(jìn)程運(yùn)行時(shí),它先執(zhí)行P(mutex)封鎖信號(hào)量,再執(zhí)行P(empty)時(shí)將被阻塞,希望消費(fèi)者取出產(chǎn)品后將其喚醒。輪到消費(fèi)者進(jìn)程運(yùn)行時(shí),它先執(zhí)行P(mutex),然而由于生產(chǎn)者進(jìn)程已經(jīng)封鎖mutex信號(hào)量,消費(fèi)者進(jìn)程也會(huì)被阻塞,這樣一來生產(chǎn)者、消費(fèi)者進(jìn)程都將阻塞,都指望對(duì)方喚醒自己,陷入了無(wú)休止的等待。同理,如果消費(fèi)者進(jìn)程已經(jīng)將緩沖區(qū)取空,即 full = 0,下次如果還是消費(fèi)者先運(yùn)行,也會(huì)出現(xiàn)類似的死鎖。不過生產(chǎn)者釋放信號(hào)量時(shí),mutex、full先釋放哪一個(gè)無(wú)所謂,消費(fèi)者先釋放mutex還是empty都可以。
下面再看一個(gè)較為復(fù)雜的生產(chǎn)者-消費(fèi)者問題:
問題描述
桌子上有一只盤子,每次只能向其中放入一個(gè)水果。爸爸專向盤子中放蘋果,媽媽專向盤子中放橘子,兒子專等吃盤子中的橘子,女兒專等吃盤子中的蘋果。只有盤子為空時(shí),爸爸或媽媽就可向盤子中放一個(gè)水果;僅當(dāng)盤子中有自己需要的水果時(shí),兒子或女兒
可以從盤子中取出。
問題分析
1) 關(guān)系分析。這里的關(guān)系稍復(fù)雜一些,首先由每次只能向其中放入一只水果可知爸爸和媽媽是互斥關(guān)系。爸爸和女兒、媽媽和兒子是同步關(guān)系,而且這兩對(duì)進(jìn)程必須連起來,兒子和女兒之間沒有互斥和同步關(guān)系,因?yàn)樗麄兪沁x擇條件執(zhí)行,不可能并發(fā),如圖2-8所示。
2) 整理思路。這里有4個(gè)進(jìn)程,實(shí)際上可以抽象為兩個(gè)生產(chǎn)者和兩個(gè)消費(fèi)者被連接到大小為1的緩沖區(qū)上。
3) 信號(hào)量設(shè)置。首先設(shè)置信號(hào)量plate為互斥信號(hào)量,表示是否允許向盤子放入水果,初值為1,表示允許放入,且只允許放入一個(gè)。信號(hào)量 apple表示盤子中是否有蘋果,初值為0,表示盤子為空,不許取,若apple=l可以取。信號(hào)量orange表示盤子中是否有橘子,初值為0,表示盤子為空,不許取,若orange=l可以取。解決該問題的代碼如下:
- semaphore plate=l, apple=0, orange=0;
- dad() { //父親進(jìn)程
- while (1) {
- prepare an apple;
- P(plate) ; //互斥向盤中取、放水果
- put the apple on the plate; //向盤中放蘋果
- V(apple); //允許取蘋果
- }
- }
- mom() { // 母親進(jìn)程
- while(1) {
- prepare an orange;
- P(plate); //互斥向盤中取、放水果
- put the orange on the plate; //向盤中放橘子
- V(orange); //允許取橘子
- }
- }
- son(){ //兒子進(jìn)程
- while(1){
- P(orange) ; //互斥向盤中取橘子
- take an orange from the plate;
- V(plate); //允許向盤中取、放水果
- eat the orange;
- }
- }
- daughter () { //女兒進(jìn)程
- while(1) {
- P(apple); // 互斥向盤中取蘋果
- take an apple from the plate;
- V(plate); //運(yùn)行向盤中取、放水果
- eat the apple;
- }
- }
進(jìn)程間的關(guān)系如圖2-9所示。dad()和daughter()、mam()和son()必須連續(xù)執(zhí)行,正因?yàn)槿绱耍仓荒茉谂畠耗米咛O果后,或兒子拿走橘子后才能釋放盤子,即V(plate)操作。
本站僅提供存儲(chǔ)服務(wù),所有內(nèi)容均由用戶發(fā)布,如發(fā)現(xiàn)有害或侵權(quán)內(nèi)容,請(qǐng)
點(diǎn)擊舉報(bào)。