搜索
第2章进程管理2.4经典的进程同步问题1．生产者与消费者问题2．哲学家进餐问题3.读者与写者问题第2章进程管理哲学家进餐问题问题描述：五个哲学家共用一张圆桌，分别坐在周围的五张椅子上，在圆桌上有五个碗和五只筷子，他们的生活方式是交替地进行思考和进餐。平时，一个哲学家进行思考，饥饿时便试图取用其左右最靠近他的筷子，只有在他拿到两只筷子时才能进餐。进餐后，放下筷子继续思考。解决方法：用一个信号量来表示一只筷子，由这5个信号量构成信号量数组。其描述如下；Varchopstick:array[0,…,4]ofsemaphore;第2章进程管理第i位哲学家的活动可描述为：repeatwait(chopstick[i]);wait(chopstick[(i+1)mod5]);…eat;…signal(chopstick[i]);signal(chopstick[(i+1)mod5]);…think;untilfalse;1043204312第2章进程管理processphilosopher0wait(chopstick[0]);wait(chopstick[1]);…当推进顺序如下所示时：processphilosopher1wait(chopstick[1]);wait(chopstick[2]);…processphilosopher2wait(chopstick[2]);wait(chopstick[3]);…processphilosopher3wait(chopstick[3]);wait(chopstick[4]);…processphilosopher4wait(chopstick[4]);wait(chopstick[0]);…philosopher0：wait(chopstick[0])，chopstick[0]=0;philosopher1：wait(chopstick[1])，chopstick[1]=0;philosopher2：wait(chopstick[2])，chopstick[2]=0;philosopher3：wait(chopstick[3])，chopstick[3]=0;philosopher4：wait(chopstick[4])，chopstick[4]=0;wait(chopstick[1])，阻塞wait(chopstick[2])，阻塞wait(chopstick[3])，阻塞wait(chopstick[4])，阻塞wait(chopstick[0])，阻塞第2章进程管理存在的问题以上解决方法中，虽然可以避免相邻两位哲学家同时进餐的问题，但是在五位哲学家同时饥饿而各自拿起左边的筷子时，就会使五个信号量chopstick均为0；当他们再试图去拿右边的筷子时，都将因无筷子可拿而无限期地等待。1043204312processphilosopher1wait(chopstick[1]);wait(chopstick[2]);…processphilosopher2wait(chopstick[2]);wait(chopstick[3]);…当philosopher1正在用餐时，philosopher2会因wait(chopstick[2])而阻塞，因此保证了不会有相邻的两位哲学家同时进餐第2章进程管理解决该死锁问题的方法为：（1）最多只允许有四位哲学家去拿左边的筷子；（2）仅当哲学家的左、右两只筷子均可用时，才允许他拿起筷子进餐；（3）规定奇数号哲学家先拿他左边的筷子，然后再去拿右边的筷子；而偶数号哲学家则相反。按此规定，将是0、1号哲学家竞争1号筷子；2、3号哲学家竞争3号筷子。即五位哲学家总是先竞争奇数号筷子，然后再去竞争偶数号筷子，最后总有一位哲学家能获得两只筷子进餐。1043204312第2章进程管理用And型信号量解决哲学家进餐问题Varchopstickarray[0,…,4]ofsemaphore:=(1,1,1,1,1);ProcessirepeatthinkSwait(chopstick[(i+1)mod5],chopstick[i]);eat;Ssignal(chopstick[(i+1)mod5],chopstick[i]);untilfalse;第2章进程管理3．读者与写者问题设某航空公司有2个售票处，它们通过远程终端访问设在公司总部的航空订票系统，并要查询或修改系统中记录所有班机当前订票数的数据库B。设Bi为某班机的当前订票数，P1和P2分别代表2个售票处的售票进程，R1和R2为进程执行时使用的工作寄存器。由于售票进程并发执行，且各自访问数据库B的时间是随机的，故有可能出现下面的访问序列（假定Bi的当前值为x）：下一页第2章进程管理P1:R1:=Bi;R1:=R1+1P2:R2=Bi;R2:=R2+1;P1:Bi:=R1;P2:Bi:=R2可见，Bi的新值是X+1，而不是X+2。这里的P1和P2均为写者，显然，对于写者而言，Bi是临界资源，因此写者之间应该互斥地访问Bi。下一页BBiP1P2R1R2第2章进程管理问题描述：允许多个读进程同时读一个共享对象，因为读操作不会使数据文件混乱。但不允许一个Writer进程和其他Reader进程或Writer进程同时访问共享对象。因为这种访问将会引起混乱。可用记录型信号量解决读者-写者问题可用信号量集机制解决读者-写者问题所谓读者—写者问题指的是保证一个写者进程必须与其他进程互斥地访问共享对象的同步问题。第2章进程管理用记录型信号量解决读者—写者问题为实现Reader和Writer进程间在读或写时的互斥而设置了一个互斥信号量Wmutex。另外，再设置一个整型变量readcount表示正在读的进程数目。Varrmutex,wmutex:semaphore:=1,1;readcount:integer:=0;beginparbeginReader:beginrepeatwait(rmutex);ifreadcount=0thenwait(wmutex);readcount:=readcount+1;signal(rmutex);…performreadoperation;…wait(rmutex);readcount:=readcount-1ifreadcount=0thensignal(wmutex);signal(rmutex);untilfalse;end第2章进程管理writer:beginrepeatwait(wmutex);performwriteoperation;signal(wmutex);untilfalse;endparendend只要有一个Reader进程在读，便不允许Writer进程去写。因此，仅当readcount=0,表示尚无Reader进程在读时，Reader进程才需要执行wait(wmutex)操作；若wait(wmutex)操作成功，Reader进程便可去读，相应地，做readcount+1操作。同理，仅当Reader进程在执行了readcount减1操作后其值为0时，才须执行signal(wmutex)操作，以便让Writer进程写。Readcount是一个可被多个Reader进程访问的临界资源，因此，应该为它设置一个互斥信号量rmutex。第2章进程管理读者—写者问题分析写者进程到达读者进程到达无进程关掉信号灯，其他所有进程都无法进入有读者自我阻塞有写者自我阻塞无进程是第一位读者，需关掉写者信号灯，不是第一位，改读者数目后，进行阅读操作有读者互斥地修改读者数目，进行阅读操作有写者自我阻塞第2章进程管理读者—写者问题分析写者进程离开读者进程离开打开信号灯，其他所有进程都可以进入互斥地修改读者数目，若是最后一位离开的读者，应该打开写信号灯第2章进程管理利用信号量集机制解决读者—写者问题与前面的读者-写者问题不同，增加了一个限制，即最多只允许RN个读者同时读。为此，又引入了一个信号量L，并赋予其初值为RN，通过执行wait(L,1,1)操作，来控制读者的数目，每当有一个读者进入时，就要先执行wait(L,1,1)操作，使L的值减1。当有RN个读者进入读后，L便减为0，第RN+1个读者要进入读时，必然会因wait(L,1,1)操作失败而阻塞。第2章进程管理VarRN:integer;L,mx:semaphore:=RN,1;beginparbeginreader:beginrepeatSwait(L,1,1);Swait(mx,1,0);…performreadoperation;…Ssignal(L,1);untilfalse;endwriter:beginrepeatSwait(mx,1,1;L,RN,0);performwriteoperation;Ssignal(mx,1);untilfalse;endparendendSwait(mx,1,0)语句起着开关的作用。只要无writer进程进入写，mx=1,reader进程就都可以进入读；一旦有writer进程进入写时，其mx=0，则任何reader进程就都无法进入读；Swait(mx,1,1,L,RN,0)语句表示仅当既无writer进程在写（mx=1），又无reader进程在读(L=RN)时，writer进程才能进入临界区写。第2章进程管理思考题嗜睡的理发师问题：一个理发店由一个有N张沙发的等候室和一个放有一张理发椅的理发室组成。没有顾客要理发时，理发师便去睡觉。当一个顾客走进理发店时，如果所有的沙发都已被占用，他便离开理发店；否则，如果理发师正在为其他顾客理发，则该顾客就找一张空沙发坐下等待；如果理发师因无顾客正在睡觉，则由新到的顾客唤醒理发师为其理发。在理发完成后，顾客必须付费，直到理发师收费后才能离开理发店。试用信号量完成这一过程。第2章进程管理吸烟者问题考虑有三个吸烟者进程和一个经销商进程的系统。每个吸烟者连续不断地做烟卷并抽他做好的烟卷。做一支烟卷需要烟草、纸和火柴三种原料。这三个吸烟者分别掌握有烟草、纸和火柴。经销商源源不断地提供上述三种原料，但他只将其中的两种原料放在桌上，具有另一种原料的吸烟者就可做烟卷并抽烟，且在做完后给经销商发信号，然后经销商再拿出两种原料放在桌上，如此反复。试设计同步算法来描述他们的活动。第2章进程管理吃水果问题桌上有一个空盘，允许存放一只水果，爸爸可向盘内放苹果，妈妈可向盘内放桔子，儿子专等吃盘内的桔子，女儿专等吃盘中的苹果。请用wait、signal操作实现爸爸、妈妈、儿子、女儿四个并发进程的同步与互斥。第2章进程管理阅览室读书问题假定一个阅览室最多可容纳100人，读者进入和离开阅览室时都必须在阅览室门口的一个登记表上进行登记，而且每次只允许一人进行登记操作。请用信号量实现上述进程的同步问题。第2章进程管理音乐爱好者问题有一间酒吧里有3个音乐爱好者队列，第1队的音乐爱好者只有随身听，第2队的音乐爱好者只有音乐磁带，第3队的音乐爱好者只有电池。然而，要听音乐就必须随身听、音乐磁带和电池这三种物品俱全。酒吧老板一次出售这三种物品中的任意两种。当一名音乐爱好者得到这三种物品并听完一首乐曲后，酒吧老板才能再一次出售这三种物品中的任意两种，于是第2名音乐爱好者得到这三种物品，并开始听乐曲。全部买卖就这样进行下去。试用信号量实现他们的同步关系。