死锁（Deadlock）简析

参考了学堂在线操作系统课程30240243X

死锁是操作系统中进程共享资源时由于循环占有并等待资源而造成的无限期等待状态。

比如A进程占有资源R1，需要资源R2，而B进程占有资源R2并需要资源R1，A、B进程互相等待对方完成任务并释放资源，形成了死锁。

死锁条件与预防（Prevention）方案

形成死锁需要同时满足4个条件（逻辑上的关系不很明确，但这4个讨论足够关键）：

1.互斥

即一个资源只能同时被一个进程所使用。可以想象，如果一个资源可以被同时使用，那么不会出现等待资源的情况。

预防

通过封装使独占资源可以同时使用，比如在打印机内部维护打印缓存队列。

2.持有并等待

至少持有一种资源，同时至少等待一种资源。

预防

持有资源可能会被其他进程请求，不持有则不可能被请求，无法形成环，我们可以要求进程在申请资源时保证其不持有任何资源。有时候这条规则变成进程初始化时必须申请完所有需要的资源。

3.非抢占

资源只能由使用它的进程完成任务后释放。

预防

如果允许抢占，即释放需要而被占用的资源，那么不需要等待，不会形成环。我们也要求只有在进程能同时获取（或抢占）到所有资源时才分配，这一点和解除持有并等待类似。

4.循环等待

进程间存在一个循环。如进程A需要进程B的资源，进程B需要进程C的资源，进程C需要进程A的资源。

预防

对资源排序，要求进程按顺序申请资源。比如进程A需要R1、R2，于是先申请R1、R2，结束任务后进程B再申请，但B可以先申请R3。也就是说，申请资源的顺序一定要符合资源的排序，资源申请形成了一个单向的通道。

预防的缺点

预防可能会导致进程等待资源时间变长很多，对效率影响很大，因此很少采用。

死锁避免（Deadlock Avoidance）

利用额外的先验信息，在进程请求分配资源时判断分配是否可能造成死锁，有可能则不分配。

避免的要求

要求进程声明所需的最大资源数，操作系统限制提供的资源，确保能满足进程所需的所有资源。这种方法要求分配资源时动态检查，不会出现死锁时分配资源。

检查要求在占有资源的所有进程中，存在一个安全序列使得这些进程能够执行完他们的所有任务。我们给这些进程编号P[1]到P[N]，要求P[I]请求的资源<=当前空闲资源+P[1到I-1]占有的所有资源。换句话说，前面的进程完成任务后会释放资源，这部分资源加上原本就可用的资源必须能够满足后面请求资源的进程，如果不够则有可能出现死锁。

银行家算法（Banker's Algorithm）

银行在提供贷款时有两个条件，一个是客户申请贷款时告知银行他需要多少钱并能用完后归还，另一个是银行提供的贷款不超过自身持有的资金但尽量满足客户需求。银行家算法与此类似。

我们假设系统中有n个线程，m种类型的资源。

于是我们可以画一个Max矩阵（n*m的总需求量矩阵）表示线程Ti最多需要请求Rj类型的资源Max[i,j]个实例；已经分配的资源用Allocation矩阵（n*m）表示；还需要的资源（Max-Allocation）用Need矩阵表示；还可以分配的（空闲的）资源用Available矩阵表示。

操作系统每次分配资源时都要检查，如果分配后，存在一个进程顺序｛P1，P2，...｝使得他们按顺序申请资源而不会造成某个进程无法取得其所需的最大资源，那么分配完的情况是安全的，操作系统同意分配。不安全状态不一定是死锁，但随着进程继续最终会变成死锁状态。

银行家算法允许互斥、部分分配和不可抢占，能够提高资源利用率，但应用程序提前声明所需的最大资源量是很难实行的。

死锁检测和恢复（Deadlock Detection & Recovery）

监测到死锁后用结束部分进程、强制释放资源或回滚等方法解除死锁。由于死锁发生概率小，预防开销大，Windows、UNIX以及数据库系统都采用这种方法。