Lock‑Free (Non‑Blocking) Algorithms and Their Implementation in Java

Lock‑free (non‑blocking) algorithms use low‑level machine instructions such as the compare‑and‑swap (CAS) instruction instead of locks to guarantee data consistency during concurrent accesses.

These algorithms provide significant advantages in scalability and liveness because multiple threads can compete for the same data without blocking, allowing finer‑grained coordination and reducing scheduling overhead, while eliminating deadlocks and other liveness issues.

Lock‑free algorithms avoid kernel‑mode to user‑mode thread switches, eliminating thread‑context‑switch costs.

In lock‑free designs, reads are non‑exclusive; only write operations use an optimistic lock based on CAS, while reads can proceed without mutual exclusion. The CAS mechanism ensures atomicity, and the volatile keyword provides visibility and ordering guarantees.

Java provides built‑in atomic variables such as AtomicLong . For example, a volatile field is declared as:

private volatile long value;

The atomic increment method can be implemented as:

/**
 * Atomically increments the current value,
 * with memory effects as specified by VarHandle#getAndAdd.
 *
 *
Equivalent to {@code getAndAdd(1)}.
 *
 * @return the previous value
 */
public final long getAndIncrement() {
    return U.getAndAddLong(this, VALUE, 1L);
}

The underlying implementation uses jdk.internal.misc.Unsafe#getAndAddLong :

/** 
 * Atomically adds the given value to the current value of a field
 * or array element within the given object {@code o}
 * at the given {@code offset}.
 *
 * @param o object/array to update the field/element in
 * @param offset field/element offset
 * @param delta the value to add
 * @return the previous value
 * @since 1.8
 */
@IntrinsicCandidate
public final long getAndAddLong(Object o, long offset, long delta) {
    long v;
    do {
        v = getLongVolatile(o, offset);
    } while (!weakCompareAndSetLong(o, offset, v, v + delta));
    return v;
}

A classic issue with CAS‑based lock‑free operations is the ABA problem: a thread may observe a value unchanged (A→B→A) and incorrectly assume no intervening modifications occurred.

Optimistic locking implementations typically use a version stamp to detect such changes. For example, MySQL optimistic locking adds a numeric version column to a table, incremented on each update and checked before committing.

In Java, the ABA problem can be solved using AtomicStampedReference , which pairs a reference with a stamp (version) to detect intermediate modifications.

Summary: Lock‑free (non‑blocking) algorithms in Java can be built on CAS and volatile , and the ABA problem can be mitigated with AtomicStampedReference .