Is it possible to write a guaranteed classic deadlock with synchronized methods?

Question

I was asked at an interview to write java code which is guaranteed deadlock. I wrote a standard code which presents at every Java book, like create 2 threads and call synchronized methods at different order, sleep a little before call the 2nd.

Of course this stuff didn't satisfy the interviewers, so now I'm proceeding to figure the solution out.

I discovered a piece of code:

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");
        }
    }

}

But I'm not sure if this code satisfied them? Sure. The code never ends execution, but is it a true deadlock? Aren't deadlocks about synchronization? And, for example, I can also write an endless cycle, put a Thread.sleep inside and name it a "deadlock".

So the question is: is it possible to write a classic deadlock using synchronized methods but 100% guaranteed? (Please don't tell me about very, very, very likely deadlock cases. I know it.)

Thanks.

One way to deadlock two threads to synchronise on two different object locks in different orders — MadProgrammer, Jun 23 '18 at 00:45
That code is 100% guaranteed true deadlock, but whether it passes at an interview probably depends on the interviewer, I guess. The deadlock happens while trying to acquire the class initialization lock, so it's not obvious. [This version is better.](https://stackoverflow.com/a/16203272/2891664) — Radiodef, Jun 23 '18 at 01:09
I think your question is mostly related to "guaranteed" part as your description of deadlock is correct. The easiest way to make deadlock guaranteed is to just wrap synchronized blocks with infinite while loop and add some logic inside the blocks to prevent their elimination by compiler. — Mikita Harbacheuski, Jun 25 '18 at 10:50

yshavit · Accepted Answer · 2018-06-23T02:33:14.087

3

Create two resources, and have each thread try to get one before releasing the other, but in different orders. For instance:

CountDownLatch a = new CountDownLatch (1);
CountDownLatch b = new CountDownLatch (1);

void one() throws InterruptedException {
  a.await();
  b.countDown();
}

void two() throws InterruptedException {
  b.await();
  a.countDown();
}

The thread that runs one can't release b, because it's waiting for a. It'll wait forever, because the thread that runs two can't release a because it's waiting for b.

One or the classic deadlock scenarios is when you acquire locks in reverse order.

edited Jun 23 '18 at 02:33

answered Jun 23 '18 at 02:05

yshavit

42,327
7
87
124

it's just a more confused (using CountDownLatch) version of a classic deadlock example: final Object lock1 = new Object(); final Object lock2 = new Object(); void method1() { synchronized(lock1) { synchronized(lock2) { //doSomething() } } } void method1() { synchronized(lock2) { synchronized(lock1) { //doSomething() } } } its very likely, but not guaranteed. Jvm can decided to execute first method completely and then the second one – arminvanbuuren Jun 23 '18 at 08:07
The JVM can't do the first method completely. When. It gets to a.await(), it'll block until another thread calls a.countDown(). And that will never happen, because that other thread will block at b.await(). – yshavit Jun 23 '18 at 13:18
ok, i see, thanks... but im pretty sure this way wouldn't satisfy interviewers, it's too high level ) I'm eager to figure out if is it possible to write GUARANTEED deadlock using just synchronized methods (or block) – arminvanbuuren Jun 24 '18 at 18:29
It's possible to do a similar thing by using Object.wait(). I'm not at a computer right now, so I can't amend the answer, but let me know if you can't figure it out and I can write it up later. – yshavit Jun 24 '18 at 19:28

score 1 · Answer 2 · edited Oct 02 '18 at 19:59

class Resource1 {
    synchronized static void method1() {
        try {
            Thread.sleep(1);
        } catch (InterruptedException e) {
        }
        Resource2.method1();
   }
}

class Resource2 {
    synchronized static void method1() {
        Resource1.method1();
   }
}


public class MultiThreadApp {
   public static void main(String[] args) {
       new Thread(new Runnable() {
           public void run() {
               Resource2.method1();
           }
      }).start();
      Resource1.method1();
  }
}

harp1814 · Answer 3 · 2019-06-22T18:07:59.547

public class Deadlock {
    public static void main(String[] args) {
        String res1 = "a";
        String res2 = "s";

        new Thread(
                () -> {
                    synchronized (res1) {
                        try {
                            Thread.sleep(2);
                        } catch (InterruptedException e) {
                        }
                        synchronized (res2) {
                        }
                    }
                }
        ).start();

        new Thread(
                () -> {
                    synchronized (res2) {
                        try {
                            Thread.sleep(2);
                        } catch (InterruptedException e) {
                        }
                        synchronized (res1) {
                        }
                    }
                }
        ).start();
    }
}

Is it possible to write a guaranteed classic deadlock with synchronized methods?

3 Answers3