1、生產者消費者問題模擬實現(z)生產者 - 消費者實驗1.1 實驗目的和要求實驗目的操作系統的基本控制和管理控制都圍繞著進程展開，其中的復雜性是由于支持并發和并發機制而引起的。自從操作系統中引入并發程序設計后，程序的執行不再是順序的， 一個程序未執行完而另一個程序便已開始執行， 程序外部的順序特性消失， 程序與計算不再一一對應。 并發進程可能是無關的，也可能是交互的。然而，交互的進程共享某些變量， 一個進程的執行可能會影響其他進程的執行結果， 交互的并發進程之間具有制約關系、 同步關系。其中典型模型便是生產者- 消費者模型。本實驗通過編寫和調試生產者 - 消費者模擬程序，進一步認識進程并發執行的

2、實質， 加深對進程競爭關系， 協作關系的理解， 掌握使用信號量機制與 P、V 操作來實現進程的同步與互斥。實驗要求1用高級語言編寫一個程序，模擬多個生圖 3.1 生產者消費者問題示意圖著名的生產者消費者問題（ producer-consumer problem ）是計算機操作系統中并發進程內在關系的一種抽象， 是典型的進程同步問題。 在操作系統中， 生產者進程可以是計算進程、 發送進程，而消費者進程可以是打印進程、接收進程等， 解決好生產者消費者問題就解決了一類并發進程的同步問題。操作系統實現進程同步的機制稱為同步機制，它通常由同步原語組成。 不同的同步機制采用不同的同步方法，迄今已設計出多種

3、同步機制，本實驗采用最常用的同步機制：信號量及PV操作。信號量與 PV操作1965 年，荷蘭計算機科學家提出新的同步工具信號量和PV操作，他將交通管制中多種顏色的信號燈管理方法引入操作系統，讓多個進程通過特殊變量展開交互。 一個進程在某一關鍵點上被迫停止直至接收到對應的特殊變量值， 通過這一措施任何復雜的進程交互要求均可得到滿足， 這種特殊變量就是信號量（semaphore）。為了通過信號量傳送信號，進程可利用 P 和 V 兩個特殊操作來發送和接收信號，如果協作進程的相應信號仍未到達， 則進程被掛起直至信號到達為止。在操作系統中用信號量表示物理資源的實體，它是一個與隊列有關的整型變量。具體實現

4、時，信號量是一種變量類型， 用一個記錄型數據結構表示，有兩個分量：一個是信號量的值，另一個是信號量隊列的指針。 信號量在操作系統中主要用于封鎖臨界區、進程同步及維護資源計數。除了賦初值之外，信號量僅能由同步原語 PV 對其操作，不存在其他方法可以檢查或操作信號量， PV 操作的不可分割性確保執行的原子性及信號量值的完整性。利用信號量和 PV 操作即可解決并發進程競爭問題， 又可解決并發進程協作問題。信號量按其用途可分為兩種：公用信號量，聯系一組并發進程， 相關進程均可在此信號量上執行 PV操作，用于實現進程互斥； 私有信號量，聯系一組并發進程， 僅允許此信號量所擁有的進程執行 P 操作，而其他

5、相關進程可在其上執行 V 操作，初值往往為 0 或正整數，多用于并發進程同步。信號量的定義為如下數據結構：typedef struct semaphoreint value; / struct pcb *list;/信號量的值信號量隊列的指針信號量說明：semaphore s;P、V 操作原語描述如下：（ 1） P(s) ：s.value- ；若 s.value 0，則執行 P(s) 的進程繼續執行；若s.value<0 ，則執行 P(s) 的進程被阻塞， 并把它插入到等待信號量 s 的阻塞隊列中。（ 2） V(s) ：s.value+ ；若 s.value 0，則執行 V(s) 的進程

6、從等待信號量 s 的阻塞隊列中喚醒頭一個進程，然后自己繼續執行。若 s.value>0 ，則執行 V(s) 的進程繼續執行；信號量實現互斥信號量和 PV 操作可用來解決進程互斥問題。為使多個進程能互斥地訪問某臨界資源， 只需為該資源設置一互斥信號量 mutex，并置初值為 1，然后將各進程訪問該資源的臨界區置于P(mutex) 和 V(mutex) 操作之間即可。用信號量和 PV操作管理并發進程互斥進入臨界區的一般形式為：semaphore mutex;mutex = 1;cobeginprocess Pi()/*i = 1,2,， n */P(mutex);/*臨界區*/V(mutex

7、);coend當有進程在臨界區中時，mutex 的值為 0 或負值，否則 mutex 值為 1，因為只有一個進程，可用 P 操作把 mutex 減至 0，故可保證互斥操作，這時試圖進入臨界區的其它進程會因執行 P(mutex) 而被迫等待 。 mutex 的取值范圍是 1-(n-1) ，表明有一個進程在臨界區內執行， 最多有 n-1 個進程在信號量隊列中等待。信號量解決生產者消費者問題信號量和 PV操作不僅可以解決進程互斥問題，而且是實現進程同步的有力工具。 在協作進程之間，一個進程的執行依賴于協作進程的信息或消息，在尚未得到來自協作進程的信號或消息時等待，直至信號或消息到達時才被喚醒。生產者

8、消費者問題是典型的進程同步問題，對于生產者進程：生產一個產品，當要送入緩沖區時，要檢查是否有空緩沖區，若有，則可將產品送入緩沖區，并通知消費者進程；否則，等待；對于消費者進程：當它去取產品時，要看緩沖區中是否有產品可取，若有則取走一個產品，并通知生產者進程，否則，等待。這種相互等待，并互通信息就是典型的進程同步。因此應該設兩個同步信號量：信號量 empty 表示可用的空緩沖區的數目，初值為 k；信號量full表示可以使用產品的數目，初值為。緩沖區是一個臨界資源， 必須互斥使用， 所以另外還需要設置一個互斥信號量 mutex，其初值為。用信號量機制解決生產者消費者問題可描述如下：item Bk;

9、semaphore empty; empty=k; /可以使用的空緩沖區數semaphore full;full=0;/緩沖區內可以使用的產品數semaphore mutex; mutex=1; /互斥信號量int in=0;int out=0;/放入緩沖區指針取出緩沖區指針cobeginprocess producer_i()process consumer()While(true)While(true)produce();P(full);P(empty);P(mutex);P(mutex);take from Bout;append to Bin;out =(out+1)%k;in = (

10、in+1)%k;V(mutex);V(mutex);V(empty);V(full);consume();Coend程序中的 P(mutex) 和 V(mutex) 必須成對出現，夾在兩者之間的代碼段是臨界區； 施加于信號量 empty 和 full 上的 PV 操作也必須成對出現，但分別位于不同的程序中。 在生產者消費者問題中， P 操作的次序是很重要的，如果把生產者進程中的兩個 P 操作交換次序， 那么，當緩沖區中存滿 k 件產品時，生產者又生產一件產品，在它欲向緩沖區存放時，將在 P(empty) 上等待，由于此時 mutex=0，它已經占有緩沖區，這時消費者預取產品時將停留在 P(mu

11、tex) 上而得不到使用緩沖區的權力。 這就導致生產者等待消費者取走產品，而消費者卻在等待生產者釋放緩沖區的占有權，這種互相之間的等待永遠不可能結束。所以，在使用信號量和PV 操作實現進程同步時，特別要當心 P 操作的次序， 而 V 操作的次序無關緊要。 一般來說，用于互斥的信號量上的P 操作總是在后面執行。Q 所1.2 生產者消費者問題模擬實現實驗內容考慮一個系統中有 n 個進程，其中部分進程為生產者進程， 部分進程為消費者進程， 共享具有 k 個單位的緩沖區?，F要求用高級語言編寫一個程序， 模擬多個生產者進程和多個消費者進程并發執行的過程，并采用信號量機制與 P、V 操作實現生產者進程和消

12、費者進程間同步以及對緩沖區的互斥訪問。利用信號量機制解決此問題的算法見示。實驗指導1設計提示（ 1）本實驗并不需要真正創建生產者和消費者進程，每個進程用一個進程控制塊（ PCB）表示。 PCB數據結構如下：typedef struct Process/進程PCBchar name10;int roleFlag;/ 進程名/進程類型（1：生產者0:消費者）int currentState;/進程狀態（ 1:可運行態0:int currentStep;阻塞態）/ 斷點int data;/ / 臨時數據/進程編號Process;（2）程序中應指定緩沖區的數目，進程總個數等，現考慮共有 4 個生產者和

13、消費者進程，緩沖區數目是兩個，定義如下所示：#define dataBufferSize 2/緩沖區數目#define processNum 4/進程數量(生產者、消費者進程總數目)struct DataBuffer/緩沖區i nt bufferdataBufferSize;i nt count;/ 當前產品數量 dataBuffer;（ 3）為解決生產者 - 消費者問題需設兩個同步信號量：信號量 empty 表示可用的空緩沖區的數目，初值為緩沖區數目；信號量 full 表示可以使用產品的數目， 初值為。緩沖區是一個臨界資源，必須互斥使用， 所以另外還需要設置一個互斥信號量 mutex，其初值

14、為。信號量定義和說明如下所示：typedef struct Seamphore/信號量int value;int *pcq;/ 信號量的值/ 信號量隊列指針 Seamphore;intproducerCongestionQueueprocessNum;/ / 等待信號量 empty 的阻塞隊列intconsumerCongestionQueueprocessNum;/ / 等待信號量 full 的阻塞隊列int shareCongestionQueueprocessNum;/ 等待信號量 mutex 的阻塞隊列Seamphoreempty=dataBufferSize,producerCong

15、estionQueue;Seamphorefull=0,consumerCongestionQueue;Seamphoremutex=1,shareCongestionQueue;（ 4）為模擬多個生產者和多個消費者進程并發執行的過程， 首先根據進程總個數產生若干生產者和若干消費者進程， 然后隨機調度一個處于就緒態的進程， 判斷是生產者還是消費者， 然后執行不同的代碼， 為模擬并發執行， 進程每執行一步操作就中斷執行，再調度其他進程運行，在被中斷進程的 PCB中記錄了中斷的位置， 等到下次被調度執行時則從此位置繼續執行。（5）生產者進程執行時分為6 步，如下所示：void produce(Pr

16、ocess *p)/ / 生產者進程執行代碼switch (p->currentStep) case 1:/1生產產品p->data = rand()%1000;printf("%20s:生產一個產品%d!n",p->name, p->data);p->currentStep+;break;case 2:/2申請空緩沖區P(&empty, p);break;case 3:/3申請訪問緩沖區P(&mutex, p);break;case 4:/4將產品送入緩沖區push(p->data);printf("%20s:

17、將產品 %d 正送入緩沖區!n", p->name, p->data);p->currentStep+;break;case 5:/5釋放緩沖區訪問權V(&mutex, p);break;case 6:/6產品已送入緩沖區，產品數量加1V(&full, p);p->currentStep = 1;break;（ 6）消費者進程執行時也分為 6 步，如下所示：void consume(Process *p)/消 費者進程執行代碼switch (p->currentStep) case 1:/1申請從緩沖區取出產品P(&full, p

18、);break;case 2:/2申請訪問緩沖區P(&mutex, p);break;case 3:/3從緩沖區中取出產品p->data = pop();printf("%20s:從緩沖區中正取出產品 %d!n", p->name, p->data);p->currentStep+;break;case 4:/4釋放緩沖區訪問權V(&mutex, p);break;case 5:/ /5已 從緩沖區取出一個產品，空緩沖區數量加1V(&empty, p);break;case 6:/ /6消 費產品printf("%2

19、0s: 消 費 產 品 %d!n", p->name, p->data);p->currentStep = 1;break;（ 6）為對生產者進程和消費者進程并發執行的過程進行分析，理解信號量和 P、V 操作在進程同步和互斥機制中的運用， 要求進程每執行一步都輸出每一步的執行情況。2程序流程圖（1）程序流程圖如圖3.2 所示：開始初始化緩沖區和信號量創建若干生產者進程和若干消費者進程隨機選取一個就緒狀態進程YN該進程是生產者？生產者進程執行一步操作消費者進程執行一步操作記錄中斷位置圖 3.2 程序流程圖（ 2）生產者進程和消費者進程執行時各有6 步操作，執行一個操作

20、后會被中斷，下次再被調度執行時接著執行下一操作。 生產者進程流程圖如圖 3.3 所示，消費者進程流程圖如圖 3.4 所示。開始1：生產產品2：P(empty)3：P(mutex)4：將產品送入緩沖區5：V(mutex)6：V(full)開始1：P(full)2：P(mutex)3：從緩沖區取一個產品4：V(mutex)5：V(full)6：消費產品圖 2.2生產者進程流程圖圖 2.3消費者進程流程圖程序示例#include "stdio.h"#include "time.h"#include "stdlib.h"#include &q

21、uot;string.h"#include "windows.h"#define dataBufferSize 2/ 緩沖區數目#define processNum 4/ 進程數量 ( 生產者、消費者進程總數目)typedef struct Seamphore/信號量int value;/ 信號量的值int *pcq;/ 信號量隊列指針 Seamphore;int producerCongestionQueueprocessNum;/ 等待信號量 empty 的阻塞隊列int consumerCongestionQueueprocessNum;/ 等待信號量 fu

22、ll 的阻塞隊列int shareCongestionQueueprocessNum;/ 等待信號量 mutex 的阻塞隊列Seamphoreempty=dataBufferSize,producerCongestionQueue; / empty：空緩沖區數目Seamphorefull=0,consumerCongestionQueue;/full：緩沖區內可用的產品Seamphore mutex=1,shareCongestionQueue;/mutex ：互斥信號量struct DataBuffer/緩沖區int bufferdataBufferSize;int count;/ 當前產品

23、數量 dataBuffer;typedef struct Process/進程PCBchar name10;int roleFlag;/ 進程名/進程類型（1:生產者消費者）int currentState;/進程狀態（1:就緒態0:阻塞態）int currentStep;int data;int code;/斷點/臨時數據/進程編號Process;Process processprocessNum; /進程集合void moveDataForward()int i;for (i = 0; i < dataBuffer.count; i+)dataBuffer.bufferi =data

24、Buffer.bufferi+1;void push(int data)/產品送入緩沖區dataBuffer.bufferdataBuffer.count+ =data;int pop()/從緩沖區取出產品int data = dataBuffer.buffer0;dataBuffer.count-;moveDataForward();return data;void initProcess() int i;char digitTemp5;srand(time(NULL);/ 初始化進程集合for (i = 0; i < processNum; i+) processi.roleFlag

25、 = rand()%2;/ 隨機指定當前進程為生產者或消費者if (processi.roleFlag)strcpy(, "生產者 ");elsestrcpy(, " 消費者 "); strcat(, itoa(i+1,digitTemp, 10);processi.currentState = 1;processi.currentStep = 1;processi.code = i + 1;producerCongestionQueuei = 0; consumerConge

26、stionQueuei = 0; shareCongestionQueuei = 0;void wakeup(int *pcq) / 喚醒進程int code = pcq0 - 1;/ 取出隊首進程processcode.currentState = 1;/進程置為就緒態/ 當進程被喚醒后繼續執行任務if (processcode.roleFlag = 1) / 生產者if (processcode.currentStep = 2)printf("%20s:該進程被喚醒 ! 申請空緩沖區成功 !n", ); else if(processco

27、de.currentStep=3)printf("%20s:該進程被喚醒 ! 申請訪問緩沖區成功 !n", ); else if(processcode.roleFlag= 0) / 消費者if (processcode.currentStep = 1)processcode.data = pop(); printf("%20s: 該進程被喚醒 ! 申請取產品 %d成功 !n", ,processcode.data); else if(processcode.currentStep=2)pr

28、intf("%20s:該進程被喚醒 ! 申請訪問緩沖區成功 !n", );processcode.currentStep+;for (int i = 1; (i < processNum) &&(pcqi != 0); i+) / 刪除隊首進程 pcqi-1 = pcqi;if (pcqi-1 > processNum) pcqi-1 = 0;pcqi-1 = 0;void sleep(int pcq, int code) /阻塞進程int i;processcode-1.currentState = 0;/ 進程

29、置為阻塞態for (i = 0; i < processNum; i+) if (!pcqi) pcqi = code;break;void P(Seamphore *s, Process *p) / 模擬 P操作s->value -= 1;if (s->value>= 0) if (p->roleFlag = 1) /生產者if (p->currentStep = 2) printf("%20s: 申請空緩沖區成功!n", p->name); else if (p->currentStep = 3) printf("

30、;%20s: 申請訪問緩沖區成功!n", p->name); else if (p->roleFlag = 0) / 消費者if (p->currentStep = 1) printf("%20s: 申請取出產品成功!n", p->name); else if (p->currentStep = 2) printf("%20s: 申請訪問緩沖區成功!n", p->name);p->currentStep+;/ 下一步 else if (s->value < 0) if (p->role

31、Flag = 1) /生產者if (p->currentStep = 2) printf("%20s:無空緩沖區 ,該進程被阻塞 !n", p->name); else if (p->currentStep = 3) printf("%20s:其他進程正在訪問緩沖區 ,該進程被阻塞 !n", p->name); else if (p->roleFlag = 0) / 消費者if (p->currentStep = 1) printf("%20s:無產品可取 ,該進程被阻塞 !n", p->na

32、me); else if (p->currentStep = 2) printf("%20s: 其他進程正在訪問緩沖區 ,該進程被阻塞 !n", p->name);sleep(s->pcq, p->code);/ 阻塞進程void V(Seamphore *s, Process *p) 產品已送入緩沖區，產品/ 模擬 V操作s->value += 1;if (p->roleFlag = 1) / 生產者if (p->currentStep = 5) printf("%20s: 釋放緩沖區訪問權 !n", p-&g

33、t;name); else if (p->currentStep = 6) printf("%20s:數量增加 !n", p->name); else if (p->roleFlag = 0) /消費者if (p->currentStep = 4) printf("%20s: 釋放緩沖區訪問權 !n", p->name); else if (p->currentStep = 5) printf("%20s: 產品已取出，空緩沖區數量增加 !n", p->name);if (s->valu

34、e<= 0) wakeup(s->pcq);p->currentStep+;void produce(Process *p) / 模擬生產者進程switch (p->currentStep) case 1:/1生產產品p->data = rand()%1000;printf("%20s:生產一個產品 %d!n",p->name, p->data);p->currentStep+;break;case 2:/2申請空緩沖區P(&empty, p);break;case 3:/3申請訪問緩沖區P(&mutex, p

35、);break;case 4:/4將產品送入緩沖區push(p->data);printf("%20s:將產品 %d正送入緩沖區!n", p->name, p->data); p->currentStep+;break;case 5:/5釋放緩沖區訪問權V(&mutex, p);break;case 6:/6產品已送入緩沖區，產品數量加1V(&full, p);p->currentStep = 1;break;void consume(Process *p) / 模擬消費者進程switch (p->currentStep)

36、 case 1:/1申請從緩沖區取出產品P(&full, p);break;case 2:/2申請訪問緩沖區P(&mutex, p);break;case 3:/3從緩沖區中取出產品p->data = pop();printf("%20s:從緩沖區中正取出產品%d!n", p->name, p->data); p->currentStep+;break;case 4:/4釋放緩沖區訪問權V(&mutex, p);break;case 5:/5已從緩沖區取出一個產品，空緩沖區數量加1V(&empty, p);break;

37、case 6:/6消費產品printf("%20s: 消費產品 %d!n", p->name, p->data);p->currentStep = 1;break;void rr() Process *p;while(1) / 模擬進程調度p = &processrand()%processNum;/ 隨機選取進程集合內某一進程if (!p->currentState) /選取的進程若為阻塞態， 重新選取其它可執行進程continue;if (p->roleFlag) /1:生產者0: 消費者produce(p); else consu

38、me(p);Sleep(100);void deal() printf("tt生產者消費者算法模擬nn");initProcess();rr();int main () deal();return 0;運行結果及分析1. 運行結果程序經編譯運行后，輸出如下結果：生產者消費者算法模擬消費者 2:無產品可取 ,該進程被阻塞 !生產者 3:生產一個產品 344!生產者 3:申請空緩沖區成功 !生產者 1:生產一個產品 723!生產者 1:申請空緩沖區成功 !生產者 3:申請訪問緩沖區成功 !生產者 3:將產品 344 正送入緩沖區 !生產者 3:釋放緩沖區訪問權 !生產者 1:申

39、請訪問緩沖區成功 !生產者 1:將產品 723 正送入緩沖區 !生產者 3:產品已送入緩沖區，產品數量增加 !消費者 2:該進程被喚醒 ! 申請取產品 344 成功 !消費者 4:無產品可取 ,該進程被阻塞 !生產者 1:釋放緩沖區訪問權 !消費者 2:申請訪問緩沖區成功 !消費者 2:從緩沖區中正取出產品 723!生產者 3:生產一個產品 924!消費者 2:釋放緩沖區訪問權 !生產者 1:產品已送入緩沖區，產品數量增加 !消費者 4:該進程被喚醒 ! 申請取產品 723 成功 !生產者 1:生產一個產品 510!生產者 1:無空緩沖區 ,該進程被阻塞 !消費者 2:產品已取出，空緩沖區數量增加 !生產者 1:該進程被喚醒 ! 申請空緩沖區成功 !生產者 1:申請訪問緩沖區成功 !消費者 4: 其他進程正在訪問緩沖區 , 該進程被阻塞 !生產者 3:無空緩沖區 ,該進程被阻塞 !生產者 1:將產品 510 正送入緩沖區 !生產者 1:釋放緩沖區訪問權 !消費者