多進程同步方法解決生產(chǎn)者-消費者問題

1、課程設(shè)計報告課程名稱：操作系統(tǒng)實驗題目：用多進程同步方法解決生產(chǎn)者-消費者問題院系：計算機科學(xué)與工程學(xué)院班級：姓名：學(xué)號：指導(dǎo)老師：、概述:1、問題描述：用多進程同步方法解決生產(chǎn)者-消費者問題設(shè)計目的：通過研究Linux的進程機制和信號量實現(xiàn)生產(chǎn)者消費者問題的并發(fā)控制.說明：有界緩沖區(qū)內(nèi)設(shè)有20個存儲單元，放入/取出的數(shù)據(jù)項設(shè)定為1-20這20個整型數(shù).設(shè)計要求：1）每個生產(chǎn)者和消費者對有界緩沖區(qū)進行操作后，即時顯示有界緩沖區(qū)的全部內(nèi)容當(dāng)前指針位置和生產(chǎn)者/消費者線程的標(biāo)識符.2）生產(chǎn)者和消費者各有兩個以上.3）多個生產(chǎn)者或多個消費者之間須有共享對緩沖區(qū)進行操作的函數(shù)代碼.2、程序設(shè)計基本思想

2、：生產(chǎn)者一消費者問題是一種同步問題的抽象描述。計算機系統(tǒng)中的每個進程都可以消費或生產(chǎn)某類資源。當(dāng)系統(tǒng)中某一進程使用某一資源時，可以看作是消耗，且該進程稱為消費者。而當(dāng)某個進程釋放資源時，則它就相當(dāng)一個生產(chǎn)者。一個有限空間的共享緩沖區(qū)，負責(zé)存放貨物。生產(chǎn)者向緩沖區(qū)中放物品，緩沖區(qū)滿則不能放。消費者從緩沖區(qū)中拿物品，緩沖區(qū)空則不能拿。因為有多個緩沖區(qū)，所以生產(chǎn)者線程沒有必要在生成新的數(shù)據(jù)之前等待最后一個數(shù)據(jù)被消費者線程處理完畢。同樣，消費者線程并不一定每次只能處理一個數(shù)據(jù)。在多緩沖區(qū)機制下，線程之間不必互相等待形成死鎖，因而提高了效率。多個緩沖區(qū)就好像使用一條傳送帶替代托架，傳送帶上一次可以放多個

3、產(chǎn)品。生產(chǎn)者在緩沖區(qū)尾加入數(shù)據(jù)，而消費者則在緩沖區(qū)頭讀取數(shù)據(jù)。當(dāng)緩沖區(qū)滿的時候，緩沖區(qū)就上鎖并等待消費者線程讀取數(shù)據(jù)；每一個生產(chǎn)或消費動作使得傳送帶向前移動一個單位，因而，消費者線程讀取數(shù)據(jù)的順序和數(shù)據(jù)產(chǎn)生順序是相同的?？梢砸胍粋€count計數(shù)器來表示已經(jīng)被使用的緩沖區(qū)數(shù)量。用Producer和Consumer來同步生產(chǎn)者和消費者線程。每當(dāng)生產(chǎn)者線程發(fā)現(xiàn)緩沖區(qū)滿(count=BufferSize),它就等待Consumer事件。同樣，當(dāng)消費者線程發(fā)現(xiàn)緩沖區(qū)空，它就開始等待Producer0生產(chǎn)者線程寫入一個新的數(shù)據(jù)之后，就立刻發(fā)出Consumer來喚醒正在等待的消費者線程；消費者線程在讀取一

4、個數(shù)據(jù)之后，就發(fā)出Producer來喚醒正在等待的生產(chǎn)者線程。通過一個有界緩沖區(qū)(用數(shù)組來實現(xiàn)，類似循環(huán)隊列)把生產(chǎn)者和消費者聯(lián)系起來。假定生產(chǎn)者和消費者的優(yōu)先級是相同的，只要緩沖區(qū)未滿，生產(chǎn)者就可以生產(chǎn)產(chǎn)品并將產(chǎn)品送入緩沖區(qū)。類似地，只要緩沖區(qū)未空，消費者就可以從緩沖區(qū)中去走產(chǎn)品并消費它。應(yīng)該禁止生產(chǎn)者向滿的緩沖區(qū)送入產(chǎn)品，同時也應(yīng)該禁止消費者從空的緩沖區(qū)中取出產(chǎn)品，這一機制有生產(chǎn)者線程和消費者線程之間的互斥關(guān)系來實現(xiàn)。二、圖形描述及算法:m個生產(chǎn)者、k個消費者、共享n個單元緩沖區(qū)口取產(chǎn)品In=(in+i)modnout=(out+i)modn基本算法如下:-varB:array0.n-1o

5、finteger;Empty:g_hFullSemaphore:=SIZE_OF_BUFFER/*可以使用的空緩沖區(qū)數(shù)*/Full:g_hEmptySemaphore=0;/*緩沖區(qū)內(nèi)可以使用的產(chǎn)品數(shù)*/Mutex:semaphore:=1;in,out:integer:=0;cobeginprocessproducer_I(I=1,2,m)BeginL1:produceaproduct;/對資源信號量與互斥信號量P操作，申請資源P(Empty);P(Mutex);Bin:=product;in:=(in+1)modn;V(Mutex);V(Full);GotoL1;end;/*放入/取出緩沖

6、區(qū)指針*/processconsumer_j(j=1,2；,k)beginL2:P(Full);/P操作生產(chǎn)消耗一個緩沖區(qū)P(Mutex);Product:=Bout;out:=(out+1)modn;V(Mutex);V(Emptyi;Consumeaproduct;GotoL2;end;Coend三、程序流程圖:4.1、生產(chǎn)者流程結(jié)構(gòu):4.2消費者流程結(jié)構(gòu):四、數(shù)據(jù)結(jié)構(gòu)及部分函數(shù)描述a)用一個整型數(shù)組Buffer_NUM來代表緩沖區(qū)。生產(chǎn)產(chǎn)品及對已有產(chǎn)品消費都需要訪問該組緩沖區(qū)。緩沖區(qū)的大小和結(jié)構(gòu)體：structBuffer(intproductBUFFER_NUM;/緩沖區(qū)intstar

7、t,end;/兩個指針相當(dāng)于教材中的inout指針g_buf;b)在實現(xiàn)本程序的消費生產(chǎn)模型時，具體地通過如下同步對象實現(xiàn)互斥：i. 設(shè)一個互斥量Mutex,以實現(xiàn)生產(chǎn)者在查詢和保留緩沖區(qū)內(nèi)的下一個空位置時進行互斥。ii. 每一個生產(chǎn)者用一個信號量與其消費者同步，通過設(shè)置Full實現(xiàn)，該組信號量用于表示相應(yīng)產(chǎn)品已生產(chǎn)。同時用一個表示空緩沖區(qū)數(shù)目的信號量Empty進行類似的同步，指示緩沖區(qū)中是否存在空位置，以便開始生產(chǎn)下一個產(chǎn)品。c)定義Windows下的P操作#defineP(S)WaitForSingleObject(S,INFINITE)說明：WaitForSingleObject函數(shù)用來

8、檢測hHandle事件的信號狀態(tài)，在某一線程中調(diào)用該函數(shù)時，線程暫時掛起，如果在掛起的dwMilliseconds毫秒內(nèi)，線程所等待的對象變?yōu)橛行盘枲顟B(tài)，則該函數(shù)立即返回；如果超時時間已經(jīng)到達dwMilliseconds毫秒,但hHandle所指向的對象還沒有變成有信號X犬態(tài),函數(shù)照樣返回。參數(shù)dwMilliseconds有兩個具有特殊意義的值：0和INFINITE。若為0,則該函數(shù)立即返回；若為INFINITE,則線程一直被掛起，直到hHandle所指向的對象變?yōu)橛行盘枲顟B(tài)時為止。d)定義Windows下的V操作#defineV(S)ReleaseSemaphore(S,1,NULL)說明R

9、eleaseSemaphoreS數(shù)用于對指定的信號量增加指定的值e)生產(chǎn)者線程代碼：DWORDWINAPIProducer(LPVOIDpara)inti=*(int*)para-CONSUMER_NUM;intptr;intdata;產(chǎn)品intj=0;while(j+<4)data=rand()%8;printf("生產(chǎn)者%01d:生產(chǎn)出:%s!n",i,thingdata);/等待存放空間P(Empty);/有地方，先鎖住緩沖區(qū)P(Mutex);記錄消費的物品ptr=gbuf.end;/再移動緩沖區(qū)指針g_buf.end=(g_buf.end+1)%BUFFER_

10、NUM;printf("生產(chǎn)者01d:放到緩沖區(qū)buf%d=%sn",i,ptr,thingdata);g_ductptr=data;/放好了完畢，釋放一個產(chǎn)品/讓其他消費者或生產(chǎn)者使用V(Mutex);V(Full);Sleep(rate/2*rand()%10+110);return0;c)消費者線程代碼：DWORDWINAPIConsumer(LPVOIDpara)/i表示第i個消費者inti=*(int*)para;/利用para傳入當(dāng)前消費者的編號intptr;/待消費的內(nèi)容的指針printf("消費者1d:需要資源n",i);i

11、ntj=0;while(j+<4)/等待產(chǎn)品P(Full);/有產(chǎn)品，先鎖住緩沖區(qū)P(Mutex);記錄消費的物品ptr=g_buf.start;/再移動緩沖區(qū)指針g_buf.start=(g_buf.start+1)%BUFFER_NUM;/讓其他消費者6生產(chǎn)者使用printf("消費者%01d:我需要buf%d=%sn",i,ptr,thingg_ductptr);/消費完畢，并釋放一個緩沖printf("消費者%01d:我消費完畢%sn",i,thingg_ductptr);V(Mutex);V(Empty);Sl

12、eep(rate*rand()%10+110);return0;五、調(diào)試過程:為解決生產(chǎn)者/消費者問題，應(yīng)該設(shè)置兩個資源信號量，其中一個表示空緩沖區(qū)的數(shù)目，用Full表示，其初始值為有界緩沖區(qū)的大小BUFFER_NUM一個表示緩沖區(qū)中產(chǎn)品的數(shù)目，用Empty表示，其初始值為00另外，由于有界緩沖區(qū)是一個臨界資源，必須互斥使用，所以還需要再設(shè)置一個互斥信號量Mutex,起初值為1。在生產(chǎn)者/消費者問題中，信號量實現(xiàn)兩種功能。首先，它是生產(chǎn)產(chǎn)品和消費產(chǎn)品的計數(shù)器，計數(shù)器的初始值是可利用的資源數(shù)目（有界緩沖區(qū)的長度）。其次，它是確保產(chǎn)品的生產(chǎn)者和消費者之間動作同步的同步器。生產(chǎn)者要生產(chǎn)一個產(chǎn)品時，首

13、先對資源信號量Full和互斥信號量Mutex進行P操作，中請資源。如果可以通過的話，就生產(chǎn)一個產(chǎn)品，并把產(chǎn)品送入緩沖區(qū)。然后對互斥信號量Mutex和資源信號量Empty進行V操作，釋放資源。消費者要消費一個產(chǎn)品時，首先對資源信號量Empty和互斥信號量Mutex進行P操作，中請資源。如果可以通過的話，就從緩沖區(qū)取出一個產(chǎn)品并消費掉。然后對互斥信號量Mutex和資源信號量Full進行V操作，釋放資源。如果緩沖區(qū)中已經(jīng)沒有可用資源，就把申請資源的進程添加到等待隊列的隊尾。如果有一個資源被釋放，在等待隊列中的第一個進程被喚醒并取得這個資源的使用權(quán)。六、程序運行結(jié)果：在程序中設(shè)置了兩個消費者，三個生產(chǎn)

14、者，為便于描述出生產(chǎn)-消費的過程，我用食物代表被緩沖區(qū)消費的資源。在實驗結(jié)果中我們可以看到幾個生產(chǎn)者生產(chǎn)的食物放在緩沖區(qū)中，消費者需求的話就去緩沖區(qū)去取。在同一個時間點上不必生產(chǎn)者生產(chǎn)一個消費者就消費一個，消費者某個時間消費的資源有可能是上一個生產(chǎn)者所生產(chǎn)的。由于按題目要求設(shè)置的緩沖區(qū)為20,所以緩沖區(qū)沒有溢出到等待消費者消費的情況。七、課程設(shè)計總結(jié)：本次課程設(shè)計通過模擬計算機操作系統(tǒng)中經(jīng)典的“生產(chǎn)者一消費者問題”，鞏固了我在操作系統(tǒng)原理課上所學(xué)的知識，加深了對操作系統(tǒng)中進程同步和互斥等問題，完成了多進程同步方法解決生產(chǎn)者-消費者問題全部過程，結(jié)果滿足設(shè)計要求。設(shè)計過程中遇到不少困難，在反復(fù)研

15、究老師的PPT及課本的原理后才逐漸明晰怎樣將代碼實現(xiàn)，雖然這學(xué)期學(xué)過Java,1java不是很熟悉，因此還是選擇C+語言。以前學(xué)習(xí)C+沒有深入了解到線程這個概念，在學(xué)習(xí)Java的時候才知道有專門的線程類。所以我在網(wǎng)上也參考了其他人用C+編寫尤其是關(guān)于多進程DWORD程序的設(shè)計實現(xiàn)。在代碼的實現(xiàn)過程中，我是主要定義了兩個函數(shù)WINAPIConsumer(LPVOIDpara)和DWORDWINAPIProducer(LPVOIDpara)，在這兩個函數(shù)中實現(xiàn)PV操作。通過本次設(shè)計，我較好地掌握了通過研究Linux的進程機制和信號量實現(xiàn)生產(chǎn)者消費者問題的并發(fā)控制全過程，尤其是對多進程程序設(shè)計方法有

16、了更深的理解，開拓了思路，鍛煉了實踐動手能手。但是我覺得課程設(shè)計的時間有點短，中間又夾雜著好幾場考試，所以沒能做出界面以便于直觀的觀察出詳細過程，只是用代碼實現(xiàn)了要描述的功能且達到了要求，所以改進的空間還比較大。參考文獻1計算機操作系統(tǒng)教程.孫鐘秀等編著.高等教育出版社，2010年8月出版2數(shù)據(jù)結(jié)構(gòu)教程.李春葆等編著清華大學(xué)出版社.2009年4月3面向?qū)ο蟪绦蛟O(shè)計與VisualC+6.0教程陳天華編著清華大學(xué)出版社.2009年7月#include#include#include#includetypedef#define#define#defineHANDLESemaphore;/信號量的Wi

17、ndowsP(S)WaitForSingleObject(S,INFINITE)V(S)ReleaseSemaphore(S,1,NULL)rate1000/原型/定義Windows下的P操作定義Windows下的V操作#defineCONSUMERNUM#definePRODUCERNUM3/*#defineBUFFER_NUM20char*thing8=/*"雞腿堡",/*消費者個數(shù)生產(chǎn)者個數(shù)*/緩沖區(qū)個數(shù)*/薯條"，"可樂"，*/"三明治"，"面包","小籠包"，"火腿

18、","饅頭"/生產(chǎn)和消費的產(chǎn)品名稱structBufferintproductBUFFER_NUM;intstart,end;g_buf;/緩沖區(qū)兩個指針相當(dāng)于教材中的inout指針SemaphoreEmpty,Full,Mutex;/分別相當(dāng)于Empty,Full,Mutex三個信號量/*消費者線程*/DWORDWINAPIConsumer(LPVOIDpara)/intintprintf(inti表示第i個消費者i=*(int*)para;ptr;/"消費者%1d:j=0;/利用para傳入當(dāng)前消費者的編號待消費的內(nèi)容的指針需要資源n",i

19、);while(j+<4)/P(Full);/等待產(chǎn)品有產(chǎn)品，先鎖住緩沖區(qū)P(Mutex);/記錄消費的物品ptr=g_buf.start;/再移動緩沖區(qū)指針g_buf.start=(g_buf.start+1)%BUFFER_NUM;/讓其他消費者或生產(chǎn)者使用printf(消費者01d:我需要buf%d=%sn",i,ptr,thingg_ductptr);附源代碼:<windows.h><stdio.h><stdlib.h><time.h>/消費完畢，并釋放一個緩沖printf("消費者01d:我消費完

20、畢%sn",i,thingg_ductptr);V(Mutex);V(Empty);Sleep(rate*rand()%10+110);return0;/*生產(chǎn)者線程*/DWORDWINAPIProducer(LPVOIDpara)inti=*(int*)para-CONSUMER_NUM;intptr;intdata;/產(chǎn)品intj=0;while(j+<4)data=rand()%8;printf("生產(chǎn)者0億：生產(chǎn)出：%s!n",i,thingdata);/等待存放空間P(Empty);/有地方，先鎖住緩沖區(qū)P(Mutex);/記錄消費的

21、物品ptr=g_buf.end;/再移動緩沖區(qū)指針g_buf.end=(g_buf.end+1)%BUFFER_NUM;printf("生產(chǎn)者0億：放到緩沖區(qū)buf%d=%sn",i,ptr,thingdata);g_ductptr=data;/放好了完畢，釋放一個產(chǎn)品/讓其他消費者或生產(chǎn)者使用V(Mutex);V(Full);Sleep(rate/2*rand()%10+110);return0;intmain(intargc,char*argv)/線程技術(shù)，前面為消費者線程，后面為生產(chǎn)者線程HANDLEhThreadCONSUMER_NUM+PRODUCER_NUM;/線程計數(shù)srand(time(NULL);rand();DWORDtid;inti=0;/初始化信號量Mutex=CreateSemaphore(NULL,1,