生产者消费者问题模拟实现

1、生产者消费者问题模拟实现(z)生产者-消费者实验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、故又称有界缓冲问题。生产者不断生成产品，只要缓冲区未满,生产者进程pi所生产的产品就可投入缓冲区；类似的，只要缓冲区非空，消费者进程cj就可以从缓冲区取走并消耗产品。生首生产者生产者图3.1生产者一消费者问题示意图著名的生产者一消费者问题(producer-consumerproblem)是计算机操作系统中并发进程内在关系的一种抽象，是典型的进程同步问题。在操作系统中，生产者进程可以是计算进程、发送进程，而消费者进程可以是打印进程、接收进程等，解决好生产者一消费者问题就解决了一类并发进程的同步问题。操作系统实现进程同步的机制称为同步机制，它通常由同步原语组成。不同的同步机制采用不同的同步方法，

4、迄今已设计出多种同步机制，本实验采用最常用的同步机制：信号量及PV操作。1.1.3信号量与PV操作1965年，荷兰计算机科学家E.W.Dijkstra提出新的同步工具一一信号量和PV操作，他将交通管制中多种颜色的信号灯管理方法引入操作系统，让多个进程通过特殊变量展开交互。一个进程在某一关键点上被迫停止直至接收到对应的特殊变量值，通过这一措施任何复杂的进程交互要求均可得到满足，这种特殊变量就是信号量(semaphore)。为了通过信号量传送信号，进程可利用P和V两个特殊操作来发送和接收信号，如果协作进程的相应信号仍未到达，则进程被挂起直至信号到达为止。在操作系统中用信号量表示物理资源的实体，它是

5、一个与队列有关的整型变量。具体实现时，信号量是一种变量类型，用一个记录型数据结构表示，有两个分量：一个是信号量的值，另一个是信号量队列的指针。信号量在操作系统中主要用于封锁临界区、进程同步及维护资源计数。除了赋初值之外，信号量仅能由同步原语PV对其操作，不存在其他方法可以检查或操作信号量，PV操作的不可分割性确保执行的原子性及信号量值的完整性。利用信号量和PV操作即可解决并发进程竞争问题，又可解决并发进程协作问题。信号量按其用途可分为两种：公用信号量，联系一组并发进程，相关进程均可在此信号量上执行PV操作，用于实现进程互斥；私有信号量，联系一组并发进程，仅允许此信号量所拥有的进程执行P操作，而

6、其他相关进程可在其上执行V操作，初值往往为0或正整数，多用于并发进程同步。信号量的定义为如下数据结构：typedefstructsemaphore信号量的值信号量队列的指intvalue;/structpcb*list;/针信号量说明：semaphores;P、V操作原语描述如下：(1) P(s):s.value-;若s.value>0,则执行P(s)的进程继续执行；若s.value<0,则执行P(s)的进程被阻塞，并把它插入到等待信号量s的阻塞队列中。V(s):s.value+;若s.value<0,则执行V(s)的进程从等待信号量s的阻塞队列中唤醒头一个进程，然后自己继续

7、执行。若s.value>0)则执行V的进程继续执行；1.1.4信号量实现互斥信号量和PV操作可用来解决进程互斥问题。为使多个进程能互斥地访问某临界资源，只需为该资源设置一互斥信号量mutex,并置初值为1,然后将各进程访问该资源的临界区置于P(mutex)和V(mutex)操作之间即可。用信号量和PV操作管理并发进程互斥进入临界区的一般形式为：semaphoremutex;mutex=1;cobeginprocessPi()/*i=1,2,)n*/P(mutex);/*临界区*/V(mutex);coend当有进程在临界区中时)mutex的值为0或负值，否则mutex值为1,因为只有一个

8、进程，可用P操作把mutex减至0,故可保证互斥操作，这时试图进入临界区的其它进程会因执行P(mutex)而被迫等待。mutex的取值范围是1-(n-1),表明有一个进程在临界区内执行，最多有n-1个进程在信号量队列中等待。1.1.5信号量解决生产者一消费者问题信号量和PV操作不仅可以解决进程互斥问题，而且是实现进程同步的有力工具。在协作进程之间，一个进程的执行依赖于协作进程的信息或消息，在尚未得到来自协作进程的信号或消息时等待，直至信号或消息到达时才被唤醒。生产者一消费者问题是典型的进程同步问题，对于生产者进程：生产一个产品，当要送入缓冲区时，要检查是否有空缓冲区，若有，则可将产品送入缓冲区

9、，并通知消费者进程；否则，等待；对于消费者进程：当它去取产品时，要看缓冲区中是否有产品可取，若有则取走一个产品，并通知生产者进程，否则，等待。这种相互等待，并互通信息就是典型的进程同步。因此应该设两个同步信号量：信号量empty表示可用的空缓冲区的数目，初值为k;信号量full表示可以使用产品的数目，初值为0。缓冲区是一个临界资源，必须互斥使用，所以另外还需要设置一个互斥信号量mutex,其初值为1。用信号量机制解决生产者一消费者问题可描述如下：itemBk;semaphoreempty;empty=k;/可以使用的空缓冲区数semaphorefull;full=0;/缓冲区内可以使用的产品数

10、semaphoremutex;mutex=1;/互斥信号量intin=0;/放入缓冲区指针intout=0;/取出缓冲区指针cobeginprocessproducer_i()processconsumer。While(true)While(true)produce。；P(full);P(empty);P(mutex);P(mutex);takefromBout;appendtoBin;out=(out+1)%k;in=(in+1)%k;V(mutex);V(mutex);V(empty);V(full);consume。;Coend程序中的P(mutex)和V(mutex)必须成对出现，夹在

11、两者之间的代码段是临界区；施加于信号量empty和full上的PV操作也必须成对出现，但分别位于不同的程序中。在生产者消费者问题中，P操作的次序是很重要的，如果把生产者进程中的两个P操作交换次序，那么，当缓冲区中存满k件产品时，生产者又生产一件产品，在它欲向缓冲区存放时，将在P(empty)上等待,由于此时mutex=0,它已经占有缓冲区，这时消费者预取产品时将停留在P(mutex)上而得不到使用缓冲区的权力。这就导致生产者等待消费者取走产品，而消费者却在等待生产者释放缓冲区的占有权，这种互相之间的等待永远不可能结束。所以，在使用信号量和PV操作实现进程同步时，特别要当心P操作的次序，而V操作

12、的次序无关紧要。一般来说，用于互斥的信号量上的P操作总是在后面执行。1.2生产者消费者问题模拟实现1.2.1 实验内容考虑一个系统中有n个进程，其中部分进程为生产者进程，部分进程为消费者进程，共享具有k个单位的缓冲区。现要求用高级语言编写一个程序，模拟多个生产者进程和多个消费者进程并发执行的过程，并采用信号量机制与P、V操作实现生产者进程和消费者进程间同步以及对缓冲区的互斥访问。利用信号量机制解决此问题的算法见3.2.4所示。1.2.2 实验指导1.设计提示（1）本实验并不需要真正创建生产者和消费者进程，每个进程用一个进程控制块（PCB表示。PCBa据结构如下：typedefstructPro

13、cess/进程PCBcharname10;进程名introleFlag;/进程类型（1:生产者0:消费者）intcurrentstate;/进程状态(1:可运行态0:阻塞态)intcurrentstep;/断点intdata;/临时数据intcode;/进程编号Process;(2)程序中应指定缓冲区的数目，进程总个数等，现考虑共有4个生产者和消费者进程,/缓冲区/进程数量缓冲区缓冲区数目是两个，定义如下所示:#definedataBufferSize2数目#defineprocessNum4（生产者、消费者进程总数目）structDataBuffer/intbufferdataBufferS

14、ize;intcount;/当前产品数量dataBuffer;(3)为解决生产者-消费者问题需设两个同步信号量：信号量empty表示可用的空缓冲区的数目，初值为缓冲区数目；信号量full表示可以使用产品的数目，初值为0。缓冲区是一个临界资源，必须互斥使用，所以另外还需要设置一个互斥信号量mutex,其初值为1。信号量定义和说明如下所示：typedefstructSeamphore/信号量intvalue;/信号量的值int*pcq;/信号量队列指针Seamphore;intproducerCongestionQueueprocessNum;/等待信号量empty的阻塞队列intconsumer

15、CongestionQueueprocessNum;/等待信号量full的阻塞队列intshareCongestionQueueprocessNum;/等待信号量mutex的阻塞队列Seamphoreempty=dataBufferSize,producerCongestionQueue;Seamphorefull=0,consumerCongestionQueue;Seamphoremutex=1,shareCongestionQueue;(4)为模拟多个生产者和多个消费者进程并发执行的过程，首先根据进程总个数产生若干生产者和若干消费者进程，然后随机调度一个处于就绪态的进程，判断是生产者还是

16、消费者，然后执行不同的代码，为模拟并发执行，进程每执行一步操作就中断执行，再调度其他进程运行，在被中断进程的PCB中记录了中断的位置，等到下次被调度执行时则从此位置继续执行。(5)生产者进程执行时分为6步，如下所示：voidproduce(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

17、(&empty,p);break;case 3: 3申请访问缓冲区P(&mutex,p);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;(6)消费者进程执行时也分为6步，

18、如下所示：voidconsume(Process*p)/消费者进程执行代码switch(p->currentStep)case1:/1申请从缓冲区取出产品P(&full,p);break;case2:/2申请访问缓冲区P(&mutex,p);/3break;case 3:从缓冲区中取出产品p->data=pop();printf("%20s:从缓冲区中正取出产品d!n",p->name,p->data);p->currentStep+;break;case 4: /4释放缓冲区访问权V(&mutex,p);break;c

19、ase 5: /5已从缓冲区取出一个产品，空缓冲区数量加1V(&empty,p);break;case 6: /6消费产品printf("%20s:消费产品%d!n",p->name,p->data);p->currentStep=1;break;(6)为对生产者进程和消费者进程并发执行的过程进行分析，理解信号量和P、V操作在进程同步和互斥机制中的运用，要求进程每执行一步都输出每一步的执行情况。2.程序流程图(1)程序流程图如图3.2所示：开始1 J初始化缓冲区和信号量图3.2程序流程图(2)生产者进程和消费者进程执行时各有6步操作，执行一个操作后

20、会被中断，下次再被调度执行时接着执行下一操作。生产者进程流程图如图3.3所示，消费者进程流程图如图3.4所示。（开始图2.2生产者进程流程图图2.3消费者进程流程图1.2.3程序示例#include"stdio.h"#include"time.h"#include"stdlib.h"#include"string.h"/缓冲区数目/进程数量（生产/信号#include"windows.h"#definedataBufferSize2#defineprocessNum4者、消费者进程总数目）typ

21、edefstructSeamphore量intvalue;/信号量的值int*pcq;/信号量队列指针Seamphore;intproducerCongestionQueueprocessNum;/等待信号量empty的阻塞队列intconsumerCongestionQueueprocessNum;/等待信号量full的阻塞队列intshareCongestionQueueprocessNum;/等待信号量mutex的阻塞队列Seamphoreempty=dataBufferSize,producerCongestionQueue;/empty:空缓冲区数目Seamphorefull=0,c

22、onsumerCongestionQueue;/full:缓冲区内可用的产品Seamphoremutex=1,shareCongestionQueue;/mutex:互斥信号量structDataBuffer/缓冲区intbufferdataBufferSize;intcount;/当前产品数量dataBuffer;typedef struct Process/进程PCBchar name10;int roleFlag;生产者0: 消费者)int currentState;就绪态0:阻塞态) int currentStep;int data;int code;/进程名/ 进程类型（1:/进程状

23、态（1:/断点/临时数据/进程编号Process;ProcessprocessprocessNum;/进程集合voidmoveDataForward()inti;for(i=0;i<dataBuffer.count;i+)dataBuffer.bufferi=dataBuffer.bufferi+1;voidpush(intdata)/产品送入缓冲区dataBuffer.bufferdataBuffer.count+=data;intpop()/从缓冲区取出产品intdata=dataBuffer.buffer0;dataBuffer.count-;moveDataForward();r

24、eturndata;voidinitProcess()/初始化进程集合inti;chardigitTemp5;srand(time(NULL);for(i=0;i<processNum;i+)processi.roleFlag=rand()%2;/随机指定当前进程为生产者或消费者生产者);消费者");if(processi.roleFlag)strcpy(,"elsestrcpy(,"strcat(,itoa(i+1,digitTemp,10);processi.currentSt

25、ate=1;processi.currentStep=1;processi.code=i+1;producerCongestionQueuei=0;consumerCongestionQueuei=0;shareCongestionQueuei=0;voidwakeup(int*pcq)/唤醒进程int code = pcq0 - 1;/取出队首进程processcode.currentState=1;/进程置为就绪态/当进程被唤醒后继续执行任务if(processcode.roleFlag=1)/生产者if(processcode.currentStep=2)printf("%20

26、s:该进程被唤醒！申请空缓冲区成功！n”,);elseif(processcode.currentStep=3)printf("%20s:该进程被唤醒！申请访问缓冲区成功！n”,);elseif(processcode.roleFlag=0)/消费者if(processcode.currentStep=1)processcode.data=pop();printf("%20s:该进程被唤醒！申请取产品d成功!n",,processcode.data);elseif(pr

27、ocesscode.currentStep=2)printf("%20s:该进程被唤醒！申请访问缓冲区成功！n”,);processcode.currentStep+;for(inti=1;(i<processNum)&&(pcqi!=0);i+)/删除队首进程pcqi-1=pcqi;if(pcqi-1>processNum)pcqi-1=0;pcqi-1=0;voidsleep(intpcq,intcode)阻塞进程inti;processcode-1.currentState=0;/进程置为阻塞态for(i=0;i<

28、;processNum;i+)if(!pcqi)pcqi=code;break;voidP(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);elseif(p->currentStep=3)printf("%20s:申请访问缓冲区成功!n",p->name);elseif(p->roleFlag

29、=0)/消费者if(p->currentStep=1)printf("%20s:申请取出产品成功!n",p->name);elseif(p->currentStep=2)printf("%20s:申请访问缓冲区成功!n",p->name);p->currentStep+;/下一步elseif(s->value<0)if(p->roleFlag=1)/生产者if(p->currentStep=2)printf("%20s:无空缓冲区,该进程被阻塞!n",p->name);els

30、eif(p->currentStep=3)printf("%20s:其他进程正在访问缓冲区，该进程被阻塞!n",p->name);elseif(p->roleFlag=0)/消费者if(p->currentStep=1)printf("%20s:无产品可取,该进程被阻塞!n",p->name);elseif(p->currentStep=2)printf("%20s:其他进程正在访问缓冲区，该进程被阻塞!n",p->name);/阻塞进sleep(s->pcq,p->code);程

31、voidV(Seamphore*s,Process*p)/模拟V操作s->value+=1;if(p->roleFlag=1)生产者if(p->currentStep=5)printf("%20s:释放缓冲区访问权!n",p->name);elseif(p->currentStep=6)printf("%20s:产品已送入缓冲区)产品数量增加!n",p->name);elseif(p->roleFlag=0)/消费者if(p->currentStep=4)printf("%20s:释放缓冲区访问权

32、!n",p->name);elseif(p->currentStep=5)printf("%20s:产品已取出，空缓冲区数量增加!n",p->name);if(s->value<=0)wakeup(s->pcq);p->currentStep+;voidproduce(Process*p)/模拟生产者进程switch(p->currentStep)case 1:/1生产产品p->data=rand()%1000;printf("%20s:生产一个产品d!n",p->name,p->

33、;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:将产品d正送入缓冲区!n",p->name,p->data);p->currentStep+;break;case 5:/5释放缓冲区访问权V(&mutex,p);break;case 6:/6产品已送入缓冲区，产品数量加1V(&full

34、,p);p->currentStep=1;break;voidconsume(Process*p)/模拟消费者进程switch(p->currentStep)case 1:/1申请从缓冲区取出产品P(&full,p)；break;case 2:/2申请访问缓冲区P(&mutex,p);break;case 3:/3从缓冲区中取出产品p->data=pop();printf("%20s:从缓冲区中正取出产m%d!n",p->name,p->data);p->currentStep+;break;case 4:/4释放缓冲区访

35、问权V(&mutex,p);break;case 5: 5已从缓冲区取出一个产品，空缓冲区数量加1V(&empty,p);break;case 6:/6消费产品printf("%20s:消费产品%d!n",p->name,p->data);p->currentStep=1;break;voidrr()/模拟进程调度Process*p;while(1)p=&processrand()%processNum;/随机选取进程集合内某一进程if(!p->currentState)/选取的进程若为阻塞态，重新选取其它可执行进contin

36、ue;if(p->roleFlag)0：消费者produce(p);elseconsume(p);Sleep(100);/1: 生产者voiddeal()printf("tt生产者消费者算法模拟nn");initProcess();rr()；intmain()deal();return0;1.2.4运行结果及分析1 .运行结果程序经编译运行后，输出如下结果：生产者消费者算法模拟消费者2:无产品可取，该进程被阻塞！生产者3:生产一个产品344!生产者3:申请空缓冲区成功！生产者1:生产一个产品723!生产者1:申请空缓冲区成功！生产者3:申请访问缓冲区成功生产者3:将产

37、品344正送入缓冲区！生产者3:释放缓冲区访问权！生产者1:申请访问缓冲区成功生产者1:将产品723正送入缓冲区！生产者3:产品已送入缓冲区，产品数量增加！消费者2:该进程被唤醒！申请取产品344成功！消费者4:无产品可取,该进程被阻塞！生产者1:释放缓冲区访问权！消费者2:申请访问缓冲区成功！消费者2:从缓冲区中正取出产品723！生产者3:生产一个产品924！消费者2:释放缓冲区访问权！生产者1:产品已送入缓冲区，产品数量增加！消费者4:该进程被唤醒！申请取产品723成功！生产者1:生产一个产品510！生产者1:无空缓冲区，该进程被阻塞！消费者2:产品已取出，空缓冲区数量增加！生产者1:该进程被唤醒！申请空缓冲区成功！生产