java - 使用 Java AtomicStampedReference 的算法可以被认为是非阻塞的吗？

Question

我正在尝试实现非阻塞二叉搜索树，如here所述使用Java。该算法基于单世界 CAS，但是:

The state and info fields are stored together in a CAS object. Thus, an internal node uses four words of memory.

我决定使用 AtomicStampedReference 来存储这些数据。问题在于它

maintains stamped references by creating internal objects representing "boxed" [reference, integer] pairs.

这个结构的内部实现:

public boolean compareAndSet(V   expectedReference,
                             V   newReference,
                             int expectedStamp,
                             int newStamp) {
    Pair<V> current = pair;
    return
        expectedReference == current.reference &&
        expectedStamp == current.stamp &&
        ((newReference == current.reference &&
          newStamp == current.stamp) ||
         casPair(current, Pair.of(newReference, newStamp)));
}

对定义为:

private static class Pair<T> {
    final T reference;
    final int stamp;
    private Pair(T reference, int stamp) {
        this.reference = reference;
        this.stamp = stamp;
    }
    static <T> Pair<T> of(T reference, int stamp) {
        return new Pair<T>(reference, stamp);
    }
}

这个实现仍然是非阻塞的吗？

还有一个额外的问题:是什么让这个 compareAndSet 操作成为原子操作？

Answer 1

我们怎么称呼无锁算法？

[免责声明]在我明确地写这篇文章之前，我的陈述是关于一般算法的，而不是考虑 Java CAS 实现。

是的，在我看来基于CAS的算法可以认为是无锁的。 Wikipedia提供无锁算法的定义:

In computer science, a non-blocking algorithm ensures that threads competing for a shared resource do not have their execution indefinitely postponed by mutual exclusion. A non-blocking algorithm is lock-free if there is guaranteed system-wide progress regardless of scheduling;

...

In modern usage, therefore, an algorithm is non-blocking if the suspension of one or more threads will not stop the potential progress of the remaining threads.

让我们看一下该上下文中基于 CAS 的算法[说算法我的意思是使用带有 while 循环的 CAS 指令设置变量]:

问题一:基于CAS的算法是非阻塞的吗？在每个特定的时刻，都有一个线程会成功CAS变量。如果我们暂停其中之一，则剩下的一个将会成功。因此，该算法满足我引用的定义，答案是肯定的。

问题二:基于CAS的算法是无锁的吗？我想答案又是肯定的，因为是系统范围的，而不是每线程的进度(每个线程最终都会成功cas-ing变量)是有保证的。

现在，让我们考虑使用 AtomicXXX 类及其对象的 CAS 操作在 Java 中实现的基于 CAS 的算法。从技术上讲，不保证无锁由于 JVM 端可能的外部影响，此类算法的使用:

public class Entity {
    static {
        new Thread(){
            @Override
            public void run() {
                synchronized (getClass().getClassLoader()){
                    try {
                        getClass().getClassLoader().wait();
                    } catch (InterruptedException e) {
                        e.printStackTrace();
                    }
                }
            }
        }.start();
        try {
            Thread.sleep(1000);
        } catch (InterruptedException e) {
            e.printStackTrace();
        }
    }

    public static void main(String[] args) {
        AtomicReference v = new AtomicReference(new Object());
        Object var = null;
        Object somenew;
        do {
            var = v.get();
            somenew = new Object();
        } while(!v.compareAndSet(var, somenew));
    }

}

在 main() 中实现的算法是无锁的，但由于类加载器的监视器从未被通知过，因此不会有系统范围的进展。 那么，我刚才到底写了什么？基于 cas 的算法在 Java 中是无锁的只是因为它们是基于 cas 的这一事实的说法是错误的。

CAS指令原子性

CAS 指令根据其定义是原子的。 在大多数现代 CPU 中都支持该指令，即执行我们期望它执行的操作并以原子方式执行。比方说，CPU 供应商保证 CPU 支持原子 CAS。

Wikipedia引用:

Compare-and-Swap (and Compare-and-Swap-Double) has been an integral part of the IBM 370 (and all successor) architectures since 1970.

As of 2013, most multiprocessor architectures support CAS in hardware.

JDK的一些证明:

AtomicInteger.compareAndSet() Javadoc状态:

Atomically sets the value to the given updated value if the current value == the expected value.

同样可以在AtomicXXX类中找到，你很容易找到它，所以不值得在这里复制粘贴。

现在，让我们考虑一下 AtomicStampedReference.compareAndSet()。它的Javadoc说:

Atomically sets the value of both the reference and stamp to the given update values if the current reference is == to the expected reference and the current stamp is equal to the expected stamp.

我认为从那个 javadoc 我们不能断定整个操作是原子的，它只是以原子方式设置值，所以要么设置 stamp 和 reference，要么都不设置，因为 CAS 失败。