第3章 进程同步与通信同步

第3章进程同步与通信●进程同步与互斥

●经典进程同步问题

●管程

●AND信号量

●进程通信本章要点进程同步的基本概念●同步：指多个进程中发生的事件存在着某种时序关系，它们必须按规定时序执行，以共同完成一项任务。●互斥：多个进程不能同时使用同一资源。●临界资源：某段时间内仅允许一个进程使用的资源。●临界区：每个进程中访问临界资源的那段代码。3信号量(semaphore)管理相应临界区的公有资源，它代表可用资源实体。4信号量是一个整型变量。≥0：可供并发进程使用的资源实体数＜0：正在等待使用临界区的进程数用于互斥的信号量初值应该大于零58.P,V原语信号量的初值只能由P,V原语操作。P:passerenV:verhoogP操作：申请资源操作sem减1若sem减1后仍大于1或等于零，则P返回，进程继续；若sem减1后小于零，则该进程阻塞转等待队列中。信号灯的PV操作voidwait(semaphores){s.value=s.value-1;if(s.value<0)block(s.queue);/*将进程阻塞，并将其投入等待队列s.queue*/}P操作7V操作：释放资源操作sem加1若sem加1后结果大于1，则V停止操作，该进程返回调用处，继续执行；若sem加1后小于或等于零，则该进程转就绪队列，同时进程调度选取一个等待队列中的进程转运行或就绪。P,V操作必须用原语实现。信号灯的PV操作voidsignal(semaphores){s.value=s.value+1;if(s.value<=0)wackup(s.queue);/*唤醒阻塞进程，将其从等待队列s.queue取出，投入就绪队列*/}V操作用信号灯解决互斥问题

semaphoremutex=1;

P1:

while(1){

P(mutex); 临界区;

V(mutex);

剩余区;

};

P2: while(1){

P(mutex); 临界区

V(mutex);

剩余区;

};10互斥进程举例1－两个进程共享一台打印机设信号量print代表打印机，初值为1.intmain(void){ intprint=1; cobegin pa();pb(); coend}pa(){ P(print);

使用打印机 V(print);}pb(){ P(print);

使用打印机 V(print);}print=1表示没有进程使用打印机print=0表示一个进程在用，没有进程等待print=-1表示一个进程在用，另一个在等待11信号量可能的取值范围假设有N个并发进程共用一台打印机，设互斥信号量mutex的初值为1，则：信号量mutex代表什么？mutex的取值范围为多少？mutex的值分别代表什么含义？12N个并发进程，互斥信号量mutex的初值为1：mutex的取值范围为：1～-(N-1)1：表示没有进程进入临界区。有一个资源，无进程等待；0：表示有1个进程进入临界区。无资源，无进程等待；-i：表示1个进程进入临界区。无资源，且有i(i<=N-1)个进程等待进入。13思考：n个并发进程，共享m个共享资源：mutex的取值范围为？互斥问题举例2[例]假设某飞机定票系统在t0时刻有A、B、C、D四个终端程序同时都要对机票库中的某航班当前剩余票数X进行操作。如果每个终端程序的当前定票需求为N，并对共享变量X进行如下操作：在机票数据库中取出当前剩余票数X；判断X>0（有票吗）？如果有，X≥N（票够吗）？如果够，则出票（打印票据）；X＝X－N（修改剩余票数）；将X回写到数据库中；1415针对临界资源机票数设置一个信号量mutex，初值为1。每个终端进程中的程序描述如下：P（mutex）；在机票数据库中取出当前剩余票数X；判断X>0（有票吗）？如果有，X≥N（票够吗）？如果够，则出票（打印票据）；X＝X－N（修改剩余票数）；将X回写到数据库中；V（mutex）；16如果有n个终端，则mutex信号量的取值范围为：

－（n－1）≤mutex≤1其物理含义为：当机票数空闲时，mutex=1。当有一个终端进入，对机票进行处理，其它终端进程还没有到来时，mutex=0。当所有终端进程都到来，且有一个正在对机票进行处理时，mutex=－（n－1）。它表示有n－1个进程在等待队列上等待。x代表某航班的可用座位数，p1和p2两个售票进程，售票工作是对变量x减1。试用信号量的P、V操作实现这两个进程的互斥。设：mutex为互斥信号量,p1() { ……

p(mutex)； ……

x:=x-1；

v(mutex)；

……

} p2() { ……

p(mutex)； ……

x:=x-1；

v(mutex)；

……

} 互斥问题举例3某车站售票厅有20个窗口，任何时刻最多可容纳20名购票者进入，当售票厅中少于20名购票者时，则厅外的购票者可立即进入，否则需在厅外等待。若把一个购票者看作一个进程，请用P、V操作管理这些并发进程，要求如下：⑴．在主函数中给出信号量的定义和初值。⑵．给出一个购票者进程的算法。⑶．给出当购票者最多不超过n(设n>20)个时，信号量可能的变化范围。18分析共享临界资源：20个同类的售票窗口先来者先进入⑴．主函数算法：main(){ intmutex=20; cobegin P1();…

Pi();…

Pn(); coend}⑵．购票者i的算法：Pi(){ P(mutex);

购票；

V(mutex);}算法描述⑶．信号量mutex的取值范围：

－(n－20)≤mutex≤20其物理含义是：当mutex=20时，表示售票厅内没有购票者进入，20个窗口都是空闲的，表示可用资源个数；当mutex=0时，表示售票厅内已经进入了20个购票者，每个窗口都被分配，没有等待的购票者，可用资源为0；当mutex=－(n－20)时，表示一共有n个购票者，其中20个购票者已经进入厅内，分别占有一个窗口，还有n－20个购票者在厅外等待，绝对值表示等待进程个数。结论：当mutex≥0时其值表示可用资源个数；当mutex＜0时其绝对值表示等待进程的个数。22思考：n个并发进程，共享m个共享资源：mutex的取值范围为？答同一类资源：m-n

≤mutex≤m不同类资源：需要m个mutex1-n

≤mutex≤1同步进程举例直接制约同步定义私用信号量PV原语实现进程同步生产者－消费者问题哲学家进餐问题241.同步进程举例1-病人就诊门诊医生：

……

开化验单；

……

等化验结果；

……

继续诊病；化验员：

……

等化验单；

……

化验；填写化验结果；

……

等待等待唤醒后唤醒后化验单化验结果继续诊病27对于医生的操作步骤：有病人时：开化验单（化验单多一个）等待化验结果（有化验结果）继续诊病28对于化验员的操作步骤：等化验单（有化验单时）进行化验

（未化验的化验单少一个）出化验结果（化验结果多一个）等待下一化验单需要两个信号量s1:表示化验结果是否出来,初值为0.s2：表示医生是否开化验单，初值为0.程序描述

main(){ints1

=0；

ints2

=1；

cobegindoctor()；test()；

coend}31对于化验员的操作步骤：test{ wait(化验单);

化验… 出化验结果… signal(有化验结果);}32对于医生的操作步骤：doctor{

给病人看病… signal(化验单); wait(化验结果);

继续诊病…}信号灯的PV操作voidwait(semaphores){s.value=s.value-1;if(s.value<0)block(s.queue);/*将进程阻塞，并将其投入等待队列s.queue*/}P操作信号灯的PV操作voidsignal(semaphores){s.value=s.value+1;if(s.value<=0)wackup(s.queue);/*唤醒阻塞进程，将其从等待队列s.queue取出，投入就绪队列*/}V操作35对于化验员的操作步骤：test{ P(s2);

化验…

出化验结果… V(s1);}36对于医生的操作步骤：doctor{

给病人看病… V(s2); P(s1);

继续诊病…}37同步进程举例2PcPpbuffer38利用过程wait和signal可简单地描述计算进程Pc和打印进程Pp的同步关系：设消息名bufempty表示buf空，消息名buffull表示buf中装满了数据。bufempty=true，buffull=false39描述：Pc: A:wait(bufempty)

计算

buf计算结果

bufemptyfalse

signal(buffull) GotoAPp: B:wait(buffull)

打印buf中的数据 清除buf中的数据

buffullfalse

signal(bufempty) GotoBwait等待合作进程发来的消息signal向合作进程发送消息40main(){ intbufempty=1,buffull=0; cobegin Pc(); Pp(); coend}41描述：Pc: A:P(bufempty)

计算

buf计算结果

V(buffull) GotoAPp: B:P(buffull)

打印buf中的数据 清除buf中的数据

V(bufempty) GotoB返回42直接制约一组在异步环境下的并发进程，各自的执行结果互为对方的执行条件，从而限制各进程的执行速度的过程称为并发进程间的直接制约。返回43同步的定义异步环境下，一组并发进程，因直接制约而互相发送消息而进行相互合作，互相等待，使得各进程按一定的速度执行的过程称为进程间同步。返回44合作进程：具有同步关系的一组并发进程称为合作进程。消息：合作进程间互相发送的信号称为消息或事件。返回45私用信号量把进程间发送的消息看作信号量，则这种信号量只与制约进程及被制约进程有关而不是整组并发进程有关(如进程互斥)，称这种信号量为私用信号量。返回互斥时使用的是公用信号量46用P,V原语操作实现同步用P,V原语操作实现进程同步的方法：为各并发进程设置私用信号量为私用信号量赋初值利用P,V原语和私用信号量规定各进程的执行顺序。返回●生产者——消费者问题●读者——写者问题●哲学家进餐问题●打磕睡的理发师问题●3.2经典进程同步问题48生产者-消费问题消费者：系统中使用某一类资源的进程称为该资源的消费者。生产者：释放同类资源的进程称为该资源的生产者。计算进程和打印进程共享缓冲区的例子中，计算进程把数据送入缓冲区，打印进程从缓冲区中取数据，则计算进程可看作数据资源的生产者，打印进程可看作是消费者。4950它们之间满足：消费者想接收数据时，有界缓冲区中至少有一个单元是满的；生产者想发送数据时，有界缓冲区中至少有一个单元是空的。生产者-消费者问题是同步关系51当有进程在写数据时（如生产者进程）则同时不允许对该缓冲区进行读操作（如消费者进程）。故有界缓冲区是临界资源，进程必须互斥访问。生产者-消费者问题同时也具有互斥关系52设信号量mutex：用于访问缓冲区时的互斥，初值是1empty：为生产者进程的私用信号量，表示有界缓冲区中的空单元数，初值为n；full：为消费者进程的私用信号量，表示缓冲区中非空单元数，初值为0。empty+full=n53consumer(data):begin P(full) P(mutex)

取缓冲区某单元数据 V(mutex)

V(empty)endproducer(data):begin P(empty) P(mutex)

送数据入缓冲区某单元 V(mutex)

V(full)end每个进程中各个P操作的次序是重要的：先检查资源数目，再检查是否互斥――否则可能死锁！分析：P操作的顺序----很重要P操作的顺序不当会产生死锁。例：假定执行顺序如下Consumer：Producer：P(empty);P(mutex);

oneunit-->buf;V(mutex);V(full);P(full);P(mutex);//进入区

oneunit<--buf;V(mutex);V(empty);//退出区分析：当full=0,mutex=1时，执行顺序：

Consumer.P(mutex);Consumer.P(full);mutex=0

//C阻塞，等待Producer发出的full信号

Producer.P(empty);Producer.P(mutex);

//P阻塞，等待Consumer发出的empty信号思考：还有其他的执行序列可以产生死锁吗？发生死锁生产者-消费者问题●指有两组进程共享一个环形的缓冲池。一组进程被称为生产者，另一组进程被称为消费者。●缓冲池是由若干个大小相等的缓冲区组成的，每个缓冲区可以容纳一个产品。●生产者进程不断地将生产的产品放入缓冲池，消费者进程不断地将产品从缓冲池中取出。用信号量解决“生产者-消费者”问题voidconsumer()//消费者进程{while(true){P(full);P(mutex);data_c=buffer[j];j=(j+1)%n;V(mutex);V(empty);consumetheitemindata_c;}}semaphoremutex=1;

semaphoreempty=n;

semaphorefull=0;inti,j;

ITEMbuffer[n];

ITEMdata_p,data_c;

voidproducer()//生产者进程{while(true){produceanitemindata_p;P(empty);P(mutex);buffer[i]=data_p;i=(i+1)%n;V(mutex);V(full);}}读者-写者问题●一个数据对象若被多个并发进程所共享，且其中一些进程只要求读该数据对象的内容，而另一些进程则要求写操作，对此，我们把只想读的进程称为“读者”，而把要求写的进程称为“写者”。

●问题描述：●读者可同时读；●读者读时，写者不可写；●写者写时，其他的读者、写者均不可进入。

读者进程： while(true) {

‘有人要读’P(Wmutex); 读;

‘无人读了’

V(Wmutex); }写者进程：while(true){

P(Wmutex); 写;

V(Wmutex);

}

semaphoreWmutex=1;用信号量解决读者-写者问题voidreader()/*读者进程*/{while(true){P(Rmutex);

if(Rcount==0)P(Wmutex);

Rcount=Rcount+1; V(Rmutex); read;/*执行读操作*/

P(Rmutex); Rcount=Rcount-1; if(Rcount==0)V(Wmutex); V(Rmutex);}}SemaphoreWmutex,Rmutex=1,1;intRcount;用信号量解决读者-写者问题voidwriter()/*写者进程*/{while(true){P(Wmutex); write;/*执行写操作*/V(Wmutex);}}60哲学家进餐问题问题描述：有五个哲学家共用一张圆桌，分别坐在周围的五张椅子上，圆桌上有五个碗和五只筷子，每两个哲学家之间放一支哲学家的动作包括思考和进餐进餐时需要同时拿起他左边和右边的两支筷子;思考时则同时将两支筷子放回原处哲学家进餐问题61(thediningphilosophersproblem)条件：只有在拿到两只筷子时才能进餐；如果筷子已在他人手上，必须等于其他哲学家进餐完毕才能拿到筷子；任一哲学家在拿到两只筷子吃饭前，决不放下手中的筷子。哲学家进餐问题3/662问题：描述一个保证不会出现两个邻座同时要求吃饭的通信算法。描述一个既没有两邻座同时吃饭，又没有人永远拿不到筷子的算法。在什么情况下，5个哲学家全部吃不上饭？⑴设5个信号量c[1]～c[5]，初值均为1，分别表示第i号筷子被拿(i=1,2,3,4,5)。eat(i):第i个哲学家要吃饭begin P(c[i]); P(c[i+1mod5]); eating; V(c[i]); V(c[i+1mod5]);end注：这个过程能保证两邻座不同时吃饭，但会出现5个哲学家一人（左手）拿一只筷子，谁也吃不到饭的死锁情况。⑵解决的思路如下：让奇数号哲学家先取右手的筷子，让偶数号哲学家先取左手的筷子。这样就防止相邻座位的哲学家同时拿筷子的可能。除非某位哲学家一直吃下去，否则不会有人会饿死。eat(i):begin if(imod2==0) then { P(c[i]); P(c[i+1mod5]); eating; V(c[i]); V(c[i+1mod5]); } else { P(c[i+1mod5]); P(c[i]); eating; V(c[i+1mod5]); V(c[i]); }end哲学家进餐问题●五个哲学家，他们的生活方式是交替地思考和进餐。●哲学家们共用一张圆桌，围绕着圆桌而坐，在圆桌上有五个碗和五支筷子，平时哲学家进行思考，饥饿时拿起其左、右的两支筷子，试图进餐，进餐完毕又进行思考。●这里的问题是哲学家只有拿到靠近他的两支筷