在以下代码中,如果两个线程同时调用 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:这是来自操作系统的教科书。这不是作业,只是死锁章节的一部分。
最佳答案
这是 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
锁。 关于multithreading - 解决死锁: Lock Ordering,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/29424306/