鎖定空閒隊列入隊如果不爲空

我已經在C中使用基於http://www.boyet.com/articles/LockfreeQueue.html的比較和交換實現了一個鎖定空閒隊列。鎖定空閒隊列入隊如果不爲空

它的工作很好，但我試圖將這個隊列整合到我已經實現的鎖定自由跳過列表中。我使用跳過列表作爲優先級隊列，並希望在每個節點內使用鎖定空閒隊列在存在優先級衝突時存儲多個值。然而，由於在跳過列表中管理節點的方式，當我檢測到優先級衝突時，只有當隊列不爲空時，我才需要能夠將該項添加到隊列中。

由於隊列的鎖定自由性im不知道如何實際執行此操作。

所以基本上我會怎麼寫一個原子enqueue_if_not_empty操作？

來源

2011-05-03 luke

此代碼有一個微妙的錯誤。正如文檔所述（http://www.boyet.com/articles/ABAProblem.html），它在C＃中工作，因爲垃圾收集。它將**不工作**在C中。 – 2011-05-03 03:13:39

我正在使用引用計數系統來解決隊列中節點上的ABA問題。所以保證節點不會早早釋放。 – luke 2011-05-03 03:34:38

我從來沒有遇到任何基於ref count的解決方案，它允許免費（）的隊列元素。我可以想象一個基於ref count的解決方案，它允許元素返回freelist，但就是這樣。你是否說過你已經設計了基於ref count的安全內存回收算法？ – 2011-05-04 11:01:35

編輯：正如它被注意到，我寫了功能與完全相反的語義 - 只入隊到一個空隊列。我固定了這個名字以反映這一點，並決定放棄它，以防萬一有人感興趣。所以，這是不正確的答案的問題，但不downvote請，除非你找到另一個原因:)

下面是一個企圖在引用的文件添加EnqueueIfEmpty()到隊列實現。我沒有驗證它是否有效，甚至沒有編譯。基本思想是在頭（而不是尾部）後面插入一個新節點，前提是頭的下一個當前爲空（這是空隊列的必要條件）。我留下額外的頭等於尾巴的檢查，這可能會被刪除。

public bool EnqueueIfEmpty(T item) { 
    // Return immediately if the queue is not empty. 
    // Possibly the first condition is redundant. 
    if (head!=tail || head.Next!=null) 
     return false; 

    SingleLinkNode<T> oldHead = null; 

    // create and initialize the new node 
    SingleLinkNode<T> node = new SingleLinkNode<T>(); 
    node.Item = item; 

    // loop until we have managed to update the tail's Next link 
    // to point to our new node 
    bool Succeeded = false; 
    while (head==tail && !Succeeded) { 

    // save the current value of the head 
    oldHead = head;   

    // providing that the tail still equals to head... 
    if (tail == oldHead) { 

     // ...and its Next field is null... 
     if (oldhead.Next == null) { 

     // ...try inserting new node right after the head. 
     // Do not insert at the tail, because that might succeed 
     // with a non-empty queue as well. 
     Succeeded = SyncMethods.CAS<SingleLinkNode<T>>(ref head.Next, null, node); 
     } 

     // if the head's Next field was non-null, another thread is 
     // in the middle of enqueuing a new node, so the queue becomes non-empty 
     else { 
     return false; 
     } 
    } 
    } 

    if (Succeeded) { 
    // try and update the tail field to point to our node; don't 
    // worry if we can't, another thread will update it for us on 
    // the next call to Enqueue() 
    SyncMethods.CAS<SingleLinkNode<T>>(ref tail, oldHead, node); 
    } 
    return Succeeded; 
}

來源

2011-05-03 20:50:30

如果head.next爲null並且tail == head，那麼隊列爲空......所以我們希望排隊失敗。我認爲你寫enqueue_if_empty不enqueue_if_not_empty ...除非我感到困惑。 – luke 2011-05-04 01:44:57

很棒！我的錯誤 - 的確，我寫了與所期望的相反的東西:)我將把它留在這個答案中，也許再寫一個。 – 2011-05-04 07:42:43

如果head == tail和oldHead = head，那麼oldHead.next會不會總是NULL？爲什麼要檢查它？ – 2011-05-04 11:05:37

好，入隊，如果不能提空似乎是相對簡單的，但有一個限制：其他線程可以同時從隊列中刪除所有以前的項目，使插入在尾完成後，新項目可能恰好是隊列中的第一項。由於原子比較和交換操作是通過不同的字段完成的（排列變化tail.Next，同時使預排列head出列），更強大的保證不僅需要此功能，而且至少在Dequeue()中還需要額外的複雜性。

到正常Enqueue()方法可以進行如下更改足夠：
1）在函數開始時，檢查head.Next被空，如果是這樣，立即返回作爲隊列是空的。
2）將head.Next!=null添加到循環條件中，以防排隊嘗試應該停止，如果在插入成功之前最初的非空隊列變空。這並不妨礙我上面描述的情況（因爲在檢查虛擬和節點插入之間存在時間窗口），但減少了發生的可能性。
3）在函數結束時，如果新節點已成功排隊，只嘗試前進尾部（就像我在Enqueue-If-Empty答案中那樣）。

來源

2011-05-04 08:48:42

鎖定空閒隊列入隊如果不爲空

回答

相關問題