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

《生产者消费者问题模拟实现(z)》由会员分享，可在线阅读，更多相关《生产者消费者问题模拟实现(z)（19页珍藏版）》请在金锄头文库上搜索。

1、生产者生产者- -消费者实验消费者实验1.11.1 实验目的和要求实验目的和要求实验目的实验目的操作系统的基本控制和管理控制都围绕着进程展开， 其中的复杂性是由于支持并发和并发机制而引起的。自从操作系统中引入并发程序设计后， 程序的执行不再是顺序的， 一个程序未执行完而另一个程序便已开始执行， 程序外部的顺序特性消失， 程序与计算不再一一对应。并发进程可能是无关的，也可能是交互的。然而，交互的进程共享某些变量，一个进程的执行可能会影响其他进程的执行结果， 交互的并发进程之间具有制约关系、 同步关系。其中典型模型便是生产者-消费者模型。本实验通过编写和调试生产者-消费者模拟程序，进一步认识进程并

2、发执行的实质，加深对进程竞争关系，协作关系的理解，掌握使用信号量机制与P、V 操作来实现进程的同步与互斥。实验要求实验要求1用高级语言编写一个程序，模拟多个生产者进程和多个消费者进程并发执行，并采用信号量机制与 P、V 操作实现进程间同步与互斥。2撰写实验报告，报告应包含以下内容：（1）实验目的；（2）实验内容；（3）设计思路；（4）程序流程图；（5）程序中主要数据结构和函数说明；（6）带注释的源程序代码；（7）程序运行结果及分析；（8）实验收获与体会。1.21.2 预备知识预备知识生产者消费者问题生产者消费者问题生产者消费者问题表述如下： 如图 3.1 所示，有 n 个生产者和 m 个消费者

3、，连接在具有 k 个单位缓冲区的有界环状缓冲上， 故又称有界缓冲问题。生产者不断生成产品，只要缓冲区未满，生产者进程 pi 所生产的产品就可投入缓冲区；类似的，只要缓冲区非空，消费者进程 cj 就可以从缓冲区取走并消耗产品。图 3.1 生产者消费者问题示意图著名的生产者消费者问题producer-consumer problem是电脑操作系统中并发进程内在关系的一种抽象， 是典型的进程同步问题。 在操作系统中， 生产者进程可以是计算进程、发送进程，而消费者进程可以是打印进程、 接收进程等，解决好生产者消费者问题就解决了一类并发进程的同步问题。操作系统实现进程同步的机制称为同步机制， 它通常由同

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

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

6、 PV 操作，用于实现进程互斥；私有信号量，联系一组并发进程，仅允许此信号量所拥有的进程执行 P 操作， 而其他相关进程可在其上执行V 操作， 初值往往为 0 或正整数，多用于并发进程同步。信号量的定义为如下数据结构：typedef struct semaphore信号量说明：semaphore s;P、V 操作原语描述如下：（1）P(s)：s.value-；假设 s.value0，则执行 P(s)的进程继续执行；假设s.value0 ，则执行 V(s)的进程继续执行；int value;/信号量的值struct pcb *list;/信号量队列的指针信号量实现互斥信号量实现互斥信号量和 PV

7、 操作可用来解决进程互斥问题。为使多个进程能互斥地访问某临界资源，只需为该资源设置一互斥信号量mutex，并置初值为 1，然后将各进程访问该资源的临界区置于 P(mutex)和 V(mutex)操作之间即可。用信号量和 PV 操作管理并发进程互斥进入临界区的一般形式为：semaphore mutex;mutex = 1;cobeginprocess Pi()/*i = 1,2, ，n */P(mutex);/*临界区*/V(mutex);coend当有进程在临界区中时，mutex 的值为 0 或负值，否则mutex 值为 1，因为只有一个进程，可用P 操作把 mutex减至 0，故可保证互斥操

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

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

10、用的产品数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 = (in+1)%k;V(mutex);V(mutex);V(empty);V(full);consume();Coend程序中的 P(m

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

12、远不可能结束。所以，在使用信号量和PV 操作实现进程同步时， 特别要留神 P 操作的次序， 而 V 操作的次序无关紧要。 一般来说，用于互斥的信号量上的 P 操作总是在后面执行。1.31.3 生产者消费者问题模拟实现生产者消费者问题模拟实现实验内容实验内容考虑一个系统中有 n 个进程，其中部分进程为生产者进程， 部分进程为消费者进程， 共享具有 k 个单位的缓冲区。现要求用高级语言编写一个程序， 模拟多个生产者进程和多个消费者进程并发执行的过程，并采用信号量机制与P、V 操作实现生产者进程和消费者进程间同步以及对缓冲区的互斥访问。利用信号量机制解决此问题的算法见3.2.4 所示。实验指导实验指

13、导1 设计提示1 本实验并不需要真正创建生产者和消费者进程， 每个进程用一个进程控制块 PCB表示。PCB 数据结构如下：typedef struct Process/进程 PCBchar name10;int roleFlag;int currentState;int currentStep;int data;int code;/进程名/进程类型1：生产者0: 消费者/进程状态1: 可运行态0: 阻塞态/断点/临时数据/进程编号Process;2程序中应指定缓冲区的数目，进程总个数等，现考虑共有4 个生产者和消费者进程，缓冲区数目是两个，定义如下所示：#define dataBufferSi

14、ze2#define processNum4/缓冲区数目/进程数量(生产者、消费者进程总数目)struct DataBuffer/缓冲区int bufferdataBufferSize;int count;/当前产品数量 dataBuffer;3为解决生产者-消费者问题需设两个同步信号量： 信号量 empty 表示可用的空缓冲区的数目，初值为缓冲区数目；信号量full 表示可以使用产品的数目，初值为。缓冲区是一个临界资源，必须互斥使用，所以另外还需要设置一个互斥信号量 mutex，其初值为。信号量定义和说明如下所示：typedef struct Seamphore/信号量int value;/

15、信号量的值int *pcq;/信号量队列指针 Seamphore;int producerCongestionQueueprocessNum;/等待信号量 empty 的阻塞队列int consumerCongestionQueueprocessNum;/等待信号量 full 的阻塞队列int shareCongestionQueueprocessNum;/等待信号量 mutex 的阻塞队列Seamphore empty=dataBufferSize,producerCongestionQueue;Seamphore full=0,consumerCongestionQueue;Seampho

16、re mutex=1,shareCongestionQueue;4为模拟多个生产者和多个消费者进程并发执行的过程，首先根据进程总个数产生假设干生产者和假设干消费者进程， 然后随机调度一个处于就绪态的进程， 判断是生产者还是消费者，然后执行不同的代码，为模拟并发执行，进程每执行一步操作就中断执行， 再调度其他进程运行，在被中断进程的 PCB 中记录了中断的位置，等到下次被调度执行时则从此位置继续执行。5生产者进程执行时分为6 步，如下所示：void produce(Process *p)/生产者进程执行代码switch (p-currentStep) case 1:/1 生产产品p-data =

17、 rand()%1000;printf(%20s: 生产一个产品%d!n, p-name, p-data);p-currentStep+;break;/2 申请空缓冲case 2:区冲区缓冲区访问权V(&mutex, p);break;/6 产品已送入push(p-data);printf(%20s: 将产品%d 正送入缓冲区!n, p-name, p-data);p-currentStep+;break;/5 释放缓冲区P(&mutex, p);break;/4 将产品送入P(&empty, p);break;/3 申请访问缓case 3:case 4:case 5:case 6:缓冲区，产

18、品数量加 16消费者进程执行时也分为6 步，如下所示：void consume(Process *p)/消费者进程执行代码V(&full, p);p-currentStep = 1;break;switch (p-currentStep) 品P(&full, p);break;/2 申请访问缓冲区case 1:/1 申请从缓冲区取出产case 2:P(&mutex, p);break;/3 从缓冲区中取出产品case 3:p-data = pop();printf(%20s: 从缓冲区中正取出产品%d!n, p-name, p-data);p-currentStep+;break;/4 释放缓

19、冲区访问权case 4:V(&mutex, p);break;/5 已从缓冲区取出一个产品， 空缓case 5:冲区数量加 16为对生产者进程和消费者进程并发执行的过程进行分析，理解信号量和 P、V 操作在进程同步和互斥机制中的运用，要求进程每执行一步都输出每一步的执行情况。2程序流程图1程序流程图如图 3.2 所示：V(&empty, p);break;/6 消费产品case 6:printf(%20s: 消费产品%d!n, p-name, p-data);p-currentStep = 1;break;开始初始化缓冲区和信号量创建若干生产者进程和若干消费者进程随机选取一个就绪状态进程Y该进

20、程是生产者？N生产者进程执行一步操作消费者进程执行一步操作记录中断位置图 3.2 程序流程图2生产者进程和消费者进程执行时各有6 步操作，执行一个操作后会被中断，下次再被调度执行时接着执行下一操作。生产者进程流程图如图3.3 所示，消费者进程流程图如图 3.4 所示。开始开始1：生产产品1：P(full)2：P(empty)2：P(mutex)3：P(mutex)3：从缓冲区取一个产品4：将产品送入缓冲区4：V(mutex)5：V(mutex)5：V(full)6：V(full)6：消费产品图 2.2 生产者进程流程图图 2.3 消费者进程流程图程序例如程序例如#include stdio.h

21、#include time.h#include stdlib.h#include string.h#include windows.h#define dataBufferSize2/缓冲区数目#define processNum 4/进程数量(生产者、消费者进程总数目)typedef struct Seamphore/信号量int value;/信号量的值int *pcq;/信号量队列指针 Seamphore;int producerCongestionQueueprocessNum;int consumerCongestionQueueprocessNum;/等待信号量 empty 的阻塞队

22、列/等待信号量 full 的阻塞队列int shareCongestionQueueprocessNum;/等待信号量 mutex 的阻塞队列Seamphore empty=dataBufferSize,producerCongestionQueue; / empty ：空缓冲区数目Seamphore full=0,consumerCongestionQueue;/ full：缓冲区内可用的产品Seamphore mutex=1,shareCongestionQueue;/mutex：互斥信号量struct DataBuffer/缓冲区int bufferdataBufferSize;int

23、count; dataBuffer;/当前产品数量typedef struct Process/进程 PCBchar name10;/进程名int roleFlag;/进程类型1: 生产者0: 消费者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.buffer

24、i = dataBuffer.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.role

25、Flag = rand()%2;if (processi.roleFlag)strcpy(processi.name, 生产者);elsestrcpy(processi.name, 消费者);strcat(processi.name, itoa(i+1, digitTemp, 10);processi.currentState = 1;processi.currentStep = 1;processi.code = i + 1;producerCongestionQueuei = 0;consumerCongestionQueuei = 0;shareCongestionQueuei = 0;

26、/ 随机指定当前进程为生产者或消费者void wakeup(int *pcq) /唤醒进程int code = pcq0- 1;/取出队首进程processcode.currentState = 1;/进程置为就绪态/当进程被唤醒后继续执行任务if (processcode.roleFlag = 1) /生产者if (processcode.currentStep = 2) printf(%20s: 该进程被唤醒!申请空缓冲区成功!n, processcode.name); else if (processcode.currentStep = 3) printf(%20s: 该进程被唤醒!申请

27、访问缓冲区成功!n,processcode.name); else if (processcode.roleFlag = 0) /消费者if (processcode.currentStep = 1) processcode.data = pop();printf(%20s: 该进程被唤醒!申请取产品%d 成功!n, processcode.name,processcode.data); else if (processcode.currentStep = 2) printf(%20s: 该进程被唤醒!申请访问缓冲区成功!n,processcode.name);processcode.curr

28、entStep+;for (int i = 1; (i processNum) pcqi-1 = 0;pcqi-1 = 0;void sleep(int pcq, int code) int i;processcode-1.currentState = 0;for (i = 0; i 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(%20s: 申请访问缓冲区成

29、功!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 roleFlag = 1) if (p-currentStep = 2) /下一步/生产者printf(%20s: 无空缓冲区, 该进程被阻塞!n, p-name); else if (p-currentSte

30、p = 3) printf(%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);sleep(s-pcq, p-code);/阻塞进程void V(Seamphore *s, Process *p) s-value += 1;if (p-roleFla

31、g = 1) if (p-currentStep = 5) /模拟 V 操作/生产者printf(%20s: 释放缓冲区访问权!n, p-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

32、 (s-valuepcq);p-currentStep+;void produce(Process *p) /模拟生产者进程switch (p-currentStep) case 1:产产品p-data = rand()%1000;printf(%20s: 生产一个产品%d!n, p-name, p-data);p-currentStep+;break;case 2:请空缓冲区P(&empty, p);break;case 3:请访问缓冲区P(&mutex, p);break;case 4:产品送入缓冲区push(p-data);printf(%20s: 将产品%d 正送入缓冲区!n, p-n

33、ame, p-data);p-currentStep+;break;case 5:放缓冲区访问权V(&mutex, p);break;case 6:品已送入缓冲区，产品数量加1V(&full, p);p-currentStep = 1;break;void consume(Process *p) /模拟消费者进程switch (p-currentStep) case 1:请从缓冲区取出产品P(&full, p);break;case 2:请访问缓冲区P(&mutex, p);break;case 3:/1 生/2 申/3 申/4 将/5 释/6 产/1 申/2 申/3 从缓冲区中取出产品p-d

34、ata = pop();printf(%20s: 从缓冲区中正取出产品%d!n, p-name, p-data);p-currentStep+;break;case 4:放缓冲区访问权V(&mutex, p);break;/4 释case 5:取出一个产品，空缓冲区数量加1V(&empty, p);break;/5 已从缓冲区case 6:费产品printf(%20s: 消费产品%d!n, p-name, p-data);p-currentStep = 1;break;void rr() /模拟进程调度Process *p;while(1) p = &processrand()%process

35、Num;if (!p-currentState) 它可执行进程continue;/6 消/随机选取进程集合内某一进程/选取的进程假设为阻塞态， 重新选取其if (p-roleFlag) /1: 生产者0: 消费者produce(p); else consume(p);Sleep(100);void deal() printf(tt 生产者消费者算法模拟nn);initProcess();rr();int main () deal();return 0;运行结果及分析运行结果及分析1.运行结果程序经编译运行后，输出如下结果：生产者消费者算法模拟消费者 2: 无产品可取, 该进程被阻塞!生产者 3

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

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

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

39、缓冲区成功!生产者 1: 其他进程正在访问缓冲区, 该进程被阻塞!生产者 3: 将产品 924 正送入缓冲区!消费者 2: 消费产品 723!生产者 3: 释放缓冲区访问权!生产者 1: 该进程被唤醒!申请访问缓冲区成功!生产者 1: 将产品 450 正送入缓冲区!生产者 3: 产品已送入缓冲区，产品数量增加!消费者 4: 该进程被唤醒!申请取产品 723 成功!生产者 1: 释放缓冲区访问权!生产者 1: 产品已送入缓冲区，产品数量增加!消费者 4: 申请访问缓冲区成功!消费者 4: 从缓冲区中正取出产品723!消费者 4: 释放缓冲区访问权!生产者 3: 生产一个产品 138!消费者 4:

40、 产品已取出，空缓冲区数量增加!生产者 1: 生产一个产品 881!生产者 1: 申请空缓冲区成功!生产者 3: 无空缓冲区, 该进程被阻塞!消费者 4: 消费产品 723!2简要分析在本次程序运行时，创建了两个生产者进程和两个消费者进程，生产者进程编号为 1、3，消费者进程编号为2、4。缓冲区数目是 2 个。从本次运行情况来看， 消费者 2 先请求取产品，因缓冲区内无产品， 此时消费者 2 被阻塞；生产者 3 和生产者 1 各生产一个产品，生产者 3 先将产品送入缓冲区后， 唤醒了消费者2 去取产品；此时消费者4 也请求取产品，因无产品可取而被阻塞；然后生产者1 将产品送入了缓冲区，消费者4

41、 被唤醒；生产者1 又生产了一个产品，由于此时消费者2 和消费者 4还未将产品取出，已无空缓冲区，所以生产者 1 被阻塞，只能等待； 等到消费者 2 取出产品后，生产者 1 被唤醒；但由于此时消费者4 正在缓冲区取产品， 生产者 1 由于不能访问缓冲区而被阻塞；等消费者 4 完成缓冲区操作后， 生产者 1 将产品送入缓冲区； 在消费者 4 取产品过程中，生产者 3 又生产了一件产品，由于无空缓冲区而被阻塞，等消费者4 取出产品，有空缓冲区时被唤醒生产者和消费者进程如此不断执行。从程序运行过程来看， 实现了生产者进程和消费者进程的同步， 同时也实现了各进程对缓冲区的互斥访问。假设再次运行此程序， 可以发现显示输出的结果会不同， 那是由于创建的生产者进程和消费者进程是随机创建的，另外调度进程时也是随机调度的。