死锁解决方案:锁排序 [英] 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并发性，即 10.1.2动态锁顺序死锁，它是专为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屋！