生产者消费者问题模拟实现z.docx
- 文档编号:11576293
- 上传时间:2023-06-01
- 格式:DOCX
- 页数:27
- 大小:49.36KB
生产者消费者问题模拟实现z.docx
《生产者消费者问题模拟实现z.docx》由会员分享,可在线阅读,更多相关《生产者消费者问题模拟实现z.docx(27页珍藏版)》请在冰点文库上搜索。
生产者消费者问题模拟实现z
生产者消费者问题模拟实现(z)
————————————————————————————————作者:
————————————————————————————————日期:
生产者-消费者实验
1.1实验目的和要求
1.1.1实验目的
操作系统的基本控制和管理控制都围绕着进程展开,其中的复杂性是由于支持并发和并发机制而引起的。
自从操作系统中引入并发程序设计后,程序的执行不再是顺序的,一个程序未执行完而另一个程序便已开始执行,程序外部的顺序特性消失,程序与计算不再一一对应。
并发进程可能是无关的,也可能是交互的。
然而,交互的进程共享某些变量,一个进程的执行可能会影响其他进程的执行结果,交互的并发进程之间具有制约关系、同步关系。
其中典型模型便是生产者-消费者模型。
本实验通过编写和调试生产者-消费者模拟程序,进一步认识进程并发执行的实质,加深对进程竞争关系,协作关系的理解,掌握使用信号量机制与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个单位缓冲区的有界环状缓冲上,故又称有界缓冲问题。
生产者不断生成产品,只要缓冲区未满,生产者进程pi所生产的产品就可投入缓冲区;类似的,只要缓冲区非空,消费者进程cj就可以从缓冲区取走并消耗产品。
图3.1 生产者—消费者问题示意图
著名的生产者—消费者问题(producer-consumerproblem)是计算机操作系统中并发进程内在关系的一种抽象,是典型的进程同步问题。
在操作系统中,生产者进程可以是计算进程、发送进程,而消费者进程可以是打印进程、接收进程等,解决好生产者—消费者问题就解决了一类并发进程的同步问题。
操作系统实现进程同步的机制称为同步机制,它通常由同步原语组成。
不同的同步机制采用不同的同步方法,迄今已设计出多种同步机制,本实验采用最常用的同步机制:
信号量及PV操作。
1.2.2信号量与PV操作
1965年,荷兰计算机科学家E.W.Dijkstra提出新的同步工具——信号量和PV操作,他将交通管制中多种颜色的信号灯管理方法引入操作系统,让多个进程通过特殊变量展开交互。
一个进程在某一关键点上被迫停止直至接收到对应的特殊变量值,通过这一措施任何复杂的进程交互要求均可得到满足,这种特殊变量就是信号量(semaphore)。
为了通过信号量传送信号,进程可利用P和V两个特殊操作来发送和接收信号,如果协作进程的相应信号仍未到达,则进程被挂起直至信号到达为止。
在操作系统中用信号量表示物理资源的实体,它是一个与队列有关的整型变量。
具体实现时,信号量是一种变量类型,用一个记录型数据结构表示,有两个分量:
一个是信号量的值,另一个是信号量队列的指针。
信号量在操作系统中主要用于封锁临界区、进程同步及维护资源计数。
除了赋初值之外,信号量仅能由同步原语PV对其操作,不存在其他方法可以检查或操作信号量,PV操作的不可分割性确保执行的原子性及信号量值的完整性。
利用信号量和PV操作即可解决并发进程竞争问题,又可解决并发进程协作问题。
信号量按其用途可分为两种:
公用信号量,联系一组并发进程,相关进程均可在此信号量上执行PV操作,用于实现进程互斥;私有信号量,联系一组并发进程,仅允许此信号量所拥有的进程执行P操作,而其他相关进程可在其上执行V操作,初值往往为0或正整数,多用于并发进程同步。
信号量的定义为如下数据结构:
typedefstructsemaphore
{
ﻩintvalue; //信号量的值
ﻩstruct pcb*list;//信号量队列的指针
}
信号量说明:
semaphores;
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)的进程从等待信号量s的阻塞队列中唤醒头一个进程,然后自己继续执行。
若s.value>0,则执行V(s)的进程继续执行;
1.2.3信号量实现互斥
信号量和PV操作可用来解决进程互斥问题。
为使多个进程能互斥地访问某临界资源,只需为该资源设置一互斥信号量mutex,并置初值为1,然后将各进程访问该资源的临界区置于P(mutex)和V(mutex)操作之间即可。
用信号量和PV操作管理并发进程互斥进入临界区的一般形式为:
semaphoremutex;
mutex= 1;
cobegin
processPi()/*i=1,2, …,n*/
{
ﻩﻩP(mutex);
ﻩﻩﻩ/*临界区*/
ﻩV(mutex);
}
coend
当有进程在临界区中时,mutex的值为0或负值,否则mutex值为1,因为只有一个进程,可用P操作把mutex减至0,故可保证互斥操作,这时试图进入临界区的其它进程会因执行P(mutex)而被迫等待。
mutex的取值范围是1~-(n-1),表明有一个进程在临界区内执行,最多有n-1个进程在信号量队列中等待。
1.2.4信号量解决生产者—消费者问题
信号量和PV操作不仅可以解决进程互斥问题,而且是实现进程同步的有力工具。
在协作进程之间,一个进程的执行依赖于协作进程的信息或消息,在尚未得到来自协作进程的信号或消息时等待,直至信号或消息到达时才被唤醒。
生产者—消费者问题是典型的进程同步问题,对于生产者进程:
生产一个产品,当要送入缓冲区时,要检查是否有空缓冲区,若有,则可将产品送入缓冲区,并通知消费者进程;否则,等待;对于消费者进程:
当它去取产品时,要看缓冲区中是否有产品可取,若有则取走一个产品,并通知生产者进程,否则,等待。
这种相互等待,并互通信息就是典型的进程同步。
因此应该设两个同步信号量:
信号量empty表示可用的空缓冲区的数目,初值为k;信号量full表示可以使用产品的数目,初值为0。
缓冲区是一个临界资源,必须互斥使用,所以另外还需要设置一个互斥信号量mutex,其初值为1。
用信号量机制解决生产者—消费者问题可描述如下:
item B[k];
semaphoreempty;empty=k;//可以使用的空缓冲区数
semaphorefull;full=0; //缓冲区内可以使用的产品数
semaphoremutex;ﻩmutex=1; //互斥信号量
intin=0;ﻩﻩﻩ //放入缓冲区指针
intout=0; //取出缓冲区指针
cobegin
processproducer_i() process consumer()
{ {
While(true)ﻩ While(true) { {
produce();ﻩﻩﻩﻩ P(full);
P(empty);ﻩﻩ P(mutex);
P(mutex);ﻩﻩﻩﻩ takefromB[out];
appendtoB[in];ﻩﻩﻩ out=(out+1)%k;
in=(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(mutex)上而得不到使用缓冲区的权力。
这就导致生产者等待消费者取走产品,而消费者却在等待生产者释放缓冲区的占有权,这种互相之间的等待永远不可能结束。
所以,在使用信号量和PV操作实现进程同步时,特别要当心P操作的次序,而V操作的次序无关紧要。
一般来说,用于互斥的信号量上的P操作总是在后面执行。
1.3生产者消费者问题模拟实现
1.3.1实验内容
考虑一个系统中有n个进程,其中部分进程为生产者进程,部分进程为消费者进程,共享具有k个单位的缓冲区。
现要求用高级语言编写一个程序,模拟多个生产者进程和多个消费者进程并发执行的过程,并采用信号量机制与P、V操作实现生产者进程和消费者进程间同步以及对缓冲区的互斥访问。
利用信号量机制解决此问题的算法见3.2.4所示。
1.3.2实验指导
1.设计提示
(1)本实验并不需要真正创建生产者和消费者进程,每个进程用一个进程控制块(PCB)表示。
PCB数据结构如下:
typedefstructProcess//进程PCB
{ﻩ
charname[10];ﻩ//进程名
int roleFlag; //进程类型(1:
生产者 0:
消费者)
ﻩintcurrentState;ﻩﻩ//进程状态(1:
可运行态0:
阻塞态)
ﻩintcurrentStep;ﻩ//断点
ﻩintdata;ﻩﻩ //临时数据
intcode;ﻩ//进程编号
}Process;
(2)程序中应指定缓冲区的数目,进程总个数等,现考虑共有4个生产者和消费者进程,缓冲区数目是两个,定义如下所示:
#definedataBufferSize 2ﻩﻩ//缓冲区数目
#defineprocessNum4ﻩﻩ//进程数量(生产者、消费者进程总数目)
structDataBuffer //缓冲区
{
ﻩintbuffer[dataBufferSize];ﻩ
intcount;ﻩﻩﻩ//当前产品数量
} dataBuffer;
(3)为解决生产者-消费者问题需设两个同步信号量:
信号量empty表示可用的空缓冲区的数目,初值为缓冲区数目;信号量full表示可以使用产品的数目,初值为0。
缓冲区是一个临界资源,必须互斥使用,所以另外还需要设置一个互斥信号量mutex,其初值为1。
信号量定义和说明如下所示:
typedefstructSeamphore //信号量
{ﻩ
ﻩint value;ﻩ//信号量的值
ﻩﻩint *pcq;//信号量队列指针
}Seamphore;
int producerCongestionQueue[processNum];//等待信号量empty的阻塞队列
intconsumerCongestionQueue[processNum];ﻩ//等待信号量full的阻塞队列
intshareCongestionQueue[processNum];//等待信号量mutex的阻塞队列
Seamphore empty={dataBufferSize,producerCongestionQueue};
Seamphorefull={0,consumerCongestionQueue};
Seamphoremutex={1,shareCongestionQueue};
(4)为模拟多个生产者和多个消费者进程并发执行的过程,首先根据进程总个数产生若干生产者和若干消费者进程,然后随机调度一个处于就绪态的进程,判断是生产者还是消费者,然后执行不同的代码,为模拟并发执行,进程每执行一步操作就中断执行,再调度其他进程运行,在被中断进程的PCB中记录了中断的位置,等到下次被调度执行时则从此位置继续执行。
(5)生产者进程执行时分为6步,如下所示:
void produce(Process*p)ﻩ//生产者进程执行代码
{ﻩ
ﻩswitch (p->currentStep) {
ﻩﻩcase1:
ﻩﻩﻩ//1 生产产品
ﻩp->data=rand()%1000;
ﻩﻩprintf("%20s:
生产一个产品%d!
\n",p->name,p->data);
ﻩﻩp->currentStep++;
ﻩbreak;
ﻩcase2:
ﻩﻩﻩﻩﻩﻩﻩﻩﻩ//2 申请空缓冲区
ﻩﻩP(&empty,p);
ﻩﻩﻩbreak;
case3:
ﻩﻩﻩﻩﻩﻩﻩ//3申请访问缓冲区
ﻩP(&mutex, p);
ﻩﻩbreak;
ﻩcase 4:
ﻩﻩﻩﻩﻩﻩ//4 将产品送入缓冲区
ﻩﻩpush(p->data);
ﻩprintf("%20s:
将产品%d正送入缓冲区!
\n",p->name,p->data);
ﻩp->currentStep++;
ﻩbreak;
ﻩcase5:
ﻩﻩﻩﻩﻩﻩ//5 释放缓冲区访问权
ﻩﻩV(&mutex,p);
ﻩbreak;
ﻩcase6:
ﻩﻩﻩﻩﻩﻩ//6产品已送入缓冲区,产品数量加1
V(&full,p);
ﻩﻩp->currentStep=1;
ﻩﻩbreak;
ﻩ}
}
(6)消费者进程执行时也分为6步,如下所示:
voidconsume(Process*p)ﻩ//消费者进程执行代码
{
switch(p->currentStep){
ﻩﻩcase1:
ﻩﻩﻩ//1申请从缓冲区取出产品
ﻩﻩﻩP(&full, p);
ﻩﻩbreak;
ﻩcase2:
ﻩﻩﻩ//2申请访问缓冲区
ﻩP(&mutex,p);
ﻩﻩﻩbreak;
ﻩﻩcase3:
ﻩﻩﻩﻩﻩ//3从缓冲区中取出产品
ﻩﻩp->data=pop();
ﻩprintf("%20s:
从缓冲区中正取出产品%d!
\n",p->name,p->data);
ﻩp->currentStep++;
ﻩﻩﻩbreak;
ﻩcase4:
ﻩﻩﻩﻩ//4 释放缓冲区访问权
ﻩﻩV(&mutex, p);
ﻩbreak;
case 5:
ﻩﻩ//5已从缓冲区取出一个产品,空缓冲区数量加1
ﻩV(&empty,p);
ﻩﻩbreak;
ﻩcase6:
ﻩﻩﻩ ﻩ//6 消费产品
ﻩﻩprintf("%20s:
消费产品%d!
\n",p->name,p->data);
ﻩp->currentStep= 1;
ﻩbreak;
ﻩ}
}
(6)为对生产者进程和消费者进程并发执行的过程进行分析,理解信号量和P、V操作在进程同步和互斥机制中的运用,要求进程每执行一步都输出每一步的执行情况。
2.程序流程图
(1)程序流程图如图3.2所示:
图3.2程序流程图
(2)生产者进程和消费者进程执行时各有6步操作,执行一个操作后会被中断,下次再被调度执行时接着执行下一操作。
生产者进程流程图如图3.3所示,消费者进程流程图如图3.4所示。
图2.2生产者进程流程图 图2.3消费者进程流程图
1.3.3程序示例
#include "stdio.h"
#include "time.h"
#include"stdlib.h"
#include"string.h"
#include"windows.h"
#define dataBufferSize2//缓冲区数目
#defineprocessNum4ﻩﻩ//进程数量(生产者、消费者进程总数目)
typedefstructSeamphore //信号量
{ﻩﻩ
intvalue;ﻩﻩ//信号量的值
int *pcq;ﻩﻩ//信号量队列指针
}Seamphore;
intproducerCongestionQueue[processNum];ﻩ//等待信号量empty的阻塞队列
intconsumerCongestionQueue[processNum];//等待信号量full的阻塞队列
intshareCongestionQueue[processNum];//等待信号量mutex的阻塞队列
Seamphoreempty={dataBufferSize,producerCongestionQueue};//empty:
空缓冲区数目
Seamphorefull={0,consumerCongestionQueue}; //full:
缓冲区内可用的产品
Seamphoremutex={1,shareCongestionQueue};//mutex:
互斥信号量
structDataBuffer //缓冲区
{ﻩ
intbuffer[dataBufferSize];ﻩ
int count;ﻩﻩ//当前产品数量
}dataBuffer;
typedefstructProcess //进程PCB
{
ﻩcharname[10];ﻩ//进程名
int roleFlag;ﻩﻩ//进程类型(1:
生产者0:
消费者)
int currentState;ﻩﻩ//进程状态(1:
就绪态0:
阻塞态)
ﻩintcurrentStep;ﻩ//断点
intdata;ﻩﻩﻩ //临时数据
int code;ﻩﻩ//进程编号
}Process;
Process process[processNum];ﻩ//进程集合
voidmoveDataForward()
{ﻩ
int i;
ﻩfor(i = 0; i ﻩdataBuffer.buffer[i]= dataBuffer.buffer[i+1]; } voidpush(int data) //产品送入缓冲区 {ﻩﻩ ﻩdataBuffer.buffer[dataBuffer.count++]=data; } intpop() //从缓冲区取出产品 {ﻩﻩﻩﻩ intdata =dataBuffer.buffer[0]; ﻩdataBuffer.count--;ﻩﻩ ﻩmoveDataForward(); ﻩreturndata; } voidinitProcess(){ﻩﻩ//初始化进程集合 ﻩinti; chardigitTemp[5]; ﻩsrand(time(NULL)); for(i=0;i< processNum; i++){ process[i].roleFlag=rand()%2;ﻩ// 随机指定当前进程为生产者或消费者 ﻩif(process[i].roleFlag) ﻩﻩﻩstrcpy(process[i].name, "生产者"); else strcpy(process[i].name, "消费者"); strcat(process[i].name,itoa(i+1,digitTemp,10)); process[i].currentState =1; ﻩprocess[i].currentStep=1; process[i].code=i+1; producerCongestionQueue[i]= 0; ﻩﻩconsumerCongestionQueue[i]=0; ﻩshareCongestionQueue[i]=0; ﻩ} } voidwakeup(int*pcq) {ﻩ//唤醒进程 intcode=pcq[0]- 1;ﻩﻩﻩﻩ//取出队首进程 process[code].currentState=1;ﻩﻩ//进程置为就绪态 ﻩ//当进程被唤醒后继续执行任务 ﻩif (process[code].roleFlag ==1) {ﻩﻩ//生产者 ﻩﻩﻩif (process[code].currentStep ==2){ ﻩprintf("%20s: 该进程被唤醒! 申请空缓冲区成功! \n",process[code].name); }elseif(process[code].currentStep==3){ ﻩﻩprintf("%20s: 该进程被唤醒! 申请访问缓冲区成功! \n",process[code].name); ﻩﻩ} ﻩ}elseif(process[code].roleFlag==0) {ﻩ//消费者 ﻩif(process[code].currentStep==1){ ﻩﻩprocess[code].data=pop(); ﻩprintf("%20s: 该进程被唤醒! 申请取产品%d成功! \n",process[code].name,process[code].data); ﻩﻩ}elseif(process[code].currentStep==2){ ﻩﻩprintf("%20s: 该进程被唤醒! 申请访问缓冲区成功! \n",process[code].name); ﻩ}ﻩ ﻩ} ﻩﻩ ﻩprocess[code].currentStep++; for(inti =1; (i =0); i++){//删除队首进程 ﻩpcq[i-1]=pcq[i]; ﻩif(pcq[i-1]> processNum){ ﻩpcq[i-1]=0; } ﻩ} pcq[i-1]= 0; ﻩ } voidsleep(int pcq[],intcode){ﻩﻩ//阻塞进程 ﻩint i; ﻩprocess[code-1].currentState=0;ﻩﻩ//进程置为阻塞态 ﻩfor(i =0; i <processNum;i++){ ﻩif
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 生产者 消费者 问题 模拟 实现