在安全性与活跃性之间通常存在着某种制衡,我们使用加锁机制来确保线程安全,但如果过度地使用加锁,则可能导致“锁顺序死锁”。同样,我们使用线程池和信号量来限制对资源的使用,但这些被限制的行为可能会导致资源死锁。
死锁
每个人都拥有其他人需要的资源,同时又等待其他人已经拥有的资源,并且每个人在获得所有需要的资源之前都不会放弃已经拥有的资源。
当一个线程永远地持有一个锁,并且其他线程都尝试获得这个锁时,那么它们将永远被阻塞。这种情况就是最简单的死锁形式(称为抱死[Deadly Embrace]),其中多个线程由于存在环路的锁依赖关系而永远等待下去。(把每个线程假想为有向图的一个节点,图中每条边表示的关系是:“线程A等待线程B所占有的资源”。如果图中形成一条环路,那么就存在一个死锁)。
1. 锁顺序死锁
两个线程试图以不同的顺序来获得相同的锁。如果按照相同的顺序来请求锁,那么就不会出现循环的加锁依赖性,不会产生死锁。如果每个需要锁L和锁M的线程都以相同的顺序来获取L和M,就不会发生死锁。
2. 动态的锁顺序死锁
考虑下方的代码,它将资金从一个账户转入到另一个账户。在开始转账之前,首先要获得这两个Account对象的锁,以却不通过原子方式来更新两个账户中的余额,同时又不能破坏一些不变性条件,例如“账户的余额不能为负数”。
//容易发生死锁
public void transferMoney(Account fromAccount,
Account toAccount,
DollarAmount amount)
throws InsufficientFundsException {
synchronized (fromAccount) {
synchronized (toAccount) {
if (fromAccount.getBalance().compareTo(amount) < 0)
throw new InsufficientFundsException();
else {
fromAccount.debit(amount);
toAccount.credit(amount);
}
}
}
复制代码
所有的线程似乎按相同的顺序来获得锁,但事实上锁的顺序取决与传递给transferMoney的参数顺序,而这些参数顺序又取决与外部输入。 如果两个线程同时调用transferMoney,其中一个线程从X向Y转账,而另一个线程从Y向X转账,那么就会发生死锁:
A: transferMoney(myAccount, yourAccount, 10);
B: transferMoney(yourAccount, myAccount, 20);
如果执行时序不当,那么A可能获得myAccount的锁并等待yourAccount的锁,然而B此时拥有yourAccount的锁并正在等到myAccount的锁。
在制定锁的顺序时,可以使用System.identityHashCode方法,该方法将返回由Object.hashCode返回的值。下方给出另一个版本的transferMoney,使用了System.identityHashCode来定义锁的顺序。 虽然加了一些新的代码,但却消除了死锁的可能性。
在极少数情况下,两个对象可能拥有相同的散列值(HashCode),此时必须通过某种任意的方法来决定锁的顺序,而这可能又会重新引入死锁。为了避免这种情况,可以使用“加时赛(Tie-Breaking)锁”。在获得两个Account锁之前,首先获得这个“加时赛”锁,从而保证每次只有一个线程以未知的顺序得到这两个锁,从而消除了死锁发生的可能性(只要一致地使用这种机制)。
如果经常出现散列冲突(hash collisions),那么这种技术可能会称为并发性的一个瓶颈(类似与在整个程序中只有一个锁的情况,因为经常要等待获得加时赛锁),但由于System.identityHashCode中出现散列冲突的频率非常低,因此这项技术以最小的代价,换来了最大的安全性。
如果在Account中包含一个唯一的,不可变的,并且具备可比性的键值,例如账号,那么要指定锁的顺序就更加容易:通过键值对对象进行排序,因而不需要使用“加时赛”锁。
3. 在协作对象之间发生的死锁
如果在持有锁的情况下需要调用某个外部方法,就需要警惕死锁。
如果在持有锁时调用某个外部方法,那么将出现活跃性问题。在这个外部方法中可能或获取其他锁(这可能产生死锁),或者阻塞时间过长,导致其他线程无法及时获得当前被持有的锁。
4. 开放调用(Open Calls)
方法调用相当于一种抽象屏障,你无需了解在调用方法中所执行的操作,也正是由于不知道在被调用方法中执行的操作,因此在持有锁的时候对调用某个外部方法将难以进行分析,从而可能出现死锁。
如果在调用某个方法时不需要持有锁,那么这种调用被称为开放调度(Open Call)。
依赖于开放调度的类通常能表现出更好的行为,并且与那些在调度方法时需要持有锁的类相比,也更易于编写。 这种通过开放来避免死锁的方法,类似于采用封装机制来提供线程安全的方法:虽然在没有封装的情况下也能确保构建线程安全的类,但对一个使用了封装的程序进行线程安全分析,要比分析没有使用封装的程序容易得多。 同理,分析一个完全依赖于开放调用的程序的活跃性,要比分析那些不依赖开放调用的程序的活跃性简单。 通过尽可能地使用开放调用,将更容易找出那些需要获取多个锁的代码路径,因此也就更容易确保采用一直的顺序来获得锁。
在程序中应尽量使用开放调用,与那些在持有锁时调用外部方法的程序相比,更容易对依赖于开放调用的程序进行死锁分析。
5. 资源死锁
正如当多个线程相互持有彼此正在等待的锁而不释放自己已持有的锁时发生死锁,当它们在相同的资源集合上等待时,也会发生死锁。
假设有两个资源池,例如两个不同数据库的连接池。资源池通常采用信号量来实现(5.5.3)当资源池为空的阻塞行为。如果一个任务需要连接两个数据库,并且在请求这两个资源时不会始终遵循相同的顺序,那么线程A可能持有与数据库D1的连接,并等待与数据库D2的连接,而线程B则持有与D2的连接并等待与D1的连接(资源池越大,出现这种情况的可能性就越小,如果每个资源池都有N个连接,那么在发生死锁时不仅需要N个循环等待的线程,而且还需要大量不恰当的执行时序)
另一种基于资源的死锁形式就是线程饥饿死锁(Thread-Starvation Deadlock)。
一个示例:一个任务提交另一个任务,并等待被提交任务在单线程的Executor中执行完成。这种情况下,第一个任务将永远等待下去,并使得另一个任务以及在这个Executor中执行的所有其他任务都停止执行。如果某些任务需要等待其他任务的结果,那么这些任务往往时产生线程饥饿死锁的主要来源,有界线程池/资源池与相互依赖的任务不能一起使用。
死锁的避免与诊断
如果必须获取多个锁,那么在设计时必须考虑锁的顺序:尽量减少潜在的加锁 交互数量,将获取锁时需要遵循的协议写入正式文档并始终遵循这些协议。
在使用细粒度(fine-grained)锁的程序中,可以通过使用一种两阶段策略(Two-Part Strategy)来检查代码中的死锁:
- 首先,找出在什么地方将获取多个锁(使这个集合尽量小)
- 然后对所有这些实例进行全局分析,从而确保它们在整个程序中获取锁的顺序都保持一致。
尽可能地使用开放调用,这能极大地简化分析过程。 如果所有的调用都是开放调用,那么要发现获取多个锁的实例是非常简单的,可以通过代码审查或者借助自动化的源代码分析工具。
1. 支持定时的锁
当使用内置锁时,只要没有获得锁,就会永远等待下去,而显式锁则可以执行一个超时时限(Timeout),在等待超过该事件后tryLock会返回一个失败信息。
如果超时时限要比获取锁的时间要长很多,那么就可以在发生某个以外情况后重新获得控制权。
当定时锁失败时,并不需要知道失败的原因。或许是因为发生了死锁,或许某个线程在持有锁时错误地进入了无限循环,还可能是某个操作的执行时间远远超出了预期。 然而,至少能记录所发生的失败,以及关于这次操作的其他有用信息,并通过一种更平缓的方法来重新启动计算,而不是关闭整个进程。
即使在整个系统中没有始终使用定时锁,使用定时锁来获取多个锁也能有效地应对死锁问题。 如果在获取锁时超时,那么可以释放这个锁,然后后退并在一段时间后再次蚕食,从而消除了死锁发生的条件,使程序恢复过来。(这项技术只有在同时获取两个锁时才有效,如果在嵌套的方法调用中请求多个锁,那么即使你知道已经有了外层的锁,也无法释放它).
2. 通过线程转储信息来分析死锁
JVM通过线程转储(Thread Dump)来帮助识别死锁的发生。
线程转储包括各个运行中的线程的栈追踪信息,这类似于发生异常时的栈追踪信息。
线程转储还包含加锁信息,例如每个线程持有了哪些锁,在那些栈帧中获得这些锁,以及被阻塞的线程正在等待获取哪一个锁。 在生成线程转储之前,JVM将在等待关系图中通过搜索循环来找出死锁。如果发现了一个死锁,则获取相应的死锁信息,例如在死锁中涉及哪些锁和线程,以及这个锁的获取操作位于程序的哪些位置.
要在UNIX平台上触发线程转储操作,可以通过向JVM的进程发送SIGQUIT信息(kill-3),或者在UNIX平台中按下Ctrl-\键,在windows平台中按下Ctrl-Break键。在许多IDE(Integrated Development Environment,集成开发环境)中都可以请求线程转储。
当有死锁发生时,可以发现类似如下的信息: Found One Java-level deadlock:
内置锁与获得它们所在的线程栈帧时相关联的,而显式的Lock只获得它的线程相关联。
其他活跃性危险
死锁是最常见的活跃性危险,在并发线程中还存在一些其他的活跃性危险,包括:饥饿,丢失信号和活锁等。
1. 饥饿
当线程由于无法访问它所需要的资源而不能继续执行时,就发生了“饥饿(Starvation)”。
引发饥饿的最常见资源就是CPU时钟周期。如果在Java应用程序中对线程的优先级使用不当,或者在持有锁时执行一些无法结束的结构(例如无限循环,或无限制等待某个资源),那么也可能导致饥饿,因为其他需要这个锁的线程将无法得到它。
在Thread API定义的线程优先级只是作为线程调度的参考。在Thread API中定义了10个优先级,JVM根据需要将它们映射到操作系统的调度优先级,这种映射时与特定平台(不同的操作系统)相关的。在某些操作系统中,如果优先级的数量少于10个,那么有多个Java优先级会被映射到同一个优先级。
要避免使用线程优先级,因为这会增加平台依赖性,并可能导致活跃性问题。在大多数并发应用程序中,都可以使用默认的线程优先级。
2. 糟糕的响应性
如果在GUI应用程序中使用了后台线程,那么糟糕的响应性时是常见的。
GUI框架中,如果你的后台任务是cpu密集型的,会与主的事件线程竞争cpu的时钟周期,可能导致cpu主线程的响应性,这时可以降低后台线程的优先级。
不良的锁管理也可能导致糟糕的响应性。如果某个线程长时间占有一个锁(或者正在对一个大容器进行迭代,并且对每个元素进行计算密集的处理),而其他想要访问这个容器的线程就必须等待很长时间。
3. 活锁(Livelock)
活锁(Livelock)是另一种形式的活跃性问题,尽管不会阻塞线程,但也不能继续执行,因为线程不断重复执行相同的操作,而且总会失败。
活锁通常发生在处理事务消息的应用程序中:如果不能成功地处理某个消息,那么消息处理机制将回滚整个事务,并将它重新放到队列的开头。如果消息处理其在处理某种特定类型的消息时存在错误并导致它失败,那么每当这个消息从队列中取出并传递到存在错误的处理器时,都会发生事务回滚。由于这条消息又被放回到队列开头,因此处理器将被反复调用,并返回先沟通的结果(有时候也被称为毒药消息,Poison Message)。
虽然处理信息的线程没有阻塞,但也无法继续执行下去。这种形式的活锁通常时由过度的错误恢复代码造成的,因为它错误将不可修复的错误作为可修复的错误。
当多个相互协作的线程都对彼此进行响应从而修改各自的状态,并使得任何一个线程都无法继续执行时,就发生了活锁。 这就像两个过于礼貌的人在半路上面对面相遇了:他们彼此都让出对方的路,然后又在另一条路上相遇了,因此他们就这样反复地避让下去。
要解决这种活锁问题,需要在重试机制中引入随机性(randomness)。 例如,在网络上,如果有两台机器尝试使用相同的载波来发送数据包,那么这些数据包就会发生冲突。这两台机器都检查到了冲突,并都在稍后再次发送。 如果二者都选择了在0.1秒后重试,那么会再次冲突,并且不断冲突下去,因而即使有大量闲置的宽带,也无法使数据包发送出去。 为了避免这种情况发生,需要让它们分别等待一段随机的时间(以太协议定义了在重复发生冲突时采用指数方式回退机制,从而降低在多台存在冲突的机器之间发生拥塞和反复失败的风险)。
在并发应用程序中,通过等待随机长度的时间和回退可以有效地避免活锁的发生。