樂觀的同步是否等待添加，刪除和包含？

如果您從書籍「多處理器編程的藝術」（Elsevier，2012 ISBN 978）的第205頁向下滾動一頁到第206頁（第9.6節「樂觀同步」）：https://books.google.com/...，您將看到add/remove/contains樂觀同步的方法（圖9.11 OptimisticList類：add()方法遍歷列表，忽略鎖，獲取鎖並在添加新節點之前驗證）圖片9.12 OptimisticList類：remove()方法遍歷忽略鎖，獲取鎖並驗證刪除節點page copy）。樂觀的同步是否等待添加，刪除和包含？

在上慵懶同步下面的部分，它不斷的狀態（參照樂觀同步）

The next step is to refine this algorithm so that contains() calls are wait-free, and add() and remove() methods, while still blocking, traverse the list only once

這似乎是說，contains方法不等待自由，所以添加或刪除方法也不會。但我似乎無法明白爲什麼會這樣。

來源

2016-07-22 Rodger Harris

執行所有3個方法調用.lock（），它可能會等待。這就是爲什麼他們不等待。 – Tsyvarev

懶惰同步基於樂觀同步。在惰性同步中，您只能遍歷列表一次，而不是獲取任何鎖，手搖鎖定。當你到達你的目的地去除/添加/包含你需要鎖定當前和前任節點。最大的區別是，當你刪除一個節點時，你首先必須將它標記爲已刪除，然後物理刪除它（垃圾回收器）。

爲什麼包含等待？與樂觀同步不同，我們不需要鎖定當前節點。回想一下，我們鎖定當前節點，以便在我們返回true時另一個線程無法刪除它。由於當前節點已經被標記，我們可以簡單地檢查當前節點是否被標記並且具有期望的密鑰。不需要任何鎖。這使它免於等待。示例代碼可能如下所示：

public boolean contains(T item) { 
int key = item.hashCode(); 
Node curr = this.head; 
while (curr.key < key) { 
curr = curr.next; 
} 
return curr.key == key && !curr.marked; 
}

來源

2017-05-04 09:56:50 jbuchel

樂觀的同步是否等待添加，刪除和包含？

回答

相關問題