multithreading - 解决死锁: Lock Ordering

Question

在以下代码中，如果两个线程同时调用 transaction()，则可能发生死锁。功能，转置不同的帐户。

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

也就是说，一个线程可能会调用

transaction(checkingaccount, savingsaccount, 25);

另一个可能会调用

transaction(savingsaccount, checkingaccount, 50);

这个问题有什么好的解决办法？

我能想到的一个是使用witness程序，它会提醒用户发生了死锁，但必须有更好的解决方案可以通过修改代码来实现。有任何想法吗？

PS:这是来自操作系统的教科书。这不是作业，只是死锁章节的一部分。

Answer 1

这是 Java Concurrency in Practice 中描述的问题(连同解决方案) ，即项目 10.1.2 动态锁顺序死锁，它是专门为 Java 编写的，但该逻辑可以很好地应用于其他上下文(如您的)。

因此，由于我们无法控制提供参数的顺序，我们需要 诱导订购 在我们正在编写的程序中，根据诱导顺序一致地获取它们。

诱导该顺序的一种方法是计算 from 的哈希码。和 to对象并同步首先从具有较低哈希码的对象中获取锁。在(罕见的)情况下，两个 Account对象具有相同的哈希码，我们需要引入第三个锁来“打破”平局。

例如在 Java 中，它将是:

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

现在，以您的代码为引用，它可能类似于以下代码。

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

补充说明

如 Account将有一个唯一的、不可变的、可比较的键，例如唯一的数字、标识符或类似的东西，引入锁排序会更容易:按对象的键排序，这样就不需要 tieBreaker锁。

完整的 Java 代码示例:http://jcip.net/listings/InduceLockOrder.java