How to write guaranteed deadlock via wait/notify

Question

I visited interview some recently. Interviewer asked me to write guaranteed deadlock.

I have wrote following:

public class DeadLockThreadSleep {
    private static class MyThread implements Runnable {
        private Object o1;
        private Object o2;

        @Override
        public void run() {
            try {
                test(o1, o2);
            } catch (InterruptedException e) {
                e.printStackTrace();
            }
        }

        public MyThread(Object o1, Object o2) {
            this.o1 = o1;
            this.o2 = o2;
        }

        public void test(Object o1, Object o2) throws InterruptedException {
            synchronized (o1) {
                System.out.println("1.acquired: " + o1);
                Thread.sleep(1000);
                synchronized (o2) {
                    System.out.println("2.acquired: " + o2);

                }
            }
        }
    }

    public static void main(String[] args) {
        Object o1 = new Object();
        Object o2 = new Object();
        new Thread(new MyThread(o1, o2)).start();
        new Thread(new MyThread(o2, o1)).start();

    }
}

Then he asked if I sure that it is guaranted. I rememebered that Thread.sleep nothing guaranteed.

Then I wrote this code:

public static void main(String[] args) {
        final Thread mainThread = Thread.currentThread();
        Thread thread = new Thread(new Runnable() {
            @Override
            public void run() {
                try {
                    mainThread.join();
                } catch (InterruptedException e) {
                    e.printStackTrace();
                }
            }
        });
        thread.start();
        try {
            thread.join();
        } catch (InterruptedException e) {
            e.printStackTrace();
        }
    }

this answer was accepted.

Also he asked to write analog via wait/notify. I thought a lot and I cannot imagine how to write this.

Is it possible?

Answer 1

A deadlock is a so-called liveness hazard (others are starvation, poor responsiveness, or livelocks), where two main types can be considered:

• Lock-ordering deadlocks
• Resource deadlocks

However, the Java documentation simplifies this as follows:

Deadlock describes a situation where two or more threads are blocked forever, waiting for each other.

Hence, IMHO you could simply enforce a deadlock with this:

public class DeadlockDemo {

    public static void main(String[] args) {
        Object a = new Object();
        Object b = new Object();

        new Thread(() -> waitLeftNotifyRight(a, b)).start();
        waitLeftNotifyRight(b, a);
    }

    public static void waitLeftNotifyRight(Object left, Object right) {
        synchronized (left) {
            try {
                System.out.println("Wait");
                left.wait();
            } catch (InterruptedException e) { /* NOP */ }
        }
        synchronized (right) {
            System.out.println("Notify");
            right.notify();
        }
    }

}

This demo never terminates because the created thread waits on a's monitor, whereas the main thread waits on b's monitor. As a result, the corresponding notify() methods aren't invoked (which would terminate the program).

Answer 2

This may be done by creating a cycle where one thread holds a resource and waits for another resource whereas the other thread does the same but in reverse order.

Thread tholds resourceOne and waits for resourceTwo , whereas t1holds resourceTwo and waits for resourceOne

Below is a sample code:

    public class WaitNotifyLock {

        boolean isONHold = false;
        public synchronized void hold(){
            while(isONHold){
                try {
                    wait();
                } catch (InterruptedException e) {
                    // TODO Auto-generated catch block
                e.printStackTrace();
            }
        }
        isONHold = true;
        System.out.println(Thread.currentThread().getId() + " : Holded");
    }

    public synchronized void unHold(){
        while(!isONHold){
            try {
                wait();
            } catch (InterruptedException e) {
                // TODO Auto-generated catch block
                e.printStackTrace();
            }
        }
        System.out.println(Thread.currentThread().getId() + " : Produced");
        isONHold = false;
        notify();
    }

    public static void main(String[] args) {
        WaitNotifyLock resourceOne =  new WaitNotifyLock();
        WaitNotifyLock resourceTwo =  new WaitNotifyLock();
        Thread t = new Thread(new Runnable() {

            @Override
            public void run() {
                // TODO Auto-generated method stub
                resourceOne.hold();
                try {
                    Thread.sleep(2);
                } catch (InterruptedException e) {
                    // TODO Auto-generated catch block
                    e.printStackTrace();
                }
                resourceTwo.hold();
                resourceOne.unHold();
                resourceTwo.unHold();
            }
        });

        Thread t1 = new Thread(new Runnable() {

            @Override
            public void run() {
                resourceTwo.hold();
                try {
                    Thread.sleep(2);
                } catch (InterruptedException e) {
                    // TODO Auto-generated catch block
                        e.printStackTrace();
                }
                resourceOne.hold();
                resourceTwo.unHold();
                resourceOne.unHold();
                }
            });

            t.start();
            t1.start();
        }

    }