第3章--进程同步与通信-同步.ppt

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,第,3,章,进程同步与通信,进程同步与互斥,经典进程同步问题,AND,信号量,进程通信,本章要点,进程同步的基本概念,同步：,指多个进程中发生的事件存在着某种时序关系，它们必须按规定时序执行，以共同完成一项任务,。,互斥：多个进程不能同时使用同一资源。,临界资源：某段时间内仅允许一个进程使用的资源。,临界区：每个进程中访问临界资源的那段代码。,3,信号量,(semaphore),管理相应临界区的公有资源，它代表可用资源实体。,5,8.P,V,原语,信号量的初值只能由,P,V,原语操作。,P:passeren V:verhoog,P,操作,：,申请资源操作,sem,减,1,若,sem,减,1,后仍大于,1,或等于零，则,P,返回，进程继续；,若,sem,减,1,后小于零，则该进程阻塞转等待队列中。,信号灯的,PV,操作,void wait(semaphore s),s.value=s.value-1;,if (s.value 0),block(s.queue);,/*,将进程阻塞，并将其投入等待队列,s.queue*/,P,操作,7,V,操作,：,释放资源操作,sem,加,1,若,sem,加,1,后结果大于,1,，则,V,停止操作，该进程返回调用处，继续执行；,若,sem,加,1,后小于或等于零，则该进程转就绪队列，同时进程调度选取一个等待队列中的进程转运行或就绪。,P,V,操作必须用原语实现。,信号灯的,PV,操作,void signal(semaphore s),s.value=s.value+1;,if (s.value=0),wackup(s.queue);,/*,唤醒阻塞进程，将其从等待队列,s.queue,取出，投入就绪队列,*/,V,操作,10,互斥进程举例,1,两个进程共享一台打印机,设信号量,print,代表打印机，初值为,1.,int main(void),int print=1;,cobegin,pa();pb();,coend,pa(),P(print);,使用打印机,V(print);,pb(),P(print);,使用打印机,V(print);,print=1,表示没有进程使用打印机,print=0,表示一个进程在用，没有进程等待,print=-1,表示一个进程在用，另一个在等待,12,N,个并发进程，互斥信号量,mutex,的,初值为,1,：,mutex,的取值范围为：,1,-(N-1),1,：表示没有进程进入临界区。有一个资源，无进程等待；,0,：表示有,1,个进程进入临界区。无资源，无进程等待；,-i,：表示,1,个进程进入临界区。无资源，且有,i(i0,（有票吗）？,如果有，,XN,（票够吗）？,如果够，则出票（打印票据）；,X,X,N,（修改剩余票数）；,将,X,回写到数据库中；,14,15,针对临界资源机票数设置一个信号量,mutex,，初值为,1,。每个终端进程中的程序描述如下：,P,（,mutex,）；,在机票数据库中取出当前剩余票数,X,；,判断,X0,（有票吗）？,如果有，,XN,（票够吗）？,如果够，则出票（打印票据）；,X,X,N,（修改剩余票数）；,将,X,回写到数据库中；,V,（,mutex,）；,16,如果有,n,个终端，则,mutex,信号量的取值范围为：,（,n,1,）,mutex1,其物理含义为：,当机票数空闲时，,mutex=1,。,当有一个终端进入，对机票进行处理，其它终端进程还没有到来时，,mutex=0,。,当所有终端进程都到来，且有一个正在对机票进行处理时，,mutex=,（,n,1,）。它表示有,n,1,个进程在等待队列上等待。,x,代表某航班的可用座位数，,p,1,和,p,2,两个售票进程，售票工作是对变量,x,减,1,。试用信号量的,P,、,V,操作实现这两个进程的互斥。,设：,mutex,为互斥信号量,p,1,(),p(mutex),；,x:=x-1,；,v(mutex),；,p,2,(),p(mutex),；,x:=x-1,；,v(mutex),；,互斥问题举例,3,某车站售票厅有,20,个窗口，任何时刻最多可容纳,20,名购票者进入，当售票厅中少于,20,名购票者时，则厅外的购票者可立即进入，否则需在厅外等待。若把一个购票者看作一个进程，请用,P,、,V,操作管理这些并发进程，要求如下：,在主函数中给出信号量的定义和初值。,给出一个购票者进程的算法。,给出当购票者最多不超过,n(,设,n20),个时，信号量可能的变化范围。,18,主函数算法：,main(),int mutex=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,个购票者在厅外等待，绝对值表示等待进程个数。,结论,：,当,mutex0,时其值表示可用资源个数；,当,mutex,0,时其绝对值表示等待进程的个数。,答,同一类资源：,m-n,mutex,m,不同类资源：,需要,m,个,mutex,1-n,mutex,1,同步进程举例,直接制约,同步定义,私用信号量,PV,原语实现进程同步,生产者消费者问题,哲学家进餐问题,24,化验单,化验结果,继续诊病,27,对于医生的操作步骤：,有病人时：,开化验单（化验单多一个）,等待化验结果,（有化验结果）继续诊病,28,对于化验员的操作步骤：,等化验单,（有化验单时）进行化验,（未化验的化验单少一个）,出化验结果（化验结果多一个）,等待下一化验单,程序描述,main(),int s1,=0,；,int s2,=1,；,cobegin,doctor(),；,test(),；,coend,31,对于化验员的操作步骤：,test,wait(,化验单,);,化验,出化验结果,signal(,有化验结果,);,32,对于医生的操作步骤：,doctor,给病人看病,signal(,化验单,);,wait(,化验结果,);,继续诊病,信号灯的,PV,操作,void wait(semaphore s),s.value=s.value-1;,if (s.value 0),block(s.queue);,/*,将进程阻塞，并将其投入等待队列,s.queue*/,P,操作,信号灯的,PV,操作,void signal(semaphore s),s.value=s.value+1;,if (s.value buf;,V(mutex);,V(full);,P(full);,P(mutex);,/进入区,one unit-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,信号,思考：还有其他的执行序列可以产生死锁吗？,发生死锁,生产者-消费者,问题,指有两组进程共享一个环形的缓冲池。一组进程被称为生产者，另一组进程被称为消费者。,缓冲池是由若干个大小相等的缓冲区组成的，每个缓冲区可以容纳一个产品。,生产者进程不断地将生产的产品放入缓冲池，消费者进程不断地将产品从缓冲池中取出。,用信号量解决“生产者-消费者”问题,void consumer()/,消费者进程,while (true),P(full);,P(mutex);,data_c=bufferj;,j=(j+1)%n;,V(mutex);,V(empty);,consume the item in data_c;,semaphore mutex=1;semaphore empty=n;semaphore full=0;,int i,j;ITEM buffern;ITEM data_p,data_c;,void producer()/,生产者进程,while (true),produce an item in data_p;,P(empty);,P(mutex);,bufferi=data_p;,i=(i+1)%n;,V(mutex);,V(full);,读者-写者问题,一个数据对象若被多个并发进程所共享，且其中一些进程只要求读该数据对象的内容，而另一些进程则要求写操作，对此，我们把只想读的进程称为“读者”，而把要求写的进程称为“写者”。,问题描述：,读者可同时读；,读者读时，写者不可写；,写者写时，其他的读者、写者均不可进入。,读者进程：,w,hile(true),有人要读,P,(,W,mutex);,读;,无人读了,V,(Wmutex);,写者进程：,w,hile(true),P,(Wmutex);,写,;,V,(Wmutex);,semaphore Wmutex=1;,用信号量,解决,读者-写者,问题,void reader()/*,读者进程,*/,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);,Semaphore Wmutex,Rmutex=1,1;int Rcount;,用信号量,解决,读者-写者,问题,void writer(),/*,写者进程,*/,while (true),P(Wmutex);,write;,/*,执行写操作,*/,V(Wmutex);,60,哲学家进餐问题,问题描述,：,有,五个哲学家,共用一张圆桌，分别坐在周围的五张椅子上，,圆桌上有五个碗和,五只筷子,，每两个哲学家之间放一支,哲学家的动作包括,思考,和,进餐,进餐,时需要同时拿起他左边和右边的两支筷子,;,思考,时则同时将两支筷子放回原处,哲学家进餐问题,61,(the dining philosophers problem),条件,：,只有在拿到两只筷子时才能进餐；,如果筷子已在他人手上，必须等于其他哲学家进餐完毕才能拿到筷子；,任一哲学家在拿到两只筷子吃饭前，决不放下手中的筷子。,哲学家进餐问题,3/6,62,问题,：,描述一个保证不会出现两个邻座同时要求吃饭的通信算法。,描述一个既没有两邻座同时吃饭，又没有人永远拿不到筷子的算法。,在什么情况下，,5,个哲学家全部吃不上饭？,设,5,个信号量,c1,c5,，初值均为,1,，分别表示第,i,号筷子被拿,(i=1,2,3,4,5),。,eat(i):,第,i,个哲学家要吃饭,begin,P(ci);,P(ci+1 mod 5);,eating;,V(ci);,V(ci+1 mod 5);,end,注：,这个过程能保证两邻座不同时吃饭，但会出现,5,个哲学家一人（左手）拿一只筷子，谁也吃不到饭的死锁情况。,解决的思路如下：,让奇数号哲学家先取右手的筷子，让偶数号哲学家先取左手的筷子。这样就防止相邻座位的哲学家同时拿筷子的可能。除非某位哲学家一直吃下去，否则不会有人会饿死。,eat(i):,begin,if(i mod 2=0),then,P(ci);,P(ci+1 mod 5);,eating;,V(ci);,V(ci+1 mod 5);,else,P(ci+1 mod 5);,P(ci);,eating;,V(ci+1 mod 5);,V(ci);,end,哲学家进餐,问题,五个哲学家，他们的生活方式是交替地思考和进餐,。,哲学家们共用一张圆桌，围绕着圆桌而坐，在圆桌上有五个碗和五支筷子，平时哲学家进行思考，饥饿时拿起其左、右的两支筷子，试图进餐，进餐完毕又进行思考。,这里的,问题是,哲学家只有拿到靠近他的两支筷子才能进餐，而拿到两支筷子的条件是他的左、右邻居此时都没有进餐。,semaphore chopstick5=1,1,1,1,1;,void philosopher(,int i,)/*,哲学家进程*/,while (true),P(chopsticki);,P(chopstick(i+1)%5);,eating;/*,进餐*/,V(chopsticki);,V(chopstick(i+1)%5);,thinking;/*,思考*/,用信号量,解决,哲学家进餐,问题,哲学家能顺利地吃到饭吗,打磕睡的理发师问题,理发店有一名理发师，一把理发椅，还有,N,把供等候理发的顾客坐的普通椅子。如果没有顾客到来，理发师就坐在理发椅上打磕睡。当顾客到来时，就唤醒理发师。如果顾客到来时理发师正在理发，顾客就坐下来等待。如果,N,把椅子都坐满了，顾客就离开该理发店去别处理发。,用信号量,解决,打磕睡的理发师问题,void customer()/,顾客进程,P(mutex);,if(waiting CHAIRS)/,如果有空位，顾客等待,waiting+;,V(customers);/,如果有必要，唤醒理发师,V(mutex);,P(barners);/,如果理发师正在理发，则顾客等待,get_haircut();,else/,如果没有空位，则顾客离开,V(mutex);,#define CHAIRS 5/,为等候的顾客准备的座椅数,semaphore customers=0;semaphore barners=0;semaphore mutex=1;int waiting;,void barber()/,理发师进程,while (true),P(customers);/,如果没有顾客，理发师就打磕睡,P(mutex);/,互斥进入临界区,waiting-;,V(barners);/,理发师准备理发了,V(mutex);,cut_hair();/,理发,