多進程同步方法解決生產者-消費者問題

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

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

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

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

5、算法如下:-var B : arrayO.n-1 of integer;Empty: g_hFullSemaphore:=SIZE_OF_BUFFER /*可以使用的空緩沖區(qū)數(shù) */Full: g_hEmptySemaphore=0;/*緩沖區(qū)內可以使用的產品數(shù) */Mutex :semaphore:*in , out:integer:= 0;/*放入/取出緩沖區(qū)指針*/cobegi nprocess producer_l(l=1,2；,m)process con sumer_j (j=1,2；,k)Beg inbegi nL1:produce a product;L2:P(Full );/對

6、資源信號量與互斥信號量/P操作生產消耗一個緩沖區(qū)P操作，申請資源P(Empty);P(Mutex);P(Mutex);Product:= Bout;Bi n := product;out:=(out+1) mod n;in:=(i n+1) mod n;V(Mutex);V(Mutex);V(Emptyi;V(Full );Con sume a product;Goto L1;Goto L2;end;end;Coend三、程序流程圖:4.1、生產者流程結構:4.2消費者流程結構:四、數(shù)據(jù)結構及部分函數(shù)描述a）用一個整型數(shù)組Buffer_NUM來代表緩沖區(qū)。生產產品及對已有產品消費都需 要訪問該

7、組緩沖區(qū)。緩沖區(qū)的大小和結構體：struct Bufferin t productBUFFER_NUM; /緩沖區(qū)int start, end; /兩個指針相當于教材中的in out 指針g_buf；b) 在實現(xiàn)本程序的消費生產模型時，具體地通過如下同步對象實現(xiàn)互斥：i. 設一個互斥量Mutex，以實現(xiàn)生產者在查詢和保留緩沖區(qū)內的下一個空位置 時進行互斥。ii. 每一個生產者用一個信號量與其消費者同步，通過設置Full實現(xiàn)，該組信號量用于表示相應產品已生產。同時用一個表示空緩沖區(qū)數(shù)目的信號量 Empty進行類似的同步，指示緩沖區(qū)中是否存在空位置，以便開始生產下一 個產品。c) 定義 Windo

8、ws下的P操作#define P(S) WaitForSingleObject(S, INFINITE)說明：WaitForSingleObject函數(shù)用來檢測hHandle事件的信號狀態(tài)，在某一線程中調用該函數(shù)時，線程暫時掛起，如果在掛起的dwMillisec on ds毫秒內，線程所等待的對象變?yōu)橛行盘枲顟B(tài)，則該函數(shù)立即返回；如果超時時間已經到達dwMilliseconds毫秒, 但hHandle所指向的對象還沒有變成有信號狀態(tài)，函數(shù)照樣返回。參數(shù) dwMilliseconds 有兩個具有特殊意義的值：0和INFINITE。若為0，則該函數(shù)立即返回；若為INFINITE， 則線程一直被掛起

9、，直到hHa ndle所指向的對象變?yōu)橛行盘枲顟B(tài)時為止。d) 定義 Windows下的V操作#define V(S) ReleaseSem aphore(S, 1, NULL)說明ReleaseSemaphoreS數(shù)用于對指定的信號量增加指定的值e) 生產者線程代碼：DWORD WINAPI Producer(LPVOID para)int i = *(i nt *)para - CONSUMER_NUM;int ptr;int data; /產品int j=0;while (j+<4)data = ran d()%8;printf("生產者 %01d:生產出:%s!n&quo

10、t;,i,thingdata);等待存放空間P(Empty);有地方，先鎖住緩沖區(qū)P(Mutex);記錄消費的物品ptr = g buf.e nd;/再移動緩沖區(qū)指針g_buf.e nd=(g_buf.e nd+1)%BUFFER_NUM;printf("生產者 %01d:放到緩沖區(qū)buf%d=%sn",i,ptr,thingdata);g_ductptr=data;放好了完畢，釋放一個產品讓其他消費者或生產者使用V(Mutex);V(Full);Sleep(rate/2*ra nd()%10+110);return 0;c)消費者線程代碼：DWORD WIN

11、API Con sumer(LPVOID para)/ i表示第i個消費者int i = *(int *)para; 利用para傳入當前消費者的編號int ptr;/待消費的內容的指針printf("消費者%1d:需要資源n",i);int j=0;while (j+<4)/等待產品P(Full);/有產品，先鎖住緩沖區(qū)P(Mutex);/記錄消費的物品ptr=g_buf.start;/再移動緩沖區(qū)指針g_buf.start= (g_buf.start+1)%BUFFER_NUM;/讓其他消費者或生產者使用printf(”消費者 %01d: 我需要 buf%d=%s

12、n",i, ptr, thingg_ductptr);/消費完畢，并釋放一個緩沖printf(" 消費者 %01d:我消費完畢 %sn", i,thingg_ductptr);V(Mutex);V(Empty);Sleep(rate*ra nd()%10+110);return 0;五、調試過程：為解決生產者 / 消費者問題，應該設置兩個資源信號量，其中一個表示空緩沖區(qū)的數(shù)目，用Full表示，其初始值為有界緩沖區(qū)的大小 BUFFER_NUW個表示緩沖區(qū)中產品的數(shù)目，用 Empty 表示，其初始值為 0。另外，由于有界緩沖區(qū)是一個臨界資源

13、，必須互斥使用，所以還需要再設置一個互斥信號量 Mutex，起初值為1。在生產者 / 消費者問題中，信號量實現(xiàn)兩種功能。首先，它是生產產品和消費產品的計數(shù) 器，計數(shù)器的初始值是可利用的資源數(shù)目 （ 有界緩沖區(qū)的長度 ） 。其次，它是確保產品的生產者 和消費者之間動作同步的同步器。生產者要生產一個產品時，首先對資源信號量 Full和互斥信號量Mutex進行P操作，申 請資源。如果可以通過的話， 就生產一個產品， 并把產品送入緩沖區(qū)。 然后對互斥信號量 Mutex 和資源信號量Empty進行V操作，釋放資源。消費者要消費一個產品時，首先對資源信號量 Empty和互斥信號量Mutex進行P操作，申

14、請資源。如果可以通過的話，就從緩沖區(qū)取出一個產品并消費掉。然后對互斥信號量 Mutex和 資源信號量Full進行V操作，釋放資源。如果緩沖區(qū)中已經沒有可用資源，就把申請資源的進程添加到等待隊列的隊尾。如果有一 個資源被釋放，在等待隊列中的第一個進程被喚醒并取得這個資源的使用權。六、程序運行結果：在程序中設置了兩個消費者，三個生產者，為便于描述出生產 -消費的過程，我用食 物代表被緩沖區(qū)消費的資源。 在實驗結果中我們可以看到幾個生產者生產的食物放在緩 沖區(qū)中，消費者需求的話就去緩沖區(qū)去取。在同一個時間點上不必生產者生產一個消費 者就消費一個，消費者某個時間消費的資源有可能是上一個生產者所生產的。

15、由于按題 目要求設置的緩沖區(qū)為 20，所以緩沖區(qū)沒有溢出到等待消費者消費的情況。七、課程設計總結：本次課程設計通過模擬計算機操作系統(tǒng)中經典的“生產者一消費者問題”，鞏固了我在操作系統(tǒng)原理課上所學的知識，加深了對操作系統(tǒng)中進程同步和互斥等 問題，完成了多進程同步方法解決生產者-消費者問題全部過程，結果滿足設計 要求。設計過程中遇到不少困難，在反復研究老師的PPT及課本的原理后才逐漸明 晰怎樣將代碼實現(xiàn)，雖然這學期學過Java,但java不是很熟悉，因此還是選擇C+語言。以前學習C+沒有深入了解到線程這個概念，在學習 Java的時候才知 道有專門的線程類。所以我在網上也參考了其他人用C+編寫尤其是

16、關于多進程程序的設計實現(xiàn)。在代碼的實現(xiàn)過程中，我是主要定義了兩個函數(shù)DWORD WINAPI Consumer(LPVOID para) 和 DWORD WINAPI Producer(LPVOID para) ，在這兩 個函數(shù)中實現(xiàn) PV 操作。通過本次設計，我較好地掌握了通過研究 Linux 的進程機制和信號量實現(xiàn)生 產者消費者問題的并發(fā)控制全過程，尤其是對多進程程序設計方法有了更深的理 解，開拓了思路，鍛煉了實踐動手能手。但是我覺得課程設計的時間有點短，中 間又夾雜著好幾場考試，所以沒能做出界面以便于直觀的觀察出詳細過程，只是 用代碼實現(xiàn)了要描述的功能且達到了要求，所以改進的空間還比較大

17、。參考文獻1 計算機操作系統(tǒng)教程 .孫鐘秀等編著 .高等教育出版社 ,2010 年 8月出版2 數(shù)據(jù)結構教程 . 李春葆等編著 清華大學出版社 .2009 年 4 月面向對象程序設計與 Visual C+6.0 教程 陳天華編著 清華大學出版社 .2009 年 7月附源代碼:#i nclude <win dows.h>#i nclude <stdio.h>#i nclude <stdlib.h>#in elude <time.h>typedef HANDLE Semaphore;/信號量的Windows原型/定義Windows下的P操作定義Win

18、dows下的V操作#defi ne P(S) WaitForSi ngleObject(S,INFINITE)/#defi ne V(S) ReleaseSemaphore(S,1,NULL) #defi ne rate 1000#defi ne CONSUMER_NUM 2/*消費者個數(shù)*/#defi ne PRODUCER_NUM 3/*生產者個數(shù)*/#defi ne BUFFER_NUM 20/* 緩沖區(qū)個數(shù) */"小籠包”，”火腿char *thing8 = "雞腿堡”，”薯條","可樂”，”三明治”，”面包"","

19、饅頭” ;/生產和消費的產品名稱struct Buffer指針int productBUFFER_NUM;int start,e nd;/g_buf;/ 緩沖區(qū)兩個指針相當于教材中的in outSemaphore Empty,Full,Mutex;*/分別相當于Empty, Full, Mutex三個信號量/i表示第i個消費者inti ='Xint *)para;/利用para傳入當前消費者的編號intptr;/待消費的內容的指針printf("消費者%1d:需要資源n" , i);intj=0;消費者線程DWORD WINAPI Co nsumer(LPVOID

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

21、x);V(Empty);Sleep(rate*ra nd()%10+110);return 0;生產者線程 *DWORD WINAPI Producer(LPVOID para)inti = *(int *)para - CONSUMER_NUM;intptr;intdata;/產品intj=0;while (j+<4)data=ra nd()%8;printf("生產者 %01d:生產出：%s!n",i,thingdata);/等待存放空間P(Empty);/有地方，先鎖住緩沖區(qū)P(Mutex);/記錄消費的物品ptr=g_buf.e nd;/再移動緩沖區(qū)指針g_b

22、uf.e nd =(g_buf.e nd+1)%BUFFER_NUM;printf("生產者 %01d:放到緩沖區(qū)buf%d=%sn" ,i,ptr,thingdata);g_ductptr=data;/放好了完畢，釋放一個產品/讓其他消費者或生產者使用V(Mutex);V(Full);Sleep(rate/2*ra nd()%1O+11O);return 0;int main( int argc, char *argv)/線程技術，前面為消費者線程，后面為生產者線程HANDLE hThreadCONSUMER_NUM+PRODUCER_NUM;/ 線程計數(shù)sran d(time(NULL);ran d();DWORD tid;int i=0;/初始化信號量Mutex=CreateSemaphore(NULL,1