Lock-free and wait-free algorithms

In contrast to algorithms that protect access to shared data with locks, lock-free and wait-free algorithms are specially designed to allow multiple threads to read and write shared data concurrently without corrupting it.

“Lock-free” refers to the fact that a thread cannot lock up: every step it takes brings progress to the system. This means that no synchronization primitives such as mutexes or semaphores can be involved, as a lock-holding thread can prevent global progress if it is switched out.

“Wait-free” refers to the fact that a thread can complete any operation in a finite number of steps, regardless of the actions of other threads. It is possible for an algorithm to be lock-free but not wait-free.

[snip /]

For example, consider a banking program where each thread represents a virtual teller. A lock-based approach to making a deposit could be to have one teller lock an account to make a deposit, so that two tellers don’t try to deposit into the same account simultaneously. To make the process lock-free, rather than designing a lock-free “deposit” algorithm you might have the teller submit a “deposit” request asynchronously to a centralized thread that handled all deposits.

Java theory and practice: Going atomic

An algorithm is said to be wait-free if every thread will continue to make progress in the face of arbitrary delay (or even failure) of other threads.

By contrast, a lock-free algorithm requires only that some thread always make progress. (Another way of defining wait-free is that each thread is guaranteed to correctly compute its operations in a bounded number of its own steps, regardless of the actions, timing, interleaving, or speed of the other threads. This bound may be a function of the number of threads in the system.

뮤텍스 (락)을 사용한 Random Number Generator의 예

public class PseudoRandomUsingSynch implements PseudoRandom {
    private int seed;

    public PseudoRandomUsingSynch(int s) { seed = s; }

    public synchronized int nextInt(int n) {
        int s = seed;
        seed = Util.calculateNext(seed);
        return s % n;
    }
}

AutomicInteger와 CompareAndSet을 사용한 lock-free 구현

public class PseudoRandomUsingAtomic implements PseudoRandom {
    private final AtomicInteger seed;

    public PseudoRandomUsingAtomic(int s) {
        seed = new AtomicInteger(s);
    }

    public int nextInt(int n) {
        for (;;) {
            int s = seed.get();
            int nexts = Util.calculateNext(s);
            if (seed.compareAndSet(s, nexts))
                return s % n;
        }
    }
}