死锁解决方案：锁定订购

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编写的，但逻辑可以很好地应用于其他上下文（如你的）。

因此，由于我们无法控制将以何种顺序提供参数，因此我们需要对锁进行排序，并根据我们编写的整个程序中的诱导排序来获取它们。

诱导该顺序的一种方法是计算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