Linux 3.0：futex-lock死鎖錯誤？

// SubFetch(x,y) = atomically x-=y and return x (__sync_sub_and_fetch) 
// AddFetch(x,y) = atomically x+=y and return x (__sync_add_and_fetch) 
// CompareWait(x, y) = futex(&x, FUTEX_WAIT, y) wait on x if x == y 
// Wake(x, y) = futex(&x, FUTEX_WAKE, y) wake up y waiters 

struct Lock 
{ 
Lock() : x(1) {} 

void lock() 
{ 
    while (true) 
    { 
     if (SubFetch(x, 1) == 0) 
      return; 

     x = -1; 

     CompareWait(x, -1); 
    } 
} 

void unlock() 
{ 
    if (AddFetch(x, 1) == 1) 
     return; 

    x = 1; 

    Wake(x, 1); 
} 

private: 
    int x; 
};

Linux 3.0提供了一個名爲futex的系統調用，在此係統調用上，很多併發實用程序都基於最近的pthread_mutex實現。無論何時編寫代碼，您都應該考慮是否使用現有的實現或自己編寫代碼是您項目的更好選擇。Linux 3.0：futex-lock死鎖錯誤？

以上是基於futex的一個鎖（互斥，1個許可證計數信號）的實現和在man futex(7)

它似乎包含死鎖錯誤，由此後多個線程試圖鎖定和解鎖它的語義描述幾千次，線程可以進入x == -1狀態，並且所有線程都卡在CompareWait中，但是沒有人持有該鎖。

任何人都可以看到錯誤在哪裏？

更新：我有點驚訝futex（7）/語義是如此的破碎。我完全重寫了Lock，如下所示...現在是否正確？

// CompareAssign(x,y,z) atomically: if (x == y) {x = z; ret true; } else ret false; 

struct Lock 
{ 
Lock() : x(0) {} 

void lock() 
{ 
    while (!CompareAssign(x, 0, 1)) 
     if (x == 2 || CompareAssign(x, 1, 2)) 
      CompareWait(x, 2); 
} 

void unlock() 
{ 
    if (SubFetch(x, 1) == 0) 
     return; 

    x = 0; 

    Wake(x, 1); 
} 

private: 
int x; 
};

這裏的想法是，x具有以下三種狀態：

0: unlocked 
1: locked & no waiters 
2: locked & waiters

來源

2012-03-08 Andrew Tomazos

我聽說futexes看起來很簡單，很難正確使用它們。你有這樣的理由嗎？ – 2012-03-08 16:43:13

見第1款 – 2012-03-08 16:44:04

呵呵？ pthread_mutex有什麼問題？ – 2012-03-08 16:46:11

的問題是，您明確-1分配給x如果SubFetch未能獲取鎖。這與解鎖的比賽。

線程1獲取鎖定。 x==0。
線程2嘗試獲取鎖。 SubFetch將x設置爲-1，然後掛起線程2。
線程1釋放鎖。 AddFetch將x設置爲0，所以代碼然後明確地將x設置爲1並且調用Wake。
線程2喚醒並將x設置爲-1，然後調用CompareWait。

線程2現在卡住等待，x設置爲-1，但由於線程1已經釋放了鎖，因此沒有人會將其喚醒。

來源

2012-03-08 16:49:46

我明顯誤讀了futex（7）它說「應該將計數器設置爲-1」。什麼是修復？ – 2012-03-08 17:13:29

在http://www.justsoftwaresolutions.co.uk/files/c_mutexes.zip有一個基於futex的互斥體的代碼。基本上，你不能盲目地設置'x'的值，你必須使用原子比較 - 並且交換操作，並檢查所有情況下的返回值。 – 2012-03-08 17:30:28

請參閱更新/重寫。現在這是否正確？ – 2012-03-08 18:22:34

這個怎麼樣的情況與三個線程，A，B和C.

這種情況下的初始狀態有：

線程A持有鎖
線程B不爭鎖在CompareWait()
x == -1從當C未能獲得鎖，只是還沒有
線程C-

 
     A     B    C 
    ============== ================ =============== 
    AddFetch() 
    (so x == 0) 
         SubFetch() 
         (so x == -1) 

    x = 1 

         x = -1 

    Wake()

此時B或C是否暢通，他們不會得到0當他們SubFetch()結果。

來源

2012-03-08 16:55:56

好吧，我完全誤解了futex（7）的語義部分，或者描述被完全破壞了。這裏的修復是什麼？ – 2012-03-08 17:16:29

請參閱更新/重寫。現在這是否正確？ – 2012-03-08 18:22:20

的正確實施基於futex的，互斥的烏利齊·德雷珀的論文「futexes的貓膩」被描述

http://people.redhat.com/drepper/futex.pdf

它不僅包括代碼也是爲什麼它是正確的一個非常詳細的解釋。從本文的代碼：

class mutex 
{ 
public: 
mutex() : val (0) { } 
void lock() { 
    int c; 
    if ((c = cmpxchg (val, 0, 1)) != 0) 
    do { 
     if (c == 2 || cmpxchg (val, 1, 2) != 0) 
     futex_wait (&val, 2); 
    } while ((c = cmpxchg (val, 0, 2)) != 0); 
} 
void unlock() { 
//NOTE: atomic_dec returns the value BEFORE the operation, unlike your SubFetch ! 
    if (atomic_dec (val) != 1) { 
    val = 0; 
    futex_wake (&val, 1); 
    } 
} 
private: 
    int val; 
};

的代碼在你的代碼的文件進行比較，我發現了一個差異

你有

如果（X == 2 || CompareAssign（X，1 ，2））

直接使用futex的值，而Drepper使用前一個CompareAssign（）的返回值。這種差異可能只會影響性能。

您的解鎖代碼也不同，但似乎在語義上相同。

無論如何，我強烈建議您按照Drepper的代碼來寫信。這篇論文經受了時間的考驗，並獲得了很多同行評議。你從滾動你自己一無所獲。

來源

2012-03-13 21:13:36 MSB

Linux 3.0：futex-lock死鎖錯誤？

回答

相關問題