在这种情况下，是否有可能与ConcurrentHashMap陷入僵局?

Question

我正在阅读JDK8中ConcurrentHashMap的源代码，请注意TreeBin使用"读写"锁来防止并发读写。

如果没有并发写入线程尝试修改树结构，则读取线程将通过 TreeNode。当"查找"操作完成后，读取线程可能会：

(1)"CAS"lockState并"取消停放"服务员(编写器)线程(如果存在)。

以下是源代码中的"find()"方法。

final Node<K,V> find(int h, Object k) {
if (k != null) {
for (Node<K,V> e = first; e != null; ) {
int s; K ek;
if (((s = lockState) & (WAITER|WRITER)) != 0) {
if (e.hash == h &&
((ek = e.key) == k || (ek != null && k.equals(ek))))
return e;
e = e.next;
}
else if (U.compareAndSwapInt(this, LOCKSTATE, s,
s + READER)) {
TreeNode<K,V> r, p;
try {
p = ((r = root) == null ? null :
r.findTreeNode(h, k, null));
} finally {
Thread w;
// (1)if no more readers, try to unpark the waiter if it exists
if (U.getAndAddInt(this, LOCKSTATE, -READER) ==
(READER|WAITER) && (w = waiter) != null)
LockSupport.unpark(w);
}
return p;
}
}
}
return null;
}

另一方面，编写器线程可以：

• (2) 通过"CAS"操作将WAITER状态添加到lockState。

• (3) 将自身设置为waiter变量。

• (4)"公园"本身。

这是编写器的代码：

private final void contendedLock() {
boolean waiting = false;
for (int s;;) {
if (((s = lockState) & ~WAITER) == 0) {
if (U.compareAndSwapInt(this, LOCKSTATE, s, WRITER)) {
if (waiting)
waiter = null;
return;
}
}
else if ((s & WAITER) == 0) {
if (U.compareAndSwapInt(this, LOCKSTATE, s, s | WAITER)) {
waiting = true;
waiter = Thread.currentThread();
}
}
else if (waiting)
LockSupport.park(this);
}
}

这是我的困惑：

如果上述四个操作按此顺序 (2) (1) (3) (4) 运行，则操作 (1) 不会取消停放任何内容，因为此时"waiter"为空。

然后服务员将永远停车，没有人可以停车。

后续写入将在"寄存"线程持有的固有锁上全部阻塞。

这是僵局的机会吗？

我对此感到非常困惑。我想也许我在源代码中遗漏了一些东西。如果您熟悉它，则需要您的帮助。

Answer 1

这个问题已经有一年多了。但这是一个很好的谜题。答案如下：

在 (2) (1) (3) 之后，在 contendedLock() 中继续执行，如下所示：

if (((s = lockState) & ~WAITER) == 0)为真，因为 (1) 已执行

if (U.compareAndSwapInt(this, LOCKSTATE, s, WRITER))也是正确的，因为(3)是在(s = lockState)之前而不是之后执行的

由于waiting在执行 (3) 之前设置为 true，因此第三个 if 语句也为真。因此，waiter设置为 null，我们退出循环。(4) 从不执行。

总结一下： 在 (2) (1) (3) 之后，操作 (4) 将永远不会执行。所以没有死锁的机会，我们都可以毫无顾虑地继续使用ConcurrentHashMap;-)