Can algorithm using Java AtomicStampedReference can be considered non-blocking?

Question

I'm trying to implement non-blocking binary search tree as described here using Java. This algorithm is based on single-world CAS but:

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

I decided to use AtomicStampedReference to store this data. The problem is that it

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

Internal implementation of this structure:

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)));
}

Pair defined as:

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);
    }
}

Is this implementation still non-blocking?

And the extra question: what's making this compareAndSet operation atomic ?

Answer 1

What do we call a lock-free algorithm?

[Disclaimer] Until I wrote this explicitly, my statements is about algorithms in general, not considering Java CAS implementation.

Yes, in my opinion algorithm based on CAS can be considered lock-free. Wikipedia provides definition of lock-free algorithm:

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.

Let's take a look over CAS-based algorithm in that context [saying algorithm I mean setting variable using CAS instruction with while loop]:

Question one: Is CAS-based algorithm non-blocking? At each particular moment of time, there is one thread that will successfully CAS variable. If we suspend one of them, one of remaining will succeed instead. Thus, the algorithm satisfies the definition I quoted and the answer is yes.

Question two: Is CAS-based algorithm lock-free? I think the answer is yes again, because system-wide, but not per-thread progress (each thread will eventually succeed cas-ing variable) is guaranteed.

Now, let's consider CAS-based algorithms implemented in Java using AtomicXXX classes and CAS operations on its objects. Technically, there is no guarantee of lock-free-ness of such algorithms because of possible external influences from JVM side:

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));
    }

}

The algorithm implemented in main() is lock-free but due to the class loader's monitor not being notified ever, there will be no system-wide progress. So, what the hell I just wrote? The statement that cas-based algorithms is lock-free in Java just because of the fact they are cas-based is wrong.

CAS instruction atomicity

CAS instruction is atomic by its definition. In most modern CPU this instruction is supported, i.e. does what we expect it to do and does it atomically. Let's say, CPU vendor guarantees that CPU supports atomic CAS.

Wikipedia quote:

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.

Some proofs from JDK:

AtomicInteger.compareAndSet() Javadoc states:

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

Same can be found on AtomicXXX classes, you can easily find it, so doesn't worth copypasting here.

Now, let's consider AtomicStampedReference.compareAndSet(). Its Javadoc says:

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.

I think from that javadoc we cannot conclude that the whole operation is atomic, it just sets the value atomically, so either both stamp and reference are set, or none of them as CAS fails.