《操作系统ch》PPT课件

1,3.3生产者消费者问题,多缓冲区的同步互斥问题同步：当缓冲池已放满了产品时(供过于求)，生产者进程必须等待；当缓冲池已空时(供不应求)，消费者进程应等待。互斥：所有进程应互斥使用缓冲池这一临界资源。,2,3.3生产者消费者问题,多缓冲区的生产者消费者问题解法,设置三个信号量mutex，empty，full的初始值分别为1，k，0；,思考：P操作的顺序可换吗？,3,3.3生产者消费者问题,注意：此解中，无论是生产者进程还是消费者进程，V操作的次序无关紧要，但P操作的次序不能随意交换，否则可能造成死锁。例如，若将生产者进程中的P(empty)与P(mutex)的次序交换，则在一定条件下就会出现死锁现象。,为将k个缓冲区管理成是循环的，须设置两个指针，一个指明当前哪个缓冲区是空闲的，可往里面存放物品；一个指明当前可从哪个位置取出物品进行消费。前一个指针起名“in”，后一个起名“out”，初值都为0。,图(a)表示往缓冲区里存放4个物品、取出一个物品后，指针in和out的位置；图(b)表示往缓冲区里存放k+2个物品、取出4个物品后，指针in和out的位置。,3.3生产者消费者问题,各生产者和消费者对缓冲区的操作应互斥，即对缓冲区的操作应为临界区。所以，要设一个初值为1的信号量mutex，用于实现临界区的互斥。,“生产者-消费者”问题的解决，要设置：,full：初值为0的信号量，表示缓冲区中已有的物品个数；,empty：初值为k的信号量，表示缓冲区中可供使用的缓冲区数目；,mutex：初值为1的信号量，用于互斥使用缓冲区；,in：初值为0，指示当前存放物品的缓冲区位置；,out：初值为0，指示当前取出缓冲区中物品的位置。,3.3生产者消费者问题,Producer():/*生产者进程程序*/while(TRUE)生产一个物品;P(empty);/*申请缓冲区里的空位*/P(mutex);/*进入临界区*/物品存入bufferin;in=(in+1)modk;/*调整存放指针in*/V(mutex);/*退出临界区*/V(full);/*缓冲区里的物品计数*/,Consumer():/*消费者进程程序*/P(full);/*缓冲区里有物品吗？*/P(mutex);/*进入临界区*/从bufferout取出物品;out=(out+1)modk;/*调整取出指针out*/V(mutex);/*退出临界区*/V(empty);/*缓冲区里增加一个空位*/消费取出放入物品;,“生产者-消费者”算法描述如下：,3.3生产者消费者问题,某招待所有个床位，住宿者入住时要先登记（在登记表上填写姓名和床位号），离去时要销掉登记项（在登记表上删去姓名和床位号）。请给出住宿登记和销掉登记过程的算法描述。,习题,桌子上有一只盘子，最多可容纳两个水果，每次只能放入或取出一个水果。爸爸专向盘子中放苹果(apple)，妈妈专向盘子中放橘子(orange)，两个儿子专门吃盘子中的橘子，两个女儿专门吃盘子中的苹果。请用、操作来实现爸爸、妈妈、儿子、女儿之间的同步与互斥关系。,习题,工厂有两个生产车间和一个装配车间，两生产车间分别生产A、B两种零件，装配车间的任务是把A、B两种零件组装成产品。两个生产车间每生产一个零件后都要分别把它们送到装配车间的货架F1和F2上，F1存放A，F2存放B，F1和F2均只能容纳一个零件。每当能从货架上取到一个A和一个B后就可以组装成一件产品。整个过程是自动进行的，试用P、V操作进行管理，使各车间相互合作、协调工作。,习题,ProcessP3beginL3:P(S3)；X=F1;/从F1上取零件AV(S1)；P(S4)Y=F2；/从F2上取零件BV(S2);组装产品；gotoL3;end;coend;end;,beginS1,S2,S3,S4:semaphore;S1=S2=1;S3=S4=0;cobeginProcessP1beginL1:生产一个零件A；P(S1)；F1=A；V(S3);gotoL1;end;ProcessP2beginL2:生产一个零件B；P(S2)；F2=B；V(S4);gotoL2;end;,11,3.4读者写者问题,有两组并发进程:读者和写者，共享一组数据区要求：允许多个读者同时执行读操作不允许读者、写者同时操作不允许多个写者同时操作,12,3.4读者写者问题,读者-写者问题有两种类型：第一类：读者优先附解当写者提出了写的要求后，允许新的读者继续进入（）第二类：写者优先当写者提出了写的要求后，不允许新的读者进入,3.4读者写者问题,(1)构筑读者进程和写者进程间的临界区,对这批数据，要保证读者和写者互斥使用，也要保证写者和写者互斥使用。设置信号量wrt，用来在读者和写者程序中构成如图所示的临界区。,这种安排在某读者进入临界区使用数据时，其他读者都不能使用该数据，这不符合题目要求。,设变量first（它不是信号量）初值为0。任何一个读者运行时，都先在first上加1，然后判定它是否取值为1。若是1，则做P(wrt)，否则不做。,与此同时，不能让每个读者退出临界区时都对信号量wrt做V操作，而是要判断它是否是最后一个读者。只有对最后一个读者，才会对信号量wrt做V操作，以便能够让写者有机会进入临界区。,3.4读者写者问题,(2)判定是否是第1个读者,3.4读者写者问题,(3)first是所有读者共享的公共变量,first=first-1(读者计数器减1),读者：,first=1?(是第1个读者?),P(MUTEX)(进入first临界区),读者读取所需信息,first=first+1(读者计数器加1),V(MUTEX)(退出first临界区),P(WRT)(进入读/写临界区),P(MUTEX)(进入first临界区),first=0?(是最后一个读者?),V(MUTEX)(退出first临界区),V(WRT)(退出读/写临界区),N,N,Y,Y,P(WRT)(进入读/写临界区),写者对数据进行修改,V(WRT)(退出读/写临界区),写者：,这样，“读者-写者”问题的解决，用到如下的信号量和变量：wrt：初值为1的互斥信号量，只要有一个写者访问数据时，其他写者和读者就要被阻止对数据的访问；mutex：保证读者互斥操作first的信号量，初值为1；first：读者计数变量，初值为0。,3.4读者写者问题,读者-写者问题中读者的算法描述如下：,3.4读者写者问题,有一条小河，河上有一座独木桥可供南来北往的人过河。由于桥面窄，只能单向行走。试用P、V操作设计一个过河算法。,习题,19,3.5哲学家进餐问题,5个哲学家围坐在圆桌旁，每人面前有一只空盘子，每2人之间放一只筷子，如图所示。为了就餐，每个哲学家必须拿到两只筷子，并且只能直接从自己的左边或右边去取筷子。,3.5哲学家进餐问题,21,3.5哲学家进餐问题-解,Semaphorechopstick5=1；/为每支筷子设置一个信号量哲学家i的活动为：voidphilosopher(inti)while(true)思考；P(chopsticki)；/取左边筷子P(chopstick(i+1)%5)；/取右边筷子进食；V(chopsticki)；/放左边筷子V(chopstick(i+1)%5)；/放右边筷子,22,3.5哲学家进餐问题,如果：5人同时拿起左边筷子，再企图拿起右边的筷子时，会如何？,死锁！,3.5哲学家进餐问题,定义三种状态：THINKING(思考)；EATING(就餐)；HUNGRY(饥饿)。,设有5个元素的数组statei(0i4)，每个元素对应一个哲学家，随时记录他们在生活过程中所处的不同状态。,设有5个元素的信号量数组：si(0i4)，初值都为0，每个对应一个哲学家。在拿不到筷子就餐时，用它来与占用筷子的有关哲学家取得同步。,为方便哲学家判定左右相邻哲学家当前的状态，设置两个变量：LEFT=(i+4)mod5，RIGHT=(i+1)mod5(0i4)根据哲学家自己的编号i，计算LEFT和RIGHT的值，就能得到左右相邻哲学家的编号。,为保证各哲学家在测试左右相邻哲学家状态和设置新状态时，能够互斥进行，算法里用到互斥信号量mutex，初值为1。,3.5哲学家进餐问题,哲学家i(0i4)的生活，由过程philosopher(i)给出：,调用思考子程序think()、获取筷子子程序take_chopstick(i)、就餐子程序eat()、归还筷子子程序put_chopstick(i)，实现自己的“思考-就餐-思考”过程。,3.5哲学家进餐问题,获取筷子子程序take_chopstick(i)的代码描述如下：,3.5哲学家进餐问题,测试状态子程序test(i)的代码描述如下：,3.5哲学家进餐问题,归还筷子子程序put_chopstick(i)的代码描述如下：,3.5哲学家进餐问题,测试状态子程序test(i)的代码描述如下：,3.5哲学家进餐问题,例：理发店有k张理发椅和n张等待理发的顾客座椅。若没顾客，理发师就在理发椅上打盹；顾客来时，唤醒打盹的理发师理发；若理发师全在工作，又来新顾客，顾客就坐在座椅上等，没有空椅就离开。试用信号量来描述理发师和顾客的行为，保证该过程的正确实现。,3.6理发师理发问题,解：设立三个信号量,(1)custs：记录等待理发的顾客数（不包括正在理发的顾客），初值为0；,(2)barbs：等待为顾客理发的理发师数，初值为k；,(3)mutex：用于保证互斥使用变量waiting的互斥信号量，初值为1。,为随时记录等待理发的顾客数，设变量waiting，初值为0。它是一个变量，不是信号量，不过它的值总是和信号量customers相同。,n：来到理发店等待理发的顾客数的上限值。,3.6理发师理发问题,理发师程序barber()的代码描述如下：,功能是在custs上做P操作，判定是否有顾客等待理发。只有通过这个P操作，才表示有顾客理发，于是进入由信号量mutex控制的临界区，确保对变量waiting操作的互斥。然后调用理发子程序cut_hair()，完成理发后，在信号量barbs上做V操作，表示又有一理发师在等待工作。,3.6理发师理发问题,顾客程序customer()的代码描述如下：,顾客到达后，执行顾客程序customer()，功能是进入mutex控制的临界区，在有座椅的情况下，对信号量custs做V操作，记录等待理发的顾客数。退出mutex临界区后，对信号量barbs做P操作，申请一位理发师为顾客理发。若k个理发师现在都忙，顾客就阻塞在信号量barbs上；否则调用子程序get_haicut()，得到理发师提供的理发服务。,3.6理发师理发问题,barber()中注有“*”号的P(custs)，与customer()中注有“*”号的V(custs)是相互呼应的一对同步