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

2、進程競爭關系，協作關系的理解，掌握使用信號量機制與P、V操作來實現進程的同步與互斥。1.1.2實驗要求1 用高級語言編寫一個程序，模擬多個生產者進程和多個消費者進程并發執行，并采用信號量機制與 P、V操作實現進程間冋步與互斥。2撰寫實驗報告，報告應包含以下內容：(1)實驗目的；(2)實驗內容；(3)設計思路；(4)程序流程圖；(5)程序中主要數據結構和函數說明;(6)帶注釋的源程序代碼；(7)程序運行結果及分析；(8)實驗收獲與體會。1.2預備知識1.2.1生產者一消費者問題生產者一消費者問題表述如下： 如圖3 1所示，有n個生產者和m個消費者，連接在具有k個單位緩沖區的有界環狀緩沖上，故又稱

3、有界緩沖問題。生產者不斷生成產品，只要緩沖區未滿，生產者進程 p 1所生產的產品就可投入緩沖區 ；類似的，只要緩沖區非空，消費者進 程c j就可以從緩沖區取走并消耗產品。生產者消費者J消拔吿圖3.1生產者一消費者問題示意圖著名的生產者一消費者問題(produ c e r-c onsumer p r o blem)是計算機操作系統中 并發進程內在關系的一種抽象，是典型的進程同步問題。在操作系統中，生產者進程可以是計算進程、發送進程，而消費者進程可以是打印進程、接收進程等，解決好生產者一消費者問題就解決了一類并發進程的同步問題。操作系統實現進程同步的機制稱為同步機制，它通常由同步原語組成。不同的同

4、步機制采用不同的同步方法，迄今已設計出多種同步機制，本實驗采用最常用的同步機制：信號量 及PV操作。1.2.2信號量與PV操作1 9 65年，荷蘭計算機科學家 E.W.Dijkstra提出新的同步工具一一信號量和PV操作，他將交通管制中多種顏色的信號燈管理方法引入操作系統，讓多個進程通過特殊變量展開交互。一個進程在某一關鍵點上被迫停止直至接收到對應的特殊變量值，通過這一措施任何復雜的進程交互要求均可得到滿足，這種特殊變量就是信號量 (semapho r e)。為了通過信號量傳送信號，進程可利用P和V兩個特殊操作來發送和接收信號,如果協作進程的相應信號仍未到達，則進程被掛起直至信號到達為止。在操

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

6、組并發進程，僅允許此信號量所擁 有的進程執行 P操作，而其他相關進程可在其上執行V操作，初值往往為0或正整數，多用于并發進程同步。信號量的定義為如下數據結構：t ypede f st ruct se m ap ho re? in t valu e;/信號量的值?s tru c t pcb *l i st; / /信號量隊列的指針信號量說明： s emaphore s ;P、V操作原語描述如下：(1) P (s ): s.va lue-;若s.va lue >0 ,則執行P (s)的進程繼續執行;若s.va l u e<0,則執行P(s )的進程被阻塞，并把它插入到等待信號量s的阻塞

7、隊列中。(2) V(s) : s. value + +;若s. valu e<0，則執行V (s)的進程從等待信 號量s的阻塞隊列中喚醒頭一個進程 ，然后自己繼續執行。若 s. value>0，則執行 V( s )的進程繼續執行；1.2.3信號量實現互斥信號量和p v操作可用來解決進程互斥問題。為使多個進程能互斥地訪問某臨界資源， 只需為該資源設置一互斥信號量mutex,并置初值為1,然后將各進程訪問該資源的臨界區置于P (mu tex) 和 V(mutex)操作之間即可。用信號量和PV操作管理并發進程互斥進入臨界區的一般形式為：s em a p hor e m u te x;mu

8、tex =1 ;c obe ginproce s s P i ()/*i = 1,2,，n */?P(mu te x );?/*臨界區*/? V (m u tex);c o end當有進程在臨界區中時，mutex的值為0或負值，否則m ut e x值為1 ,因為只有一個進程，可用P操作把mutex減至0,故可保證互斥操作，這時試圖進入臨界區的其它進程會因 執行P (mutex)而被迫等待。mut ex的取值范圍是1-(n - 1),表明有一個進程在臨界區 內執行，最多有n-1個進程在信號量隊列中等待。1.2.4信號量解決生產者一消費者問題信號量和pv操作不僅可以解決進程互斥問題，而且是實現進程

9、同步的有力工具。在協作進程之間，一個進程的執行依賴于協作進程的信息或消息，在尚未得到來自協作進程的信號或消息時等待，直至信號或消息到達時才被喚醒。生產者一消費者問題是典型的進程同步問題，對于生產者進程：生產一個產品，當要送入緩沖區時，要檢查是否有空緩沖區，若有,則可將產品送入緩沖區，并通知消費者進程；否則, 等待；對于消費者進程：當它去取產品時，要看緩沖區中是否有產品可取，若有則取走一個 產品，并通知生產者進程，否則，等待。這種相互等待，并互通信息就是典型的進程同步。因此應該設兩個同步信號量：信號量emp t y表示可用的空緩沖區的數目 初值為 k；信 號量full表示可以使用產品的數目，初值

10、為0。緩沖區是一個臨界資源，必須互斥使用，所以另外還需要設置一個互斥信號量mutex，其初值為1。用信號量機制解決生產者一消費者問題可描述如下：item B k;s em ap hor e emp t y; empty= k ;/可以使用的空緩沖區數semap h or e full; fu ll = 0;/緩沖區內可以使用的產品數sema pho r e mutex; ?mu t ex=1;/ 互斥信號量int in= 0 ;?/放入緩沖區指針int o u t= 0 ;/取出緩沖區指針 cobe g inp roces s coW hile(tru e)proce s s pro d uc

11、er _ i() n su mer()W hile(true) ? prod uce(); ?P (f ull);P(emp t y);?P(mute x );P(mut e x);?t a k e f rom Bo ut ;app e nd to Bi n ;?5o ut = (ou t + 1)%k;in = (in+1)%k;x );?V (mutea bV(mu t ex) ;?V(em pty);V(fu ll); ?c onsume(); ? ?Co end程序中的P(m ut e x)和V(m u te x )必須成對出現，夾在兩者之間的代碼段是臨界區；施加于信號量e mpty和

12、f u II上的PV操作也必須成對出現，但分別位于不同的程序中。在生產者 消費者問題中,P操作的次序是很重要的，如果把生產者進程中的兩個P操作交換次序，那么,當緩沖區中存滿k件產品時，生產者又生產一件產品，在它欲向緩沖區存放時，將在P (e mpt y)上等待，由于此時 mu tex=0,它已經占有緩沖區，這時消費者預取產品時將停留在P(mute x )上而得不到使用緩沖區的權力。這就導致生產者等待消費者取走產品，而消費者 卻在等待生產者釋放緩沖區的占有權，這種互相之間的等待永遠不可能結束。所以，在使用信號量和PV操作實現進程同步時，特別要當心P操作的次序，而V操作的次序無關緊要。一 般來說，

13、用于互斥的信號量上的P操作總是在后面執行。1.3生產者消費者問題模擬實現1.3.1實驗內容考慮一個系統中有n個進程，其中部分進程為生產者進程，部分進程為消費者進程 ，共享 具有k個單位的緩沖區。現要求用高級語言編寫一個程序，模擬多個生產者進程和多個消費者進程并發執行的過 程,并采用信號量機制與 P、V操作實現生產者進程和消費者進程間同步以及對緩沖區的互斥 訪問。利用信號量機制解決此問題的算法見 3.2.4所示。1.3.2實驗指導1.設計提示(1) 本實驗并不需要真正創建生產者和消費者進程，每個進程用一個進程控制塊(PCB)表示。PCE數據結構如下：t y pedef st r uct Pro

14、ce ss/進程 PCB?ch ar name 1 0 ;?/進程名in t r o leFla g;/進程類型(1:生產者 0:消費者)?i n t currentState; ?/進程狀態(1:可運行態 0:阻塞態)?int cur r ent Ste p;?/ 斷點?i n t data;?臨時數據i n t c ode ;?/進程編號P roce ss;(2) 程序中應指定緩沖區的數目，進程總個數等，現考慮共有4個生產者和消費者進程， 緩沖區數目是兩個，定義如下所示：#de fi n e d ata Bu f fe r Si ze 2 ?/ 緩沖區數目#def i ne pr o c

15、essN um 4? ?/進程數量(生產者、消費者進程總數目)st rue t Da t aBuffer/ 緩沖區?int b u f f erdat a Buf fe rSi z e;?int cou n t;? ?/當前產品數量 d a t aB u f fer;(3) 為解決生產者-消費者問題需設兩個同步信號量：信號量empt y表示可用的空緩沖區的數目，初值為緩沖區數目；信號量fu 1 l表示可以使用產品的數目，初值為0。緩沖區是一個臨界資源，必須互斥使用，所以另外還需要設置一個互斥信號量mu t ex,其初值為1。信號量定義和說明如下所示：t y p edef s t ruc t S

16、ea mph o re/ 信號量 ?i ntvalue;?/信號量的值? i nt * pcq;/信號量隊列指針 S eam p ho re;int p r oduc er Co n ge sti on Que u e p roce s s Num ;/ 等待信號量 emp t y的阻塞隊列int cons u m e rCon gesti o n Queue pr oce s sNum;? / / 等待信號量 ful 1的阻塞 隊列int s har eCon ge s tion Queue pr oc ess Num;/ 等待信號量mute x的阻塞隊列Sea mpho re empty

17、= data Buf ferSize,pr o ducer C o n ge s tio n Queu e；Seamp h or e ful l= 0, c on sumerC on ge st io n Q ueue;S eamph o re m utex= 1 ,shareC on gesti on Queue;(4) 為模擬多個生產者和多個消費者進程并發執行的過程，首先根據進程總個數產生若干生產者和若干消費者進程，然后隨機調度一個處于就緒態的進程，判斷是生產者還是消費者,然后執行不同的代碼，為模擬并發執行，進程每執行一步操作就中斷執行，再調度其他進程運行，在被中斷進程的PC B中記錄了中

18、斷的位置，等到下次被調度執行時則從此位置繼續執行。(5 )生產者進程執行時分為 6步，如下所示：vo id pr oduce(Proces s * p)?/生產者進程執行代碼 ? s w i t c h ( p->cu r re n tSt e p )?case1:?/1 生產產品?p->da ta = rand() %100 0;? ?p r int f ("%2 Os:生產一個產品 %d! n", p ->name, p->da t a);? p >c urrent S te p+ +;bre a k;?c ase 2: ?/2 申請空緩沖

19、區?P (&empt y , p);?bi r eak ;c ase 3: ?/3申請訪問緩沖區?P (&mutex,p)5?brea k;?c ase 4： ?/ 4 將產品送入緩沖區?p u sh (p >da ta );p rintf( " %20 s： 將產品 %d 正送入緩沖區！n", p ->name,p >data);? p - >c u r rent S tep + + ;b reak;?cas e 5:? ?/5釋放緩沖區訪問權? V (&mut ex, p );?brea k ;? 6產品已送入緩沖區，產品

20、數量加1?ca se 6:?V(&f u II,p);? p ->cur r entStep = 1;? b reak;?(6)消費者進程執行時也分為6步,如下所示：v oi d consu m e (P ro c es s * p ) ?/消費者進程執行代碼sw itch (p >current S tep) ?case 1 :?1申請從緩沖區取出產品?P (& f ull, p );? b reak;? c ase 2:?/ 2申請訪問緩沖區? P (& m u t e x, p);?br e ak;? c ase 3:? ?/3從緩沖區中取出產品?p-

21、>data = p o p ();?prin t f("%20s:從緩沖區中正取出產品 % d !n", p >n a me,? p -> c urr e ntS te p+;?b r ea k ;?case 4: ?/4 釋放緩沖區訪問權?V(&mut e x, p);?break；case 5:?5已從緩沖區取出一個產品,加1? V(&e mpt y, p );? break;?case 6 :?6？消費產品? prin t f("%20s: 消費產品 %d! n", p > name, p > d a

22、ta);?p >cur rentStep = 1;? br e ak;?(6)為對生產者進程和消費者進程并發執行的過程進行分析，理解信號量和 在進程同步和互斥機制中的運用，要求進程每執行一步都輸出每一步的執行情況。p->dat a );空緩沖區數量P、V操作2 程序流程圖(1 )程序流程圖如圖3.2所示:圖3 .2程序流程圖(2 )生產者進程和消費者進程執行時各有6步操作，執行一個操作后會被中斷，下次再被調度執行時接著執行下一操作。生產者進程流程圖如圖3.3所示，消費者進程流程圖如圖3 .4所示。圖2 .2生產者進程流程圖圖2 .3消費者進程流程圖1.3.3程序示例#incl u

23、d e "stdi o .h"# in cl u d e "time. h "#incl u de " stdlib . h"# includ e "s t ring . h "#in cl ud e "w i ndo w s. h"#d e fine dataB u ffe r Size 2/ 緩沖區數目#d ef i ne proce s sNum 4 ? /進程數量（生產者、消費者進程總數目）typ e def str u c t Seam p hore ?/信號量int value ;

24、?/信號量的值i nt *pc q ; ?/信號量隊列指針 S eampho r e;in t produc e rCo n g e s t ionQueuepr o c e ssNum;?/ 等待信號量 empty 的阻塞隊列 in t co nsum e rC on ges ti on Q ueue p roce ss N u m;/等待信號量 full 的阻塞隊列int shareCo nges t ion Qu eueprocessNum;/等待信號量mu tex 的阻塞隊列S eamp h or e emp t y= d ataBu f f e rS i ze,p roduce r

25、Con g est ionQ ue u e;/ empt y：空緩沖區數目Sea mphor e ful l = 0, con sum er Con g e s tio nQueu e ;/ ful l :緩沖區內可用的產品Seamphore m u tex= 1,sh areConges t ionQu eu e;/m u t e x： 互斥信號量/ /緩沖區struct D at aBuffer ?in t buf fe r da t a B ufferSize;?/當前產品數量i nt co un t ;? d a ta Bu f fer;typed e f s t ruct Pr o

26、ce s ? c har n ame10 ;? in t ro l eFlag;int curr en?int c u r rentStep;int dat a ; ?i nt code;/進程PC B/進程名/進程類型（1:生產者 0 :消費者） ?/ /進程狀態（1 :就緒態 0 :阻塞態）/斷點臨時數據?/進程編號?State;P r ocess;Proc ess p roc e s s processN u m ;?/ 進程集合void mo v eDa taFo r w a rd () ?int i;? f or (i =0; i < data Buffer. c ou n t

27、; i+)?d ata Buffe r .b u fferi = d a taBuffer.buf v o i d pus h(in t data)/產品送入緩沖區? ?data B uffe r . bu ffer dataBuff e r.count + + = da t a;f eri+ 1 ;int p o p()/從緩沖區取出產品?int data = d ataB uff e r.b u ffer 0;? d ataB u ffe r .count -;?mo v eD a t a Fo rwa rd();?retur n data;v o id ini t Process ()?

28、 / 初始化進程集合?in t i;ch a r dig it Temp5;?s r and (time(NULL);fo r (i = 0 ; i < p r o cessNum; i + +) p r oces s i .ro 1 eFlag = ra nd ()%2;?/消費者?i f (pr o ces si. ro l e Fl ag)? s tr c py(pr o cess i .name,"生產者");elsest r cpy( p ro c essi. n ame ,"消費者");strc at (pr oc ess i .n a

29、me, i t oa( i +1, d i g it T epr o cessi. cu r rents ta te = 1;?p r oce ss i .currentSte p = 1;pr o cess i. code = i + 1;隨機指定當前進程為生產者或p,10);p r o d ucerCongest i o n Queue i =0;?con s um erConges tionQueue i = 0;?shareConge sti onQueuei = 0;?voi d wa keu p (int * p cq) ?/ 喚醒進程int code = pcq 0 -1; ?/

30、 /取出隊首進程p ro c esscod e . cu r re n tS tate = 1 ;?/ 進程置為就緒態?/當進程被喚醒后繼續執行任務?if (p r o cessc o d e. roleF 1 ag= 1)?/生產者?if (p ro c e ss co de. cur ren t St e p = = 2)?p r in t f(" %20 s:該進程被喚醒！申請空緩沖區成功！n " , p r o cess c od ); else if (proce s s cod e .currentStep = = 3) ?pri n tf(&quo

31、t;% 2 0s:該進程被喚醒！申請訪問緩沖區成功！n " , p ro c ess co d en ame);? ? else i f (p r o cessco d e. roleFI ag = 0)? / / 消費者? i f (proce s s code. cur r entS t e p = = 1)? ?pro c es s c o d e .d a t a = p op();?p r intf ("% 20s:該進程被喚醒！申請取產品d成功！ n " , pro cesscode .nam e , p roces s code . data);?

32、else i f ( pr o cesscode.curre n t St e p = 2)? printf(" % 2 0 s:該進程被喚醒！申請訪問緩沖區成功！n", pr ocesscod e . n ame);? ?p ro cessc ode.cur r ent S t ep+ +;for (int i = 1;/刪除隊首進程pcqi-1 = p cqi;(i < proce ssN um)& &( pcq i != 0); i +) ?if (pcqi-1> p r oces sNum ) pcqi -1 = 0;pcq i -1 =

33、 0;v oid sleep(intpcq , int co d e)?/ 阻塞進程?int i;? p ro c e s scode-1 .current S tate = 0;?/ 進程置為阻塞態?for ( i = 0; i v pr o ces s Num ; i +)? if (! P cq i )?pcqi= code;break;? ? ?v o i d P(Seamp hore *s, Proces s * p) ?/ 模擬 P 操作 ?s->value =1;/生產者if ( s >val ue > = 0) ? ? ?if ( p ->roleFla

34、g = 1)?if (p->current S tep =2)?printf ("%20s :申請空緩沖區成功!n" ,p->na m e);else if (p >c urrentS t e p=3) ?pr int f("%20s:申請訪問緩沖區成功！n", p_>name)? ?e ls ei f(p- > ro l e Flag = 0 ) ?/消費者? i f (p->cu r re n t S t e p = 1) ? ?pr i n t f ("%2 0s:申請取出產品成功！n", p

35、->name);? e l se if (p->currentStep = 2) ?p r in tf ("% 2 0 s:申請訪問緩沖區成功 nH,p->name);?p >cur r entStep+; ?/ 下一步? e lse if (s >value < 0)? i f (p->roleF l ag = = 1) ?/ 生產者? ?if (p- > cu rren tSt e p = 2) ?printf ("% 20 s :無空緩沖區，該進程被阻塞n ",p >name);? els e if (p

36、 >cu rre ntS tep =3 ) ?pr in tf("%20s:其他進程正在訪問緩沖區,該進程被阻塞!n", p-> name );? ? else if (p->roleFl ag = 0) ?/消費者i f (p >c u r rent Step = 1) ?pr i n tf( "%20s:無產品可取，該進程被阻塞n ",p->name); else i f (p ->cu rr e ntStep =2) ? ?pr i n tf("%20s :其他進程正在訪問緩沖區 ，該進程被阻塞!n ”

37、，p->name );? ?sleep(s-> p cq,p ->cod e);?/阻塞進程？voi d V (Seamp h o re *s , Pro ce ss *p) ?/模擬 V 操作? s >value + =1 ;?if (p->roleFl a g = 1) ?/ 生產者?if ( p->currentStep = 5)pri n tf("%20 s :釋放緩沖區訪問權!n", p->name);? else if (p ->cu r r en tStep = 6) ? prin tf (” 2 Os:產品已送

38、入緩沖區，產品數量增加！n", p > n a me);? e ls e if (p->r o le Fla g = 0) ?/ / 消費者?if (p >curr en tStep = 4) p r i ntf("%2 0 s:釋放緩沖區訪問權n ",p->name);? els e i f (p- > cur r entStep = = 5) ? prin tf("% 2 0 s :產品已取出，空緩沖區數量增加！ n ", p ->n ame);? ?i f (s->value<= 0) ?

39、w a keup(s->p cq );? ?p->cur ren tS t e p+;?v oid produ ce ( P r ocess * p ) ?/ /模擬生產者進程s witch ( p -> curr e n tSt e p) ?cas e 1 :?/1生產產品? p->data = r a n d () %1 0 00;? pr i ntf("%2 0 s： 生產一個產品 %d! n " , p->nam e , p->d a ta);? ?p->cu r ren t Ste p+ + ;? br eak ;?ca

40、se 2: ? ?/ 2申請空緩沖區?P(&empty, p );? b rea k;?case 3:?/3申請訪問緩沖區? P(&m u t e x, p);? b reak;?c ase 4:?/ 4 將產品送入緩沖區?push(p >d a ta);?pri n tf("%20s:將產品 %d正送入緩沖區!n",p->nam e , p >d ata);?p->curre ntStep+;b re ak ;?c a se 5:?#? V (&mut e x, p);? ?bre ak;case 6: ?V(&fu

41、ll, p );?p ->cu rr e? br e ak;?ntStepv oid c o nsume(Proce s s *p)s witch (p- > currentS t ep)?case 1 :?115釋放緩沖區訪問權?/6產品已送入緩沖區，產品數量加1/模擬消費者進程?/1申請從緩沖區取出產品P (&fu 11 , p);? b re ak;?case 2: ?/2申請訪問緩沖區? P(utex, p);? b reak;?case 3:?/從緩沖區中取出產品?p->data = pop();?p r?p >cu r re ntStep+;b re

42、 ak;?case 4： ? V (& mutex, p);br e ak;?case 5 :?品,空緩沖區數量加1?V (&empt y ,p);?in tf (”20s:從緩沖區中正取出產品 d!n",p->name,p->d at a );?/4釋放緩沖區訪問權/ 5已從緩沖區取出一個產b r eak;case 6 : ?p r in t f (”20s： 消費產品 %d! p->c u rre n tSt e p = 1;b r e ak;/6消費產品 n" , p - >n a m e, p -> d ata);dPr

43、ocess *p;? w hile(1) ?p = &pr oce ss rand() % p r ocessN um; ? if (!p ->c u rrentSta t e) ?程VO irr ()?/模擬進程調度/ /隨機選取進程集合內某一進程?/選取的進程若為阻塞態，重新選取其它可執行進c o nti nue;? if (p->ro 1 eFlag) /1:生產者 0:消費者?prod uce (p);? else ? ?co n sume(p);? Sleep (10 0);v o i d deal ()printf(" tt生產者消費者算法模擬nn&q

44、uot;);?ini t P roce s s();?rr ();int m a in ()d eal();? r e t urn 0;1.3.4運行結果及分析1運行結果程序經編譯運行后，輸出如下結果：生產者消費者算法模擬消費者2 :無產品可取，該進程被阻塞！生產者3:生產一個產品34 4 !生產者3:申請空緩沖區成功！生產者1 :生產一個產品 723!生產者1:申請空緩沖區成功！生產者3:申請訪問緩沖區成功！生產者3:將產品3 44正送入緩沖區！生產者3 :釋放緩沖區訪問權！生產者1 :申請訪問緩沖區成功！生產者1:將產品7 2 3正送入緩沖區！生產者3 :產品已送入緩沖區，產品數量增加！ 消費者2:該進程被喚醒！申請取產品344成功!消費者4:無產品可取，該進程被阻塞！生產者1:釋放緩沖區訪問權