在有些情况下死锁是可以避免的。本文将展示三种用于避免死锁的技术:
- 加锁顺序
- 加锁时限
- 死锁检测
加锁顺序
当多个线程需要相同的一些锁,但是按照不同的顺序加锁,死锁就很容易发生。
如果能确保所有的线程都是按照相同的顺序获得锁,那么死锁就不会发生。看下面这个例子:
Thread 1:
lock A
lock B
Thread 2:
wait for A
lock C (when A locked)
Thread 3:
wait for A
wait for B
wait for C
如果一个线程(比如线程 3)需要一些锁,那么它必须按照确定的顺序获取锁。它只有获得了从顺序上排在前面的锁之后,才能获取后面的锁。
例如,线程 2 和线程 3 只有在获取了锁 A 之后才能尝试获取锁 C(译者注:获取锁 A 是获取锁 C 的必要条件)。因为线程 1 已经拥有了锁 A,所以线程 2 和 3 需要一直等到锁 A 被释放。然后在它们尝试对 B 或 C 加锁之前,必须成功地对 A 加了锁。
按照顺序加锁是一种有效的死锁预防机制。但是,这种方式需要你事先知道所有可能会用到的锁(译者注:并对这些锁做适当的排序),但总有些时候是无法预知的。
加锁时限
另外一个可以避免死锁的方法是在尝试获取锁的时候加一个超时时间,这也就意味着在尝试获取锁的过程中若超过了这个时限该线程则放弃对该锁请求。若一个线程没有在给定的时限内成功获得所有需要的锁,则会进行回退并释放所有已经获得的锁,然后等待一段随机的时间再重试。这段随机的等待时间让其它线程有机会尝试获取相同的这些锁,并且让该应用在没有获得锁的时候可以继续运行(译者注:加锁超时后可以先继续运行干点其它事情,再回头来重复之前加锁的逻辑)。
以下是一个例子,展示了两个线程以不同的顺序尝试获取相同的两个锁,在发生超时后回退并重试的场景:
Thread 1 locks A
Thread 2 locks B
Thread 1 attempts to lock B but is blocked
Thread 2 attempts to lock A but is blocked
Thread 1's lock attempt on B times out
Thread 1 backs up and releases A as well
Thread 1 waits randomly (e.g. 257 millis) before retrying.
Thread 2's lock attempt on A times out
Thread 2 backs up and releases B as well
Thread 2 waits randomly (e.g. 43 millis) before retrying.
在上面的例子中,线程 2 比线程 1 早 200 毫秒进行重试加锁,因此它可以先成功地获取到两个锁。这时,线程 1 尝试获取锁 A 并且处于等待状态。当线程 2 结束时,线程 1 也可以顺利的获得这两个锁(除非线程 2 或者其它线程在线程 1 成功获得两个锁之前又获得其中的一些锁)。
需要注意的是,由于存在锁的超时,所以我们不能认为这种场景就一定是出现了死锁。也可能是因为获得了锁的线程(导致其它线程超时)需要很长的时间去完成它的任务。
此外,如果有非常多的线程同一时间去竞争同一批资源,就算有超时和回退机制,还是可能会导致这些线程重复地尝试但却始终得不到锁。如果只有两个线程,并且重试的超时时间设定为 0 到 500 毫秒之间,这种现象可能不会发生,但是如果是 10 个或 20 个线程情况就不同了。因为这些线程等待相等的重试时间的概率就高的多(或者非常接近以至于会出现问题)。
(译者注:超时和重试机制是为了避免在同一时间出现的竞争,但是当线程很多时,其中两个或多个线程的超时时间一样或者接近的可能性就会很大,因此就算出现竞争而导致超时后,由于超时时间一样,它们又会同时开始重试,导致新一轮的竞争,带来了新的问题。)
这种机制存在一个问题,在 Java 中不能对 synchronized 同步块设置超时时间。你需要创建一个自定义锁,或使用 Java5 中 java.util.concurrent 包下的工具。写一个自定义锁类不复杂,但超出了本文的内容。后续的 Java 并发系列会涵盖自定义锁的内容。
死锁检测
死锁检测是一个更好的死锁预防机制,它主要是针对那些不可能实现按序加锁并且锁超时也不可行的场景。
每当一个线程获得了锁,会在线程和锁相关的数据结构中(map、graph 等等)将其记下。除此之外,每当有线程请求锁,也需要记录在这个数据结构中。
当一个线程请求锁失败时,这个线程可以遍历锁的关系图看看是否有死锁发生。例如,线程 A 请求锁 7,但是锁 7 这个时候被线程 B 持有,这时线程 A 就可以检查一下线程 B 是否已经请求了线程 A 当前所持有的锁。如果线程 B 确实有这样的请求,那么就是发生了死锁(线程 A 拥有锁 1,请求锁 7;线程 B 拥有锁 7,请求锁 1)。