死锁的解决方案：锁顺序

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

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

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

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

Answer 1

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

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

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

例如，在 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