0

所以我有这个用 C 编写的基本事务（）函数：

void transaction (Account from, Account to, double amount) {

    mutex lock1, lock2;
    lock1 = get_lock(from);
    lock2 = get_lock(to);

    acquire(lock1);
        acquire(lock2);

            withdraw(from, amount);
            deposit(to, amount);

    release(lock2);
    release (lock1);

}

据我了解，该功能几乎没有死锁，因为该功能先锁定一个帐户，然后锁定另一个帐户（而不是锁定一个帐户，进行更改，然后锁定另一个帐户）。但是，如果这两个调用同时调用此函数：

transaction (savings_account, checking_account, 500);

transaction (checking_account, savings_account, 300);

我被告知这会导致僵局。如何编辑此函数以使其完全没有死锁？

4

2 回答 2

1

您需要创建对象的总排序（在本例中为 Account 对象），然后根据该总排序始终以相同的顺序锁定它们。您可以决定将它们锁定在什么顺序中，但简单的事情是首先锁定总排序中排在首位的一个，然后再锁定另一个。

例如，假设每个帐户都有一个帐号，这是一个唯一的*整数。（* 表示没有两个帐户具有相同的号码）然后您总是可以先锁定具有较小帐号的那个。使用您的示例：

void transaction (Account from, Account to, double amount)
{
    mutex first_lock, second_lock;

    if (acct_no(from) < acct_no(to))
    {
        first_lock  = get_lock(from);
        second_lock = get_lock(to);
    }
    else
    {
        assert(acct_no(to) < acct_no(from)); // total ordering, so == is not possible!
        assert(acct_no(to) != acct_no(from)); // this assert is essentially equivalent

        first_lock  = get_lock(to);
        second_lock = get_lock(from);
    }

    acquire(first_lock);
    acquire(second_lock);

    withdraw(from, amount);
    deposit(to, amount);

    release(second_lock);
    release(first_lock);
}

所以按照这个例子，如果 checks_account 有帐号。1 和 Savings_account 有帐号。2、transaction (savings_account, checking_account, 500);会先锁定checking_account再锁定saving_account，transaction (checking_account, savings_account, 300);也会先锁定checking_account再锁定savings_account。

如果您没有帐号（比如说您使用 Foo 类而不是 Account 类），那么您需要找到其他东西来建立总排序。如果每个对象都有一个名称，作为一个字符串，那么您可以进行字母比较以确定哪个字符串是“少”。或者，您可以使用任何其他与 > 和 < 可比较的类型。

但是，每个对象的值都是唯一的，这一点非常重要！如果两个对象在您正在测试的任何字段中具有相同的值，那么它们在排序中的相同位置。如果这可能发生，那么它是“部分排序”而不是“全排序”，并且对于这个锁定应用程序有一个全排序是很重要的。

如有必要，您可以组成一个“键值”，它是一个没有任何意义的任意数字，但保证该类型的每个对象都是唯一的。在创建每个对象时为其分配一个新的唯一值。

另一种选择是将所有该类型的对象保存在某种列表中。然后他们的列表位置用于将它们置于总排序中。（坦率地说，“键值”方法更好，但某些应用程序可能出于应用程序逻辑目的将对象保存在列表中，因此您可以在这种情况下利用现有列表。）但是，请注意不要结束当您使用这种方法时，需要花费 O(n) 时间（而不是像其他方法 * 那样 O(1)）来确定总排序中哪个排在第一位。

(* 如果您使用字符串来确定总排序，那么它并不是真正的 O(1)，但它与字符串的长度成线性关系，并且与包含这些字符串的对象的数量保持一致......但是，取决于在您的应用程序中，字符串长度可能比对象的数量更合理。）

于 2013-07-02T00:01:12.683 回答
1

您要解决的问题称为哲学家进餐问题，这是一个众所周知的并发问题。

在您的情况下，天真的解决方案是更改获取以接收 2 个参数（来往和来自），并且仅在它可以同时获得两个锁时才返回，并且如果不能同时拥有两个锁则不获得任何锁（因为那是可能发生死锁的情况，当获得一个锁并等待另一个锁时）。阅读哲学家进餐问题，您就会明白为什么。

希望能帮助到你！

于 2013-07-01T23:39:56.640 回答