Lock Free Programming

Disadvantages

Locks have some disadvantages:

• Performance may suffer because of context-switch overhead
• When waiting for a lock, the thread cannot do anything else
• Permanent locks
• Amdahl's law

Example: Synchronized Counter

First Draft with locks:

public final class Counter {
    private long value = 0;

    public synchronized long getValue(){
        return value;
    }

    public synchronized long increment(){
        return ++value;
    }
}

How can we now avoid using locks? First, we can remove one lock by adding volatile:

public final class Counter {
    private volatile long value = 0;

    public long getValue(){
        return value;
    }

    public synchronized long increment(){
        return ++value;
    }
}

This is nice but volatile does not support read-modify-write sequences. This solution also allows more concurrency since more can read the value at once. But how can we get rid of the second synchronized ? We use atomic compare and swap instructions.

Compare and Set (CAS)

The Compare and Set (CAS) instruction is an atomic operation used to achieve lock-free synchronization. It works by comparing the current value of a variable to an expected value. If they match, it updates the variable to a new value in a single, indivisible step. If they don't match, the operation fails, and the process can be retried. CAS ensures that no other thread modifies the variable between the comparison and the update, making it ideal for implementing thread-safe operations without locks.

A CAS Counter:

public final class Counter {
    private volatile long value = 0;

    public long getValue(){
        return value;
    }

    public long increment(){
       while(true){
            long current = getValue();
            long next = current + 1;
            if(compareAndSwap(current, next)) return next;
       }
    }
}

Use java unsafe package. But this is not the recommended way.

Java Atomics

All atomic scalars and field updaters support the CAS. Atomic Variables are good to use for one variable but can become quite complicated if theres more than one of the same kind to manage. If possible, create a new type and use AtomicReference<>.

Example of rewrite:

class SyncAccumulator {
    private int total = 0;
    private int lastValue = 0;

    public synchronized void update(int newValue) {
        total += newValue;
        lastValue = newValue;
    }

    public synchronized Result get() {
        return new Result(total, lastValue);
    }
}

class Result {
    public final int total;
    public final int lastValue;

    public Result(int total, int lastValue) {
        this.total = total; this.lastValue = lastValue;
    }
}

Now the exact same functionality but without locks (class Result stays):

class WithoutLocks {
    private final AtomicReference<Result> value = new AtomicReference<Result>(new Result(0,0));

    public void update(int newValue) {
        while(true) {
            Result current = value.get();
            Result newResult = new Result(current.total + newValue, newValue);
            if(value.compareAndSet(current, newResult)) { return; }
        }
    }

    public Result get() {
        return value.get();
    }
}

When using multiple atomic variables to represent related state, such as AtomicInteger for lower and upper in a range, maintaining consistency between them can be problematic. Each atomic operation (e.g., compareAndSet) only guarantees atomicity for a single variable, not across multiple variables. This can lead to race conditions where one thread updates one variable while another thread updates the other, resulting in an inconsistent state.

For example, if lower and upper are updated independently, a situation where lower > upper can occur, violating the intended invariant. This happens because there is no mechanism to ensure that the updates to both variables happen atomically as a single operation.

To solve this, you can use an AtomicReference to store a single immutable object that encapsulates all related state. By doing so, updates to the state can be performed atomically as a single operation. This ensures consistency and avoids race conditions, making the code thread-safe and easier to reason about.

Non-Blocking Algorithms