操作系统原理 周苏 教学课件 第6章 死锁和饥饿新.ppt

6.5.4 饥 饿 与死锁和活锁非常相似的一个问题是饥饿（starvation）。在动态运行的系统中，在任何时刻都可能请求资源。这就需要一些策略来决定在什么时候谁获得什么资源。虽然这个策略表面上很有道理，但依然有可能使一些进程永远得不到服务，虽然它们并不是死锁进程。 作为一个例子，考虑打印机分配。设想系统采用某种算法来保证打印机分配不产生死锁。现在假设若干进程同时请求打印机，究竟哪一个进程能获得打印机呢？ 6.5.4 饥 饿 一个可能的分配方案是把打印机分配给打印最小文件的进程（假设这个信息可知）。这个方法让尽量多的顾客满意，并且看起来很公平。我们考虑下面的情况：在一个繁忙的系统中，有一个进程有一个文件要打印，每当打印机空闲，系统纵观所有进程，并把打印机分配给打印最小文件的进程。如果存在一个固定的进程流，其中的进程都是只打印小文件，那么，要打印大文件的进程永远也得不到打印机。很简单，它会“饥饿而死”（无限制地推后，尽管它没有被阻塞）。 6.5.4 饥 饿 饥饿可以通过先来先服务资源分配策略来避免。在这种机制下，等待最久的进程会是下一个被调度的进程。随着时间的推移，所有进程都会变成最“老”的，因而，最终能够获得资源而完成。 6.6 哲学家就餐问题 现在来考虑Dijkstra引入的哲学家就餐问题。有五位哲学家住在一栋房子里，在他们的面前有一张餐桌。每位哲学家的生活就是思考和吃饭。通过多年的思考，所有的哲学家一致同意最有助于他们思考的食物是意大利面条。由于缺乏手工技能，每位哲学家需要两把叉子来吃意大利细面条。 6.6 哲学家就餐问题 吃饭的布置很简单，如图6-15所示：一张圆桌上有一大碗面和5个盘子，每位哲学家一个，还有5把叉子。每位想吃饭的哲学家将坐到桌子旁分配给他的位置上，使用盘子两侧的叉子，取面和吃面。问题是：设计一套礼仪（算法）以允许哲学家吃饭。算法必须保证互斥（没有两位哲学家同时使用同一把叉子），同时还要避免死锁和饥饿（此时，该术语的字面含义和算法的意思相同）。 图6-15 哲学家的就餐布局 6.6 哲学家就餐问题 这个问题确实说明了死锁和饥饿中的基本问题。此外，解决方案的研究展现了并发程序设计中的许多困难。哲学家就餐问题可以视为当应用程序中包含并发线程的执行时，协调处理共享资源的一个有代表性的问题。因此，该问题是评价同步方法的一个测试标准。 6.6.1 基于信号量解决方案 图6-16给出了基于信号量的解决方案。每位哲学家首先拿起左边的叉子，然后拿起右边的叉子。在哲学家吃完面后，这两把叉子又被放回桌子。这个解决方案会导致死锁：如果所有的哲学家在同一时刻都感到饥饿，他们都坐下来，都拿起左边的叉子，都伸手拿右边的叉子但都没拿到。在这种有损尊严的状态下，所有的哲学家都会处于饥饿状态。 图6-16 哲学家就餐问题的第一种解决方案 6.6.1 基于信号量解决方案 为避免死锁的危险，可以再另买5把叉子（一种更卫生的解决方案），或者教会哲学家仅用一把叉子吃面。另一种方法是，考虑增加一位服务员，他只允许4位哲学家同时进入餐厅，由于最多有4位哲学家就座，因而至少有一位哲学家可以拿到两把叉子。图6-17显示了这种方案，这里再次使用了信号量，这个方案不会发生死锁和饥饿。 图6-17 哲学家就餐问题的第二种解决方案 6.6.2 基于管程解决方案 图6-18给出了基于管程的哲学家就餐问题的解决方案。这种方案定义了一个含有5个条件变量的向量，每把叉子对应一个条件变量。这些条件变量用来标示哲学家等待的叉子可用情况。另外，用一个布尔向量记录每把叉子的可用情况（true表示叉子可用）。管程包含了两个过程。get_forks函数用于表示哲学家取他/她左边和右边的叉子。如果至少有一把叉子不可用，那么哲学家进程就会在条件变量的队列中等待。这可让另外的哲学家进程进入管程。Release_forks函数用来标示两把叉子可用。 图6-18 哲学家就餐问题 的管程解决为案 6.6.2 基于管程解决方案 注意，这种解决方案的结构和图6-16中的信号量解决方案相似。在这两种方案中，哲学家都是先取左边的叉子，然后取右边的叉子。和信号量不同的是，管程不会发生死锁，因为在同一时刻只有一个进程进入管程。比如，第一位哲学家进程进入管程保证了只要他拿起了左边的叉子，在他右边的哲学家可以拿到其左边的叉子之前（即这位哲学家右边的叉子），就一定可以拿到右边的叉子。 Thanks！ 6.4.2 破坏占有和等待条件 这种方法的一个直接问题是很多进程直到运行时才知道它需要多少资源。实际上，如果进程能够知道它需要多少资源，就可以使用银行家算法。 6.4.2 破坏占有和等待条件 另一个问题是这种方法的资源利用率不是最优的。例如，有一个进程先从输入磁带上读取数据，进