C - 这个简单的 transaction() 函数如何才能完全避免死锁？

Question

所以我有这个用 C 语言编写的基本 transaction() 函数:

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

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

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

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

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

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

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

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

(* 如果您使用字符串来确定总排序，那么它并不是真正的 O(1)，但它与字符串的长度和常量 w.r.t. 保持这些字符串的对象数量成线性关系......但是，根据您的应用程序，字符串长度可能比对象的数量更合理。)