死锁的解决方案:锁排序 [英] Solution to Deadlock: Lock Ordering

问题描述

在以下代码中，如果两个线程同时调用 transaction() 函数，转置不同的帐户，则可能出现死锁.

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

另一个可能会调用

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:这是来自一本关于操作系统的教科书.这不是家庭作业，只是死锁章节的一部分.

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

推荐答案

这是 中描述的问题(连同解决方案)Java Concurrency in Practice，即item 10.1.2 Dynamic lock order deadlocks，它是专门为Java编写的，但逻辑可以很好地应用于其他上下文(比如你的).

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.

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

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.

例如在 Java 中，它会是:

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

<小时>

补充说明

• 如果 Account 有一个唯一的、不可变的、可比较的键，例如唯一的数字、标识符或类似的东西，那么引入锁排序会更容易:通过键对对象进行排序, 这样就不需要 tieBreaker 锁了.

• If Account would has 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.

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

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

这篇关于死锁的解决方案:锁排序的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！