计算机操作系统哲学家进餐问题的教学探讨.pdf

《计算机操作系统哲学家进餐问题的教学探讨.pdf》由会员分享，可在线阅读，更多相关《计算机操作系统哲学家进餐问题的教学探讨.pdf（4页珍藏版）》请在得力文库 - 分享文档赚钱的网站上搜索。

1、隆卜一赢面面蕊确瞳蟹冒垂一一一斓碉碉文章编号：1 6 7 2 5 9 1 3(2 0 0 9)1 4 0 0 8 6-0 3计算机操作系统哲学家进餐问题的教学探讨窦金凤1，曹家宝2，郭忠文1，刘颖健1(1 中国海洋大学，山东青岛2 6 6 10 0；2 青岛阿尔卡特朗讯公司，山东青岛2 6 6 1 0 1)摘要：本文根据多年的教学经验，利用信号量机制、管程机制等思想对哲学家进餐问题进行研究，提出了解决思路，并在教学实验过程中进行了验证。希望与其他相关领域的学习者共享，方便“操作系统”的教学、学习和应用。关键词：进程同步；哲学家进餐问题；信号量；死锁；管程中图分类号：G 6 4 2文献标识码：B

2、1 引言由荷兰学者D i j k s t r a 提出的哲学家进餐问题(T h eD i n n i n gP h i l o s o p h e r sP r o b l e m)是经典的同步问题之一。哲学家进餐问题是一大类并发控制问题的典型例子，涉及信号量机制、管程机制以及死锁等操作系统中关键问题的应用，在操作系统文化史上具有非常重要的地位。对该问题的剖析有助于学生深刻地理解计算机系统中的资源共享、进程同步机制、死锁等问题，并能熟练地将该问题的解决思想应用于生活中的控制流程。2 问题描述(2)如果筷子已被别人拿走，则必须等别人吃完之后才能拿到筷子。(3)任一哲学家在自己未拿到两只筷子吃饭前

3、，不会放下手中拿到的筷子。3 用信号量机制解决问题3 1 记录型信号量筷子是临界资源，一段时间只允许一位哲学家使用。为了表示互斥，用一个信号量表示一只筷子，五个信号量构成信号量数组。由于计算机专业本科生先行课开设C 语言，所以本文中算法用类C 语言描述伪码算法。算法描述如下：磕2 卒五尘誓笔粪二棼曼：辇粤惹z 分型半龛要粤堂五警S e m a p h o r ec h o p s t i c k 5 ：(1，l，1，l，1)；+分别表篁三上：垦桌圭塑五尘孽翌戛昼堡姜，m 誓全要望各擎=昼示5 支筷子+1“。“。“筷子，如图1 所示。哲学家们是交替思考和进餐，饥饿时二：i 占。图1 哲学家进餐描

4、述图第1 位哲学家的活动描述为：哲学家进餐问题可看作是并发进程并发执行时，处理p h i，o s o p h e r n tI。l(i)共享资源的一个有代表性的问题。分析其约束条件：w h i I e(七r u e)(I)只有拿到两只筷子时，哲学家才能吃饭。(本研究得到计算机操作系统课程教学改革研究项目(T J Y 0 8 0 5)的支持，作者简介：窦金凤(1 9 7 6-)，女，山东沂源人，讲师，博士，从事计算机操作系统、传感器网络、海洋学、智能控制方面的研究。万方数据卜一一一1 豳隧型型坚堕一一斓诵思考jw a i t(c h o p s t i c k I )jw a i t(c h o

5、 p s t i c k (I+1)5 )；进餐；S i g n a l(c h o p s t i c k I】)；S i g n a l(c h o p s t i c k (I+1)5 )；当哲学家饥饿时，总是先去拿他左边的筷子，执行w a i t(c h o p s t i c k I )，成功后，再去拿他右边的筷子，执行w a i t(c h o p s t i c k I+1】5)；成功后便可进餐。进餐毕，先放下他左边的筷子，然后再放下右边的筷子。当五个哲学家同时去取他左边的筷子，每人拿到一只筷子且不释放，即五个哲学家只得无限等待下去，引起死锁。3 2 死锁问题的解决预防死锁即是破

6、坏死锁的必要条件之一。通常用下列方法解决死锁问题。3 _ 2 1破坏请求保持条件利用原子思想完成。即只有拿起两支筷子的哲学家才可以进餐，否则，一支筷子也不拿。解法一：利用A N D 机制实现第1 位哲学家的活动描述为：p h i l o s o p h e r(i n tI)w h i l e(t r u e)思考js w a i t(c h o p s t i c k (I+1)5，c h o p s t i c k I )；进餐：S s i g n a l(c h o p s t i c k I ，c h o p s t i c k (I+i)5 )j)解法二：利用记录型信号量机制实现在初

7、始化中增加一个信号量定义：s e m a p h o r em u t e x=1：第1 位哲学家的活动描述：p h i l o s o p h e r(i n tI)w h i l e(t r u e)t思考jw a i t(m u t e x)；w a i t(s t i C k I )jw a i t(S t i c k (I+1)5 )jS i g n a l(m u t e x)；进餐；s i g n a l(s t i c k I )jS i g n a l(S t i c k (I+1)5 )；该方法将拿两只筷子的过程作为临界资源，一次只允许一个哲学家进入。3 2 2 破坏环路等

8、待条件在上述死锁问题中，哲学家对筷子资源的申请构成了有向环路，如图2 所示。图2 环路等待解法一：奇数号哲学家先拿他左边的筷子，偶数号哲学家先拿他右边的筷子。这样破坏了同方向环路，一个哲学家拿到一只筷子后，就阻止了他邻座的一个哲学家吃饭。按此规定，将是1、2 号哲学家竞争I 号筷子；3、4号哲学家竞争4 号筷子。两种算法描述如下：f 1)第1 个哲学家的活动：p h i l o s o p h e r(i n tI)fw h i l e(t r u e)思考jI fI2=1t h e nw a i t(S t i c k I )jw a i t(s t i c k (I+1)5 )j进餐：S

9、i g n a l(s t i c k IJ)；s i g n a l(s t i c k (I+1)5 )；e 1 S ew a i t(s t i c k (I+1)5 )；w a i t(s t i c k I】)j进餐；s i g n a l(s t i c k (I+1)5 )；S i g n a l(s t i c k I )j)(2)第1 个哲学家的活动：p h i l o s o p h e r(i n tI)w h i l e(t r u e)思考jw a i t(c h o p s t i c k I+(I 2)；w a i t(c h o p s t i c k (I+(

10、I+1)2)5 )进餐：s i g n a l(c h o p s t i c k I+(I 2)；S i g n a l(c h o p s t i c k (I+(I+1)2)5 )；万方数据卧卜面磊赢蒜啊豳霭圈碉解法二：至多允许四位哲学家进餐，将最后一个哲学家停止申请资源，断开环路。最终能保证有一位哲学家能进餐，用完释放两只筷子，从而使更多的哲学家能够进餐。增加一个信号量定义s e m a p h o r ec o u n t=4：算法描述第1个哲学家的活动：p h i l o s o p h e r(i n t工)w h i3 _ e(t r u e)思考；w a i t(c o u

11、n t)；w a i t(c h o p s t i o k T )；w a i t(c h o p s t i c k I+1 m o d5)；进餐；s i g n a l(c h o p s t i c k I )；sJ _ g n a l(c h o p s t i c k I+1 m o d5)s i g n a l(c o u n t)解法三：哲学家申请资源总是按照资源序号先大后小的顺序，这样0 3 号哲学家先右后左，但是4 号哲学家先左后右，改变方向，破坏了环路。算法描述第1 个哲学家的活动：p h i l o s o p h e r(i n tI)w h i l e(t r u

12、e)思考；i fI (I+1)5t h e nw a i t(c h o p s t i c k I )jw a i t(c h o p s t i c k I+1 m o d5)；e l s ew a i t(c h o p s t i c k T+1 m o d5)；w a i t(c h o p s t i c k T )j*哲学家总是先取最大序号的筷子*进餐js i g n a l(c h o p s t i c k I )；s i g n a l(c h o p s t i c k I+1 m o d 5)；3 2 3 破坏非剥夺条件打破约束条件(3)，设立优先权。比如，根据哲学家等

13、待筷子的时间设定，时间越大优先权越高，优先权高的可以抢夺优先权低的筷子。4 用管程机制解决哲学家进餐问题在用信号量机制解决同步问题时，往往比较繁琐，采用面向对象的思想，将资源及资源的共享操作封装起来，用管程来管理，实现哲学家进餐问题，使用起来更加方便。算法实现描述如下：4 1建立管程m o n i t o rP C+建立管程+s e m a p h o r ec h o p s t i c k【5 =1 1，1，1，1，1)；X：c o n d i t i o n；定义条件变量+v o i dG e t：(i n tT)定义取筷子过程+T fc h o p s t i c k I =1a n

14、dc h o p s t i c k (i+1)5 =1t h e ng e tt h ec h o p s t i c k I】a n dc h o p s t i c k(i+1)5 ；e l s eX w a i t；+左右筷子没有，则等待+)v o i dP u t(i n ti)*定义放下筷子过程*p u t：t h ec h o p s t i c k【工 a n dc h o p s t i c k(i+1)5 ；T fX q u e n et h e nX s i g n a l j 唤醒等待筷子的哲学家+)4 2 使用管程第1 个哲学家的活动：v o i dp h i l o

15、 s o p h e r(i n tT)w h i l e(t r u e)思考；g e t：(T)j进餐；p u t(I)j5 结束语哲学家进餐问题是操作系统中个常见且复杂的同步问题，它可为多个竞争进程或者线程互斥地访问有限资源这一类问题的解决提供思路。本文根据多年的教学所得，利用不同的机制探讨并提出了这一问题的解决思路。然后提出了解决死锁问题的相关思路，将其应用到教学实验中。提出的解决策略可有效地实现，并且避免饥饿和死锁现象的产生。希望与其他相关领域的学习者共享，方便操作系统的教学、学习和应用。墨参考文献：1 A n d r e wS T a n e n b a u m，M o d e r

16、 n0 p e r a t i n gS y s t e m M 2 n de d E n g l e w o o dC 1 i f f s 2 A b r a h a mS 操作系统概念(影印版)M】6 版北京：高等教育出版社，2 0 0 2 3】汤子瀛，哲凤屏，汤小丹计算机操作系统(修订版)M 西安：西安电子科技大学出版社，2 0 0 2 4】周苏，金海溶，李洁操作系统原理实验 M】北京：科学出版社，2 0 0 3 o万方数据计算机操作系统哲学家进餐问题的教学探讨计算机操作系统哲学家进餐问题的教学探讨作者：窦金凤，曹家宝，郭忠文，刘颖健作者单位：窦金凤,郭忠文,刘颖健(中国海洋大学,山东青岛,266100)，曹家宝(青岛阿尔卡特朗讯公司,山东青岛,266101)刊名：计算机教育英文刊名：COMPUTER EDUCATION年，卷(期)：2009(14)参考文献(4条)参考文献(4条)1.周苏;金海溶;李洁 操作系统原理实验 20032.汤子瀛;哲凤屏;汤小丹 计算机操作系统(修订版)20023.Abraham S 操作系统概念(影印版)20024.Andrew S.Tanenbaum Modern Operating System 2001 本文链接：http:/