第八章 死锁
更新日期：2005.3.21
（文中图片来自原作者的幻灯片）
在多道程序设计环境中，多个进程可能要为有限的资源展开竞争。进程请求资源；如果当前这些资源不可用，那么该进程进入等待状态。正在等待的进程可能不会再改变状态，因为它所请求的资源一直被其它进程所持有。这种情况被称为死锁（deadlock）。我们已经通过联系信号量在第七章简要的讨论了这个问题。
或许对死锁的最好阐述来自于20世纪初期的堪萨斯州立法机关。（Perhaps the best illustration of a deadlock can be drawn from a law passed by the Kansas legislature early in the 20th century.）它说“当两列火车在交叉路口相遇时，他们两个都要停下而不能启动，直到其中的一个开走”。
我们将在本章描述操作系统用于预防和处理死锁的方法。当前大多数操作系统并没有提供这种机制，但是可能不久就会添加上去。看到当前的趋势，包括进程不断增多数量、多线程程序、系统中包含越来越多的资源和对生命周期长的文件和数据库服务器的侧重（不是批处理系统），死锁将更加普遍。
8.1 系统模型
一个系统有有限的资源构成，而多个进程竞争使用资源。（A system consists of a finite number of resources to be distributed among a number of competing processes.）这些资源被分为多个类型，每个类型有一些相同的实例（instance）。内存空间、CPU周期、文件和I/O设备（如打印机和磁带驱动器）是资源类型的例子。如果一个系统有两个CPU，那么资源类型CPU有两个实例。与此类似，资源类型打印机可能有五个实例。
如果一个进程请求某一资源类型的一个实例，那么把该类型的任何一个实例分配给这个进程都可以满足请求。否则，这些实例不相同，对资源类型的划分不合适。例如，一个系统可能有两台打印机。如果没有人介意用的是哪个打印机，那么可以把这两个打印机定义为同样的资源类型。然而，如果一台打印机在九楼，另一台在地下室，那么在九楼的使用者可不觉得这两个打印机相同，于是就需要为每个打印机定义独立的资源类型。
进程在使用资源之前必须要先请求，并且在使用完毕之后释放。为了完成指定的任务，进程可能请求所需的资源。（A process may request as many resources as it requires to carry out its designated task.）很显然，进程请求资源的数量不能多于系统中有效地资源数量。换句话说，如果系统中只有两台打印机，那么进程不能够请求三个。
在普通操作方式下，进程只能通过如下的顺序使用资源：
1. 请求：如果请求不能够立刻得到允许（例如，所请求的资源正为另一个进程所用），那么发出请求的进程必须等待，直到它可以获得该资源。
2. 使用：进程可以对资源进行操作（例如，如果资源是打印机，那么该进程可以在这个打印机上打印）。
3. 释放：进程释放资源。
正如在第三章中解释的，对资源的请求和释放都要通过系统调用。如：请求和释放设备、打开和关闭文件、分配和释放内存系统调用。对其它资源的请求和释放可以通过信号量上的wait和signal操作来完成。因此，对于资源的每次使用，操作系统要检查并确保进程已经发出请求并被分配了资源。系统利用一个系统表记录每个资源是空闲的还是被分配了；如果被分配了，要记录分配给了哪个进程。如果一个进程请求一个当前被分配给另一个进程的资源，那么该进程将被添加到这个资源的进程等待队列中。
在一个进程集中，如果每个进程都在等待另一个进程发生的事件，那么这个进程集处于死锁状态。我们所关心的事件主要是资源的请求和释放。资源可能是物理资源（如：打印机、磁带驱动器、内存空间和CPU周期）或逻辑资源（如：文件、信号量、管程）。然而，其它类型的事件也可能导致死锁（例如在第四章中讨论的IPC机制）。
为了阐述死锁状态，我们考虑一个拥有三个磁带驱动器的系统。假设系统中有三个进程，每个进程持有一个磁带驱动器。如果现在每个进程都要请求另一个磁带驱动器，那么这三个进程将处于死锁状态。它们每个都在等待事件“磁带驱动器被释放”，而这个事件只能够由其它等待进程中的一个产生。这个例子说明死锁包括同样的资源类型。
死锁也可能包括不同的资源类型。例如，考虑一个拥有一台打印机和一个磁带驱动器的系统。假如进程Pi持有磁带驱动器，进程Pj持有打印机。如果Pi请求打印机，Pj请求磁带驱动器，那么就会发生死锁。
开发多线程应用程序的程序员必须非常注意：多线程程序很容易发生死锁，因为多个线程可能会竞争共享资源。
详细内容请见 http://www.tulipsys.com
