欢迎来到天天文库
浏览记录
ID:41092382
大小:57.00 KB
页数:4页
时间:2019-08-16
《哲学家就餐问题--计算机操作系统》由会员上传分享,免费在线阅读,更多相关内容在工程资料-天天文库。
1、13、分析下面用信号量解决哲学家进餐问题的同步算法是否满足同步机制的准则。若不满足,说明为什么,并给出满足同步机制准则的同步算法。Varchopstick:array[0,…,4]ofsemaphore;Chopstick[0]:=chopstick[1]:=chopstick[2]:=chopstick[3]:=chopstick[4]:=1;Pi:repeatwait(chopstick[i]);wait(chopstick[(i+1)mod5]);eat;signal(chopstick[i]);signal(chopstick[(i+1)mod5]);think;un
2、tilfalse;答:该算法不满足同步机制的“有限等待”原则,即每个哲学家都只拿一个筷子时就会产生死锁。下面给出三种解决办法。1、互斥申请资源设置信号量mutex初值为4,即最多可以有4个哲学家同时申请筷子。这样保证了4个哲学家中至少有1人可以拿到两个筷子就餐而不发生死锁。mutex=4Pi(i=0,1,…,4);Repeatwait(mutex);wait(chopstick[i]);wait(chopstick[(i+1)mod5]);signal(mutex);Eat;signal(chopstick[i]);signal(chopstick[(i+1)mod5]);t
3、hink;untilfalse;2、改变申请资源次序规定奇数号哲学家先拿起左边的筷子,然后再去拿右边的筷子;偶数号哲学家正好相反。也即拿到一个筷子的哲学家才有权去拿下一个筷子,而没有拿到筷子的哲学家则退出竞争。这样就不会出现5个哲学家都只拿一个筷子的情况。pi(i=0,1,…4)repeatifodd(i)then/*如果i为奇数*/beginwait(chopstick[i]);wait(chopstick[(i+1)mod5]);endelsebeginwait(chopstick[(i+1)mod5]);4wait(chopstick[i]);endeat;signal
4、(chopstick[i]);signal(chopstick[(i+1)mod5]);think;untilfalse;3、采用AND型信号量机制AND型同步机制的思想是:将进程所需要的所有资源一次性全部分配给它,但只要有一个资源不能分配给该进程,则其它所有资源也不能分配给它。pi(i=0,1,…,4)repeatSwait(chopstick[i],chopstick[(i+1)mod5]);eat;Ssignal(chopstick[(i+1)mod5],chopstick[i);think;untilfalse;15、设有5位哲学家,共享一张放有5把椅子的桌子,每人分
5、得一把椅子。但是,桌上总共有5支筷子,在每人两边分开各放一支。哲学家只有在饥饿时方可分两次从两边抢占筷子就餐。就餐的条件如下:①哲学家想吃饭时,先提出吃饭请求。②提出吃饭请求时,并拿到两支筷子后,方可吃饭。③如筷子已被他人获得,则必须等待此人吃饭后才能获取筷子。④任一哲学家在自己未拿到两支筷子吃饭之前,决不放下手中的筷子。⑤刚开始就餐时,只允许两个哲学家吃饭。试问:1)描述一个保证不会出现两个邻座同时要求吃饭的算法。2)描述一个即没有两邻座同时吃饭,又没有人饥饿的算法。3)在什么情况下,5个哲学家全部吃不上饭。答为了保证不会出现相邻的两个哲学家同时提出吃饭的请求,特设置信号量
6、S[0]~S[4]来互斥两两相邻的哲学家吃饭请求,其初值均为1。注意:对第I个哲学家来说,他的两个邻座分别为(I+1)mod5和(I+4)mod5,第I个哲学家的左右邻座定位如图所示。4i(I+1)mod5(I+2)mod5(i+4)mod5(I+3)mod5此外,5支筷子也为临界资源,即chopstick[0]~chopstick[4]初值为1。由于禁止两相邻的哲学家同时申请,因此也就不存在同时竞争请求筷子的问题。(但可能申请的筷子正在别的哲学家手上),故可以去掉公用信号量mutex,相应的同步算法如下:begins[0]=s[1]=s[2]=s[3]=s[4]=1;cho
7、pstick[0]=chopstick[1]=chopstick[2]=chopstick[3]=chopstick[4]=1;cobeginPi(I=0,1,2,3,4);BeginRepeatP(s[I]);/*第I个哲学家提出吃饭请求*/P(s[(I+1)mod5])/*禁止左邻哲学家提出申请;如果左邻哲学家已经提出申请,则阻塞哲学家I的此次请求*/P(s[(I+4)mod5]);/*禁止右邻哲学家提出申请;如果右邻哲学家已提出申请,则阻塞哲学家I的此次申请*/P(chopstick[I]);P(
此文档下载收益归作者所有