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

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

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

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

6、行p操作，而其他相关进程可在其上执行v操作，初值往往为0 或正整数，多用于并发进程同步。. . 信号量的定义为如下数据结构：typedef struct semaphore int value; /信号量的值 struct pcb *list; /信号量队列的指针 信号量说明： semaphore s; p、v操作原语描述如下：（1）p(s) ：s.value-；若 s.value 0，则执行 p(s) 的进程继续执行；若s.value0 ， 则执行 v(s)的进程继续执行；1.2.3 信号量实现互斥信号量和pv操作可用来解决进程互斥问题。为使多个进程能互斥地访问某临界资源，只需为该资源设置一

7、互斥信号量mutex，并置初值为1，然后将各进程访问该资源的临界区置于 p(mutex) 和 v(mutex) 操作之间即可。用信号量和pv操作管理并发进程互斥进入临界区的一般形式为：semaphore mutex; mutex = 1; cobegin process pi() /*i = 1,2, ， n */ p(mutex); /* 临界区 */ v(mutex); coend 当有进程在临界区中时，mutex 的值为 0 或负值，否则mutex 值为 1，因为只有一个进程，可用 p操作把 mutex 减至 0，故可保证互斥操作，这时试图进入临界区的其它进程会因执行 p(mutex)

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

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

10、=0; /放入缓冲区指针int out=0; /取出缓冲区指针cobegin process 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(mutex) 和 v(mutex)

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

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

13、b数据结构如下：typedef struct process/进程 pcb char name10; / 进程名int roleflag; /进程类型（ 1：生产者 0: 消费者）int currentstate; / 进程状态（ 1: 可运行态 0: 阻塞态）int currentstep; / 断点int data; / 临时数据int code; /进程编号process; （2）程序中应指定缓冲区的数目，进程总个数等，现考虑共有4 个生产者和消费者进程，缓冲区数目是两个，定义如下所示：. . #define databuffersize 2 / 缓冲区数目#define process

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

15、nt *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-da

17、ta = 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: 将产品 %d正送入缓冲区 !n, p-name, p-data); p-currentstep+; break; case 5: /5 释放缓冲区访问权v(&am

18、p;mutex, p); break; case 6: /6 产品已送入缓冲区，产品数量加1 v(&full, p); p-currentstep = 1; break; （6）消费者进程执行时也分为6 步，如下所示：void consume(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();

19、 printf(%20s: 从缓冲区中正取出产品%d!n, p-name, p-data); p-currentstep+; break; case 4: /4 释放缓冲区访问权v(&mutex, p); break; case 5: /5 已从缓冲区取出一个产品，空缓冲区数量加1 v(&empty, p); break; case 6: /6 消费产品printf(%20s: 消费产品 %d!n, p-name, p-data); p-currentstep = 1; break; （6）为对生产者进程和消费者进程并发执行的过程进行分析，理解信号量和p、v操作在进程同步和互斥

20、机制中的运用，要求进程每执行一步都输出每一步的执行情况。2程序流程图（1）程序流程图如图3.2 所示：. . 开始该进程是生产者？生产者进程执行一步操作消费者进程执行一步操作随机选取一个就绪状态进程记录中断位置创建若干生产者进程和若干消费者进程初始化缓冲区和信号量yn图 3.2 程序流程图（2）生产者进程和消费者进程执行时各有6 步操作，执行一个操作后会被中断，下次再被调度执行时接着执行下一操作。生产者进程流程图如图3.3 所示，消费者进程流程图如图 3.4 所示。. . 开始1：生产产品2：p(empty)3：p(mutex)4：将产品送入缓冲区5：v(mutex)6：v(full)开始1：

21、p(full)2：p(mutex)3：从缓冲区取一个产品4：v(mutex)5：v(full)6：消费产品图 2.2 生产者进程流程图图 2.3 消费者进程流程图1.3.3 程序示例#include stdio.h #include time.h #include stdlib.h #include string.h #include windows.h #define databuffersize 2 / 缓冲区数目#define processnum 4 / 进程数量 ( 生产者、消费者进程总数目) typedef struct seamphore /信号量 int value; / 信号

22、量的值int *pcq; / 信号量队列指针 seamphore; int producercongestionqueueprocessnum; / 等待信号量empty 的阻塞队列int consumercongestionqueueprocessnum; / 等待信号量full的阻塞队列. . int sharecongestionqueueprocessnum; / 等待信号量mutex 的阻塞队列seamphore empty=databuffersize,producercongestionqueue; / empty：空缓冲区数目seamphore full=0,consumerc

23、ongestionqueue; / full：缓冲区内可用的产品seamphore mutex=1,sharecongestionqueue; /mutex：互斥信号量struct databuffer /缓冲区 int bufferdatabuffersize; int count; / 当前产品数量 databuffer; typedef struct process /进程 pcb char name10; / 进程名int roleflag; /进程类型（ 1: 生产者 0: 消费者）int currentstate; /进程状态（ 1: 就绪态 0: 阻塞态）int currents

24、tep; /断点int data; /临时数据int code; /进程编号process; process processprocessnum; / 进程集合void movedataforward() int i; for (i = 0; i databuffer.count; i+) databuffer.bufferi = databuffer.bufferi+1; void push(int data) /产品送入缓冲区 databuffer.bufferdatabuffer.count+ = data; int pop() /从缓冲区取出产品 int data = databuff

25、er.buffer0; databuffer.count-; movedataforward(); return data; . . void initprocess() / 初始化进程集合int i; char digittemp5; srand(time(null); for (i = 0; i processnum; i+) processi.roleflag = rand()%2; / 随机指定当前进程为生产者或消费者if (processi.roleflag) strcpy(, 生产者 ); else strcpy(, 消费者 );

26、 strcat(, itoa(i+1, digittemp, 10); processi.currentstate = 1; processi.currentstep = 1; processi.code = i + 1; producercongestionqueuei = 0; consumercongestionqueuei = 0; sharecongestionqueuei = 0; void wakeup(int *pcq) / 唤醒进程int code = pcq0 - 1; / 取出队首进程processcode.currentstate = 1; /

27、 进程置为就绪态/ 当进程被唤醒后继续执行任务if (processcode.roleflag = 1) / 生产者if (processcode.currentstep = 2) printf(%20s: 该进程被唤醒 ! 申请空缓冲区成功!n, ); else if (processcode.currentstep = 3) printf(%20s: 该进程被唤醒 ! 申请访问缓冲区成功!n, ); else if (processcode.roleflag = 0) / 消费者if (processcode.currents

28、tep = 1) processcode.data = pop(); printf(%20s: 该进程被唤醒 ! 申请取产品 %d成功 !n, , processcode.data); . . else if (processcode.currentstep = 2) printf(%20s: 该进程被唤醒 ! 申请访问缓冲区成功!n, ); processcode.currentstep+; for (int i = 1; (i processnum) pcqi-1 = 0; pcqi-1 = 0; void sleep(int

29、 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: 申请访问缓冲区成功!n, p-name); else if (p-roleflag = 0) / 消费者if (p-current

30、step = 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-currentstep = 3) printf(%20s: 其他进程正在访问缓冲区, 该进程被阻塞!n, p-n

31、ame); 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) / 模拟 v操作s-value += 1; if (p-roleflag = 1) / 生产者if (p-currentstep

32、= 5) 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 (s-valuepcq); . . p-currentstep+;

33、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); break; case 4: /4 将产品送入缓冲区push(p-data); printf(%20s: 将产品 %d正送入缓

34、冲区!n, p-name, p-data); p-currentstep+; break; case 5: /5 释放缓冲区访问权v(&mutex, p); break; case 6: /6 产品已送入缓冲区，产品数量加1 v(&full, p); p-currentstep = 1; break; void consume(process *p) / 模拟消费者进程switch (p-currentstep) case 1: /1 申请从缓冲区取出产品p(&full, p); break; . . case 2: /2 申请访问缓冲区p(&mutex, p)

35、; 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 已从缓冲区取出一个产品，空缓冲区数量加1 v(&empty, p); break; case 6: /6 消费产品printf(%20s: 消费产品 %d!n, p-name, p-data); p-currentstep = 1; break; voi

36、d rr() / 模拟进程调度process *p; while(1) p = &processrand()%processnum; / 随机选取进程集合内某一进程if (!p-currentstate) / 选取的进程若为阻塞态，重新选取其它可执行进程continue; if (p-roleflag) /1: 生产者 0: 消费者produce(p); else consume(p); sleep(100); . . void deal() printf(tt生产者消费者算法模拟nn); initprocess(); rr(); int main () deal(); return

37、0; 1.3.4 运行结果及分析1. 运行结果程序经编译运行后，输出如下结果：生产者消费者算法模拟消费者 2: 无产品可取 , 该进程被阻塞! 生产者 3: 生产一个产品344! 生产者 3: 申请空缓冲区成功! 生产者 1: 生产一个产品723! 生产者 1: 申请空缓冲区成功! 生产者 3: 申请访问缓冲区成功! 生产者 3: 将产品 344 正送入缓冲区 ! 生产者 3: 释放缓冲区访问权! 生产者 1: 申请访问缓冲区成功! 生产者 1: 将产品 723 正送入缓冲区 ! 生产者 3: 产品已送入缓冲区，产品数量增加! 消费者 2: 该进程被唤醒 ! 申请取产品344 成功 ! 消费者

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