生产者消费者问题模拟实现zWord文件下载.docx
《生产者消费者问题模拟实现zWord文件下载.docx》由会员分享，可在线阅读，更多相关《生产者消费者问题模拟实现zWord文件下载.docx（26页珍藏版）》请在冰点文库上搜索。
一个进程在某一关键点上被迫停止直至接收到对应的特殊变量值，通过这一措施任何复杂的进程交互要求均可得到满足，这种特殊变量就是信号量（semaphore）。
为了通过信号量传送信号，进程可利用P和V两个特殊操作来发送和接收信号，如果协作进程的相应信号仍未到达，则进程被挂起直至信号到达为止。
在操作系统中用信号量表示物理资源的实体，它是一个与队列有关的整型变量。
具体实现时，信号量是一种变量类型，用一个记录型数据结构表示，有两个分量：
一个是信号量的值，另一个是信号量队列的指针。
信号量在操作系统中主要用于封锁临界区、进程同步及维护资源计数。
除了赋初值之外，信号量仅能由同步原语PV对其操作，不存在其他方法可以检查或操作信号量，PV操作的不可分割性确保执行的原子性及信号量值的完整性。
利用信号量和PV操作即可解决并发进程竞争问题，又可解决并发进程协作问题。
信号量按其用途可分为两种：
公用信号量，联系一组并发进程，相关进程均可在此信号量上执行PV操作，用于实现进程互斥；
私有信号量，联系一组并发进程，仅允许此信号量所拥有的进程执行P操作，而其他相关进程可在其上执行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的阻塞队列中。
（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表示可以使用产品的数目，初值为０。
缓冲区是一个临界资源，必须互斥使用，所以另外还需要设置一个互斥信号量mutex，其初值为１。
用信号量机制解决生产者—消费者问题可描述如下：
itemB[k];
semaphoreempty;
empty=k;
//可以使用的空缓冲区数
semaphorefull;
full=0;
//缓冲区内可以使用的产品数
mutex=1;
//互斥信号量
intin=0;
//放入缓冲区指针
intout=0;
//取出缓冲区指针
processproducer_i（）processconsumer（）
{{
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];
//进程名
introleFlag;
//进程类型（1：
生产者0:
消费者）
intcurrentState;
//进程状态（1:
可运行态0:
阻塞态）
intcurrentStep;
//断点
intdata;
//临时数据
intcode;
//进程编号
}Process;
（2）程序中应指定缓冲区的数目，进程总个数等，现考虑共有4个生产者和消费者进程，缓冲区数目是两个，定义如下所示：
#definedataBufferSize2//缓冲区数目
#defineprocessNum4//进程数量（生产者、消费者进程总数目）
structDataBuffer//缓冲区
{
intbuffer[dataBufferSize];
intcount;
//当前产品数量
}dataBuffer;
（3）为解决生产者-消费者问题需设两个同步信号量：
信号量empty表示可用的空缓冲区的数目，初值为缓冲区数目；
信号量定义和说明如下所示：
typedefstructSeamphore//信号量
{
intvalue;
int*pcq;
//信号量队列指针
}Seamphore;
intproducerCongestionQueue[processNum];
//等待信号量empty的阻塞队列
intconsumerCongestionQueue[processNum];
//等待信号量full的阻塞队列
intshareCongestionQueue[processNum];
//等待信号量mutex的阻塞队列
Seamphoreempty={dataBufferSize,producerCongestionQueue};
Seamphorefull={0,consumerCongestionQueue};
Seamphoremutex={1,shareCongestionQueue};
（4）为模拟多个生产者和多个消费者进程并发执行的过程，首先根据进程总个数产生若干生产者和若干消费者进程，然后随机调度一个处于就绪态的进程，判断是生产者还是消费者，然后执行不同的代码，为模拟并发执行，进程每执行一步操作就中断执行，再调度其他进程运行，在被中断进程的PCB中记录了中断的位置，等到下次被调度执行时则从此位置继续执行。
（5）生产者进程执行时分为6步，如下所示：
voidproduce（Process*p）//生产者进程执行代码
switch（p->
currentStep）{
case1:
//1生产产品
p->
data=rand（）%1000;
printf（"
%20s:
生产一个产品%d!
\n"
p->
name,p->
data）;
currentStep++;
break;
case2:
//2申请空缓冲区
P（&
empty,p）;
case3:
//3申请访问缓冲区
mutex,p）;
case4:
//4将产品送入缓冲区
push（p->
将产品%d正送入缓冲区!
case5:
//5释放缓冲区访问权
V（&
case6:
//6产品已送入缓冲区，产品数量加1
full,p）;
currentStep=1;
}
（6）消费者进程执行时也分为6步，如下所示：
voidconsume（Process*p）//消费者进程执行代码
//1申请从缓冲区取出产品
//2申请访问缓冲区
//3从缓冲区中取出产品
data=pop（）;
从缓冲区中正取出产品%d!
//4释放缓冲区访问权
//5已从缓冲区取出一个产品，空缓冲区数量加1
//6消费产品
消费产品%d!
（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"
time.h"
stdlib.h"
string.h"
windows.h"
#defineprocessNum4//进程数量（生产者、消费者进程总数目）
int*pcq;
//empty：
空缓冲区数目
//full：
缓冲区内可用的产品
//mutex：
互斥信号量
typedefstructProcess//进程PCB
//进程名
//进程类型（1:
生产者0:
就绪态0:
Processprocess[processNum];
//进程集合
voidmoveDataForward（）
inti;
for（i=0;
i<
dataBuffer.count;
i++）
dataBuffer.buffer[i]=dataBuffer.buffer[i+1];
voidpush（intdata）//产品送入缓冲区
dataBuffer.buffer[dataBuffer.count++]=data;
intpop（）//从缓冲区取出产品
{
intdata=dataBuffer.buffer[0];
dataBuffer.count--;
moveDataForward（）;
returndata;
voidinitProcess（）{//初始化进程集合
chardigitTemp[5];
srand（time（NULL））;
processNum;
i++）{
process[i].roleFlag=rand（）%2;
//随机指定当前进程为生产者或消费者
if（process[i].roleFlag）
strcpy（process[i].name,"
生产者"
）;
else
消费者"
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（"
该进程被唤醒!
申请空缓冲区成功!
process[code].name）;
}elseif（process[code].currentStep==3）{
申请访问缓冲区成功!
}
}elseif（process[code].roleFlag==0）{//消费者
if（process[code].currentStep==1）{
process[code].data=pop（）;
申请取产品%d成功!
process[code].name,process[code].data）;
}elseif（process[code].currentStep==2）{
}
process[code].currentStep++;
for（inti=1;
（i<
processNum）&
&
（pcq[i]!
=0）;
i++）{//删除队首进程
pcq[i-1]=pcq[i];
if（pcq[i-1]>
processNum）{
pcq[i-1]=0;
pcq[i-1]=0;
voidsleep（intpcq[],intcode）{//阻塞进程
process[code-1].currentState=0;
//进程置为阻塞态
if（!
pcq[i]）{
pcq[i]=code;
voidP（Seamphore*s,Process*p）{//模拟P操作
s->
value-=1;
if（s->
value>
=0）{
if（p->
roleFlag==1）{//生产者
if（p->
currentStep==2）{
申请空缓冲区成功!
name）;
}elsei
升级会员 