1、操作系統綜合設計實現生產者消費者問題目 錄第一部分：實現生產者與消費者問題一、題目21、課程設計目的22、課程設計要求2二、設計內容2三、開發環境3四、分析設計31、設計原理32、涉及的數據結構53、流程圖6五、運行示例及結果分析81、運行示例82、運行結果分析：9六、個人體會9七、附錄（源程序）10第一部分：實現生產者與消費者問題一、題目：實現生產者與消費者問題此問題是經典的進程同步互斥問題，問題描述參見教材第36頁和第46頁，要求編程實現，生產者放入產品的和消費者取走產品的速度可以調節。1、課程設計目的：在我們所學的操作系統這門課程中，關于經典進程的同步問題進行了一定的描述和探討，介紹了幾

2、個經典的算法，需要我們在實踐中學會熟練運用。在生產者與消費者問題中，需要我們了解進程同步的概念，理解信號量機制的原理，掌握運用信號量解決進程同步問題的方法，進而學會運用進程的同步與互斥解決生產者與消費者的沖突問題。2、課程設計要求：生產者與消費者問題可以算作是經典進程同步問題的典型代表。該課程設計要求運用基于單緩沖區和多緩沖區的生產者與消費者問題的多種實現機制,其中利用了數據結構中的循環隊列和堆棧來模擬實現是一種比較容易實現的方法。這種思想能夠幫助我們更好的理解所學內容，并加以鍛煉我們的動手實踐能力,實現它內在具有的超強的參考價值和實踐意義。該課程設計通過了解進程間的兩種制約關系，從而理解信號

3、量機制；通過對實例的分析和討論，理解信號量機制實現進程的同步及互斥的方法；通過對經典進程同步問題的剖析，初步掌握運用信號量解決進程同步問題的方法。二、設計內容在同一個進程地址空間內執行的兩個線程。生產者線程生產物品，然后將物品放置在一個空緩沖區中供消費者線程消費。消費者線程從緩沖區中獲得物品，然后釋放緩沖區。當生產者線程生產物品時，如果沒有空緩沖區可用，那么生產者線程必須等待消費者線程釋放出一個空緩沖區。當消費者線程消費物品時，如果沒有滿的緩沖區，那么消費者線程將被阻塞，直到新的物品被生產出來，我的具體做法也是如此，建立緩沖區，生產者生產的產品放入，消費者從中取產品，如果沒有產品，則等待。三、

4、開發環境此程序的設計在Windows XP操作系統下,基于Microsoft Visual C+6.00環境下的一個關于實現生產者與消費者問題的程序。用C語言實現編程。四、分析設計1、設計原理進程同步是指幾個進程相互合作，一個進程到達某個點后，除非另一個進程已經完成某些操作，否則就不得不停下來，等待這些操作的結束，這就是進程同步的概念。生產者-消費者問題是一個經典的進程同步問題，該問題最早由Dijkstra提出，用以演示他提出的信號量機制。本作業要求設計在同一個進程地址空間內執行的兩個線程。生產者線程生產物品，然后將物品放置在一個空緩沖區中供消費者線程消費。消費者線程從緩沖區中獲得物品，然后釋

5、放緩沖區。當生產者線程生產物品時，如果沒有空緩沖區可用，那么生產者線程必須等待消費者線程釋放出一個空緩沖區。當消費者線程消費物品時，如果沒有滿的緩沖區，那么消費者線程將被阻塞，直到新的物品被生產出來。生產者消費者問題是一種同步問題的抽象描述。計算機系統中的每個進程都可以消費或生產某類資源，當系統中某一進程使用某一資源時，可以看作是消耗，且該進程稱為消費者。而當某個進程釋放資源時，則它就相當一個生產者。 通過一個有界緩沖區把生產者和消費者聯系起來。假定生產者和消費者是相互等效的，只要緩沖區未滿，生產者就可以將產品送入緩沖區，類似地，只要緩沖區未空，消費者就可以從緩沖區中去走物品并消費它。生產者和

6、消費者的同步關系將禁止生產者向滿的緩沖區輸送產品，也禁止消費者從空的緩沖區中提取物品。 在生產者消費者問題中，信號燈具有兩種功能。首先，它是跟蹤資源的生產和消費的計數器；其次，它是協調資源的生產者和消費者之間的同步器。消費者通過再一指派給它的信號燈上做P操作來表示消耗資源，而生產者通過在同一信號燈上做V操作來表示生產資源。再這種信號燈的實施中，計數在每次P操作后減1，而在每次V操作中加1。個這一計數器的初始值是可利用的資源數目。當資源是不可利用時，將申請資源的進程放置在等待隊列中。如果有一個資源釋放，在等待隊列中的第一個進程被喚醒并得到資源的控制權。 為解決這一類生產者消費者問題，設置了兩個同

7、步信號燈，一個說明空緩沖區的數目，用empty表示，其初值為有界緩沖區的大小n，另一個說明緩沖區的數目，用full表示，其初制值為0。由于有界緩沖區是一個零界資源，必須互斥使用，所以另外還需設置一個互斥信號燈mutex,起初值為1。 假定在生產者和消費者之間的公用緩沖區中，具有n個緩沖區，這時可以利用互斥信號量mutex實現諸進程對緩沖池的互斥使用；利用信號量empty和full分別表示緩沖池中空緩沖區和滿緩沖區的數量。又假定這些生產者和消費者互相等效果，只要緩沖池未滿，生產者便可以將消息送入緩沖池；只要緩沖池未空，消費者便可以從緩沖池中取走一個消息。在生產者-消費者問題中應注意：首先，在每個

8、程序中用于互斥的wait(mutex)和signal(mutex)必須成對出現；其次，對資源信號量empty和full的wait和signal操作，同樣需要成對地出現，但它們分別處于不同的程序中。生產者與消費者進程共享一個大小固定的緩沖區。其中，一個或多個生產者生產數據，并將生產的數據存入緩沖區，并有一個或多個消費者從緩沖區中取數據。假設緩沖區的大小為n（存儲單元的個數），它可以被生產者和消費者循環使用。分別設置兩個指針in和out，指向生產者將存放數據的存儲單元和消費者將取出數據的存儲單元，如圖，指針in和out初始化指向緩沖區的第一個存儲單元。生產者從第一個存儲單元開始存放數據，一次存放一

9、條數據一條數據且in指針向后移一個位置，當in 指針指向第n個存儲單元，下一次將指向第一個存儲單元，如此循環反復使用緩沖區。消費者從緩沖區中逐條取走數據，一次取一條數據，相應的存儲單元變為“空”，可以被生產者再次使用。每次取走一條數據，out指針向后移一個存儲單元位置。試想，如果不控制生產者與消費者，將會產生什么結果？ 1 2 3 4 5 6 7 8 n In out 1 2 3 4 5 6 7 8 n In out 其中，in表示存數據位置，out表示取數據位置： ：被占用單元 ：空存儲單元圖：生產者/消費者循環使用緩沖區首先，生產者和消費者可能同時進入緩沖區，甚至可能同時讀/寫一個存儲單元

10、，將導致執行結果不確定。這顯然是不允許的。所以，必須使生產者和消費者互斥進入緩沖區。即某時刻只允許一個實體（生產者或消費者）訪問緩沖區，生產者互斥消費者和其他任何生產者。其次，生產者不能向滿的緩沖區寫數據，消費者也不能在空緩沖區中取數據，即生產者與消費者必須同步。當生產者產生出數據，需要將其存入緩沖區之前，首先檢查緩沖區中是否有“空”存儲單元，若緩沖區存儲單元全部用完，則生產者必須阻塞等待，直到消費者取走一個存儲單元的數據，喚醒它。若緩沖區內有“空”存儲單元，生產者需要判斷此時是否有別的生產者或消費者正在使用緩沖區，若是有，則阻塞等待，否則，獲得緩沖區的使用權，將數據存入緩沖區，釋放緩沖區的使

11、用權。消費者取數據之前，首先檢查緩沖區中是否存在裝有數據的存儲單元，若緩沖區為“空”，則阻塞等待，否則，判斷緩沖區是否正在被使用，若正被使用，若正被使用，則阻塞等待，否則，獲得緩沖區的使用權，進入緩沖區取數據，釋放緩沖區的使用權。其執行流程如圖所示，偽代碼如圖所示。2、涉及的數據結構用資源向量Available。這是一個含有m個元素的數組，其中的每一個元素代表一類可利用的資源數目，其初始值是系統中所配置的該類全部可用資源的數目，其數值隨該類資源的分配和回收而動態地改變。如果Availablej=K，則表示系統中縣有RJ類資源K個。需求矩陣MAX。這是一個N*M的矩陣，它定義了系統中N個進程中的

12、每一個進程對M類資源的最大需求。如果MAXi,j=K，則表示進程I需要RJ類資源的最大數目為K。矩陣Allocation。這也是一個N*M的矩陣，它定義了系統中每一類資源當前已分配給每一進程的資源數。如果Allocationi,j=K，則表示進程i當前已分得RJ類資源的數目為K。矩陣Need。這也是一個N*M的矩陣，用以表示每一個進程尚需的各類資源數。如果Needi,j=K，則表示進程I還需要RJ類資源K個，方能完成其任務。 上述三個矩陣間存在下述關系： Needi,j=MAXi,j-Allocationi,j3、流程圖等待使用權，阻塞被喚醒等待資源，阻塞數據單元加1，喚醒一個消費者歸還使用權

13、存入一條數據生產一條數據是否可用存儲單元 無 有是否可用 否被喚醒是否有數據單元等待資源，阻塞 有被喚醒是否可用 否消費數據空單元加1，喚醒一個生產者歸還使用權被喚醒取走一條數據等待使用權，阻塞 是五、運行示例及結果分析1、運行示例：2、運行結果分析：此程序可自動輸入生產者、消費者數目等條件，但程序執行過程中也進入了一種無限循環狀態，若要得到較好的結果和界面需要加強編程練習。六、個人體會經過快一個月的時間來弄這個大型作業。我當時真的有點力不從心。后來老師只要我們實現OS里面的一部分功能-進程的控制和管理。就是比較有名的那兩個進程算法。有于當時在實驗室就對進程之間的運轉有了一個全面的了解，雖然好

14、多的細節部分還不是太了解，但是對一個進程的流向和執行過程還是有個大概的認識，所以這個大型作業做起來也不是那么的簡單。那些東西的詳細說明在我們的教材上是沒有的。后來，我就在網上和圖書館大量的找資料。先對那些算法有一個大致全面的了解。經過兩個多星期的查資料。我就開始對那兩個算法的代碼進行完善和修改，以達到我的要求。有經過了一個多星期的調試和運行終于達到了我的要求了。并把結果截取如下。在生產者與消費者問題的算法編寫程序的時候要盡可能用全所學到的函數，因為這是檢測我們用C語言進行程序設計的能力的重要方式。在編寫程序的時候我們不可能一次就成功，往往一個圖形要修改甚至是十幾次數據才能得到預期的結果。因此在

15、編寫程序的時候一定不能急躁，要耐心地檢測輸入的數據和輸出的結果，在沒達到預期目的的情況下，要及時修改數據進行下一次的檢測，只有這樣才能成功地用C語言編寫出需要的程序。 編寫程序是一個長期的過程，因此不能急躁，要坐的住。由于對C語言知識已經有些遺忘，所以我找出了以前的筆記，花了半天的時間去回憶和理解。對操作系統有關消費者-生產者問題的含義也已經有點模糊，我花了一天的時間看教材，還到圖書館借閱了相關的資料，才開始編程。剛開始對如何動態實現消費者-生產者問題一籌莫展，于是和一些同學就這個問題討論過，但是沒什么好的效果。編寫程序有的時候需要的就是靈感，因此當有靈感的時候就要開始做，而不能等，必須在靈感

16、未消失前付諸行動，所以才有了凌晨兩點才最后做完大型作業。雖然很累，但是覺得值得。歷經快一個月的時間讓我馬馬乎乎的完成了它，從中讓我得到了好多的東西，首先，這個過程鍛煉了我的意志，還讓我對進程的控制和編寫過程有了一個更深層次的認識和理解。其次，我現在對Windows操作系統執行流程有了一個透明的認識，同時也讓我對它更有親切感。總之，這次作業讓我受益匪淺！七、附錄(源程序) #include #include #include typedef HANDLE Semaphore; /信號量的Windows原型 #define P(S) WaitForSingleObject(S, INFINITE)

17、 /定義Windows下的P操作 #define V(S) ReleaseSemaphore(S, 1, NULL)/定義Windows下的V操作 #define rate 1000 #define CONSUMER_NUM 4 /* 消費者個數 */ #define PRODUCER_NUM 4 /* 生產者個數 */ #define BUFFER_NUM 4 /* 緩沖區個數 */ char *thing10=s1, s2, s3, s4,; struct Buffer int productBUFFER_NUM; / 緩沖區 int start, end; / 兩個指針 g_buf; S

18、emaphore g_semBuffer, g_semProduct, g_mutex; /消費者線程 DWORD WINAPI Consumer(LPVOID para) /i表示第i個消費者 Int i = *(int *)para; int ptr; /待消費的內容的指針 printf(小白兔-%03d:葉子n, i); Sleep(1800); while (1) printf(小白兔-%03d:我餓了.!n,i); /等待產品 P(g_semProduct); /有產品，先鎖住緩沖區g_buf P(g_mutex); /記錄消費的物品 ptr=g_buf.start; /再移動緩沖區

19、指針 g_buf.start= (g_buf.start+1)%BUFFER_NUM; /讓其他消費者或生產者使用g_buf V(g_mutex); printf(小白兔-%03d:我需要buf%d = %sn, i, ptr, thingg_ductptr); Sleep(rate*rand()%10+1800); /消費完畢，并釋放一個緩沖 printf(小白兔-%03d:吃綠葉buf%d = %sn,i, ptr, thingg_ductptr); V(g_semBuffer); Return 0; /生產者線程 DWORD WINAPI Producer(L

20、PVOID para) int i=*(int*)para-CONSUMER_NUM; int ptr; int data; /產品 printf(小草-%03d:小白兔快來找我!n, i); Sleep(1800); while (1) printf(小草-%03d:我愛陽光n, i); Sleep(rate*rand()%10+1800); data = rand()%10; printf(小草-%03d:我要長大!data = %s!n, i, thingdata); /等待存放空間 P(g_semBuffer); /有地方,先鎖住緩沖區g_buf P(g_mutex); /記錄消費的物

21、品 ptr = g_buf.end; /再移動緩沖區指針 g_buf.end = (g_buf.end+1)%BUFFER_NUM; /讓其他消費者或生產者使用 g_buf V(g_mutex); printf(小草-%03d:長大了!buf%d = %sn, i, ptr, thingdata); g_ductptr = data; Sleep(rate/2*rand()%10+1800); /放好了完畢，釋放一個產品 printf(小草-%03d: buf%d=%s 小白兔快來!n,i, ptr,thingg_ductptr); V(g_semProduct);

22、 return 0; int main(int argc, char *argv) /線程技術，前面為消費者線程，后面為生產者線程 HANDLE hThreadCONSUMER_NUM+PRODUCER_NUM; /線程計數 /srand(time(); DWORD tid; int i=0; /初始化信號量 g_mutex=CreateSemaphore(NULL,BUFFER_NUM,BUFFER_NUM,mutexOfConsumerAndProducer); g_semBuffer=CreateSemaphore(NULL,BUFFER_NUM,BUFFER_NUM,BufferSemaphone); g_semProduct= CreateSemaphore(NULL, 0, BUFFER_NUM, Prod