Solution to Deadlock: Lock Ordering

Question

In the following code a deadlock is possible if two threads simultaneously invoke the transaction() function, transposing different accounts.

void transaction(Account from, Account to, double amount)
{
      mutex lock1, lock2;
      lock1 = getlock(from);
      lock2 = getlock(to);

      acquire(lock1);
      acquire(lock2);
         withdraw(from, amount);
         deposit(to, amount);
      release(lock2);
      release(lock1);
}

That is, one thread might invoke

transaction(checkingaccount, savingsaccount, 25);

and another might invoke

transaction(savingsaccount, checkingaccount, 50);

What is a good solution to this problem?

One I can think of is to use a witness program that will alert the user that a deadlock has occurred, but there must be a better solution implementable by modifying the code. Any ideas?

PS: This is from a textbook on operating systems. This is not homework, just part of the chapter on deadlocks.

Answer 1

This is a problem described (along with the solution) in Java Concurrency in Practice, namely item 10.1.2 Dynamic lock order deadlocks, which is written specifically for Java but the logic can be well applied to other contexts (like yours).

So, as we cannot control in which order the arguments are going to be provided, we need to induce an ordering on the locks and acquire them according to the induced ordering consistently throughout the program we are writing.

One way to induce that order would be calculate the hash code of the from and to objects and synchronize first taking the lock from the object with lower hash code. In (the rare) case that two Account objects have the same hash code, we would need to introduce a third lock which would "break" the tie.

For example in Java, it would be:

int fromHash = System.identityHashCode(from);
int toHash = System.identityHashCode(to);

---

Now, taking your code as reference, it could be something like the below code.

Object objectForTieBreakerLock = new Object(); // a valid new object here according to your language
void transaction(Account from, Account to, double amount)
{
      mutex lock1, lock2, tieBreaker;
      lock1 = getlock(from);
      lock2 = getlock(to);

      int fromHash = /*any language specific function to get object hash*/;
      int toHash = /*any language specific function to get object hash*/;

      if (fromHash < toHash) {
          acquire(lock1);
          acquire(lock2);
          doTransaction(from, to, amount);
          release(lock2);
          release(lock1);
      }
      else if (fromHash > toHash) {
          acquire(lock2);
          acquire(lock1);
          doTransaction(from, to, amount);
          release(lock1);
          release(lock2);
      }
      else {
          tieBreaker = getlock(objectForTieBreakerLock);
          acquire(tieBreaker);
          acquire(lock1);
          acquire(lock2);
          doTransaction(from, to, amount);
          release(lock2);
          release(lock1);
          release(tieBreaker);
      }
}

// this must be a private (helper) method
void doTransaction(Account from, Account to, double amount)
{
     withdraw(from, amount);
     deposit(to, amount);
}

---

Additional notes

• If Account would have a unique, immutable, comparable key such as a unique number, identifier, or something like that, inducing a lock ordering would be easier: order objects by their keys, eliminating this way the need for the tieBreaker lock.

• Full Java Code Example: http://jcip.net/listings/InduceLockOrder.java

Answer 2

I solved this problem in my C# FeatureLoom library by keeping track of which thread holds or waits for which lock. So I am able to identify a lock ordering deadlock before it actually happens and can resolve it by "borrowing" the lock.

Simply replace your lock(lockObject){ ... } code-blocks with using(LockOrderDeadlockResolver(lockObject)){ ... } and possible deadlocks will be resolved!

Here is the full implementation of the solution:

using System;
using System.Collections.Concurrent;
using System.Collections.Generic;
using System.Runtime.CompilerServices;
using System.Threading;

namespace FeatureLoom.Core.Synchronization
{
    public static class LockOrderDeadlockResolver
    {
        // Maps the lockObject to the thread that it holds it.
        static ConcurrentDictionary<object, Thread> holdingThreads = new ConcurrentDictionary<object, Thread>();

        // ConditionalWeakTable is used to ensure that the thread is not kept alive after it finished.
        // The alternative would be to remove it from the table each time it does not hold any lock and add it again when it enters a lock,
        // but that would be quite costly.
        static ConditionalWeakTable<Thread, ThreadLockInfo> threadLockInfos = new ConditionalWeakTable<Thread, ThreadLockInfo>();

        private class ThreadLockInfo
        {            
            public List<object> heldLocks = new List<object>();
            public object waitingForLock = null;
        }

        /// <summary>
        /// Enters a Monitor lock for the passed lockObject and returns a disposable handle to be used in a using-statement.
        /// If a deadlock (caused by inverse lock order) is detected, the blocked lock is "borrowed" to finally resolve the deadlock.
        /// Usage is similar to the lock() statement: using(LockOrderDeadlockResolver.Lock(lockObject)){ ... }
        /// Note: Deadlocks can only be detected if all involved threads used LockOrderDeadlockResolver.Lock() instead of lock() or Monitor.Enter().
        /// But beside this, LockOrderDeadlockResolver.Lock() works together with lock() and Monitor.Enter().
        /// </summary>
        /// <param name="lockObject">The object that is used for the Monitor.Enter(lockObject)</param>
        /// <returns></returns>
        public static MonitorLockHandle Lock(object lockObject)
        {
            Thread thread = Thread.CurrentThread;
            ThreadLockInfo threadLockInfo = threadLockInfos.GetValue(thread, _ => new ThreadLockInfo() );            

            if (Monitor.TryEnter(lockObject))
            {                       
                // heldLocks does not have any concurrent access, because only the own thread will access it.
                threadLockInfo.heldLocks.Add(lockObject);
                holdingThreads[lockObject] = thread;
            }
            else
            {                
                if (isDeadlock(lockObject, threadLockInfo.heldLocks))
                {                    
                    // That would normally be a deadlock. But, we know that the owner of the lock is blocked until the current thread finishes,
                    // so we let it "borrow" the lock from the actual owner, in order to resolve the deadlock.
                    return new MonitorLockHandle(null);
                }

                threadLockInfo.waitingForLock = lockObject;

                Monitor.Enter(lockObject);

                threadLockInfo.waitingForLock = null;
                threadLockInfo.heldLocks.Add(lockObject);
                holdingThreads[lockObject] = thread;
            }

            return new MonitorLockHandle(lockObject);
        }

        private static bool isDeadlock(object lockObject, List<object> heldLocks)
        {
            if (heldLocks.Count == 0) return false;

            if (holdingThreads.TryGetValue(lockObject, out Thread holdingThread))
            {
                if (threadLockInfos.TryGetValue(holdingThread, out ThreadLockInfo holdingThreadInfo) &&
                    holdingThreadInfo.waitingForLock != null)
                {
                    if (heldLocks.Contains(holdingThreadInfo.waitingForLock))
                    {
                        // Current Thread A holds a lock that Thread B waits for. But Thread B holds the lock that Thread A wants to get right now. That is a deadlock.
                        return true;
                    }
                    else
                    {
                        // Thread B holds the lock that Thread A wants to get right now, but it waits for a lock that Thread C holds.
                        // We need to check if Thread C waits for the lock that Thread A holds, because that would be a deadlock, too.
                        // The recursion can detect a deadlock chain of any length.
                        return isDeadlock(holdingThreadInfo.waitingForLock, heldLocks);
                    }
                }
            }
            return false;
        }

        private static void ReleaseLock(object lockObject)
        {
            Thread thread = Thread.CurrentThread;
            if (threadLockInfos.TryGetValue(thread, out var threadLockInfo))
            {
                threadLockInfo.heldLocks.Remove(lockObject);
            }
            holdingThreads.TryRemove(lockObject, out _);
            Monitor.Exit(lockObject);
        }

        // To be used in a using statement to ensure the release of the lock.
        public struct MonitorLockHandle :IDisposable
        {
            object lockObject;

            public MonitorLockHandle(object lockObject)
            {
                this.lockObject = lockObject;
            }

            public void Dispose()
            {
                // If no lockObject was set, the lock was "borrowed", due to a deadlock.
                if (lockObject != null) ReleaseLock(lockObject);
            }
        }
    }
}