1. 死锁 1.1 死锁
哲学家进餐问题
这里有 5 个哲学家,以及 5 根筷子。
如果每个人都拿起左边的筷子,等待右侧筷子可用,同时不放弃手中的筷子,将导致死锁产生。
当一个线程永远占有有一个锁,而其它线程尝试去占有这个锁,那么它们将永远被阻塞。
1.2 锁顺序死锁
简单的顺序死锁
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 public class LeftRightDeadlock { private final Object left = new Object (); private final Object right = new Object (); public void leftRight () { synchronized (left) { synchronized (right) { doSomething(); } } } public void rightLeft () { synchronized (right) { synchronized (left) { doSomethingElse(); } } } void doSomething () { } void doSomethingElse () { } }
对于 A、B 两个线程,分别锁住 left、right。
这个时候 A 线程想获取 right,B 线程想获取 left 锁
A 线程获取不到 right,因为已经被 B 线程锁住
同样 B 线程也获取不到 left,因为 left 已经被 A 线程锁住
如果所有的线程能够以固定的秩序获取锁,程序就不会出现锁顺序锁死了。
1.3 动态的锁顺序死锁 动态的锁顺序死锁是指两个线程调用同一个方法时,传入的参数颠倒造成的死锁。
有时候我们并不能一目了然地看清是否己经对锁有足够的控制,来避免死锁的发生。
动态加锁顺序产生的死锁
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 import java.util.concurrent.atomic.AtomicInteger;public class DynamicOrderDeadlock { public static 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); } } } } static class DollarAmount implements Comparable <DollarAmount> { private int amount = 0 ; public DollarAmount (int amount) { this .amount = amount; } public DollarAmount add (DollarAmount d) { this .amount = this .amount + d.amount; return this ; } public DollarAmount subtract (DollarAmount d) { this .amount = this .amount - d.amount; return this ; } public int compareTo (DollarAmount dollarAmount) { return Integer.compare(this .amount, dollarAmount.amount); } public int getAmount () { return amount; } } static class Account { private DollarAmount balance; private final int acctNo; private static final AtomicInteger sequence = new AtomicInteger (); public Account () { acctNo = sequence.incrementAndGet(); } void debit (DollarAmount d) { balance = balance.subtract(d); } void credit (DollarAmount d) { balance = balance.add(d); } DollarAmount getBalance () { return balance; } public void setBalance (DollarAmount balance) { this .balance = balance; } int getAcctNo () { return acctNo; } } static class InsufficientFundsException extends Exception { } }
如果两个线程同时调用 transferMoney()
,一个从 X 向 Y 转账,另一个从 Y 向 X 转账,那么就会发生死锁:
1 2 3 4 transferMoney(myAccount, yourAccount, 10 ); transferMoney(yourAccount, myAccount, 20 );
在偶发的时序中,thread_a 会获得 myAccount 的锁,并等待 yourAccount 的锁,然而 B 此时持有 yourAccount 的锁,正在等待 myAccount 的锁。
如何避免着清情况的死锁问题
解决办法:通过制定锁的顾序来避免死锁。
在制定锁顺序时,可以使用 System.identityHashCode()
方法,该方法将返回由 Object.hashCode()
返回的值。
示例:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 import java.util.concurrent.atomic.AtomicInteger;public class InduceLockOrder { private static final Object tieLock = new Object (); public static void transferMoney (final Account fromAcct, final Account toAcct, final DollarAmount amount) throws InsufficientFundsException { class Helper { public void transfer () throws InsufficientFundsException { if (fromAcct.getBalance().compareTo(amount) < 0 ) throw new InsufficientFundsException (); else { fromAcct.debit(amount); toAcct.credit(amount); } } } int fromHash = System.identityHashCode(fromAcct); int toHash = System.identityHashCode(toAcct); if (fromHash < toHash) { synchronized (fromAcct) { synchronized (toAcct) { new Helper ().transfer(); } } } else if (fromHash > toHash) { synchronized (toAcct) { synchronized (fromAcct) { new Helper ().transfer(); } } } else { synchronized (tieLock) { synchronized (fromAcct) { synchronized (toAcct) { new Helper ().transfer(); } } } } } static class DollarAmount implements Comparable <DollarAmount> { private int amount = 0 ; public DollarAmount (int amount) { this .amount = amount; } public DollarAmount add (DollarAmount d) { this .amount = this .amount + d.amount; return this ; } public DollarAmount subtract (DollarAmount d) { this .amount = this .amount - d.amount; return this ; } public int compareTo (DollarAmount dollarAmount) { return Integer.compare(this .amount, dollarAmount.amount); } public int getAmount () { return amount; } } static class Account { private DollarAmount balance; private final int acctNo; private static final AtomicInteger sequence = new AtomicInteger (); public Account () { acctNo = sequence.incrementAndGet(); } void debit (DollarAmount d) { balance = balance.subtract(d); } void credit (DollarAmount d) { balance = balance.add(d); } DollarAmount getBalance () { return balance; } public void setBalance (DollarAmount balance) { this .balance = balance; } int getAcctNo () { return acctNo; } } static class InsufficientFundsException extends Exception { } }
开始一个循环,它在典型条件下制定死锁
使用 DynamicOrderDeadlock,容易产生死锁:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 import java.util.Random;public class DemonstrateDeadlock { private static final int NUM_THREADS = 20 ; private static final int NUM_ACCOUNTS = 5 ; private static final int NUM_ITERATIONS = 1000000 ; public static void main (String[] args) { final Random rnd = new Random (); final DynamicOrderDeadlock.Account[] accounts = new DynamicOrderDeadlock .Account[NUM_ACCOUNTS]; for (int i = 0 ; i < accounts.length; i++) { DynamicOrderDeadlock.Account account = new DynamicOrderDeadlock .Account(); account.setBalance(new DynamicOrderDeadlock .DollarAmount(200000000 )); accounts[i] = account; } class TransferThread extends Thread { public void run () { for (int i = 0 ; i < NUM_ITERATIONS; i++) { int fromAcct = rnd.nextInt(NUM_ACCOUNTS); int toAcct = rnd.nextInt(NUM_ACCOUNTS); DynamicOrderDeadlock.DollarAmount amount = new DynamicOrderDeadlock .DollarAmount(rnd.nextInt(1000 )); try { DynamicOrderDeadlock.transferMoney(accounts[fromAcct], accounts[toAcct], amount); System.out.println("线程【" + Thread.currentThread().getName() + "】运行第" + i + "次------ " + "账户【" + fromAcct + "】向账户【" + toAcct + "】转账" + amount.getAmount() + "$ ------ " + "账户【" + fromAcct + "】剩下 " + accounts[fromAcct].getBalance().getAmount() + "$ ------ " + "账户【" + toAcct + "】剩下 " + accounts[toAcct].getBalance().getAmount() + "$" ); } catch (DynamicOrderDeadlock.InsufficientFundsException ignored) { } } } } for (int i = 0 ; i < NUM_THREADS; i++) { TransferThread transferThread = new TransferThread (); transferThread.start(); } } }
Output:
这里它们正常,20个线程,分别都应该发生 1000000 次交易的,不过在前面已经发生了死锁了。非法交易被警察抓了。
开始一个循环,它在制定锁顺序后的条件下,交易成功
使用 InduceLockOrder,笔笔交易完成:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 import java.util.Random;public class DemoInduceLockOrder { private static final int NUM_THREADS = 20 ; private static final int NUM_ACCOUNTS = 5 ; private static final int NUM_ITERATIONS = 1000000 ; public static void main (String[] args) { final Random rnd = new Random (); final InduceLockOrder.Account[] accounts = new InduceLockOrder .Account[NUM_ACCOUNTS]; for (int i = 0 ; i < accounts.length; i++) { InduceLockOrder.Account account = new InduceLockOrder .Account(); account.setBalance(new InduceLockOrder .DollarAmount(200000000 )); accounts[i] = account; } class TransferThread extends Thread { public void run () { for (int i = 0 ; i < NUM_ITERATIONS; i++) { int fromAcct = rnd.nextInt(NUM_ACCOUNTS); int toAcct = rnd.nextInt(NUM_ACCOUNTS); InduceLockOrder.DollarAmount amount = new InduceLockOrder .DollarAmount(rnd.nextInt(1000 )); try { InduceLockOrder.transferMoney(accounts[fromAcct], accounts[toAcct], amount); System.out.println("线程【" + Thread.currentThread().getName() + "】运行第" + i + "次------ " + "账户【" + fromAcct + "】向账户【" + toAcct + "】转账" + amount.getAmount() + "$ ------ " + "账户【" + fromAcct + "】剩下 " + accounts[fromAcct].getBalance().getAmount() + "$ ------ " + "账户【" + toAcct + "】剩下 " + accounts[toAcct].getBalance().getAmount() + "$" ); } catch (InduceLockOrder.InsufficientFundsException ignored) { } } } } for (int i = 0 ; i < NUM_THREADS; i++) { TransferThread transferThread = new TransferThread (); transferThread.start(); } } }
Output:
在有序的规则下,没有被抓,顺利完成了多次交易。
1.4 协作对象间的死锁 如果在持有锁的情况下需要调用某个外部方法,就需要警惕死锁。
如果在持有锁时调用某个外部方法,那么将出现活跃性问题。在这个外部方法中可能或获取其他锁(这可能产生死锁),或者阻塞时间过长,导致其他线程无法及时获得当前被持有的锁。
协作对象间的锁顺序死锁
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 import net.jcip.annotations.GuardedBy;import java.awt.Point;import java.util.HashSet;import java.util.Set;public class CooperatingDeadlock { class Taxi { @GuardedBy("this") private Point location, destination; private final Dispatcher dispatcher; public Taxi (Dispatcher dispatcher) { this .dispatcher = dispatcher; } public synchronized Point getLocation () { return location; } public synchronized void setLocation (Point location) { this .location = location; if (location.equals(destination)) { dispatcher.notifyAvailable(this ); } } public synchronized Point getDestination () { return destination; } public synchronized void setDestination (Point destination) { this .destination = destination; } } class Dispatcher { @GuardedBy("this") private final Set<Taxi> taxis; @GuardedBy("this") private final Set<Taxi> availableTaxis; public Dispatcher () { taxis = new HashSet <Taxi>(); availableTaxis = new HashSet <Taxi>(); } public synchronized void notifyAvailable (Taxi taxi) { availableTaxis.add(taxi); } public synchronized Image getImage () { Image image = new Image (); for (Taxi t : taxis) { image.drawMarker(t.getLocation()); } return image; } } class Image { public void drawMarker (Point p) { } } }
虽然没有显示调用锁,但是Taxi.setLocation
方法和Dispatcher.getImage
由于获取锁仍然可能发生死锁情况:
使用开放调用来避免协作对象之间的死锁
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 import net.jcip.annotations.GuardedBy;import net.jcip.annotations.ThreadSafe;import java.awt.Point;import java.util.HashSet;import java.util.Set;public class CooperatingNoDeadlock { @ThreadSafe class Taxi { @GuardedBy("this") private Point location, destination; private final Dispatcher dispatcher; public Taxi (Dispatcher dispatcher) { this .dispatcher = dispatcher; } public synchronized Point getLocation () { return location; } public synchronized void setLocation (Point location) { boolean reachedDestination; synchronized (this ) { this .location = location; reachedDestination = location.equals(destination); } if (reachedDestination) { dispatcher.notifyAvailable(this ); } } public synchronized Point getDestination () { return destination; } public synchronized void setDestination (Point destination) { this .destination = destination; } } @ThreadSafe class Dispatcher { @GuardedBy("this") private final Set<Taxi> taxis; @GuardedBy("this") private final Set<Taxi> availableTaxis; public Dispatcher () { taxis = new HashSet <Taxi>(); availableTaxis = new HashSet <Taxi>(); } public synchronized void notifyAvailable (Taxi taxi) { availableTaxis.add(taxi); } public Image getImage () { Set<Taxi> copy; synchronized (this ) { copy = new HashSet <Taxi>(taxis); } Image image = new Image (); for (Taxi t : copy) { image.drawMarker(t.getLocation()); } return image; } } class Image { public void drawMarker (Point p) { } } }
1.5 开放调用 方法调用相当于一种抽象屏障,你无需了解在调用方法中所执行的操作,也正是由于不知道在被调用方法中执行的操作,因此在持有锁的时候对调用某个外部方法将难以进行分析,从而可能出现死锁。
如果在调用某个方法时不需要持有锁,那么这种调用被称为开放调度(Open Call)。
依赖于开放调用的类会具有更好的行为,并且比那些需要获得锁才能调用的方法相比,更容易与其他的类合作。
使用开放调用来避免死锁类似于使用封裝来提供线程安全:尽管我们能够保证在没有封装的情况下构建线程安全的程序,但是对一个有效封装的类进行线程安全分析,要比分析没有封装的类容易得多。
类似地,分析一个完全依赖于开放调用的程序的程序活跃度,比分析那些非开放调用的程序更简单。尽量让你自己使用开放调用,这要比获得多重锁后识别代码路径更简单,因此可以确保用一致的顺序获得锁。
在程序中尽量使用开放调用。依赖于开放调用的程序,相比于那些在持有锁的时侯还调用外部方法的程序,更容易进行死锁自由度(deadlock-freedom)的分析。
1.6 资源死锁
当线程间相互等待对方持有的锁,并且谁都不会释放自己的锁时就会发生死锁,当线程持有和等待的目标变为资源时,会发生与之相类似的死锁。
假设你有两个放入池中的资源,比如分别是到两个数据库连接的连接池。当池为空的时候发生阻塞。
如果一个任务需要连接到两个数据库,并且两个资源并不是按照相同顺序进行调用的。
线程A可能持有数据库 D1 的连接,并等待连接到数据库 D2。
而线程B持有数据库 D2 的连接并等待到 D1 的连接。
资源死锁 … 完蛋
另一种基于资源的死锁形式就是线程饥饿死锁(Thread-Starvation Deadlock)。
一个 TaskA 将工作提交到单线程化的 Executor,并等待后面向该 Executor 提交的 TaskB 的计算结果。
TaskA 等待 TaskB 的计算结果,久久不能结束。
而单线程化的 Executor 需要执行完一个任务(TaskA)才能执行第二个任务(TaskB)。
即 TaskA 等 TaskB,TaskB 等 TaskA。就互等。
2. 避免和诊断死锁 2.1 避免和诊断死锁
如果一个程序一次至多获得一个锁,那么就不会产生锁顺序死锁。
如果必须获得多个锁那么我们应该要制定锁顺序。尽量减少潜在锁之间的交互数量。
2.2 尝试定时的锁
在使用内部锁 synchronized 时,如果一个程序需要获得多个锁,容易造成死锁。
可以使用显式锁,来检测死锁和从锁中恢复。
java.util.concurrent.locks.Lock 类,与使用 synchronized 代码块相比,Lock 实现提供了更广泛的锁定操作。它们允许更灵活的结构。
调用 Lock.tryLock()
方法。如果锁可用,则获取锁并立即返回值为true。如果锁不可用,则此方法将立即返回值false。
在内部锁(synchronized)机制中,只有没有获得锁,就会永远保持等待,而 Lock.tryLock(long time, TimeUnit unit)
可以自定义超时时间。
2.3 通过线程转储分析死锁
JVM 通过 线程转储
(thread dump) 帮助开发者识别死锁的发生。
线程转储
包括每个运行中线程的栈追踪信息
与之相似并随之发生的异常
以及锁的信息(如:被哪个线程获得、锁的栈结构、阻塞线程等待的是哪个锁)
在生成线程转储之前,JVM 在表示 “正在等待(is-waiting-for)” 关系的(有向)图中搜索循环来寻找死锁。
如果发现了死锁,它就会包括死锁的识别信息,其中参与了哪些锁和线程,以及程序中造成不良后果的锁请求发生在哪里。
转储分析死锁
【第10章 - 1.死锁】部分的示例:开始一个循环,它在典型条件下制定死锁
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 import java.util.Random;public class DemonstrateDeadlock { private static final int NUM_THREADS = 20 ; private static final int NUM_ACCOUNTS = 5 ; private static final int NUM_ITERATIONS = 1000000 ; public static void main (String[] args) { final Random rnd = new Random (); final DynamicOrderDeadlock.Account[] accounts = new DynamicOrderDeadlock .Account[NUM_ACCOUNTS]; for (int i = 0 ; i < accounts.length; i++) { DynamicOrderDeadlock.Account account = new DynamicOrderDeadlock .Account(); account.setBalance(new DynamicOrderDeadlock .DollarAmount(200000000 )); accounts[i] = account; } class TransferThread extends Thread { public void run () { for (int i = 0 ; i < NUM_ITERATIONS; i++) { int fromAcct = rnd.nextInt(NUM_ACCOUNTS); int toAcct = rnd.nextInt(NUM_ACCOUNTS); DynamicOrderDeadlock.DollarAmount amount = new DynamicOrderDeadlock .DollarAmount(rnd.nextInt(1000 )); try { DynamicOrderDeadlock.transferMoney(accounts[fromAcct], accounts[toAcct], amount); System.out.println("线程【" + Thread.currentThread().getName() + "】运行第" + i + "次------ " + "账户【" + fromAcct + "】向账户【" + toAcct + "】转账" + amount.getAmount() + "$ ------ " + "账户【" + fromAcct + "】剩下 " + accounts[fromAcct].getBalance().getAmount() + "$ ------ " + "账户【" + toAcct + "】剩下 " + accounts[toAcct].getBalance().getAmount() + "$" ); } catch (DynamicOrderDeadlock.InsufficientFundsException ignored) { } } } } for (int i = 0 ; i < NUM_THREADS; i++) { TransferThread transferThread = new TransferThread (); transferThread.start(); } } }
启动程序后,控制台通过 jps 获取进程 PID:
jcmd 工具向目标 JVM 发送一串命令:
其中有一部分输出是这样的:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 Found one Java-level deadlock: ============================= "Thread-19": waiting to lock monitor 0x00007fd1f1a3bb48 (object 0x00000006c001e998, a DynamicOrderDeadlock$Account), which is held by "Thread-18" "Thread-18": waiting to lock monitor 0x00007fd1f32b3de8 (object 0x00000006c001e970, a DynamicOrderDeadlock$Account), which is held by "Thread-17" "Thread-17": waiting to lock monitor 0x00007fd1f1818cc8 (object 0x00000006c001e9e8, a DynamicOrderDeadlock$Account), which is held by "Thread-5" "Thread-5": waiting to lock monitor 0x00007fd1f32b3de8 (object 0x00000006c001e970, a DynamicOrderDeadlock$Account), which is held by "Thread-17" Java stack information for the threads listed above: ===================================================
Thread-19 等 Thread-18
Thread-18 等 Thread-17
Thread-17 等 Thread-5
Thread-5 等 Thread-17
互等,完犊子了。
3. 其它活跃度危险 3.1 饥饿(starvation)
当线程访问它需要的资源时却被永久拒绝,将会发生饥饿。
线程 API 定义了 10 个优先级级别, 并对应到操作系统相应的调度优先级中。
线程 API 定义的线程优先级仅仅作为调度的参考。
有一些操作系统优先级别本身就少于10个,那么其中多个 Java 的优先级会映射到操作系统相同的优先级。
抵制使用线程优先级的诱惑,因为这会增加平台依赖性,并且可能引起活跃度问题。
3.2 弱响应性
如果在 GUI 应用程序中,使用了后台线程,那么较大可能会引起响应性差。
GUI框架中,如果后台任务是cpu密集型的,那么它会与主的GUI事件线程竞争 cpu 的时钟周期,可能导致 cpu 主线程的响应性弱。这时我们可以降低后台线程的优先级。
不良的锁管理也可能导致糟糕的响应性。如果某个线程长时间占有一个锁(或者正在对一个大容器进行迭代,并且对每个元素进行计算密集的处理),而其他想要访问这个容器的线程就必须等待很长时间。
3.3 活锁(livelock) 活锁是线程活跃度失败的另一种形式,尽管没有阻塞,线程仍不能继续进行,因为它不断尝试相同的操作,却总是失败。
如:
在消息处理应用程序中,如果消息处理失败,其中传递消息的底层架构会会退整个事物,并把它置回队首。
如果消息处理程序对某种特定类型的消息处理存在bug,每次处理都会失败,那么每一次这个消息都会被从队列中取出,传递到存在问题的处理器(handler),然后发生事务回退。
因为这条消息又会回到队首,处理器会不断被这样重复调用,并返回重复结果。这就是通常称为毒药信息 (poison message)的问题。
如何避免:在重试机制中引入随机性。
如:
两台机器尝试使用相同的频率,来发送数据包,那么这些数据包就会发生冲突。并又双双重试。
如果它们都非常精确地在一秒后重试,它们又会发生冲突,并不断冲突下去,导致数据包永远不能发送。
为了避免这种情况发生,我们可以通过用使一个随机组件它们进行等待。
在并发程序中,通过随机等待和撇回来进行重试能够相当有效地避免活锁的发生。