Why do we need to compareAndSet when set is already atomic in Java?

Question

Since Atomic means thread safe. When do we ever use compareAndSet when .set() itself is Atomic and thread safe in java?

say for example I want to set a variable atomically such that every other thread can see it (but I want the variable to be set in a thread safe manner) I could simple declare it as volatile AtomicBoolean or volatile AtomicInteger and that should be good right? what are some of cases where I need to use compareAndSet?

Answer 1

There are two important concepts in multithreading environment.

1. atomicity
2. visibility

Volatile solves the visibility problem but it does not deal with atomicity e.g. i++. Here i++ is not a single machine instruction rather it is three machine instructions.

1. copy the value to register
2. increment it
3. place it back

AtomicInteger, AtomicReference are based on the Compare and swap instruction. CAS has three operands a memory location V on which to operate, the expected old value A, and the new value B. CAS atomically updates V to the new value B, but only if the value in V matches the expected old value A; otherwise it does nothing. In either case, it returns the value currently in V. This is used by JVM in AtomicInteger, AtomicReference and they call the function as compareAndSet() if this functionality is not supported by underlying processor then JVM implements it by spin lock.

Set is atomic (it is not always correct) but compare and then set is not atomic. So when you have a requirement for this e.g. when the value is X then only change to Y so to do this atomically you need this kind of primitives you can use compareAndSet of AtomicInteger, AtomicReference e.g. atomicLong.compareAndSet(long expect, long update)

You can actually use this primitives to develop powerful datastrucutures like Concurrent stack.

import java.util.concurrent.atomic.AtomicReference;

public class MyConcurrentStack<T> {

    private AtomicReference<Node> head = new AtomicReference<Node>();

    public MyConcurrentStack() {
    }

    public void push(T t) {
        if (t == null) {
            return;
        }
        Node<T> n = new Node<T>(t);
        Node<T> current;

        do {
            current = head.get();
            n.setNext(current);
        } while (!head.compareAndSet(current, n));
    }

    public T pop() {
        Node<T> currentHead = null;
        Node<T> futureHead = null;
        do {
            currentHead = head.get();
            if (currentHead == null) {
                return null;
            }
            futureHead = currentHead.next;
        } while (!head.compareAndSet(currentHead, futureHead));

        return currentHead.data;
    }

    /**
     *
     * @return null if no element present else return a element. it does not
     * remove the element from the stack.
     */
    public T peek() {
        Node<T> n = head.get();
        if (n == null) {
            return null;
        } else {
            return n.data;
        }
    }

    public boolean isEmpty() {
        if (head.get() == null) {
            return true;
        }
        return false;
    }

    private static class Node<T> {

        private final T data;
        private Node<T> next;

        private Node(T data) {
            this.data = data;
        }

        private void setNext(Node next) {
            this.next = next;
        }
    }
}

Answer 2

A simple write operation is inherently atomic (in most cases). There's nothing special about set(). If you look at the source code for AtomicInteger.set(), you'll see this:

public final void set(int newValue) {
    value = newValue;
}

The magic of atomic classes is that they can read and modify atomically. In a multi-threaded environment, if you try to implement compare-and-set logic using a simple if, you might read a value, run some calculation and try to update the variable. But between your read and write operations, the value could have been updated by another thread, invalidating your calculation. Atomic classes make sure that nothing gets between your reads and writes. Hence the compareAndSet() methods, along with getAndSet(), getAndIncrement() etc.

Answer 3

You use compareAndSet when you need to update some data already existent in AtomicReference and then put it back to this reference.

For example: you need to increment a value from several threads (or update it in any other way).

Integer n = new Integer(10);
AtomicReference<Integer> ref = new AtomicReference<>(n);

// later...
int i = ref.get().intValue(); // i == 10

// some other thread increments the value in ref and now it is 11

ref.set(new Integer(i + 1));

// Oops! Now ref contains 11, but should be 12.

But with compareAndSet we could increase it atomically.

Integer n = new Integer(10);
AtomicReference<Integer> ref = new AtomicReference<>(n);

// later...

boolean success = false;
do {
    Integer old = ref.get(); // old == 10 on first pass, 11 on second pass
    // On first pass some other thread incrments the value in ref and now it is 11
    Integer updated = new Integer(old + 1);
    success = ref.compareAndSet(old, updated);
    // On first pass success will be false and value in ref will not update
} while (!success);

// Now ref contains 12 if other thread increments it to 11 between get and set.

Answer 4

compareAndSet is an essential primitive for non-blocking algorithms.

For example, it's basically impossible to implement wait-free algorithms with atomic read/write only — there must be compareAndSet or something similar.

compareAndSet is much more powerful that atomic read/write.
The power is expressed in consensus number:

• compareAndSet has consensus number infinity
• atomic read/write has consensus number 1

Consensus number is the maximum number of threads for which the concurrent object can solve a consensus problem (threads propose their candidate values and agree on a single consensus value) in a wait-free (i.e. without blocking, every thread is guaranteed to complete in no more that some fixed max number of steps) implementation.
It was proven that objects with consensus number of n can implement any object with a consensus number of n or lower, but cannot implement any objects with higher consensus number.

More explanations can be found in "The Art of Multiprocessor Programming" by M. Herlihy and N. Shavit.