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

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

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

4、個(gè)數(shù)據(jù)之后，就發(fā)出Producer來(lái)喚醒正在等待的生產(chǎn)者線程。通過(guò)一個(gè)有界緩沖區(qū)(用數(shù)組來(lái)實(shí)現(xiàn)，類似循環(huán)隊(duì)列)把生產(chǎn)者和消費(fèi)者聯(lián)系起來(lái)。假定生產(chǎn)者和消費(fèi)者的優(yōu)先級(jí)是相同的，只要緩沖區(qū)未滿，生產(chǎn)者就可以生產(chǎn)產(chǎn)品并將產(chǎn)品送入緩沖區(qū)。類似地，只要緩沖區(qū)未空，消費(fèi)者就可以從緩沖區(qū)中去走產(chǎn)品并消費(fèi)它。應(yīng)該禁止生產(chǎn)者向滿的緩沖區(qū)送入產(chǎn)品，同時(shí)也應(yīng)該禁止消費(fèi)者從空的緩沖區(qū)中取出產(chǎn)品，這一機(jī)制有生產(chǎn)者線程和消費(fèi)者線程之間的互斥關(guān)系來(lái)實(shí)現(xiàn)。二、圖形描述及算法:m個(gè)生產(chǎn)者、k個(gè)消費(fèi)者、共享n個(gè)單元緩沖區(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;/對(duì)資源信號(hào)量與互斥信號(hào)量P操作，申請(qǐng)資源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)消耗一個(gè)緩沖區(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消費(fèi)者流程結(jié)構(gòu):四、數(shù)據(jù)結(jié)構(gòu)及部分函數(shù)描述a)用一個(gè)整型數(shù)組Buffer_NUM來(lái)代表緩沖區(qū)。生產(chǎn)產(chǎn)品及對(duì)已有產(chǎn)品消費(fèi)都需要訪問(wèn)該組緩沖區(qū)。緩沖區(qū)的大小和結(jié)構(gòu)體：structBuffer(intproductBUFFER_NUM;/緩沖區(qū)intstar

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

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

9、eleaseSemaphoreS數(shù)用于對(duì)指定的信號(hào)量增加指定的值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);記錄消費(fèi)的物品ptr=gbuf.end;/再移動(dòng)緩沖區(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;/放好了完畢，釋放一個(gè)產(chǎn)品/讓其他消費(fèi)者或生產(chǎn)者使用V(Mutex);V(Full);Sleep(rate/2*rand()%10+110);return0;c)消費(fèi)者線程代碼：DWORDWINAPIConsumer(LPVOIDpara)/i表示第i個(gè)消費(fèi)者inti=*(int*)para;/利用para傳入當(dāng)前消費(fèi)者的編號(hào)intptr;/待消費(fèi)的內(nèi)容的指針printf("消費(fèi)者1d:需要資源n",i);i

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

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

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

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

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

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

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

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

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

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);/記錄消費(fèi)的

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