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

Question

我正在阅读ConcurrentHashMapJDK8中的源代码，请注意，该代码TreeBin使用“读写”锁来防止并发读写。

如果没有并发的写线程试图修改树结构，则读线程将通过TreeNodes。当“查找”操作完成时，读取线程可能会：

（1）lockState如果存在，则“ CAS” 和“取消”服务线程。

以下是源代码中的“ 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) 之后，confusedLock() 中的执行继续如下：

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

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

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

总结一下：在(2)(1)(3)之后，操作(4)将永远不会被执行。因此不会出现死锁，我们都可以毫无疑虑地继续使用 ConcurrentHashMap ;-)