乐观同步是否可以等待添加、删除和包含？

Question

如果您从“多处理器编程艺术”(Elsevier，2012年ISBN 9780123977953)的第205页向下滚动一页，到第206页(第9.6节乐观同步)：https://books.google.com/...，您将看到添加/删除/包含乐观同步的方法(图9.11 OptimisticList类：add()方法在添加新节点之前遍历列表忽略锁、查询锁和验证)。图9.12 OptimisticList类：remove()方法在删除节点之前遍历忽略锁、获取锁和验证。页副本)。

在下面关于延迟同步的部分中，它将继续到状态(同时引用乐观同步)。

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

这似乎是在说would方法并不是免费等待的，因此添加或删除方法也不会是免费的。但我似乎不明白为什么会这样。

Answer 1

延迟同步是基于乐观同步的。在延迟同步时，您只遍历列表一次，不获取任何锁，不像手动锁定。当您到达要删除/添加/包含的目的地时，您需要锁定当前和先前节点。最大的区别是，当您删除一个节点时，首先必须将其标记为已删除，然后物理上删除它(垃圾收集器)。

为什么包含无等待？与乐观同步不同，我们不需要锁定当前节点。回想一下，我们锁定当前节点，以便在返回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;
}