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

1、第第3 3章章 进程同步与通信进程同步与通信进程同步与互斥进程同步与互斥 经典进程同步问题经典进程同步问题 管程管程 AND信号量信号量 进程通信进程通信 进程同步的基本概念进程同步的基本概念同步：同步：指多个进程中发生的事件存在着某种时指多个进程中发生的事件存在着某种时序关系，它们必须按规定时序执行，以共同完成序关系，它们必须按规定时序执行，以共同完成一项任务一项任务 。互斥：多个进程不能同时使用同一资源。互斥：多个进程不能同时使用同一资源。临界资源：某段时间内仅允许一个进程使用的临界资源：某段时间内仅允许一个进程使用的资源。资源。临界区：每个进程中访问临界资源的那段代码。临界区：每个进程中

2、访问临界资源的那段代码。3信号量信号量(semaphore)(semaphore)管理相应临界区的公有资源，它代管理相应临界区的公有资源，它代表可用资源实体。表可用资源实体。4信号量是一个整型变量。信号量是一个整型变量。0 0：可供并发进程使用的资源实体数：可供并发进程使用的资源实体数0 0：正在等待使用临界区的进程数：正在等待使用临界区的进程数用于互斥的信号量初值应该大于零用于互斥的信号量初值应该大于零5信号灯的信号灯的PV操作操作void wait(semaphore s) s.value = s.value - 1; if (s.value 0) block(s.queue); /* 将

3、进程阻塞，并将其投入等待队列将进程阻塞，并将其投入等待队列s.queue */P操作操作7信号灯的信号灯的PV操作操作void signal(semaphore s) s.value = s.value + 1; if (s.value = 0) wackup(s.queue); /* 唤醒阻塞进程，将其从等待队列唤醒阻塞进程，将其从等待队列s.queue 取出，投入就绪队列取出，投入就绪队列*/V操作操作用信号灯解决互斥问题用信号灯解决互斥问题semaphore mutex=1;P1: while (1)P(mutex);临界区临界区;V(mutex);剩余区剩余区; ; P2: while

4、 (1)P(mutex);临界区临界区V(mutex);剩余区剩余区; ;10互斥进程举例互斥进程举例1 1两个进程共享一台打印机两个进程共享一台打印机设信号量设信号量printprint代表打印机，初值为代表打印机，初值为1.1.intint main(voidmain(void) ) intint print=1; print=1;cobegincobeginpa(); pa(); pbpb();();coendcoend pa()pa() P(print);P(print);使用打印机使用打印机V(print);V(print); pb()pb() P(print);P(print);使

5、用打印机使用打印机V(print);V(print); 11信号量可能的取值范围信号量可能的取值范围假设有假设有N N个并发进程个并发进程共用共用一台一台打印机，设打印机，设互斥信号量互斥信号量mutexmutex的初值为的初值为1 1，则：，则：J信号量信号量mutexmutex代表什么？代表什么？Jmutexmutex的取值范围为多少？的取值范围为多少？Jmutexmutex的值分别代表什么含义？的值分别代表什么含义？12N N个并发进程，互斥信号量个并发进程，互斥信号量mutexmutex的的初值为初值为1 1：mutexmutex的取值范围为：的取值范围为：1 1-(N-1)-(N-1

6、)1 1：表示没有进程进入临界区。有一个资源，无：表示没有进程进入临界区。有一个资源，无进程等待；进程等待；0 0：表示有：表示有1 1个进程进入临界区。无资源，无进程个进程进入临界区。无资源，无进程等待；等待；-i -i：表示：表示1 1个进程进入临界区。无资源，且有个进程进入临界区。无资源，且有i i (i=N-1)(i0（有票吗）？（有票吗）？如果有，如果有， XN（票够吗）？（票够吗）？如果够，则出票（打印票据）；如果够，则出票（打印票据）；XXN（修改剩余票数）；（修改剩余票数）；将将X回写到数据库中；回写到数据库中；141516某车站售票厅有某车站售票厅有20个窗口，任何时刻最多可

7、容个窗口，任何时刻最多可容纳纳20名购票者进入，当售票厅中少于名购票者进入，当售票厅中少于20名购票名购票者时，则厅外的购票者可立即进入，否则需在者时，则厅外的购票者可立即进入，否则需在厅外等待。若把一个购票者看作一个进程，请厅外等待。若把一个购票者看作一个进程，请用用P、V操作管理这些并发进程，要求如下：操作管理这些并发进程，要求如下：在主函数中给出信号量的定义和初值。在主函数中给出信号量的定义和初值。给出一个购票者进程的算法。给出一个购票者进程的算法。给出当购票者最多不超过给出当购票者最多不超过n (设设n20)个时，个时，信号量可能的变化范围。信号量可能的变化范围。18分析分析n共享临界

8、资源：共享临界资源：20个同类的售票窗口个同类的售票窗口n先来者先进入先来者先进入主函数算法：主函数算法：main()int mutex=20;cobeginP1(); Pi();Pn();coend购票者购票者i的算法：的算法：Pi()P(mutex);购票；购票；V(mutex); 信号量信号量mutex的的取值范围取值范围： (n20) mutex 20其其物理含义物理含义是：是：当当mutex=20时，表示售票厅内没有购票者进入，时，表示售票厅内没有购票者进入，20个窗口都是个窗口都是空闲的，表示可用资源个数；空闲的，表示可用资源个数；当当mutex=0时，表示售票厅内已经进入了时，表

9、示售票厅内已经进入了20个购票者，每个窗口个购票者，每个窗口都被分配，没有等待的购票者，可用资源为都被分配，没有等待的购票者，可用资源为0；当当mutex=(n20)时，表示一共有时，表示一共有n个购票者，其中个购票者，其中20个购票者个购票者已经进入厅内，分别占有一个窗口，还有已经进入厅内，分别占有一个窗口，还有n20个购票者在厅个购票者在厅外等待，绝对值表示等待进程个数。外等待，绝对值表示等待进程个数。结论结论：当当mutex0时其值表示可用资源个数；时其值表示可用资源个数；当当mutex0时其绝对值表示等待进程的个数。时其绝对值表示等待进程的个数。22思考：思考：n n个并发进程，共享个

10、并发进程，共享mm个共享资源：个共享资源：mutexmutex的取值范围为？的取值范围为？答n同一类资源：同一类资源： m-n mutex mn不同类资源：不同类资源： 需要需要m个个mutex 1-n mutex 1同步进程举例同步进程举例直接制约直接制约同步定义同步定义私用信号量私用信号量PV原语实现进程同步原语实现进程同步生产者消费者问题生产者消费者问题哲学家进餐问题哲学家进餐问题24门诊医生：门诊医生： 开开化验单；化验单； 等等化验结果；化验结果； 继续诊病；继续诊病；化验员：化验员： 等等化验单；化验单； 化验；化验； 填写化验结果；填写化验结果； 等等待待等等待待唤唤醒醒后后唤唤

11、醒醒后后继续诊病继续诊病2728n需要两个信号量需要两个信号量ns1: 表示化验结果是否出来表示化验结果是否出来,初值为初值为0.ns2：表示医生是否开化验单，初值为：表示医生是否开化验单，初值为0.程序描述程序描述main( ) int s1 =0； int s2 =1； cobegin doctor( )；test( )； coend3132信号灯的信号灯的PV操作操作void wait(semaphore s) s.value = s.value - 1; if (s.value 0) block(s.queue); /* 将进程阻塞，并将其投入等待队列将进程阻塞，并将其投入等待队列s.

12、queue */P操作操作信号灯的信号灯的PV操作操作void signal(semaphore s) s.value = s.value + 1; if (s.value one unit-bufbuf; ;V(mutexV(mutex); );V(fullV(full); );P(fullP(full); );P(mutexP(mutex); );/进入区进入区 one unit-one unit-bufbuf; ;V(mutexV(mutex); );V(emptyV(empty); );/退出区退出区分析：分析：当当full=0, full=0, mutexmutex = 1 = 1时

13、，执行顺序：时，执行顺序： / C / C阻塞，等待阻塞，等待Producer Producer 发出的发出的fullfull信号信号 / P / P 阻塞，等待阻塞，等待ConsumerConsumer发出的发出的emptyempty信号信号生产者生产者-消费者消费者问题ji满空指有两组进程共享一个环形的缓冲池。一组进程被称为指有两组进程共享一个环形的缓冲池。一组进程被称为生产者，另一组进程被称为消费者。生产者，另一组进程被称为消费者。缓冲池是由若干个大小相等的缓冲区组成的，每个缓冲缓冲池是由若干个大小相等的缓冲区组成的，每个缓冲区可以容纳一个产品。区可以容纳一个产品。生产者进程不断地将生产

14、的产品放入缓冲池，消费者进生产者进程不断地将生产的产品放入缓冲池，消费者进程不断地将产品从缓冲池中取出。程不断地将产品从缓冲池中取出。 用信号量解决用信号量解决“生产者生产者-消费者消费者”问问题题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;i

15、nt 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); 读者读者-写者问题写者问题一个数据对象若被多个并发进程所共享，一个数据对象若被多个并发进程所共享，且其中一些进程只要求读该数据对象的内且其中一些进程只要求读该数据对象的内容，而另一些进程则要求写操作，对此，容，而另一些进程则要求写操作

16、，对此，我们把只想读的进程称为我们把只想读的进程称为“读者读者”，而把，而把要求写的进程称为要求写的进程称为“写者写者”。 问题描述：问题描述：读者可同时读；读者可同时读；读者读时，写者不可写；读者读时，写者不可写；写者写时，其他的读者、写者均不可写者写时，其他的读者、写者均不可进入。进入。读者进程：读者进程：while(true) 有人要读有人要读 P(Wmutex); 读读; 无人读了无人读了 V(Wmutex);写者进程：写者进程：while(true) P(Wmutex);写写;V(Wmutex); semaphore Wmutex=1;用信号量用信号量解决读者读者-写者写者问题voi

17、d 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(W

18、mutex);write; /* 执行写操作执行写操作 */V(Wmutex); 60哲学家进餐问题哲学家进餐问题问题描述问题描述：v有有五个哲学家五个哲学家共用一张圆桌，分别坐在周围的五张椅子上，共用一张圆桌，分别坐在周围的五张椅子上，v圆桌上有五个碗和圆桌上有五个碗和五只筷子五只筷子，每两个哲学家之间放一支，每两个哲学家之间放一支v哲学家的动作包括哲学家的动作包括思考思考和和进餐进餐v进餐进餐时需要同时拿起他左边和右边的两支筷子时需要同时拿起他左边和右边的两支筷子; ;v思考思考时则同时将两支筷子放回原处时则同时将两支筷子放回原处哲学家进餐问题61(the dining philosoph

19、ers problem)(the dining philosophers problem)条件条件：v 只有在拿到两只筷子时才能进餐；只有在拿到两只筷子时才能进餐；v 如果筷子已在他人手上，必须等于其他哲学家进餐如果筷子已在他人手上，必须等于其他哲学家进餐完毕才能拿到筷子；完毕才能拿到筷子；v 任一哲学家在拿到两只筷子吃饭前，决不放下手中任一哲学家在拿到两只筷子吃饭前，决不放下手中的筷子。的筷子。哲学家进餐问题 3/662问题问题： 描述一个保证不会出现两个邻座同时要求吃饭的描述一个保证不会出现两个邻座同时要求吃饭的通信算法。通信算法。 描述一个既没有两邻座同时吃饭，又没有人永远描述一个既没有

20、两邻座同时吃饭，又没有人永远拿不到筷子的算法。拿不到筷子的算法。 在什么情况下，在什么情况下，5 5个哲学家全部吃不上饭？个哲学家全部吃不上饭？设设5个信号量个信号量c1c5，初值均为，初值均为1，分别表示第，分别表示第i号筷子被拿号筷子被拿(i=1,2,3,4,5)。eat(i): 第第i个哲学家要吃饭个哲学家要吃饭beginP(ci);P(ci+1 mod 5);eating;V(ci);V(ci+1 mod 5);end注：注：这个过程能保证两邻座不同时吃饭，但这个过程能保证两邻座不同时吃饭，但会出现会出现5个哲学家一人（左手）拿一只筷子，个哲学家一人（左手）拿一只筷子，谁也吃不到饭的死

21、锁情况。谁也吃不到饭的死锁情况。解决的思路如下：解决的思路如下：让奇数号哲学家先取右手的筷子，让偶数号哲学让奇数号哲学家先取右手的筷子，让偶数号哲学家先取左手的筷子。这样就防止相邻座位的哲学家先取左手的筷子。这样就防止相邻座位的哲学家同时拿筷子的可能。除非某位哲学家一直吃下家同时拿筷子的可能。除非某位哲学家一直吃下去，否则不会有人会饿死。去，否则不会有人会饿死。eat(i):beginif (i mod 2 = 0)thenP(ci);P(ci+1 mod 5);eating;V(ci);V(ci+1 mod 5);elseP(ci+1 mod 5);P(ci);eating;V(ci+1 m

22、od 5);V(ci);end哲学家进餐哲学家进餐问题五个哲学家，他们的生活方式是交替地思考和五个哲学家，他们的生活方式是交替地思考和进餐进餐。哲学家们共用一张圆桌，围绕着圆桌而坐，在哲学家们共用一张圆桌，围绕着圆桌而坐，在圆桌上有五个碗和五支筷子，平时哲学家进行思圆桌上有五个碗和五支筷子，平时哲学家进行思考，饥饿时拿起其左、右的两支筷子，试图进餐，考，饥饿时拿起其左、右的两支筷子，试图进餐，进餐完毕又进行思考。进餐完毕又进行思考。这里的这里的问题是问题是哲学家只有拿到靠近他的两支筷哲学家只有拿到靠近他的两支筷子才能进餐，而拿到两支筷子的条件是他的左、子才能进餐，而拿到两支筷子的条件是他的左、

23、右邻居此时都没有进餐。右邻居此时都没有进餐。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; /* 思考思考 */用信号量用信号量解决哲学家进餐哲学家进餐问题哲学家能顺利地吃到饭吗哲学家能顺利地吃到饭吗打磕睡的理发师问题打磕睡的理发师问题 理发店有一名理发师，一把理发椅，还有理发店有一