追加、削除、および含まれている楽観的な同期待ちはありますか？

Question

「マルチプロセッサプログラミングの技術」（Elsevier、2012 ISBN 978）、206ページ（セクション9.6楽観的同期）：https://books.google.com/...のページ205から1ページ下にスクロールすると、追加/削除/包含図9.12 OptimisticListクラス：add()メソッドは、新しいノードを追加する前に、ロックを無視してロックを取得し、検証します。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

状態に移行これにより方法が自由に待っていないが含まれ、と言っているように見えますどちらのメソッドも追加または削除されません。しかし、なぜそうなるのか分かりません。

Answer 1

レイジー同期は、オプティミスティック同期に基づいています。遅延同期では、リストを1回だけトラバースし、ロックを取得することはありません。ハンドオーバーハンドロッキング。 remove/add/containsの目的地に到達したら、現在のノードと先行ノードをロックする必要があります。 大きな違いは、ノードを削除すると、ノードを削除済みとしてマークしてから物理的に削除する必要があることです（ガベージコレクタ）。

なぜ、待機時間が含まれていませんか？ 楽観的な同期とは異なり、現在のノードをロックする必要はありません。現在のノードをロックして、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; 
}