写一个肯定会陷入僵局的程序

我最近在采访中得到了这个问题。

我回答说，如果交错发生，就会发生死锁，但是采访者坚持认为，一个程序总是会陷入僵局，而不pipe交错如何。

我们可以写这样的程序吗？ 你能指点我一些这样的例子程序？

Answer 1

更新： 这个问题是我的博客在2013年1月的主题 。 感谢您的好问题！

---

我们如何编写一个无论线程如何安排都会进入死锁的程序呢？

这是C＃中的一个例子。 请注意该程序似乎不包含locking和共享数据。 它只有一个局部variables和三个语句，然而它以100％的确定性死锁。 一个人很难想出一个简单的程序，肯定会陷入僵局。

运用读者＃1：解释这个僵局如何。 （答案在评论中。）

运用读者＃2：展示Java中的相同死锁。 （答案在这里： https : //stackoverflow.com/a/9286697/88656 ）

class MyClass { static MyClass() { // Let's run the initialization on another thread! var thread = new System.Threading.Thread(Initialize); thread.Start(); thread.Join(); } static void Initialize() { /* TODO: Add initialization code */ } static void Main() { } } 

Answer 2

这里的闩锁确保当每个线程试图locking另一个锁时，两个锁都被保持：

 import java.util.concurrent.CountDownLatch; public class Locker extends Thread { private final CountDownLatch latch; private final Object obj1; private final Object obj2; Locker(Object obj1, Object obj2, CountDownLatch latch) { this.obj1 = obj1; this.obj2 = obj2; this.latch = latch; } @Override public void run() { synchronized (obj1) { latch.countDown(); try { latch.await(); } catch (InterruptedException e) { throw new RuntimeException(); } synchronized (obj2) { System.out.println("Thread finished"); } } } public static void main(String[] args) { final Object obj1 = new Object(); final Object obj2 = new Object(); final CountDownLatch latch = new CountDownLatch(2); new Locker(obj1, obj2, latch).start(); new Locker(obj2, obj1, latch).start(); } } 

有趣的是运行jconsole，它将正确地显示线程选项卡中的死锁。

Answer 3

当线程（或任何你的平台调用其执行单元）获取资源时， 会发生死锁 ，每个资源一次只能由一个线程持有，并以这种方式持有这些资源，使得持有不能被抢占;在线程之间存在一些“循环”关系，使得死锁中的每个线程都在等待获取另一个线程所持有的资源。

所以，避免死锁的简单方法是对资源进行一些总体sorting ，并规定只有线程才能获得资源。 相反，可以通过运行获取资源的线程有意创build死锁，但不要按顺序获取它们。 例如：

两个线程，两个锁。 第一个线程运行一个循环，尝试以某种顺序获取锁，第二个线程运行一个循环，尝试以相反的顺序获取锁。 每个线程在成功获取锁之后释放这两个锁。

 public class HighlyLikelyDeadlock { static class Locker implements Runnable { private Object first, second; Locker(Object first, Object second) { this.first = first; this.second = second; } @Override public void run() { while (true) { synchronized (first) { synchronized (second) { System.out.println(Thread.currentThread().getName()); } } } } } public static void main(final String... args) { Object lock1 = new Object(), lock2 = new Object(); new Thread(new Locker(lock1, lock2), "Thread 1").start(); new Thread(new Locker(lock2, lock1), "Thread 2").start(); } } 

现在，这个问题上有几点意见指出了僵局的可能性和确定性的区别。 从某种意义上说，这个区别是一个学术问题。 从实际的angular度来看，我当然希望看到一个正在运行的系统，它不会与我上面写的代码发生死锁:)

然而，面试问题有时可能是学术性的，而这个问题在标题中确实有“肯定”一词，所以接下来是一个肯定会陷入僵局的程序。 创build两个Locker对象，每个对象都有两个锁和一个用于在线程之间同步的CountDownLatch 。 每个Lockerlocking第一个锁，然后倒计数一次。 当两个线程都获得一个锁并倒计时时，它们继续经过闩锁屏障并试图获得第二个锁，但是在每种情况下，另一个线程已经保持了期望的锁。 这种情况导致了一定的僵局。

 import java.util.concurrent.CountDownLatch; import java.util.concurrent.locks.Lock; import java.util.concurrent.locks.ReentrantLock; public class CertainDeadlock { static class Locker implements Runnable { private CountDownLatch latch; private Lock first, second; Locker(CountDownLatch latch, Lock first, Lock second) { this.latch = latch; this.first = first; this.second = second; } @Override public void run() { String threadName = Thread.currentThread().getName(); try { first.lock(); latch.countDown(); System.out.println(threadName + ": locked first lock"); latch.await(); System.out.println(threadName + ": attempting to lock second lock"); second.lock(); System.out.println(threadName + ": never reached"); } catch (InterruptedException e) { throw new RuntimeException(e); } } } public static void main(final String... args) { CountDownLatch latch = new CountDownLatch(2); Lock lock1 = new ReentrantLock(), lock2 = new ReentrantLock(); new Thread(new Locker(latch, lock1, lock2), "Thread 1").start(); new Thread(new Locker(latch, lock2, lock1), "Thread 2").start(); } } 

Answer 4

以下是文档中的示例 ：

 public class Deadlock { static class Friend { private final String name; public Friend(String name) { this.name = name; } public String getName() { return this.name; } public synchronized void bow(Friend bower) { System.out.format("%s: %s" + " has bowed to me!%n", this.name, bower.getName()); bower.bowBack(this); } public synchronized void bowBack(Friend bower) { System.out.format("%s: %s" + " has bowed back to me!%n", this.name, bower.getName()); } } public static void main(String[] args) { final Friend alphonse = new Friend("Alphonse"); final Friend gaston = new Friend("Gaston"); new Thread(new Runnable() { public void run() { alphonse.bow(gaston); } }).start(); new Thread(new Runnable() { public void run() { gaston.bow(alphonse); } }).start(); } } 

Answer 5

下面是Eric Lippert的一个Java例子：

 public class Lock implements Runnable { static { System.out.println("Getting ready to greet the world"); try { Thread t = new Thread(new Lock()); t.start(); t.join(); } catch (InterruptedException ex) { System.out.println("won't see me"); } } public static void main(String[] args) { System.out.println("Hello World!"); } public void run() { try { Thread t = new Thread(new Lock()); t.start(); t.join(); } catch (InterruptedException ex) { System.out.println("won't see me"); } } } 

Answer 6

我已经重写了尤里·祖巴列夫的Java版本的Eric Lippert发布​​的死锁例子： https ://stackoverflow.com/a/9286697/2098232更接近于C＃版本。 如果Java的初始化块与C＃静态构造函数类似，并且首先获取锁，我们不需要另一个线程来调用联接方法来获得死锁，那么只需要调用一些Lock类的静态方法，就像原来的C＃例。 导致的僵局似乎证实了这一点。

 public class Lock { static { System.out.println("Getting ready to greet the world"); try { Thread t = new Thread(new Runnable(){ @Override public void run() { Lock.initialize(); } }); t.start(); t.join(); } catch (InterruptedException ex) { System.out.println("won't see me"); } } public static void main(String[] args) { System.out.println("Hello World!"); } public static void initialize(){ System.out.println("Initializing"); } } 

Answer 7

这不是一个最简单的面试任务：在我的项目中，一个团队的工作一整天都陷于瘫痪。 让程序停止是非常容易的，但是很难将其转到线程转储写入的状态，

 Found one Java-level deadlock: ============================= "Thread-2": waiting to lock monitor 7f91c5802b58 (object 7fb291380, a java.lang.String), which is held by "Thread-1" "Thread-1": waiting to lock monitor 7f91c6075308 (object 7fb2914a0, a java.lang.String), which is held by "Thread-2" Java stack information for the threads listed above: =================================================== "Thread-2": at uk.ac.ebi.Deadlock.run(Deadlock.java:54) - waiting to lock <7fb291380> (a java.lang.String) - locked <7fb2914a0> (a java.lang.String) - locked <7f32a0760> (a uk.ac.ebi.Deadlock) at java.lang.Thread.run(Thread.java:680) "Thread-1": at uk.ac.ebi.Deadlock.run(Deadlock.java:54) - waiting to lock <7fb2914a0> (a java.lang.String) - locked <7fb291380> (a java.lang.String) - locked <7f32a0580> (a uk.ac.ebi.Deadlock) at java.lang.Thread.run(Thread.java:680) 

所以我们的目标就是解决JVM会陷入僵局的僵局。 显然，没有解决scheme

 synchronized (this) { wait(); } 

将在这个意义上工作，即使他们将永远停止。 依靠竞争条件也不是一个好主意，因为在采访过程中，你通常想展示一些可行的工作，而不是大多数时候应该工作的东西。

现在， sleep()解决scheme在某种意义上是可以的，很难想象一个不行的情况，但是不公平（我们处于一个公平的运动中，不是吗？）。 @artbristol的解决scheme （我的是相同的，只是不同的对象作为监视器）是很好，但很长，并使用新的并发原语，使线程处于正确的状态，这是没有多less乐趣：

 public class Deadlock implements Runnable { private final Object a; private final Object b; private final static CountDownLatch latch = new CountDownLatch(2); public Deadlock(Object a, Object b) { this.a = a; this.b = b; } public synchronized static void main(String[] args) throws InterruptedException { new Thread(new Deadlock("a", "b")).start(); new Thread(new Deadlock("b", "a")).start(); } @Override public void run() { synchronized (a) { latch.countDown(); try { latch.await(); } catch (InterruptedException ignored) { } synchronized (b) { } } } } 

我记得synchronized唯一的解决scheme符合11..13行代码（不包括注释和导入），但还没有回想起实际的技巧。 如果我这样做会更新。

更新：这是一个丑陋的synchronized解决scheme：

 public class Deadlock implements Runnable { public synchronized static void main(String[] args) throws InterruptedException { synchronized ("a") { new Thread(new Deadlock()).start(); "a".wait(); } synchronized ("") { } } @Override public void run() { synchronized ("") { synchronized ("a") { "a".notifyAll(); } synchronized (Deadlock.class) { } } } } 

请注意，我们用一个对象监视器replace一个闩锁（使用"a"作为对象）。

Answer 8

 import java.util.concurrent.CountDownLatch; public class SO8880286 { public static class BadRunnable implements Runnable { private CountDownLatch latch; public BadRunnable(CountDownLatch latch) { this.latch = latch; } public void run() { System.out.println("Thread " + Thread.currentThread().getId() + " starting"); synchronized (BadRunnable.class) { System.out.println("Thread " + Thread.currentThread().getId() + " acquired the monitor on BadRunnable.class"); latch.countDown(); while (true) { try { latch.await(); } catch (InterruptedException ex) { continue; } break; } } System.out.println("Thread " + Thread.currentThread().getId() + " released the monitor on BadRunnable.class"); System.out.println("Thread " + Thread.currentThread().getId() + " ending"); } } public static void main(String[] args) { Thread[] threads = new Thread[2]; CountDownLatch latch = new CountDownLatch(threads.length); for (int i = 0; i < threads.length; ++i) { threads[i] = new Thread(new BadRunnable(latch)); threads[i].start(); } } } 

程序总是死锁，因为每个线程都在其他线程的屏障上等待，但为了等待屏障，线程必须将显示器放在BadRunnable.class 。

Answer 9

一个简单的search给了我下面的代码：

 public class Deadlock { static class Friend { private final String name; public Friend(String name) { this.name = name; } public String getName() { return this.name; } public synchronized void bow(Friend bower) { System.out.format("%s: %s" + " has bowed to me!%n", this.name, bower.getName()); bower.bowBack(this); } public synchronized void bowBack(Friend bower) { System.out.format("%s: %s" + " has bowed back to me!%n", this.name, bower.getName()); } } public static void main(String[] args) { final Friend alphonse = new Friend("Alphonse"); final Friend gaston = new Friend("Gaston"); new Thread(new Runnable() { public void run() { alphonse.bow(gaston); } }).start(); new Thread(new Runnable() { public void run() { gaston.bow(alphonse); } }).start(); } } 

来源： 僵局

Answer 10

这里有一个Java的例子

http://baddotrobot.com/blog/2009/12/24/deadlock/

绑架者陷入僵局，拒绝放弃受害者直到获得现金，但谈判者拒绝放弃现金，直到他成为受害者。

Answer 11

这里是一个示例，其中一个线程保持锁启动另一个线程，要求相同的锁，然后启动器等待，直到开始完成…永远：

 class OuterTask implements Runnable { private final Object lock; public OuterTask(Object lock) { this.lock = lock; } public void run() { System.out.println("Outer launched"); System.out.println("Obtaining lock"); synchronized (lock) { Thread inner = new Thread(new InnerTask(lock), "inner"); inner.start(); try { inner.join(); } catch (InterruptedException e) { e.printStackTrace(); } } } } class InnerTask implements Runnable { private final Object lock; public InnerTask(Object lock) { this.lock = lock; } public void run() { System.out.println("Inner launched"); System.out.println("Obtaining lock"); synchronized (lock) { System.out.println("Obtained"); } } } class Sample { public static void main(String[] args) throws InterruptedException { final Object outerLock = new Object(); OuterTask outerTask = new OuterTask(outerLock); Thread outer = new Thread(outerTask, "outer"); outer.start(); outer.join(); } } 

Answer 12

这个C＃版本，我猜java应该是非常相似的。

 static void Main(string[] args) { var mainThread = Thread.CurrentThread; mainThread.Join(); Console.WriteLine("Press Any key"); Console.ReadKey(); } 

Answer 13

这里是一个例子：

两个线程正在运行，每个线程都在等待其他人释放locking

公共类ThreadClass extends Thread {

 String obj1,obj2; ThreadClass(String obj1,String obj2){ this.obj1=obj1; this.obj2=obj2; start(); } public void run(){ synchronized (obj1) { System.out.println("lock on "+obj1+" acquired"); try { Thread.sleep(3000); } catch (InterruptedException e) { e.printStackTrace(); } System.out.println("waiting for "+obj2); synchronized (obj2) { System.out.println("lock on"+ obj2+" acquired"); try { Thread.sleep(3000); } catch (InterruptedException e) { e.printStackTrace(); } } } } 

}

运行这将导致死锁：

公共类SureDeadlock {

 public static void main(String[] args) { String obj1= new String("obj1"); String obj2= new String("obj2"); new ThreadClass(obj1,obj2); new ThreadClass(obj2,obj1); } 

}