C - 這個簡單的transaction（）函數怎麼可以完全沒有死鎖？

所以我有這個基本的交易（）函數寫在C：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);

我被告知這會導致死鎖。我如何編輯這個函數使它完全沒有死鎖？

來源

2013-07-01 user1729250

沒有明顯的互斥體概念，允許以您擁有它的方式進行分配。互斥體擁有某種「獨特的所有權」。此外，你真的應該更努力不要混淆互斥和鎖定。 –

您需要創建對象的總體排序（在這種情況下爲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，然後儲蓄帳戶，transaction (checking_account, savings_account, 300);也會先鎖住checking_account，然後鎖定savings_account。

如果您沒有帳號（例如您使用Foo類而不是類Account），那麼您需要找到其他方法來確定總排序。如果每個對象都有一個名稱（字符串），則可以進行字母比較以確定哪個字符串是「較少」的。或者，您可以使用任何其他類型的「>和<」。

但是，值對於每個對象都是唯一的非常重要！如果兩個對象在您測試的任何字段中具有相同的值，則它們在排序中的相同位置。如果發生這種情況，那麼這是一種「部分排序」而不是「總排序」，並且對此鎖定應用程序進行總排序非常重要。

如有必要，您可以組成一個「關鍵值」，該關鍵值是一個任意數字，並不代表任何意義，但對於該類型的每個對象都是唯一的。每個對象在創建時都會分配一個新的唯一值。

另一種選擇是將該類型的所有對象保留在某種列表中。然後，他們的名單職位將把他們放在一個完整的排序中。（坦率地說，「關鍵值」方法更好，但爲了應用程序邏輯的目的，某些應用程序可能已將對象保存在列表中，因此您可以利用現有列表。）但是，請注意，當您使用此方法時，最終不會像O（n）時間（而是像其他方法*那樣使用O（1））來確定哪一個在總排序中排在第一位。（*如果你使用一個字符串來確定總排序，那麼它並不是真的O（1），但它與字符串的長度成線性關係，並且保持這些字符串的對象的數量不變。但是，根據您的應用程序，字符串長度可能比數字對象合理得多。）

來源

2013-07-02 00:01:12

這很有道理。謝謝！ – user1729250

沒問題！順便說一句，我不是100％確定這是解決問題的唯一方法......但我知道它確實解決了這個問題，我想不出另一種方式來解決問題。 –

你正試圖解決的問題叫做餐飲哲學家問題，它是一個衆所周知的併發問題。

在你的情況下，天真的解決方案將改變獲取接收2個參數（來回），只有當它可以同時獲得兩個鎖，並且如果它不能同時獲得任何鎖，（因爲這種情況發生時可能發生死鎖，當獲得1鎖並等待另一個時）。閱讀有關哲學家就餐問題，你會明白爲什麼。

希望它能幫助！

來源

2013-07-01 23:39:56

我查了一下，這是一個非常感興趣的閱讀！感謝您的洞察！ – user1729250

C - 這個簡單的transaction（）函數怎麼可以完全沒有死鎖？

回答

相關問題