死锁在多道程序环境下多个进程可能竞争一定数量的资源某.DOC

第4章 死锁 在多道程序环境下，多个进程可能竞争一定数量的资源。某个进程申请资源，如果这时资源不可用，那么该进程进入等待状态。如果所申请的资源被其他等待进程占有，那么该等待进程有可能再也无法改变其状态。这种情况称为死锁(deadlock)。前面已经结合信号量讨论了这类情况。 生活中死锁例子可能是Kansas立法机构于20世纪初通过的一个法规，其中说到“当两列列车在十字路口逼近时，它们要完全停下来，且在一列列车开走之前，另一列列车不能启动。” 本章将介绍一些操作系统用于预防或处理死锁的方法。虽然现在绝大多数操作系统并不提供死锁预防功能，但是这些功能也可能很快会加入。随着更多数量的进程、多线程程序、更多的系统资源，死锁问题会变得更普遍。 4.1 死锁的概念 在计算机系统中存在一定数量的资源，分布在若干竞争进程之间共同使用。这些资源可分成多种类型，每种类型有一定数量的实例。资源类型的例子有内存空间、CPU周期、文件、I/O设备（打印机和DVD驱动器）等。如果系统有两个CPU，那么资源类型CPU就有两个实例。类似地，资源类型打印机可能有5个实例。 如果一个进程申请某个资源类型的一个实例，那么分配这种类型的任何实例都可满足申请。否则，这些实例就不相同，且资源类型的分类也没有正确定义。例如，一个系统有两台打印机。如果没有人关心哪台打印机打印哪些输出，那么这两台打印机可定义为属于同一资源类型。然而，如果一台打印机是激光打印，而另一台是喷墨打印，那么对输出质量有要求的用户或许就不会认为这两台打印机是相同的，这样每个打印机就可能需要定义为属于不同类型。 进程在使用资源前必须申请资源，在使用资源之后必须释放资源。一个进程可能会申请许多资源以便完成其指定的任务。显然，所申请的资源数量不能超过系统所有资源的总量。换言之，如果系统只有两台打印机，那么进程就不能申请三台打印机。 在正常操作模式下，进程只能按如下顺序使用资源： ①申请：如果申请不能立即被允许（例如，所申请资源正在为其他进程所使用）．那么申请进程必须等待，直到它获得该资源为止。 ②使用：进程对资源进行操作（例如，如果资源是打印机，那么进程就可以在打印机上打印了）。 ③释放：进程释放资源。 如先前章节所述，资源的申请与释放为系统调用，例如针对设备的有request()/release()系统调用针对文件的有open()/close()系统调用，针对内存的有allocate()/free()系统调用。因此，对于进程或线程的每次使用，操作系统会检查以确保使用进程已经申请并获得了资源。操作系统使用一个专门的表来记录每个资源是否空闲或已被分配，分配给了哪个进程。如果进程所申请的资源正在为其他进程所使用，那么该进程会增加到该资源的等待队列。 这种对资源的申请和等待可能会诱发死锁。当一组进程中的每个进程都在等待一个事件，而这一事件只能由这一组进程的另一进程引起，那么这组进程就处于死锁状态。这里所关心的主要事件是资源获取和释放。资源可能是物理资源（例如，打印机、磁带驱动器、内存空间和CPU周期），也可能是逻辑资源（例如，文件、信号量）。 为说明死锁状态，我们以一个具有三个CD刻录机的系统为例。假定有三个进程，每个进程当前都占用了一个CD刻录机。如果每个进程现在需要另一个刻录机，那么这三个进程会处于死锁状态。每个进程都在等待 “CD刻录机释放” 事件，而这恰恰又只可能由另外两个等待进程来完成。这个例子说明了涉及同一种资源类型的死锁。 死锁也可能涉及不同资源类型。例如，某一个系统有一台打印机和一台DVD驱动器。假如当前进程Pi占有DVD驱动器而Pj占有打印机，如果Pi申请打印机而Pj申请DVD驱动器，那么就会出现死锁。 开发多进程或者多线程应用程序的程序员必须特别关注死锁问题，因为多个线程可能因为竞争共享资源而容易产生死锁。 死锁实力动画演示： //文件名：M4.U1 死锁 当出现死锁时，进程永远不能完成，并且系统资源被阻碍使用，阻止了其他作业开始执行。在讨论处理死锁问题的各种方法之前，先深入讨论一下死锁的特征。 1. 必要条件 如果在一个系统中下面4个条件同时满足，那么会引起死锁。 ①互斥（mutual exclusion）：至少有一个资源必须处于非共享模式，即一次只有一个进程使用。如果另一进程申请该资源，那么申请进程必须等到该资源被释放为止。 ②占有并等待（hold and wait）：一个进程必须占有至少一个资源，并等待另一资源，而这另一个资源正好为其他进程所占有。 ⑧非抢占（non-preemptive）：资源不能被抢占，即资源只能在进程完成任务后主动释放。 ④循环等