生产者消费者问题模拟实现(z)

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 个单位的缓冲区。现要求用高级语言编写一个程序， 模拟多个生产者进程和多个消费者进程并发执行的过程，并采用信号量机制与 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:释放缓冲区访问权 !消费者