本文共 1799 字，大约阅读时间需要 5 分钟。

死锁（产生的条件、死锁避免（银行家算法）、死锁检测）

定义

线程死锁是指由于两个或多个线程互相持有对方所需要的资源，导致这些线程处于等待状态，无法前往执行。当线程进入对象的synchronized代码块时，便占有了资源，直到它退出该代码块或者调用wait方法，才释放资源。在此期间，其他线程将不能进入该代码块。当线程互相持有对方所需要的资源时，会互相等待对方释放资源，如果线程都不主动释放所占有的资源，将产生死锁。

产生的条件

要产生死锁，必须同时满足以下条件：

互斥条件：进程对所分配到的资源不允许其他进程访问，若其他进程访问该资源，只能等待，直至占有该资源的进程使用完成后释放该资源。

请求和保持条件：进程获得一定的资源后，又对其他资源发出请求，但是该资源可能被其他进程占有，此时请求阻塞，但该进程不会释放自己已经占有的资源。

不可剥夺条件：进程已获得的资源，在未完成使用之前，不可被剥夺，只能在使用后自己释放。

环路等待条件：进程发生死锁后，必然存在一个进程-资源之间的环形链，环路中每个进程都在等待下一个进程所占有的资源。

如果上述情况中的任何一个条件不成立，死锁就不会发生。破坏其中任意一个条件可以解决死锁问题。

死锁避免

为了避免死锁，可以采取以下措施：

破坏请求和等待条件：所有进程在开始运行之前，必须一次性地申请其在整个运行过程中所需要的全部资源。

破坏不可抢占条件：当进程未能获得新请求的资源时，释放已占有的资源。

破坏环路等待条件：系统给每类资源赋予一个序号，每个进程按编号递增的请求资源，释放则相反。

银行家算法

问题

一个银行家共有20亿财产。第一个开发商已贷款15亿，资金紧张还需3亿。第二个开发商已贷款5亿，运转良好能收回。第三个开发商欲贷款18亿。

在这种情况下，如果你是银行家，你应该如何处理？一个常规的想法是先等待第二个开发商收回5亿，然后再将3亿贷款给第一个开发商，等其收回18亿后，再将钱贷款给第三个开发商。

实现思想

允许进程动态地申请资源，但在每次实施资源分配之前，先计算资源分配的安全性。如果此次资源分配安全，即资源分配后，系统能按某种顺序来为每个进程分配其所需的资源，直至满足所有进程的最大需求，使每个进程都能顺利完成任务，那么便将资源分配给进程，否则不分配资源，让进程等待。

数据结构

可利用资源向量Available：是一个含有m个元素的数组，表示系统中每类资源的可用数目。

最大需求矩阵Max：一个n×m的矩阵，表示每个进程对每类资源的最大需求。

分配矩阵Allocation：一个n×m的矩阵，表示当前已分配给每个进程的资源数目。

需求矩阵Need：一个n×m的矩阵，表示每个进程尚需获取的资源数目。

上述矩阵间满足关系：Need[i,j] = Max[i,j] - Allocation[i,j]。

算法流程

每次资源请求时，系统检查：

请求的资源数量不超过进程当前需求。

系统中可用资源数量不少于请求的数量。

系统试探性地将资源分配给进程，并更新数据结构。

执行安全性检查，判断是否能在资源分配后确保所有进程能正常完成任务。

如果安全，正式分配资源；否则，恢复原有资源分配状态，让进程等待。

死锁检测

每种类型一个资源的死锁检测

每种资源类型都有一个资源。例如，打印机是一个资源，但不会超过一个。

如果存在一个或多个环，说明存在死锁，处于环中的任意一个进程都是死锁进程。

每种类型多个资源的死锁检测

如果有多种相同的资源，需要采用矩阵方法检测死锁。构造一个矩阵，检测从P1到Pn的死锁。

构造两个数组：C（当前分配矩阵）和 R（请求矩阵）。Cj表示进程Pi持有资源j的数量。Rij表示进程Pi请求的资源j的数量。

通过向量比较和标记，检测是否存在环。未被标记的进程判定为死锁进程。

检测时机

每当有资源请求时进行检测（资源检测频率高，可能带来较高的CPU负担）。

每隔k分钟进行检测（适合系统空闲时）。

死锁恢复

抢占恢复：强制剥夺某个资源，恢复系统的可用性，但可能导致数据不一致。

回滚恢复：周期性地记录系统状态，遇到死锁时回滚到之前的状态。

杀死进程恢复：直接终止死锁进程，但可能导致资源无法利用。

鸵鸟算法

最简单的解决办法是使用鸵鸟算法，假装死锁根本不存在。

工程师认为死锁发生的概率很低，可能由其他系统故障引起，优先解决其他问题。

转载地址：http://ipuiz.baihongyu.com/