Locking Strategies and Techniques for Preventing Deadlocks in Code

Locking strategies and techniques for preventing deadlocks in code

The technique you describe isn't just common: it's the one technique that has been proven to work all the time. There are a few other rules you should follow when coding threaded code in C++, though, among which the most important may be:

don't hold a lock when calling a virtual function: even if at the time you're writing your code you know which function will be called and what it will do, code evolves, and virtual functions are there to be overridden, so ultimately, you won't know what it does and whether it will take any other locks, meaning you will lose your guaranteed order of locking
watch out for race conditions: in C++, nothing will tell you when a given piece of data is shared between threads and you don't use some kind of synchronization on it. One example of this was posted in the C++ Lounge on SO chat a few days ago, by Luc, as an example of this (code at the end of this post): just trying to synchronize on something else that happens to be in the neighborhood doesn't mean your code is correctly synchronized.
try to hide asynchronous behavior: you're usually better hiding your concurrency in your software's architecture, such that most calling code won't care whether there's a thread there or not. It makes the architecture easier to work with - especially for some-one who isn't used to concurrency.

I could go on for a while, but in my experience, the easiest way to work with threads is using patterns that are well-known to everyone who might work with the code, such as the producer/consumer pattern: it's easy to explain and you only need one tool (a queue) to allow your threads to communicate with each other. After all, the only reason for two threads to be synchronized with each other, is to allow them to communicate.

More general advice:

Don't try your hand at lock-free programming until you've had experience with concurrent programming using locks - it's an easy way to blow your foot off, or run into very strange bugs.
Reduce the number of shared variables and the number of times those variables are accessed to a bare minimum.
Don't count on two events always occurring in the same order, even if you can't see any way of them reversing order.
More generally: don't count on timing - don't think a given task should always take a given amount of time.

The following code will fail:

#include <thread>
#include <cassert>
#include <chrono>
#include <iostream>
#include <mutex>
 
void
nothing_could_possibly_go_wrong()
{
    int flag = 0;
 
    std::condition_variable cond;
    std::mutex mutex;
    int done = 0;
    typedef std::unique_lock<std::mutex> lock;
 
    auto const f = [&]
    {
        if(flag == 0) ++flag;
        lock l(mutex);
        ++done;
        cond.notify_one();
    };
    std::thread threads[2] = {
        std::thread(f),
        std::thread(f)
    };
    threads[0].join();
    threads[1].join();
 
    lock l(mutex);
    cond.wait(l, [done] { return done == 2; });
 
    // surely this can't fail!
    assert( flag == 1 );
}
 
int
main()
{
    for(;;) nothing_could_possibly_go_wrong();
}

Tips to prevent deadlocks in java

Some quick tips out of my head

don't use multiple threads (like Swing does, for example, by mandating that everything is done in the EDT)
don't hold several locks at once. If you do, always acquire the locks in the same order
don't execute foreign code while holding a lock
use interruptible locks

What is a deadlock?

A lock occurs when multiple processes try to access the same resource at the same time.

One process loses out and must wait for the other to finish.

A deadlock occurs when the waiting process is still holding on to another resource that the first needs before it can finish.

So, an example:

Resource A and resource B are used by process X and process Y

X starts to use A.
X and Y try to start using B
Y 'wins' and gets B first
now Y needs to use A
A is locked by X, which is waiting for Y

The best way to avoid deadlocks is to avoid having processes cross over in this way. Reduce the need to lock anything as much as you can.

In databases avoid making lots of changes to different tables in a single transaction, avoid triggers and switch to optimistic/dirty/nolock reads as much as possible.

How to prevent deadlocks in synchronized methods?

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

}

Avoid deadlocks in a multithreaded process

Please see What are common reasons for deadlocks?

Is what I am doing preventing Deadlock?

TL;DR: Yes, this system is totally immune to deadlock. At any point in time, the thread holding the highest-numbered lock must be able to make progress, since it cannot be waiting to acquire any locks held by other processes. More formally, your conditions ensure a total ordering on lock acquisition by all processes, which in turn ensures that circular wait can never occur. Circular wait is a necessary precondition for deadlock.

Detail: In order for deadlock to take place, all four of the following conditions must apply (see relevant Wikipedia):

Mutual exclusion - i.e. concurrent processes are accessing unsharable resources. Locks are unsharable by definition (they are also called mutexes for this reason).
Hold and wait - at least one process is attempting to access multiple resources, and it does so by holding some of them and then waiting for the others. This condition probably applies in your case, depending on the exact semantics of your program.
No preemption - it is not possible for processes to have their resources taken from them by other processes. Once again, this is a property of the locks we're using.
Circular wait - there is a cycle of processes, each waiting on a resource held by the next. This condition doesn't apply here. Consider a thread A, waiting on accessing a lock L_i. That lock must be held by a thread B which has already obtained all the locks it requires from indices 1 to i. As a result, B cannot be waiting on A. Similarly, any thread that B is waiting on in order to acquire its next lock L_j (where j > i by the order in which locks are acquired) cannot be waiting on any locks with indices 1 to j. By induction, there can be no cycles of dependency in this system.

In concurrent programming, it is typical for the first three cases to be set by the context in which you are developing (which concurrency primitives are being used etc.), whereas the last can occasionally™ be avoided by cleverness.

Deadlock prevention in a complicated system

If the mutex support non-blocking acquisition (often referred as trylock), a deadlock-avoiding solution can be implemented without lock ordering/hierarchy. The algorithm is as follows:

Acquire the lock for the first resource; here waiting is allowed.
Once the first lock is acquired, try acquiring another one with try-lock.
If try-lock fails (indicating that a resource is busy), release all previously acquired locks and go to the step 1.
If try-lock succeeds, repeat from step 2 for all remaining resources.

Deadlock avoidance is achieved through non-blocking acquisition (never wait for a lock if you already hold one) and cooperation (be a good neighbor and release whatever you already acquired if you cannot continue without blocking).

Such a strategy is used in e.g. Boost for acquiring multiple locks at once. Actually, in Boost it's even more advanced: after releasing locks at step 3, they start waiting from the lock that was busy at the previous attempt.

Also, look at these SO topics: Acquire a lock on two mutexes and avoid deadlock, Multiple mutex locking strategies and why libraries don't use address comparison

Synchronized methods to avoid deadlock

for example when a thread has a lock on a variable res1 but needs a lock on variable res2

What matters is not that there are two variables, what matters is that there must be two (or more) locks.

The names "res1" and "res2" are meant to suggest two resources each of which may have one or more variables, and each of which has its own lock. Here's where you get into trouble:

final Object lock1 = new Object();
final Object lock2 = new Object();

public void method1() {
    synchronized (lock1) {
        // Call Thread.sleep(1000) here to simulate the thread losing its time slice.
        synchronized(lock2) {
            doSomethingThatRequiresBothLocks
        }
    }
}

public void method2() {
    synchronized (lock2) {
        // Do the same here 'cause you can't know which thread will get to run first.
        synchronized(lock1) {
            doSomethingElseThatRequiresBothLocks()
        }
    }
}

If thread A calls method1(), there is a very small chance that it could lose its time slice (i.e., turn to run) just after it successfully locks lock1, but before it locks lock2.

Then, while thread A is waiting its turn to run again, thread B calls method2(). Thread B will be able to lock lock2, but then it gets stuck because lock1 is locked by thread A. Furthermore, when thread A gets to run again, it will immediately be blocked when it tries to lock lock2 which is owned by thread B. Neither thread will ever be able to continue from that point.

In real code, it's never so obvious. When it happens in real-life, it usually is because of some unforseen interaction between code from two or more different modules that may not even be aware of each other, but which access the same common resources.

Locking Strategies and Techniques for Preventing Deadlocks in Code