在操作系统中的并发处理场景中, 进程对资源的持有与请求过程中,会产生死锁. Say, Process A has resource R1 , Process B has resource R2. If Process A request resource R2 and Process B requests resource R1, at the same time , then deadlock occurs.
Deadlock can occur if all the given 4 conditions ( Coffman Conditions ) are satisfied, that is if all are true :
Mutual Exclusion(互斥)
Hold and Wait(持有&等待)
No Preemption(无占先)
Circular wait(环路等待)
Let’s look at each one in detail :
Mutual exclusion – If At least one or more resource are in non shareable mode , the resources should be in mutual exclusion. Non Shareable means , resource can’t be used by more than 1 process at a time, unless the resource gets released. Hold and Wait – Processes which are already holding at least 1 resource may request new resource. No Pre emptive condition – Resources can’t be released by force , only the process holding the resource can release it, which does so after the process has finished its task. Circular wait – 2 or more process form a circular chain where each process waits and want to acquire the resource which the next process in the chain holds.
Ref: https://prepinsta.com/operating-systems/deadlock-introduction/
同样的在 Java 多线程并发编程中, 多个线程请求对象的时候,也会产生死锁.图示如下 (需要知道的是, 在 Java 中一个对象在同一时刻只能有一把锁):
多线程和并发性并不是什么新内容,但是 Java 语言设计中的创新之一就是,它是第一个直接把跨平台线程模型和正规的内存模型集成到语言中的主流语言。核心类库包含一个 Thread 类,可以用它来构建、启动和操纵线程,Java 语言包括了跨线程传达并发性约束的构造 —— synchronized 和 volatile 。在简化与平台无关的并发类的开发的同时,它决没有使并发类的编写工作变得更繁琐,只是使它变得更容易了。
Ref:https://www.cnblogs.com/cxzdgs/p/5746895.html
虽然进程在运行过程中,可能发生死锁,但死锁的发生也必须具备一定的条件,死锁的发生必须具备以下四个必要条件。 1)互斥条件:指进程对所分配到的资源进行排它性使用,即在一段时间内某资源只由一个进程占用。如果此时还有其它进程请求资源,则请求者只能等待,直至占有资源的进程用毕释放。 2)请求和保持条件:指进程已经保持至少一个资源,但又提出了新的资源请求,而该资源已被其它进程占有,此时请求进程阻塞,但又对自己已获得的其它资源保持不放。 3)不剥夺条件:指进程已获得的资源,在未使用完之前,不能被剥夺,只能在使用完时由自己释放。 4)环路等待条件:指在发生死锁时,必然存在一个进程——资源的环形链,即进程集合{P0,P1,P2,···,Pn}中的P0正在等待一个P1占用的资源;P1正在等待P2占用的资源,……,Pn正在等待已被P0占用的资源。
Ref: https://baike.baidu.com/item/%E6%AD%BB%E9%94%81/2196938
破坏产生死锁的条件.
一个简单的死锁代码实例:
fun usingSynchronized() { val accountA = Account(10000, "A") val accountB = Account(10000, "B") val t1 = Thread { synchronized(accountA) { println("t1 aquired lock on $accountA") synchronized(accountB) { println("t1 aquired lock on $accountB") val rand = Random() for (i in 0..10) { Account.transfer(accountA, accountB, rand.nextInt(1000)) } } } } val t2 = Thread { synchronized(accountB) { println("t2 aquired lock on $accountB") synchronized(accountA) { println("t2 aquired lock on $accountA") val rand = Random() for (i in 0..10) { Account.transfer(accountB, accountA, rand.nextInt(1000)) } } } } t1.start() t2.start() }
运行发现,程序输出了下面两行之后,就卡住不动了:
t1 aquired lock on Account(balance=10000, name='A') t2 aquired lock on Account(balance=10000, name='B')
fun usingReentrantLock() { val accountA = Account(10000, "A") val accountB = Account(10000, "B") val lock1 = ReentrantLock() val lock2 = ReentrantLock() val t1 = Thread { val rand = Random() for (i in 0..10) { lock1.lock() lock2.lock() try { Account.transfer(accountA, accountB, rand.nextInt(1000)) } finally { lock1.unlock() lock2.unlock() } } } val t2 = Thread { val rand = Random() for (i in 0..10) { lock2.lock() lock1.lock() try { Account.transfer(accountB, accountA, rand.nextInt(1000)) } finally { lock2.unlock() lock1.unlock() } } } t1.start() t2.start() }
代码运行到一段,卡住了:
Account(balance=9827, name='A') transfer Account(balance=10173, name='B'): 173 ...... Account(balance=7264, name='B') transfer Account(balance=12736, name='A'): 645 Account(balance=6368, name='B') transfer Account(balance=13632, name='A'): 896 t1 aquired lock on Account(balance=10000, name='A') t1 aquired lock on Account(balance=10000, name='B') Account(balance=9037, name='A') transfer Account(balance=10963, name='B'): 963 t1 aquired lock on Account(balance=9037, name='A') t2 aquired lock on Account(balance=10963, name='B')
use command jps -l -m to list the process id of this deadlock program.
$ jps -l -m 17248 com.kotlin.notes.DeadLockKt 10226 16548 org.gradle.launcher.daemon.bootstrap.GradleDaemon 5.5 11317 com.ak47.cms.cms.CmsApplicationKt 17274 sun.tools.jps.Jps -l -m ...
jstack [pid]
$ jstack 17248 2019-07-06 22:10:57 Full thread dump Java HotSpot(TM) 64-Bit Server VM (25.131-b11 mixed mode): "Attach Listener" #13 daemon prio=9 os_prio=31 tid=0x00007f917a890800 nid=0x3d03 waiting on condition [0x0000000000000000] java.lang.Thread.State: RUNNABLE "DestroyJavaVM" #12 prio=5 os_prio=31 tid=0x00007f917b009000 nid=0x1703 waiting on condition [0x0000000000000000] java.lang.Thread.State: RUNNABLE "Thread-1" #11 prio=5 os_prio=31 tid=0x00007f917c102000 nid=0x4203 waiting for monitor entry [0x0000700010f6b000] java.lang.Thread.State: BLOCKED (on object monitor) at com.kotlin.notes.DeadLockKt$usingSynchronized$t2$1.run(DeadLock.kt:31) - waiting to lock <0x00000007956f92b8> (a com.kotlin.notes.Account) - locked <0x0000000795717ac8> (a com.kotlin.notes.Account) at java.lang.Thread.run(Thread.java:748) "Thread-0" #10 prio=5 os_prio=31 tid=0x00007f917b88a800 nid=0x4303 waiting for monitor entry [0x0000700010e68000] java.lang.Thread.State: BLOCKED (on object monitor) at com.kotlin.notes.DeadLockKt$usingSynchronized$t1$1.run(DeadLock.kt:18) - waiting to lock <0x0000000795717ac8> (a com.kotlin.notes.Account) - locked <0x00000007956f92b8> (a com.kotlin.notes.Account) at java.lang.Thread.run(Thread.java:748) "Service Thread" #9 daemon prio=9 os_prio=31 tid=0x00007f917b88f800 nid=0x4503 runnable [0x0000000000000000] java.lang.Thread.State: RUNNABLE "C1 CompilerThread2" #8 daemon prio=9 os_prio=31 tid=0x00007f917c0f4800 nid=0x4703 waiting on condition [0x0000000000000000] java.lang.Thread.State: RUNNABLE "C2 CompilerThread1" #7 daemon prio=9 os_prio=31 tid=0x00007f917c0e9800 nid=0x3903 waiting on condition [0x0000000000000000] java.lang.Thread.State: RUNNABLE "C2 CompilerThread0" #6 daemon prio=9 os_prio=31 tid=0x00007f917c0e9000 nid=0x4903 waiting on condition [0x0000000000000000] java.lang.Thread.State: RUNNABLE "Monitor Ctrl-Break" #5 daemon prio=5 os_prio=31 tid=0x00007f917a832800 nid=0x3603 runnable [0x0000700010856000] java.lang.Thread.State: RUNNABLE at java.net.SocketInputStream.socketRead0(Native Method) at java.net.SocketInputStream.socketRead(SocketInputStream.java:116) at java.net.SocketInputStream.read(SocketInputStream.java:171) at java.net.SocketInputStream.read(SocketInputStream.java:141) at sun.nio.cs.StreamDecoder.readBytes(StreamDecoder.java:284) at sun.nio.cs.StreamDecoder.implRead(StreamDecoder.java:326) at sun.nio.cs.StreamDecoder.read(StreamDecoder.java:178) - locked <0x00000007957c0508> (a java.io.InputStreamReader) at java.io.InputStreamReader.read(InputStreamReader.java:184) at java.io.BufferedReader.fill(BufferedReader.java:161) at java.io.BufferedReader.readLine(BufferedReader.java:324) - locked <0x00000007957c0508> (a java.io.InputStreamReader) at java.io.BufferedReader.readLine(BufferedReader.java:389) at com.intellij.rt.execution.application.AppMainV2$1.run(AppMainV2.java:64) "Signal Dispatcher" #4 daemon prio=9 os_prio=31 tid=0x00007f917b83b000 nid=0x3403 runnable [0x0000000000000000] java.lang.Thread.State: RUNNABLE "Finalizer" #3 daemon prio=8 os_prio=31 tid=0x00007f917c032800 nid=0x5203 in Object.wait() [0x0000700010650000] java.lang.Thread.State: WAITING (on object monitor) at java.lang.Object.wait(Native Method) - waiting on <0x0000000795588ec8> (a java.lang.ref.ReferenceQueue$Lock) at java.lang.ref.ReferenceQueue.remove(ReferenceQueue.java:143) - locked <0x0000000795588ec8> (a java.lang.ref.ReferenceQueue$Lock) at java.lang.ref.ReferenceQueue.remove(ReferenceQueue.java:164) at java.lang.ref.Finalizer$FinalizerThread.run(Finalizer.java:209) "Reference Handler" #2 daemon prio=10 os_prio=31 tid=0x00007f917c02c000 nid=0x2f03 in Object.wait() [0x000070001054d000] java.lang.Thread.State: WAITING (on object monitor) at java.lang.Object.wait(Native Method) - waiting on <0x0000000795586b68> (a java.lang.ref.Reference$Lock) at java.lang.Object.wait(Object.java:502) at java.lang.ref.Reference.tryHandlePending(Reference.java:191) - locked <0x0000000795586b68> (a java.lang.ref.Reference$Lock) at java.lang.ref.Reference$ReferenceHandler.run(Reference.java:153) "VM Thread" os_prio=31 tid=0x00007f917c02b800 nid=0x2d03 runnable "GC task thread#0 (ParallelGC)" os_prio=31 tid=0x00007f917c00b000 nid=0x1d07 runnable "GC task thread#1 (ParallelGC)" os_prio=31 tid=0x00007f917c00b800 nid=0x1e03 runnable "GC task thread#2 (ParallelGC)" os_prio=31 tid=0x00007f917c00c000 nid=0x5403 runnable "GC task thread#3 (ParallelGC)" os_prio=31 tid=0x00007f917c00c800 nid=0x5303 runnable "VM Periodic Task Thread" os_prio=31 tid=0x00007f917b06b800 nid=0x3b03 waiting on condition JNI global references: 22 Found one Java-level deadlock: ============================= "Thread-1": waiting to lock monitor 0x00007f917c02f4b8 (object 0x00000007956f92b8, a com.kotlin.notes.Account), which is held by "Thread-0" "Thread-0": waiting to lock monitor 0x00007f917c031f58 (object 0x0000000795717ac8, a com.kotlin.notes.Account), which is held by "Thread-1" Java stack information for the threads listed above: =================================================== "Thread-1": at com.kotlin.notes.DeadLockKt$usingSynchronized$t2$1.run(DeadLock.kt:31) - waiting to lock <0x00000007956f92b8> (a com.kotlin.notes.Account) - locked <0x0000000795717ac8> (a com.kotlin.notes.Account) at java.lang.Thread.run(Thread.java:748) "Thread-0": at com.kotlin.notes.DeadLockKt$usingSynchronized$t1$1.run(DeadLock.kt:18) - waiting to lock <0x0000000795717ac8> (a com.kotlin.notes.Account) - locked <0x00000007956f92b8> (a com.kotlin.notes.Account) at java.lang.Thread.run(Thread.java:748) Found 1 deadlock.
可以看到最后的部分,输出了deadlock 的信息.
Avoids deadlock by avoiding circular wait with no preemption. Both method are now requesting lock in same order
Read more: https://javarevisited.blogspot.com/2018/08/how-to-avoid-deadlock-in-java-threads.html#ixzz5suadJSSP
Ref: How to avoid deadlock in Java Threads? https://javarevisited.blogspot.com/2018/08/how-to-avoid-deadlock-in-java-threads.html
给锁加个等待时间超时时间,超时还未获得锁就放弃,不至于无限等下去.
Lock 框架是同步的兼容替代品,它提供了 synchronized 没有提供的许多特性,它的实现在争用下提供了更好的性能。
多线程编程中,当代码需要同步时我们会用到锁。Java为我们提供了:
内置锁 (synchronized)
显式锁(ReentrantLock)
两种同步方式。
内置锁能够解决大部分需要同步的场景,只有在需要额外灵活性是才需要考虑显式锁,比如可定时、可中断、多等待队列等特性。
显式锁虽然灵活,但是需要显式的申请和释放,并且释放一定要放到finally块中,否则可能会因为异常导致锁永远无法释放!这是显式锁最明显的缺点。
// requesting lock in same order fun solvedSynchronized() { val accountA = Account(10000, "A") val accountB = Account(10000, "B") val t1 = Thread { val rand = Random() for (i in 0..10) { synchronized(accountA) { println("t1 aquired lock on $accountA") synchronized(accountB) { println("t1 aquired lock on $accountB") Account.transfer(accountA, accountB, rand.nextInt(1000)) } } } } val t2 = Thread { val rand = Random() for (i in 0..10) { synchronized(accountA) { println("t2 aquired lock on $accountA") synchronized(accountB) { println("t2 aquired lock on $accountB") Account.transfer(accountB, accountA, rand.nextInt(1000)) } } } } t1.start() t2.start() }
运行输出:
t1 aquired lock on Account(balance=10000, name='A') t1 aquired lock on Account(balance=10000, name='B') Account(balance=9992, name='A') transfer Account(balance=10008, name='B'): 8 t1 aquired lock on Account(balance=9992, name='A') t1 aquired lock on Account(balance=10008, name='B') Account(balance=9076, name='A') transfer Account(balance=10924, name='B'): 916 t1 aquired lock on Account(balance=9076, name='A') t1 aquired lock on Account(balance=10924, name='B') Account(balance=8476, name='A') transfer Account(balance=11524, name='B'): 600 t1 aquired lock on Account(balance=8476, name='A') t1 aquired lock on Account(balance=11524, name='B') Account(balance=7745, name='A') transfer Account(balance=12255, name='B'): 731 t1 aquired lock on Account(balance=7745, name='A') t1 aquired lock on Account(balance=12255, name='B') Account(balance=6780, name='A') transfer Account(balance=13220, name='B'): 965 t1 aquired lock on Account(balance=6780, name='A') t1 aquired lock on Account(balance=13220, name='B') Account(balance=6577, name='A') transfer Account(balance=13423, name='B'): 203 t1 aquired lock on Account(balance=6577, name='A') t1 aquired lock on Account(balance=13423, name='B') Account(balance=6038, name='A') transfer Account(balance=13962, name='B'): 539 t1 aquired lock on Account(balance=6038, name='A') t1 aquired lock on Account(balance=13962, name='B') Account(balance=5392, name='A') transfer Account(balance=14608, name='B'): 646 t1 aquired lock on Account(balance=5392, name='A') t1 aquired lock on Account(balance=14608, name='B') Account(balance=4965, name='A') transfer Account(balance=15035, name='B'): 427 t1 aquired lock on Account(balance=4965, name='A') t1 aquired lock on Account(balance=15035, name='B') Account(balance=4518, name='A') transfer Account(balance=15482, name='B'): 447 t1 aquired lock on Account(balance=4518, name='A') t1 aquired lock on Account(balance=15482, name='B') Account(balance=3562, name='A') transfer Account(balance=16438, name='B'): 956 t2 aquired lock on Account(balance=3562, name='A') t2 aquired lock on Account(balance=16438, name='B') Account(balance=16437, name='B') transfer Account(balance=3563, name='A'): 1 t2 aquired lock on Account(balance=3563, name='A') t2 aquired lock on Account(balance=16437, name='B') Account(balance=16255, name='B') transfer Account(balance=3745, name='A'): 182 t2 aquired lock on Account(balance=3745, name='A') t2 aquired lock on Account(balance=16255, name='B') Account(balance=15433, name='B') transfer Account(balance=4567, name='A'): 822 t2 aquired lock on Account(balance=4567, name='A') t2 aquired lock on Account(balance=15433, name='B') Account(balance=14707, name='B') transfer Account(balance=5293, name='A'): 726 t2 aquired lock on Account(balance=5293, name='A') t2 aquired lock on Account(balance=14707, name='B') Account(balance=14193, name='B') transfer Account(balance=5807, name='A'): 514 t2 aquired lock on Account(balance=5807, name='A') t2 aquired lock on Account(balance=14193, name='B') Account(balance=13997, name='B') transfer Account(balance=6003, name='A'): 196 t2 aquired lock on Account(balance=6003, name='A') t2 aquired lock on Account(balance=13997, name='B') Account(balance=13683, name='B') transfer Account(balance=6317, name='A'): 314 t2 aquired lock on Account(balance=6317, name='A') t2 aquired lock on Account(balance=13683, name='B') Account(balance=13541, name='B') transfer Account(balance=6459, name='A'): 142 t2 aquired lock on Account(balance=6459, name='A') t2 aquired lock on Account(balance=13541, name='B') Account(balance=13274, name='B') transfer Account(balance=6726, name='A'): 267 t2 aquired lock on Account(balance=6726, name='A') t2 aquired lock on Account(balance=13274, name='B') Account(balance=13135, name='B') transfer Account(balance=6865, name='A'): 139 t2 aquired lock on Account(balance=6865, name='A') t2 aquired lock on Account(balance=13135, name='B') Account(balance=12458, name='B') transfer Account(balance=7542, name='A'): 677
使用 ReentrantLock 的顺序加锁:
// lock in same order fun solvedReentrantLock1() { val accountA = Account(10000, "A") val accountB = Account(10000, "B") val lock1 = ReentrantLock() val lock2 = ReentrantLock() val t1 = Thread { val rand = Random() for (i in 0..10) { lock1.lock() lock2.lock() try { Account.transfer(accountA, accountB, rand.nextInt(1000)) } finally { lock1.unlock() lock2.unlock() } } } val t2 = Thread { val rand = Random() for (i in 0..10) { lock1.lock() lock2.lock() try { Account.transfer(accountB, accountA, rand.nextInt(1000)) } finally { lock1.unlock() lock2.unlock() } } } t1.start() t2.start() }
运行输出:
Account(balance=9308, name='A') transfer Account(balance=10692, name='B'): 692 Account(balance=8989, name='A') transfer Account(balance=11011, name='B'): 319 Account(balance=8390, name='A') transfer Account(balance=11610, name='B'): 599 Account(balance=8283, name='A') transfer Account(balance=11717, name='B'): 107 Account(balance=7660, name='A') transfer Account(balance=12340, name='B'): 623 Account(balance=6957, name='A') transfer Account(balance=13043, name='B'): 703 Account(balance=6714, name='A') transfer Account(balance=13286, name='B'): 243 Account(balance=5728, name='A') transfer Account(balance=14272, name='B'): 986 Account(balance=5300, name='A') transfer Account(balance=14700, name='B'): 428 Account(balance=4543, name='A') transfer Account(balance=15457, name='B'): 757 Account(balance=4336, name='A') transfer Account(balance=15664, name='B'): 207 Account(balance=14954, name='B') transfer Account(balance=5046, name='A'): 710 Account(balance=14526, name='B') transfer Account(balance=5474, name='A'): 428 Account(balance=14289, name='B') transfer Account(balance=5711, name='A'): 237 Account(balance=13655, name='B') transfer Account(balance=6345, name='A'): 634 Account(balance=13621, name='B') transfer Account(balance=6379, name='A'): 34 Account(balance=13226, name='B') transfer Account(balance=6774, name='A'): 395 Account(balance=13161, name='B') transfer Account(balance=6839, name='A'): 65 Account(balance=12382, name='B') transfer Account(balance=7618, name='A'): 779 Account(balance=12365, name='B') transfer Account(balance=7635, name='A'): 17 Account(balance=11611, name='B') transfer Account(balance=8389, name='A'): 754 Account(balance=11563, name='B') transfer Account(balance=8437, name='A'): 48
fun solvedReentrantLock2() { val accountA = Account(10000, "A") val accountB = Account(10000, "B") val lockA = ReentrantLock() val lockB = ReentrantLock() val t1 = Thread { val rand = Random() for (i in 0..10) { aquireLock(lockA, lockB) try { Account.transfer(accountA, accountB, rand.nextInt(1000)) } finally { lockA.unlock() lockB.unlock() } } } val t2 = Thread { val rand = Random() for (i in 0..10) { aquireLock(lockB, lockA) try { Account.transfer(accountB, accountA, rand.nextInt(1000)) } finally { lockB.unlock() lockA.unlock() } } } t1.start() t2.start() }
其中, aquireLock() 方法如下:
fun aquireLock(lock1: Lock, lock2: Lock) { while (true) { // aquire lock var gotLock1 = false var gotLock2 = false try { gotLock1 = lock1.tryLock() gotLock2 = lock2.tryLock() } finally { if (gotLock1 && gotLock2) return if (gotLock1) { lock1.unlock() } if (gotLock2) { lock2.unlock() } } // if locks not aquired Thread.sleep(1) } }
运行输出:
Account(balance=9922, name='A') transfer Account(balance=10078, name='B'): 78 Account(balance=9898, name='A') transfer Account(balance=10102, name='B'): 24 Account(balance=9503, name='A') transfer Account(balance=10497, name='B'): 395 Account(balance=8673, name='A') transfer Account(balance=11327, name='B'): 830 Account(balance=8254, name='A') transfer Account(balance=11746, name='B'): 419 Account(balance=7887, name='A') transfer Account(balance=12113, name='B'): 367 Account(balance=7768, name='A') transfer Account(balance=12232, name='B'): 119 Account(balance=7454, name='A') transfer Account(balance=12546, name='B'): 314 Account(balance=7434, name='A') transfer Account(balance=12566, name='B'): 20 Account(balance=7047, name='A') transfer Account(balance=12953, name='B'): 387 Account(balance=6345, name='A') transfer Account(balance=13655, name='B'): 702 Account(balance=12859, name='B') transfer Account(balance=7141, name='A'): 796 Account(balance=12576, name='B') transfer Account(balance=7424, name='A'): 283 Account(balance=11733, name='B') transfer Account(balance=8267, name='A'): 843 Account(balance=11117, name='B') transfer Account(balance=8883, name='A'): 616 Account(balance=10256, name='B') transfer Account(balance=9744, name='A'): 861 Account(balance=9944, name='B') transfer Account(balance=10056, name='A'): 312 Account(balance=9352, name='B') transfer Account(balance=10648, name='A'): 592 Account(balance=8944, name='B') transfer Account(balance=11056, name='A'): 408 Account(balance=8009, name='B') transfer Account(balance=11991, name='A'): 935 Account(balance=7517, name='B') transfer Account(balance=12483, name='A'): 492 Account(balance=6616, name='B') transfer Account(balance=13384, name='A'): 901
ReentrantLock是基于AQS实现的,AQS的基础又是CAS. AQS基于FIFO队列.
Ref: ReentrantLock的实现原理: https://www.cnblogs.com/xrq730/p/4979021.html
我相信乔布斯说的,只有那些疯狂到认为自己可以改变世界的人才能真正地改变世界。面对压力,我可以挑灯夜战、不眠不休;面对困难,我愿意迎难而上、永不退缩。
其实我想说的是,我也只是一个程序员,这也是我现在简单/纯粹人生的全部。
https://gitee.com/universsky/kotlin-notes
国内第一Kotlin 开发者社区公众号,主要分享、交流 Kotlin 编程语言、Spring Boot、Android、React.js/Node.js、函数式编程、编程思想等相关主题。