test_and_set線程的這種用法是否安全？

我一直在想如何實現一個無鎖的單向鏈表。說實話，我沒有看到許多防彈的方法來做到這一點。即使更強大的方式使用CAS結束了一定程度的ABA problem。因此，我不得不去思考。部分無鎖系統不會比總是使用鎖更好嗎？可能有些操作可以是原子的並且無鎖定的？如果我能做到這一點，它應該仍然是線程安全的。test_and_set線程的這種用法是否安全？

因此，到問題。我正在考慮一個簡單的單鏈表。 2個主要業務。 push和pop。 push總是插在前面。類似這樣的：

void push(int n) { 
    T *p = new T; 
    p->n = n; 
    p->next = root; 
    root = p; 
}

而彈出總是需要第一個元素。像這樣的：

T *pop() { 
    T *p = root; 
    root = root->next; 
    return p; 
}

顯然推是不夠平凡，一個簡單的無鎖方法可能不會發生。但流行看起來可能是可行的。使用gcc-內在我已經想到了這一點：

T *pop() { 
    return __sync_lock_test_and_set(&root, root->next); 
}

功能等同的？對。無鎖？對。線程安全？ 我不知道。我的直覺反應是否定的，這是爲什麼。

我擔心的是test_and_set的其中一個參數必須對內存進行解引用。如果根目錄在root->next和__sync_lock_test_and_set之間改變，該怎麼辦？

我想，這個代碼是相同的：

T *pop() { 
    T *temp = root->next; 
    // are we broken if a push/pop happens here? 
    return __sync_lock_test_and_set(&root, temp); 
}

所以，就像我說的，我覺得此代碼是不正確的。但是有誰能夠肯定地說我正在得出正確的結論（我討厭寫出一些很好的東西）。如果它真的被破壞，我懷疑。有沒有簡單的解決方案？

來源

2010-05-24 Evan Teran

你是對的。在C++中，函數的參數是以任意順序求值的，但是當然你的編譯器無法知道你的序列中的原子操作是root->next。

考慮兩個線程調用pop()：一個線程計算root->next，那麼其他評估root->next，和兩個呼叫test_and_set()。現在你只彈出一個節點。

來源

2010-05-24 21:11:55 rlbond

在這兩個版本的pop：

T *pop() { 
    T *p = root; 
    root = root->next; 
    return p; 
}

和

T *pop() { 
    return __sync_lock_test_and_set(&root, root->next); 
}

你有一個錯誤，已經，這是你沒有驗證您的列表/堆棧不爲空之前從假定的根節點讀取。

這會增加您提到的有關在test_and_set甚至發生之前必須取消引用root以獲得下一個問題的問題。它本質上變成了test_and_then_test_and_set操作，其中and_then表示需要多個步驟。

你彈出的第一個版本必須是：

T *pop() { 
    T *p = root; 
    if (root) { 
     root = root->next; 
    } 
    return p; 
}

和我敢肯定，你可以看到這使在混合甚至更多的步驟。

來源

2010-05-24 21:12:36 nategoose

當然，空列表上的彈出顯然是未定義的行爲。但這對於真正的問題有點問題。 – 2010-05-24 21:22:26

兩件事：（1）test & set只有共識數2;對於這樣弱的同步原語，僅僅使用讀/寫存儲器屏障而不會招致專用指令的開銷就足夠了; （2）ABA問題是一個真正的問題，只有極少的解決方案;但是，使用CAS（32位系統上的cmpxchg8b和x86/64上的64位系統上的cmpxchg16b），寄存器的上部有足夠的空間來存儲如此大的時間戳，以至於在實踐中ABA永遠不會出現（甚至在相當人爲的設置中，它將需要一個線程停頓幾天或幾周，然後在恰當的時刻喚醒）。

我認爲，儘管如此，您正試圖實現一個無鎖隊列（而不是列表）。隊列比列表更容易實現。 Edya Lazan-Mozes和Nir Shavit撰寫的論文「無鎖FIFO隊列的樂觀方法」以及Maged M. Michael和Michael L. Scott的「簡單，快速和實用的非阻塞和阻塞併發隊列算法」都是非常豐富且容易實現無鎖隊列的方法。

但是，如果您堅持使用無鎖鏈接列表，請考慮Michail Fomitchev和Eric Ruppert在「無鎖鏈接列表和跳過列表」中的實現。你也可以看看Damian Dechev的無鎖動態數組（有一個鏈接關閉維基百科）。

來源

2010-05-24 23:41:24 thechao

真的我想實現的是一個自由列表（基於鏈表的堆棧）。因爲我在同一端推/拉:-)。感謝您的回答。 – 2010-05-25 00:29:35

然後，您應該閱讀Danny Hendler，Nir Shavit和Lena Yerushalmi的「可伸縮的無鎖棧協議算法」。此外，非常平易近人，易於實施。雖然，我發現一個無鎖隊列（對於一個空閒列表）比堆棧會有（稍微）更好的運行時特性;這取決於你的平臺。 – thechao 2010-05-25 16:34:52

你可以給我一個關於如何構建這樣的標記參考的實例嗎？我無法弄清楚如何從指針中竊取數據。 – Raffo 2011-05-22 10:47:07

test_and_set線程的這種用法是否安全？

回答

相關問題