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

Question

我试图用Java实现这里描述的非阻塞二叉查找树。该算法基于单世界CAS，但是:

状态和信息字段一起存储在 CAS 对象中。因此，内部节点使用四个字的内存。

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

通过创建表示“盒装”[引用，整数] 对的内部对象来维护标记引用。

该结构的内部实施：

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的算法可以认为是无锁的。维基百科提供了无锁算法的定义:

在计算机科学中，非阻塞算法确保竞争共享资源的线程不会因互斥而无限期推迟执行。如果不管调度如何都有保证的系统范围的进度，则非阻塞算法是无锁的；

...

因此，在现代用法中，如果一个或多个线程的挂起不会停止其余线程的潜在进程，则算法是非阻塞的。

让我们看看在这种情况下基于CAS的算法[说算法我的意思是使用CAS指令设置变量，同时循环]：

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

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

现在，让我们考虑在 Java 中使用 AtomicXXX 类和对其对象执行 CAS 操作的基于 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));
    }

}

在< code>main()中实现的算法是无锁的，但是由于类装入器的监视器从来没有得到通知，所以不会有系统范围的进展。那么，我刚才到底写了什么？仅仅因为基于cas的算法在Java中是无锁的，这种说法是错误的。

CAS指令根据其定义是原子的。在大多数现代CPU中，这种指令是受支持的，也就是说，做我们期望它做的事情，并且是自动完成的。比方说，CPU厂商保证CPU支持原子CAS。

维基百科引用：

自1970年以来，比较和交换(以及比较和交换双精度)一直是IBM 370(以及所有后继者)体系结构不可或缺的一部分。

截至2013年，大多数多处理器架构在硬件上支持CAS。

JDK的一些证明：

AtomicInteger.compareAndSet（）Javadoc声明：

如果当前值==预期值，则原子地将值设置为给定的更新值。

在 AtomicXXX 类上也可以找到相同的内容，您可以轻松找到它，因此不值得在此处复制粘贴。

现在，让我们考虑AtomicStampedReference.compareAndSet（）。它的Javadoc说：

如果当前引用==预期引用并且当前标记等于预期标记，则原子地将引用和标记的值设置为给定的更新值。

我认为从javadoc中我们不能断定整个操作是原子性，它只是原子性地设置值，所以要么同时设置stamp和reference，要么都不设置，因为CAS会失败。