在有些情况下死锁是可以避免的. 本文将展示三种用于避免死锁的技术:
加锁顺序 http://ifeve.com/deadlock-prevention/#ordering
加锁时限 http://ifeve.com/deadlock-prevention/#timeout
死锁检测 http://ifeve.com/deadlock-prevention/#detection
加锁顺序
当多个线程需要相同的一些锁, 但是按照不同的顺序加锁, 死锁就很容易发生.
如果能确保所有的线程都是按照相同的顺序获得锁, 那么死锁就不会发生. 看下面这个例子:
- 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).
当然, 死锁一般要比两个线程互相持有对方的锁这种情况要复杂的多. 线程 A 等待线程 B, 线程 B 等待线程 C, 线程 C 等待线程 D, 线程 D 又在等待线程 A. 线程 A 为了检测死锁, 它需要递进地检测所有被 B 请求的锁. 从线程 B 所请求的锁开始, 线程 A 找到了线程 C, 然后又找到了线程 D, 发现线程 D 请求的锁被线程 A 自己持有着. 这是它就知道发生了死锁.
下面是一幅关于四个线程 (A,B,C 和 D) 之间锁占有和请求的关系图. 像这样的数据结构就可以被用来检测死锁.
那么当检测出死锁时, 这些线程该做些什么呢?
一个可行的做法是释放所有锁, 回退, 并且等待一段随机的时间后重试. 这个和简单的加锁超时类似, 不一样的是只有死锁已经发生了才回退, 而不会是因为加锁的请求超时了. 虽然有回退和等待, 但是如果有大量的线程竞争同一批锁, 它们还是会重复地死锁(编者注: 原因同超时类似, 不能从根本上减轻竞争).
一个更好的方案是给这些线程设置优先级, 让一个 (或几个) 线程回退, 剩下的线程就像没发生死锁一样继续保持着它们需要的锁. 如果赋予这些线程的优先级是固定不变的, 同一批线程总是会拥有更高的优先级. 为避免这个问题, 可以在死锁发生的时候设置随机的优先级.
来源: http://www.bubuko.com/infodetail-3650708.html