2.8 死锁

2.8 死锁

　　计算机系统中有许多独占资源，它们在任一时刻都只能被一个进程使用，如磁带机、绘图仪等独占型外围设备，或进程表、临界区等软件资源。两个进程同时向一台打印机输出将导致一片混乱，两个进程同时进入临界区将导致数据错误乃至程序崩溃。在许多应用中，一个进程需要独占访问不止一个资源，而操作系统允许多个进程并发执行共享系统资源时，此时可能会出现进程永远被阻塞的现象。例如，两个进程分别等待对方占有的一个资源，于是两者都不能执行而处于永远等待。这种现象称为“死锁”。

2.8.1 系统模型

　　一个系统由有限的资源构成，而多个进程竞争使用资源。这些资源被分为多个类型，每个类型有一些相同的实例。内存空间、CPU周期、文件和I/O设备（如打印机和磁带驱动器）是资源类型的例子。如果一个系统有两个CPU，那么资源类型CPU有两个实例。与此类似，资源类型打印机可能有五个实例。
　　如果一个进程请求某一资源类型的一个实例，那么把该类型的任何一个实例分配给这个进程都可以满足请求。否则，这些实例不相同，对资源类型的划分不合适。例如，一个系统可能有两台打印机。如果没有人介意用的是哪个打印机，那么可以把这两个打印机定义为同样的资源类型。然而，如果一台打印机在九楼，另一台在地下室，那么在九楼的使用者可不觉得这两个打印机相同，于是就需要为每个打印机定义独立的资源类型。
　　进程在使用资源之前必须要先请求，并且在使用完毕之后释放。为了完成指定的任务，进程可能请求所需的资源。很显然，进程请求资源的数量不能多于系统中有效的资源数量。换句话说，如果系统中只有两台打印机，那么进程不能够请求三个。
　　在普通操作方式下，进程只能通过如下的顺序使用资源：
　　1．请求：如果请求不能够立刻得到允许（例如，所请求的资源正为另一个进程所用），那么发出请求的进程必须等待，直到它可以获得该资源；
　　2．使用：进程可以对资源进行操作（例如，如果资源是打印机，那么该进程可以在这个打印机上打印）；
　　3．释放：进程释放资源。
　　对资源的请求和释放都要通过系统调用，如请求和释放设备、打开和关闭文件、分配和释放内存等。对其他资源的请求和释放可以通过信号量上的wait 和signal 操作来完成。因此，对于资源的每次使用，操作系统要检查并确保进程已经发出请求并被分配了资源。系统利用一个系统表记录每个资源是空闲的还是被分配了；如果被分配了，要记录分配给了哪个进程。如果一个进程请求一个当前被分配给另一个进程的资源，那么该进程将被添加到这个资源的进程等待队列中。
　　在一个进程集中，如果每个进程都在等待另一个进程发生的事件，那么这个进程集处于死锁状态。我们所关心的事件主要是资源的请求和释放。资源可能是物理资源（如打印机、磁带驱动器、内存空间和CPU周期）或逻辑资源（如文件、信号量、管程）。然而，其他类型的事件也可能导致死锁。
　　为了阐述死锁状态，我们考虑一个拥有三个磁带驱动器的系统。假设系统中有三个进程，每个进程持有一个磁带驱动器。如果现在每个进程都要请求另一个磁带驱动器，那么这三个进程将处于死锁状态。它们每个都在等待事件“磁带驱动器被释放”，而这个事件只能够由其他等待进程中的一个产生。这个例子说明死锁包括同样的资源类型。
　　死锁也可能包括不同的资源类型。例如，考虑一个拥有一台打印机和一个磁带驱动器的系统。假如进程Pi 持有磁带驱动器，进程Pj 持有打印机。如果Pi 请求打印机，Pj 请求磁带驱动器，那么就会发生死锁。开发多线程应用程序的程序员必须非常注意：多线程程序很容易发生死锁，因为多个线程可能会竞争共享资源。