多進(jìn)程同步方法解決生產(chǎn)者-消費(fèi)者問(wèn)題

1、-. z. - - s-課程設(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ò)研究Linu*的進(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ì)緩沖

2、區(qū)進(jìn)展操作的函數(shù)代碼.2、程序設(shè)計(jì)根本思想: 生產(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ū)就好似

3、使用一條傳送帶替代托架，傳送帶上一次可以放多個(gè)產(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ū)空，它就開(kāi)場(chǎng)等待Producer。生產(chǎn)者線程寫(xiě)入一個(gè)新的數(shù)據(jù)之后，就立刻發(fā)出Consum

4、er來(lái)喚醒正在等待的消費(fèi)者線程；消費(fèi)者線程在讀取一個(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ū)根本算法如下：-var B : array0.n-1 of

5、integer; Empty: g_hFullSemaphore:= SIZE_OF_BUFFER; /* 可以使用的空緩沖區(qū)數(shù) */ Full: g_hEmptySemaphore:=0; /* 緩沖區(qū)內(nèi)可以使用的產(chǎn)品數(shù) */ Mute* :semaphore:=1; in , out:integer:= 0; /* 放入/取出緩沖區(qū)指針*/cobeginprocess producer_I(I=1,2,m) process consumer_j (j=1,2,k) Begin beginL1:produce a product; L2:P(Full);/對(duì)資源信號(hào)量與互斥信號(hào)量 /P操作生

6、產(chǎn)消耗一個(gè)緩沖區(qū)P操作，申請(qǐng)資源P(Empty); P(Mute*);P(Mute*); Product:= Bout;Bin := product; out:=(out+1) mod n;in:=(in+1) mod n; V(Mute*);V(Mute*); V(Empty);V(Full); Consume a product;Goto L1; Goto L2;end; end; Coend 三、程序流程圖：4.1、生產(chǎn)者流程構(gòu)造：生產(chǎn)者線程開(kāi)場(chǎng)資源信號(hào)量P操作互斥信號(hào)量P操作生產(chǎn)一個(gè)產(chǎn)品把產(chǎn)品送入緩沖區(qū)互斥信號(hào)量V操作資源信號(hào)量V操作等待隊(duì)列中有消費(fèi)者線程等待隊(duì)列中有消費(fèi)者線程線程自我

7、阻塞添加到等待隊(duì)列線程自我阻塞添加到等待隊(duì)列未通過(guò)未通過(guò)通過(guò)通過(guò)喚醒對(duì)頭的消費(fèi)者線程喚醒對(duì)頭的消費(fèi)者線程生產(chǎn)者線程完畢YYNN4.2消費(fèi)者流程構(gòu)造：消費(fèi)者線程開(kāi)場(chǎng)資源信號(hào)量P操作互斥信號(hào)量P操作從緩沖區(qū)取出一個(gè)產(chǎn)品消費(fèi)一個(gè)產(chǎn)品互斥信號(hào)量V操作資源信號(hào)量V操作等待隊(duì)列中有生產(chǎn)者線程等待隊(duì)列中有生產(chǎn)者線程線程自我阻塞添加到等待隊(duì)列線程自我阻塞添加到等待隊(duì)列未通過(guò)未通過(guò)通過(guò)通過(guò)喚醒對(duì)頭的生產(chǎn)者線程喚醒對(duì)頭的生產(chǎn)者線程消費(fèi)者線程完畢YYNN四、數(shù)據(jù)構(gòu)造及局部函數(shù)描述用一個(gè)整型數(shù)組Buffer_NUM來(lái)代表緩沖區(qū)。生產(chǎn)產(chǎn)品及對(duì)已有產(chǎn)品消費(fèi)都需要訪問(wèn)該組緩沖區(qū)。 緩沖區(qū)的大小和構(gòu)造體：struct Buf

8、fer int productBUFFER_NUM; / 緩沖區(qū) int start, end; / 兩個(gè)指針相當(dāng)于教材中的 in out 指針g_buf; 在實(shí)現(xiàn)本程序的消費(fèi)生產(chǎn)模型時(shí)，具體地通過(guò)如下同步對(duì)象實(shí)現(xiàn)互斥：設(shè)一個(gè)互斥量Mute*，以實(shí)現(xiàn)生產(chǎn)者在查詢和保存緩沖區(qū)內(nèi)的下一個(gè)空位置時(shí)進(jìn)展互斥。每一個(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ū)中是否存在空位置，以便開(kāi)場(chǎng)生產(chǎn)下一個(gè)產(chǎn)品。c)定義Windows下的P操作#define P(S) WaitForSingleObj

9、ect(S, INFINITE)說(shuō)明：WaitForSingleObject函數(shù)用來(lái)檢測(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)狀態(tài)，函數(shù)照樣返回。參數(shù)dwMilliseconds有兩個(gè)具有特殊意義的值：0和INFINITE。假設(shè)為0，則該函數(shù)立即返回；假設(shè)為INFINITE，則線程一直被掛起，直到hHandle所指向的對(duì)象變?yōu)橛行盘?hào)狀態(tài)時(shí)為止。d)定義Windows下的

10、V操作#defineV(S) ReleaseSemaphore(S, 1, NULL) 說(shuō)明ReleaseSemaphore函數(shù)用于對(duì)指定的信號(hào)量增加指定的值 e)生產(chǎn)者線程代碼：DWORD WINAPI Producer(LPVOID para) int i = *(int *)para - CONSUMER_NUM; int ptr; int data; /產(chǎn)品 int j=0; while (j+4) data = rand()%8; printf(生產(chǎn)者%01d: 生產(chǎn)出: %s!n,i,thingdata); /等待存放空間 P(Empty); /有地方，先鎖住緩沖區(qū) P(Mute*

11、); /記錄消費(fèi)的物品 ptr = g_buf.end; /再移動(dòng)緩沖區(qū)指針 g_buf.end = (g_buf.end+1)%BUFFER_NUM; printf(生產(chǎn)者%01d: 放到緩沖區(qū) buf%d=%sn,i,ptr,thingdata); g_ductptr=data; /放好了完畢，釋放一個(gè)產(chǎn)品 /讓其他消費(fèi)者或生產(chǎn)者使用 V(Mute*); V(Full); Sleep(rate/2*rand()%10+110); return 0; 消費(fèi)者線程代碼： DWORD WINAPI Consumer(LPVOID para) / i表示第i個(gè)消費(fèi)者 int i =

12、*(int *)para; /利用para傳入當(dāng)前消費(fèi)者的編號(hào) int ptr; / 待消費(fèi)的內(nèi)容的指針 printf(消費(fèi)者%1d: 需要資源n, i); int j=0; while (j+4) /等待產(chǎn)品 P(Full); /有產(chǎn)品，先鎖住緩沖區(qū) P(Mute*); /記錄消費(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); /消費(fèi)完畢，并釋放一

13、個(gè)緩沖 printf( 消費(fèi)者%01d: 我消費(fèi)完畢%sn, i,thingg_ductptr); V(Mute*); V(Empty); Sleep(rate*rand()%10+110); return 0; 五、調(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表示，其初始值為0。另外，由于有界緩沖區(qū)是一個(gè)臨界資源，必須互斥使用，所以還需要再設(shè)置一個(gè)互斥信號(hào)量Mute*，起初值為1。 在生產(chǎn)者/消費(fèi)者問(wèn)題中，信號(hào)量實(shí)現(xiàn)兩種功能。首先

14、，它是生產(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í)，首先對(duì)資源信號(hào)量Full和互斥信號(hào)量Mute*進(jìn)展P操作，申請(qǐng)資源。如果可以通過(guò)的話，就生產(chǎn)一個(gè)產(chǎn)品，并把產(chǎn)品送入緩沖區(qū)。然后對(duì)互斥信號(hào)量Mute*和資源信號(hào)量Empty進(jìn)展V操作，釋放資源。 消費(fèi)者要消費(fèi)一個(gè)產(chǎn)品時(shí)，首先對(duì)資源信號(hào)量Empty和互斥信號(hào)量Mute*進(jìn)展P操作，申請(qǐng)資源。如果可以通過(guò)的話，就從緩沖區(qū)取出一個(gè)產(chǎn)品并消費(fèi)掉。然后對(duì)互斥信號(hào)量Mute*和資源信號(hào)量Full進(jìn)展V操作，釋放資源。如果緩沖區(qū)中已經(jīng)沒(méi)有可用

15、資源，就把申請(qǐng)資源的進(jìn)程添加到等待隊(duì)列的隊(duì)尾。如果有一個(gè)資源被釋放，在等待隊(duì)列中的第一個(gè)進(jìn)程被喚醒并取得這個(gè)資源的使用權(quán)。 六、程序運(yùn)行結(jié)果：在程序中設(shè)置了兩個(gè)消費(fèi)者，三個(gè)生產(chǎn)者，為便于描述出生產(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)題，穩(wěn)固了我

16、在操作系統(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ù)研究教師的PPT及課本的原理后才逐漸明晰怎樣將代碼實(shí)現(xiàn)，雖然這學(xué)期學(xué)過(guò)Java，但java不是很熟悉，因此還是選擇C+語(yǔ)言。以前學(xué)習(xí)C+沒(méi)有深入了解到線程這個(gè)概念，在學(xué)習(xí)Java的時(shí)候才知道有專門(mén)的線程類。所以我在網(wǎng)上也參考了其他人用C+編寫(xiě)尤其是關(guān)于多進(jìn)程程序的設(shè)計(jì)實(shí)現(xiàn)。在代碼的實(shí)現(xiàn)過(guò)程中，我是主要定義了兩個(gè)函數(shù) DWORD WINAPI Consumer(LPVOID para) 和 DWORD WINAPI Produce

17、r(LPVOID para)，在這兩個(gè)函數(shù)中實(shí)現(xiàn)PV操作。通過(guò)本次設(shè)計(jì)，我較好地掌握了通過(guò)研究Linu* 的進(jìn)程機(jī)制和信號(hào)量實(shí)現(xiàn)生產(chǎn)者消費(fèi)者問(wèn)題的并發(fā)控制全過(guò)程，尤其是對(duì)多進(jìn)程程序設(shè)計(jì)方法有了更深的理解，開(kāi)拓了思路，鍛煉了實(shí)踐動(dòng)手能手。但是我覺(jué)得課程設(shè)計(jì)的時(shí)間有點(diǎn)短，中間又夾雜著好幾場(chǎng)考試，所以沒(méi)能做出界面以便于直觀的觀察出詳細(xì)過(guò)程，只是用代碼實(shí)現(xiàn)了要描述的功能且到達(dá)了要求，所以改良的空間還比擬大。參 考 文 獻(xiàn)1計(jì)算機(jī)操作系統(tǒng)教程.孫鐘秀等編著.高等教育,2010年8月出版2數(shù)據(jù)構(gòu)造教程.李春葆等編著 清華大學(xué).2009年4月3面向?qū)ο蟪绦蛟O(shè)計(jì)與Visual C+6.0教程 陳天華編著 清華

18、大學(xué).2009年7月附源代碼：#include #include #include #include typedef HANDLE Semaphore; / 信號(hào)量的Windows原型 #define P(S) WaitForSingleObject(S,INFINITE) / 定義Windows下的P操作 #define V(S) ReleaseSemaphore(S,1,NULL) / 定義Windows下的V操作 #define rate 1000 #define CONSUMER_NUM 2 /* 消費(fèi)者個(gè)數(shù) */#define PRODUCER_NUM 3 /* 生產(chǎn)者個(gè)數(shù) */#d

19、efine BUFFER_NUM 20 /* 緩沖區(qū)個(gè)數(shù) */char *thing8 = 雞腿堡, 薯?xiàng)l, 可樂(lè), *治, 面包, 小籠包, 火腿,饅頭; /生產(chǎn)和消費(fèi)的產(chǎn)品名稱 struct Buffer int productBUFFER_NUM; / 緩沖區(qū) int start,end; / 兩個(gè)指針相當(dāng)于教材中的 in out 指針g_buf; Semaphore Empty,Full,Mute*; /分別相當(dāng)于Empty, Full, Mute*三個(gè)信號(hào)量 /* 消費(fèi)者線程*/ DWORD WINAPI Consumer(LPVOID para) / i表示第i個(gè)消費(fèi)者 int i

20、 = *(int*)para; /利用para傳入當(dāng)前消費(fèi)者的編號(hào)int ptr; / 待消費(fèi)的內(nèi)容的指針 printf(消費(fèi)者%1d: 需要資源n, i); int j=0;while (j+4) / 等待產(chǎn)品 P(Full); / 有產(chǎn)品，先鎖住緩沖區(qū) P(Mute*); / 記錄消費(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); /消費(fèi)完畢，

21、并釋放一個(gè)緩沖 printf( 消費(fèi)者%01d: 我消費(fèi)完畢%sn, i,thingg_ductptr); V(Mute*); V(Empty); Sleep(rate*rand()%10+110); return 0; /* 生產(chǎn)者線程*/ DWORD WINAPI Producer(LPVOID para) int i = *(int*)para - CONSUMER_NUM; int ptr; int data; /產(chǎn)品 int j=0;while(j+4) data=rand()%8; printf(生產(chǎn)者%01d: 生產(chǎn)出: %s!n,i,thingdata); /等待

22、存放空間 P(Empty); /有地方，先鎖住緩沖區(qū) P(Mute*); /記錄消費(fèi)的物品 ptr=g_buf.end; /再移動(dòng)緩沖區(qū)指針 g_buf.end =(g_buf.end+1)%BUFFER_NUM; printf(生產(chǎn)者%01d: 放到緩沖區(qū) buf%d=%sn,i,ptr,thingdata); g_ductptr=data; /放好了完畢，釋放一個(gè)產(chǎn)品 /讓其他消費(fèi)者或生產(chǎn)者使用 V(Mute*); V(Full); Sleep(rate/2*rand()%10+110); return 0; int main(int argc,char*argv) /線程技術(shù)，前面為消費(fèi)者線程，后面為生產(chǎn)者線程 HANDLE hThreadCONSUMER_NUM+PRODUCER