How to prevent deadlocks in synchronized methods?

Question

In the following Code there is a potential to enter a Deadlock similar to this Question "Deadlocks and Synchronized methods", now i understand why the two Threads are entering a deadlock, but when i execute the code the Threads always enters a Deadlock so:

1 - When is a Deadlock not possible in this code ?

2 - How to prevent it from happening ?

I tried using wait() and notifyAll() like this :

wait()
waver.waveBack(this)

and then calling notifyAll() in waveBack(), but it didn't work what am i missing or misunderstood ?

package mainApp;

public class Wave {

    static class Friend {

        private final String name;

        public Friend(String name) {
            this.name = name;
        }

        public String getName() {
            return this.name;
        }

        public synchronized void wave(Friend waver) {
            String tmpname = waver.getName();
            System.out.printf("%s : %s has waved to me!%n", this.name, tmpname);
            waver.waveBack(this);
        }

        public synchronized void waveBack(Friend waver) {
            String tmpname = waver.getName();
            System.out.printf("%s : %s has waved back to me!%n", this.name, tmpname);
        }
    }

    public static void main(String[] args) {
        final Friend friendA = new Friend("FriendA");
        final Friend friendB = new Friend("FriendB");
        new Thread(new Runnable() {
            public void run() {
                friendA.wave(friendB);
            }
        }).start();
        new Thread(new Runnable() {
            public void run() {
                friendB.wave(friendA);
            }
        }).start();
    }

}

Answer 1

In this case, simply do not call another method that might need the lock while holding the lock. This ensures that there is always a moment in time where a method can get the lock and progress can be made.

Calling wait() before waver.waveBack(this) causes a chicken and egg problem: waveBack(this) is never called because the thread stops execution at the wait() statement and thus notifyAll() is never called to continue execution.

There are various ways to prevent deadlocks in the context of the example, but let's go with the advice from sarnold in one of the comments in his answer from the question you linked. To paraphrase sarnold: "it is usually easier to reason about locks on data".

Let's assume that the synchronized methods are synchronized to ensure some consistent update of state (i.e. some variables need to be updated but only one thread at any given time can modify these variables). For example, let's register the amount of waves send and waves received. The runnable code below should demonstrate this:

import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.Random;
import java.util.concurrent.ExecutorService;
import java.util.concurrent.Executors;
import java.util.concurrent.Future;
import java.util.stream.Collectors;
import java.util.stream.IntStream;

public class Wave {

    static class Waves {

        final Map<Friend, Integer> send = new HashMap<>();
        final Map<Friend, Integer> received = new HashMap<>();

        void addSend(Friend f) {
            add(f, send);
        }
        void addReceived(Friend f) {
            add(f, received);
        }
        void add(Friend f, Map<Friend, Integer> m) {
            m.merge(f, 1, (i, j) -> i + j);
        }
    }

    static class Friend {

        final String name;

        public Friend(String name) {
            this.name = name;
        }

        final Waves waves = new Waves();

        void wave(Friend friend) {

            if (friend == this) {
                return; // can't wave to self.
            }
            synchronized(waves) {
                waves.addSend(friend);
            }
            friend.waveBack(this); // outside of synchronized block to prevent deadlock
        }

        void waveBack(Friend friend) {

            synchronized(waves) {
                waves.addReceived(friend);
            }
        }

        String waves(boolean send) {

            synchronized(waves) {
                Map<Friend, Integer> m = (send ? waves.send : waves.received);
                return m.keySet().stream().map(f -> f.name + " : " + m.get(f))
                        .sorted().collect(Collectors.toList()).toString();
            }
        }

        @Override
        public String toString() {
            return name + ": " + waves(true) + " / " + waves(false);
        }
    }

    final static int maxThreads = 4;
    final static int maxFriends = 4;
    final static int maxWaves = 50_000;

    public static void main(String[] args) {

        try {
            List<Friend> friends = IntStream.range(0, maxFriends)
                    .mapToObj(i -> new Friend("F_" + i)).collect(Collectors.toList());
            ExecutorService executor = Executors.newFixedThreadPool(maxThreads);
            Random random = new Random();
            List<Future<?>> requests = IntStream.range(0, maxWaves)
                    .mapToObj(i -> executor.submit(() -> 
                        friends.get(random.nextInt(maxFriends))
                            .wave(friends.get(random.nextInt(maxFriends)))
                        )
                    ).collect(Collectors.toList());
            requests.stream().forEach(f -> 
                { try { f.get(); } catch (Exception e) { e.printStackTrace(); } }
            );
            executor.shutdownNow();
            System.out.println("Friend: waves send / waves received");
            friends.stream().forEachOrdered(p -> System.out.println(p));
        } catch (Exception e) {
            e.printStackTrace();
        }
    }

}