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

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的算法[说算法我的意思是使用带有while循环的CAS指令设置变量]:

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

问题二:基于CAS的算法是否无锁？我认为答案是肯定的,因为系统范围内,但不是每个线程的进度(每个线程最终将成功获取变量)得到保证.

现在,让我们考虑使用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));
    }

}

实现的算法main()是无锁的,但是由于类加载器的监视器没有得到通知,所以没有系统范围的进展.那么,我刚才写的到底是什么？基于cas的算法在Java中无锁是因为它们是基于cas的事实是错误的.

CAS指令原子性

CAS指令的定义是原子的.在大多数现代CPU中,支持该指令,即完成我们期望它执行的操作并以原子方式执行.假设CPU供应商保证CPU支持原子CAS.

维基百科报价:

自1970年以来,Compare-and-Swap(以及Compare-and-Swap-Double)已成为IBM 370(以及所有后续)架构不可或缺的一部分.

截至2013年,大多数多处理器架构都支持CAS硬件.

JDK的一些证明:

AtomicInteger.compareAndSet() Javadoc说:

如果当前值==期望值,则以原子方式将值设置为给定的更新值.

同样可以在AtomicXXX课堂上找到,你可以轻松找到它,所以不值得在这里进行复制.

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

如果当前引用= =预期引用且当前标记等于预期标记,则以原子方式将引用和标记的值设置为给定的更新值.

我认为从javadoc我们不能得出结论整个操作是原子的,它只是原子地设置值,所以设置了戳和引用,或者它们都没有作为CAS失败.