死锁(Deadlock)是在多任务环境中的一种资源竞争问题,其中两个或多个进程(线程)互相等待对方持有的资源,导致所有进程都无法继续执行。死锁是一种非常棘手的问题,因为它会导致系统无法正常运行。
举个例子。比如买东西,如果商家要先拿钱才给东西,顾客要先拿到东西才给钱,那么会发生死锁。
另外,哲学家就餐问题是一个死锁的经典例子。
死锁需要满足四个必要条件:
死锁只有在四个条件同时满足时发生,预防死锁必须至少破坏其中一项。
只要破坏死锁的四个必要条件的任意一个,便可避免死锁。
最常见的有两个算法:
资源有序分配法通过破坏「环路等待条件」避免死锁。
线程 A 和 线程 B 获取资源的顺序要一样,当线程 A 是先尝试获取资源 A,然后尝试获取资源 B 的时候,线程 B 同样也是先尝试获取资源 A,然后尝试获取资源 B。也就是说,线程 A 和线程 B 总是以相同的顺序申请自己想要的资源。
银行家算法是由 Edsger W. Dijkstra 于 1965 年 THE 操作系统设计的一种避免死锁产生的算法。它以银行借贷系统的分配策略为基础,判断并保证系统安全运行。
在银行中,银行拥有的资金是有限的。当客户向银行贷款时,银行家会评估客户申请贷款的数量是否超过可用资金,如果不超过则放贷,如果超过则客户需要等待。在这样的描述中,银行家好比操作系统,资金就是资源,客户相当于要申请资源的进程。
银行家算法的核心思想是「通过预先判断资源分配是否安全,来决定是否分配资源」。
当一个进程申请资源的时候,银行家算法先「试探」分配给该进程资源,然后判断分配后的系统是否处于安全状态。如果处于安全状态,则资源请求是安全的,分配资源;如果脱离安全状态,则资源请求不安全,该进程继续等待。
那什么是安全状态?
如果存在一个由系统中「所有进程」构成的安全序列 P1, …, Pn,则系统处于安全状态。
那什么是安全序列?
介绍安全序列之前需要知道银行家算法涉及的四种变量:
其中 Need[i,j]=Max[i,j]-Allocation[i,j]。i 和 j 表示第 i 个进程和第 j 种资源。
假设进程 P1 申请某个资源,银行家算法先试探地分配给它(当然先要看看当前资源池中的资源数量够不够),若申请的资源数量小于等于Available。然后接着判断分配给 P1 后剩余的资源,能不能使进程队列的某个进程执行完毕。若没有进程可执行完毕,则系统处于不安全状态(即此时没有一个进程能够完成并释放资源,随时间推移,系统终将处于死锁状态)。
若进程 P2 可执行完毕,则假设回收已分配给 P2 的资源(剩余资源数量增加),把这个进程标记为可完成,并继续判断队列中的其它进程。若所有进程都可执行完毕,则系统处于安全状态。可完成的进程顺序构成一个安全序列。
安全序列是指一个进程序列 {P1,…,Pn} 是安全的,即对于每一个进程 Pi(1≤i≤n),它以后尚需要的资源量不超过系统当前剩余资源量与所有进程 Pj (j < i ) 占有资源量之和。
判断资源分配是否安全流程如下:
银行家算法是一种有效的避免死锁的资源分配策略,通过模拟资源分配的情况,前置检查系统是否处于安全状态来避免死锁。
如果分配完资源,剩余资源能够满足某个进程执行完成,然后回收执行完成的进程资源,找到一个安全序列,那么系统处于安全状态。
通过银行家算法分配资源,进程不会出现环路等待的情况,因为剩余资源可以满足某个进程完成执行,所以不会发生死锁。
如果你想排查你的 Java 程序是否死锁,则可以使用 jstack 工具,它是 JDK 自带的线程堆栈分析工具。
在 Linux 下,我们可以使用 pstack + gdb 工具来定位死锁问题。
pstack 命令可以显示每个线程的栈跟踪信息(函数调用过程),它的使用方式也很简单,只需要 pstack PID 就可以了。
那么,在定位死锁问题时,我们可以多次执行 pstack 命令查看线程的函数调用过程,多次对比结果,确认哪几个线程一直没有变化,且是因为在等待锁,那么大概率是由于死锁问题导致的。
当然,也可以使用 gdb 调试进程,查看代码执行流是否阻塞在获取锁的位置。
活锁(Livelock)与死锁相似,死锁是行程都在等待对方先释放资源;活锁则是行程彼此释放资源又同时占用对方释放的资源。当此情况持续发生时,尽管资源的状态不断改变,但每个行程都无法获取所需资源,使得事情没有任何进展。
活锁的时候进程是不会挂起,会一直占用 CPU 资源。
假设两人正好面对面碰上对方:
对于某些检测死锁并从死锁中恢复的算法来说,Livelock 是一种风险。如果有多个进程执行操作,则可以重复触发死锁检测算法。这可以通过确保只有一个进程(任意选择或按优先级选择)执行操作来避免。