Home‎ > ‎Lockfree Algorithms‎ > ‎

Introduction

I bet you had heard terms like "lockfree" and "waitfree". So what it's all about? Let's start with some definitions.


Wait-freedom
Wait-freedom means that each thread moves forward regardless of external factors like contention from other threads, other thread blocking. Each operations is executed in a bounded number of steps. It's the strongest guarantee for synchronization algorithms. Wait-free algorithms usually use such primitives as atomic_exchange, atomic_fetch_add (InterlockedExchange, InterlockedIncrement, InterlockedExchangeAdd, __sync_fetch_and_add), and they do not contain cycles that can be affected by other threads. atomic_compare_exchange primitive (InterlockedCompareExchange, __sync_val_compare_and_swap) is usually not used, because it is usually tied with a "repeat until succeed" cycle.

Below is an example of a wait-free algorithm:
void increment_reference_counter(rc_base* obj)
{
    atomic_increment(obj->rc);
}

void decrement_reference_counter(rc_base* obj)
{
    if (0 == atomic_decrement(obj->rc))
        delete obj;
Each thread is able to execute the function in a bounded number of steps regardless of any external factors.

Lock-freedom
Lock-freedom means that a system as a whole moves forward regardless of anything. Forward progress for each individual thread is not guaranteed (that is, individual threads can starve). It's a weaker guarantee than wait-freedom. Lockfree algorithms usually use atomic_compare_exchange primitive (InterlockedCompareExchange, __sync_val_compare_and_swap).

An example of a lockfree algorithm is:
void stack_push(stack* s, node* n)
{
    node* head;
    do
    {
        head = s->head;
        n->next = head;
    }
    while ( ! atomic_compare_exchange(s->head, head, n));

As can be seen, a thread can "whirl" in the cycle theoretically infinitely. But every repeat of the cycle means that some other thread had made forward progress (that is, successfully pushed a node to the stack). A blocked/interrupted/terminated thread can not prevent forward progress of other threads. Consequently, the system as a whole undoubtedly makes forward progress.

Obstruction-freedom
Obstruction-freedom guarantee means that a thread makes forward progress only if it does not encounter contention from other threads. That is, two threads can prevent each other's progress and lead to a livelock. It's even weaker guarantee than loсk-freedom. This guarantee may look a bit strange at first. However, note that (1) blocked/interrupted/terminated threads can not prevent progress of other threads, and (2) obstruction-free algorithms can be faster than lockfree algorithms.

I am unable to come up with a single example, so I refer you to the original paper Obstruction-Free Synchronization: Double-Ended Queues as an Example.

Termination-safety
Waitfree, lockfree and obstruction-free algorithms provide a guarantee of termination-safety. That is, a terminated thread does not prevent system-wide forward progress.

Blocking Algorithms
It's the weakest guarantee - basically all bets are off, the system as a whole may not make any forward progress. A blocked/interrupted/terminated thread may prevent system-wide forward progress infinitely. Mutex-based algorithms are also amenable to deadlocks, and a deadlocked system clearly makes no forward progress.

Practical Implications
Don't get it as it's impossible to create mutex-based programs what make forward progress. It's indeed possible to create mutex-based programs that do make eventual forward progress, and there are zillions of examples of it out there. Wait-freedom, loсk-freedom are theoretical properties that consider kind of corner cases. However, there are some practical implications as well:

1. With lockfree algorithms a thread that can make forward progress is always one of the currently running threads, and thus it actually makes forward progress. With mutex-based algorithms there is also usually a thread that can make forward progress, however it may be a currently non-running thread, and thus no actual forward progress happens (at least until, for example, a page will be loaded from disk and/or several context switches happen and/or some amount of active spinning happens). 

2. Waitfree, lockfree algorithms can be used in some contexts where lock-based algorithms can not be used. For example, it's generally unsafe to use locks in signal handlers, because the lock can be currently acquired by the preempted thread, and it instantly leads to a deadlock. Another example is hard real-time systems, where wait-free algorithms are preferable because of strict upper bounds on execution time. 

3.  In some systems (most notably in multi-process systems that use inter-process shared memory for communication) threads can be unexpectedly terminated due to timeouts, fatal failures or by operator's command. In such systems mutexes are inherently unsafe to use, because, if a terminated thread holds a mutex, the mutex will be never released (yes, there are so called robust mutexes, but that's another story, and in the end they still require usage of lockfree algorithms or something like that).

Performance/scalability
As you may have noticed, I did not say anything about performance yet. That's right - the terms are about forward progress guarantees, and are orthogonal to performance. Of course, some lockfree algorithms are faster than mutex-based algorithms, but only by accident. In general lockfree algorithms are slower than analogous algorithms not burdened with forward progress guarantees (think of Quality-Of-Service vs. Best-Effort). Let me refine the point, here I am looking from the point of view of what guarantee your system requires. Lockfree is a subset of blocking (stricter guarantee), so if your system is Ok with blocking (does not require any particular forward progress guarantees), then you can choose the fastest algorithm from blocking/lockfree/wait-free. If your system requires lockfree forward progress guarantees, then you can choose only from lockfree/waitfree. And if your system requires wait-free guarantees, then you can choose only from wait-free algorithms. So blocking is at least as fast as lockfree, while it can be faster (when it happened so that the fastest known algorithm is at least partially blocking).

Comments