经典同步问题的死锁解决方案

谢士春

宿州学院信息工程学院,安徽宿州,234000



经典同步问题的死锁解决方案

谢士春

宿州学院信息工程学院,安徽宿州,234000

哲学家就餐问题和吸烟者问题是两个经典的进程同步问题模型，它们均是对多个竞争进程互斥地访问有限资源(例如I/O设备)问题的建模。针对这两类进程步问题，分析不合理地使用PV操作导致死锁产生的原因，提出了阻止死锁产生的详细方案。对此类问题的深度剖析有助于学生深刻地理解操作系统原理中的资源共享、进程同步及死锁等重要概念。

死锁；进程同步；信号量；哲学家就餐问题；吸烟者问题

1 预备知识

在多道程序环境下，进程有异步和同步两种并发执行方式。异步执行是指运行中的各进程在操作系统的调度下以不可预知的速度向前推进。异步执行的进程大多没有时序要求，不存在“执行结果与语句的特定执行顺序有关”的条件竞争。然而存在一类协作进程，“保证数据的一致性”的前提要求它们必须按某种特定顺序执行，并且遵守如下两种限制[2]。

(1)R1(顺序化执行)：进程A的eventA事件必须发生在进程B的eventB事件之前；

(2)R2(互斥执行)：进程A的eventA事件与进程B的event事件B不能同时发生。

把上述限制下多进程的运行状态叫作进程的同步执行。进程同步执行时因存在着明显的执行上的时序要求而相互等待。如果说进程异步是进程并发执行的自然结果，那么进程同步则需要程序员通过准确嵌入一些诸如加解锁、信号量、管程等关键技术来确保实现。

信号量无疑是一个较为理想的同步工具。它最早由荷兰科学家Edsger Dijkstra于1965年提出，该工具具有如下三个优点[2]：(1)仅需要两个基本操作即可完成进程的同步和互斥，而且两个原子操作代码简洁高效，易于扩充；(2)精心设计的信号量对象类似一条条“触发器”规则，加上信号量机制的强制作用可以帮助程序员少犯错误；(3)信号量已在很多系统中实现，解决方案中有意识地选用信号量无疑将使进程更“瘦身”，运行更高效。

信号量技术的引入是对早期忙等型(busy waiting)进程控制变量(例如各种软件锁、Dekker算法和Peterson算法中各类标志变量)是个巨大的提升，但在使用过程中仍然存在不少缺点：一是不能随时读取信号量的值，必要时须重复定义一个跟踪信号量值的普通变量，二是程序员对信号量的PV操作的正确使用与否没有任何控制和保证(后来引入管程和条件变量，PV操作完全由编译器而非程序员安排)，不合理地使用将导致进程饥饿甚至死锁。

死锁应尽可能阻止。系统死锁导致诸进程将进入无法向前推进的僵持状态，除非借助于外力[3]。死锁的原因除了系统资源偏少之外，更多的是进程推进速度不当，或者说进程申请和释放信号量的顺序不合理所致，毕竟系统提供的资源是有限的。以哲学家就餐问题为例，若派发给每位哲学家一双筷子(更准确地说，6支就足够)，则一定不会死锁。事实上，若信号量的PV操作顺序处置得当，5支筷子同样也可以保证不会发生死锁。

其实，随着时代的变迁和交通、印刷业、传媒业的迅猛发展，再加上跨地域之间的艺术交流的日趋频繁，早年以地域为特征的所谓“南宗”“北宗”乃至“海派”“浙派”，其地域特征和艺术分野正在慢慢消弭，如果溯本求源，有些流派本来就是同源同宗，一些流派之间不过是同干异枝或是同源异流的关系。

2 经典同步问题的死锁解决方案

2.1 哲学家就餐问题

哲学家就餐问题(The Dinning Philosophers Problem)是经典的同步问题之一，对于多个竞争进程互斥地访问有限资源(例如I/O设备)这一类问题的建模非常有用。用信号量机制解决本问题的基本算法[2-4]见表1。

表1 有死锁风险的方案

当5个哲学家进程并发执行时，某个时刻恰好每个哲学家进程都执行语句2，并且成功申请到第i支筷子(相当于5个哲学家同时拿起他左边的筷子)，接着他们又都执行语句3，申请第i+1支筷子。此时每个哲学家仅拿到一支筷子，另外一支只得无限等待下去，引起死锁。在给出几种有效阻止死锁的方案之前，首先给出两个断言：

(1)系统中有N个并发进程。若规定每个进程需要申请2个某类资源，则当系统提供N+1个同类资源时，无论采用何种方式申请资源，一定不会发生死锁。

分析：N+1个资源被N个进程竞争，由抽屉原理可知，则至少存在一个进程获得2个以上的同类资源。这就是前面提到的哲学家就餐问题中5个哲学家提供6支筷子时一定不会发生死锁的原因。

(2)系统中有N个并发进程。若规定每个进程需要申请R个某类资源，则当系统提供K=N*(R-1)+1个同类资源时，无论采用何种方式申请使用，一定不会发生死锁。

分析：在最坏的情况下，每个进程都申请到R-1个同类资源，此时它们均阻塞。试想若系统再追加一个同类资源，则N个进程中必有一个进程获得R个资源，死锁解除。

结合以上分析，哲学家就餐问题可以被抽象描述为：系统中有5个并发进程，规定每个进程需要申请2个某类资源。若系统提供5个该类资源，在保证一定不会产生死锁的前提下，最多允许多少个进程并发执行？假设允许N个进程，将R=2，K=5带入上述公式，有N*(2-1)+1=5 ，所以N=4。也就意味着，如果在任何时刻系统最多允许4个进程并发执行，则一定不会发生死锁。大多数哲学家就餐问题死锁阻止算法都是基于这个结论。

方案1：增加一个信号量，控制最多有4个进程并发执行，算法见表2。

表2 无死锁风险的方案之一

方案2：从5位哲学家中选择其中一位改变申请筷子的次序，比如先右后左，其余哲学家仍采用先左后右，算法见表3。

当5个进程并发执行时，某时刻0号进程与4号进程均执行语句2，同时竞争0号筷子，争夺结果必然会造成一方阻塞，从而导致整个系统变成4个哲学家竞争5支筷子的局面，则一定不会发生死锁。

塔内鲍姆(Tanenbau)提供了一个阻止死锁的算法[5]。该算法设置一个状态变量，用来指明每个哲学家的状态是思考中、就餐中，还是等待就餐(饥饿中)；一个信号量用来互斥访问此状态变量；另一信号量指示哲学家是否可以开始就餐(仅当左右筷子均可用时才可以)。需要注意的是第二个信号量不再代表筷子资源，而是“左右筷子均可用”的标志，这里不再赘述。除此之外，还有规定奇数号哲学家与偶数号哲学家采用不同的申请次序等算法。判定此类算法性能优劣的标准之一是能否达到最多允许4个哲学家同时就餐这一最大并发度，其次信号量的使用是否高效，是否存在着误用和滥用问题也是设计算法时所要考虑的。

2.2 吸烟者问题(CigaretteSmokersProblem)

问题描述：一个烟草代理商和三个抽烟者。抽烟者若要抽烟，必须具有烟叶、烟纸和火柴。三个抽烟者中，一个有烟叶、一个有烟纸、一个有火柴。烟草代

表3 无死锁风险的方案之二

理商会源源不断地分别供应烟叶、 烟纸和火柴，并将它们放在桌上。如果桌上放的是烟纸和火柴， 则有烟叶的抽烟者会拾起烟纸和火柴，制作香烟，然后抽烟；其他类推。试用信号量同步烟草代理商和三个抽烟者。

方案1：用信号量机制解决问题的算法见表4。设想一下，若某时刻代理商提供烟叶和烟纸，因携带火柴的烟客1等待烟叶, 它可能被唤醒而执行语句1；而烟客2也在等待烟纸，所以它也很有可能被唤醒而执行语句1，此时两线程均在语句2阻塞，造成死锁。

表4 有死锁风险的方案

方案2：一个网络上比较常见的死锁解决方案，见表5。尽管该算法无死锁风险，但不是一个好的解决方案，因为方案违背了SuhasPati最初设计这个典型问题的初衷[2]。这里的代理商进程相当于操作系统，它的作用是仅仅向多个用户进程提供资源，不可能也不需要知道他们中间谁在等待什么资源以及如何使用这些资源，因此在这一点上SuhasPati的要求是合理的。用户进程对这些资源的使用对操作系统来讲是透明的，所以方案2中的代理商进程显然违反了这一分层设计原则。基于方案1代理商进程比较忠实地反映SuhasPati的初衷，在保留此算法的基础上，Parnas提出了下面的解决方案[2,6]。

表5 无死锁风险的方案之一

方案3：引入3个名为“推送进程”(pusher)的辅助进程，负责处理agent进程放置的制烟原料信息，之后再转发给相应的烟客进程。主要工作是推送进程完成，agent进程同方案一，smoker1,smoker2,smoker3同方案2，算法不再赘述。这里只给出3个推送进程的伪代码，见表6。

表6 无死锁风险的方案之二

算法分析：agent进程随机产生两种原料，例如烟叶和烟纸，此时信号量tabacoo和paper增至1，系统分别唤醒pusherTobacoo和pusherPaper两进程：若先调度进程pusherTobacoo，由于isPaper和isMatch均为假，执行语句10，将isTobacoo设置为真；再调度进程pusherPaper时，执行语句3，将信号量matchSem曾至1，系统唤醒携带火柴的烟客进程smoker1。同样，若先调度进程pusherPaper运行结果与前面一致。

3 结束语

哲学家就餐问题和吸烟者问题是两类经典进程的同步问题，它可为多个进程互斥地访问有限资源这一类问题的解决提供思路，对问题的深度剖析有助于学生深刻地理解操作系统原理中的资源共享、进程同步及死锁等问题。笔者根据多年的教学经验，分析了不合理地使用PV操作导致死锁产生的原因，总结并提出了阻止死锁产生的方案。方案以实现进程或线程最大限度地并发以及系统资源透明使用为优化目标，它们的提出对读者以后解决此类问题具有很大的启发性。

[1]GregoryR.Andrews.ConcurrentProgramming:PrinciplesandPractice[M].NewJersey:Addison-Wesley,1991:1-3

[2]AllenB.Downey.TheLittleBookofSemaphores[EB/OL].[2014-10-18]．http://greenteapress.com/semaphores

[3]汤小丹,梁红兵,哲凤屏,等.计算机操作系统[M].3版.西安：西安电子科技大学出版社,2007:103-104

[4]窦金凤,曹家宝,郭忠文,等.计算机操作系统哲学家进餐问题的教学探讨[J].计算机教育,2009,14(3):86-88

[5]AndrewS.ModernOperatingSystems[M].2nded.UpperSaddleRiver:prenticehall,2009:55-56

[6]DavidL.Parnas.Onasolutiontothecigarettesmokers'problemwithoutconditionalstatements[J].CommunicationsoftheACM,1975,18:181-183

(责任编辑：汪材印)

10.3969/j.issn.1673-2006.2015.04.027

2014-12-10

安徽省高校质量工程项目“计算机科学与技术专业综合改革试点”(NO.2012zy075)。

谢士春(1970-),安徽濉溪人,硕士,讲师,主要研究方向：计算机操作系统、程序设计、图像识别方面的教学和研究。

TP311.12

A

1673-2006(2015)04-0094-05