利用管程概念求解哲学家进餐问题

2015-03-25詹劲松

长春大学学报 2015年12期

詹劲松

(福建师范大学福清分校电子与信息工程学院，福建福清350300)

0 引言

哲学家进餐问题是操作系统中经典的同步问题，它需要在多个进程或线程之间分配多个资源，使进程(线程)能向前推进。我们的目的是要在这种情况下采用某种策略，预防死锁的发生。管程是一种高级的同步构造，利用Java 高级别并发对象可以实现管程概念。通过管程可以方便地实现这种死锁预防策略。

1 哲学家进餐问题

5 位哲学家围坐在一张圆桌旁边，圆桌中央放置一碗米饭，每两人之间放置一支筷子。每位哲学家思考、饥饿，然后吃饭。为了吃饭，他必须拿起与他相邻的左、右两支筷子。他不能从别的哲学家手里抢夺筷子。吃完饭后，他会放下筷子，并又开始思考。

如果对每个哲学家的吃饭过程不加限制，很快就进入这样一个状态，每人抢得一支筷子，结果谁也吃不了饭，也就是进入了死锁的状态。产生死锁有4 个必要条件，互斥、占有并等待、非抢占和循环等待［1］。如果能够使一组进程(线程)在推进的整个过程中，这4 个条件之一或更多保持不成立，那么这组进程(线程)就不会陷入死锁状态。哲学家问题的死锁预防有多种方法。其中一种是:每位哲学家要能取到手边的两支筷子才开始吃饭，否则他一支筷子也不取。这种解法的实质是预先分配需要的全部资源，从而破坏产生死锁的占有并等待这个必要条件。本文就是采用这种解法。

2 管程

为了解决同步问题程序中使用信号量容易出错的问题，70 年代初，P.B.Hansen 和C.A.R.Hoare 等人提出了管程的概念。其基本思想是:把分散于各进程(线程)中的临界区集中起来统一管理，并把共享资源用数据结构来抽象表示，建立一个管程结构来管理相应的访问［2］。管程结构确保一次只能有一个进程(线程)在管程内活动。

管程结构通过防止对一个资源的并发访问来达到了实现临界区的目的，从而提供了实现互斥的手段，但是管程并没有提供进程(线程)和其他进程(线程)之间同步的途径。当一个进程(线程)进入了管程并调用了管程的一个过程。如果该过程在执行时发现资源不能得到满足，当然应该让此进程(线程)阻塞，同时需要开放管程，让之前被阻挡在管程外边的进程(线程)之一进入。为此需要定义一个另外的同步机制，这可由条件(Condition)结构来提供。条件变量只有操作wait()和signal()。前者用于阻塞调用的进程(线程)。后者用于启动一个被阻塞的进程(线程)。

3 Java 高级别并发对象

在Java SE 5.0 之前，用Java 实现管程有些不精确。因为线程之间的同步只能使用Object 类的wait()，和notify()或notifyAll()来实现。只能向任何一个被阻塞线程或者全部被阻塞线程发送启动消息，不能准确定位向某一个被阻塞线程发送消息。Java SE 5.0 引入了ReentrantLock 类和Condition 接口［3］，改变了这个状况。通过调用Condtiton 对象的signal 方法，某个哲学家吃完饭，放下筷子就可以准确地向其相邻的两位哲学家线程发出启动信号。