這需要鎖定空閒，因爲它必須在SMP系統的中斷處理程序中運行。我不能鎖。鎖定自由Deque，支持刪除任意節點
我有一個連續的數組持有一些值。這個數組中的一些條目是「免費的」，它們沒有被佔用。我想列出這些條目，以便我可以快速分配一個條目。但是，我偶爾需要分配一個任意的條目。
因此，我看到以下將是一個很好的做事方式： 連續數組不僅包含值，還包含左指針和右指針，從而形成一個雙端隊列。只有空白值纔有有效的左/右指針。我可以快速到達任意節點，因爲它只是對deque的索引訪問。
現在，關鍵是：是否有一個很好的鎖定免費deque算法，相對高效，可以支持刪除任意節點？
連續數組不僅包含值，還包含左指針和右指針，因此使得 成爲雙端隊列。
[剪斷]
現在，問題的癥結所在：是否有一個很好的無鎖雙端隊列算法是相對 高效，可支持取消任意節點的？
具有移除任意元素的能力是一個真正的雙鏈表;你放棄的唯一的東西是插入任意元素的能力，移除是很難的部分 - 如果你可以移除，你當然可以添加。
存在一個無鎖雙向鏈表，但它需要垃圾收集。
這個怎麼樣;有一個freelist。這代表可用節點。節點實際上是一個數組，因此您可以將它們編入索引。當你必須使用任意節點時，索引到數組中，然後在該元素中加入一個標誌，但將其留在freelist中（當然，因爲它不在freelist的頂部）。當你將來會彈出並且你發現你彈出了一個已經使用過的元素時，只要不斷彈出，直到你找到一個可用的元素。
在一個垃圾收集系統中，如果你不關心物品的內存何時被釋放，並且如果它是不可能的，那麼可以有一個單鏈表支持無鎖邏輯刪除項目在要刪除的項目之後立即添加項目。給每個項目一個刪除的標誌，並且有一個列表遍歷例程，它會在每個項目訪問下一個節點是否被刪除時檢查;如果有，使用compare和swap來擺動當前節點的「下一個」指針。請注意，有可能被刪除的節點的「下一個」指針可能被更改，但只能跳過其後的節點。有可能擺動下一個指針可能會導致剛剛從列表中斷開的節點重新鏈接（例如，如果B和C同時被移除，A-> B-> C-> D可能會變成A-> B- > D（擺動B 的指針），然後A-> C-> D（將A的指針擺動到B的「下一個」指針的鎖存值），但是如果節點C繼續被標記爲「已刪除」這應該不會造成問題，因爲下一次迭代列表時，A的指針將擺動到D.
兩個注意事項：-1-在非垃圾收集系統中，可能很難知道何時可以釋放節點;釋放一個節點然後將指針擺回它可能會導致未定義的行爲; -2-如果在刪除的節點之後立即添加節點，指針可能會擺動以斷開新節點。如果節點總是被添加到隊列的末尾，那麼可以通過用一個虛擬節點結束隊列來避免後一個問題，該虛擬節點在它之後有另一個節點之前不能被刪除。