I think I have finally got a better understanding on a few locking related concepts, so I shall provide a few code snippets to elaborate in my way. The concepts I plan to cover in this post are non-blocking, lock free and wait free. The scope of them is basically, non-blocking > lock free > wait free.

§Non-blocking

an algorithm is called non-blocking if failure or suspension of any thread cannot cause failure or suspension of another thread

Then, as soon as we use blocking locking, pthread_mutex_lock, in multiple thread, the program is disqualified as non-blocking program, for if the one holding the lock is suspended, other threads who need the same lock would block.

One example, that’s non-blocking, but not lock free could be:

#include <pthread.h>
#include <stdbool.h>

extern int a_lock;
extern int b_lock;

int a_lock = 0;
int b_lock = 0;

static bool lock(int *l)
{
    int tmp = 0;
    return __atomic_compare_exchange_n(l, &tmp, 1,
            false, __ATOMIC_SEQ_CST, __ATOMIC_SEQ_CST);
}
static void unlock(int *l)
{
    __atomic_store_n(l, 0, __ATOMIC_SEQ_CST);
}

void* thread_P(void * arg)
{
    while(1) {
        if (lock(&a_lock)) {
            if (lock(&b_lock)) {
                // do stuff with a and b
                unlock(&b_lock);
                unlock(&a_lock);
                break;
            } else {
                unlock(&a_lock);
            }
        }
    }
    return NULL;
}

void* thread_Q(void * arg)
{
    while(1) {
        if (lock(&b_lock)) {
            if (lock(&a_lock)) {
                // do stuff with a and b
                unlock(&a_lock);
                unlock(&b_lock);
                break;
            } else {
                unlock(&b_lock);
            }
        }
    }
    return NULL;
}

int main(int argc, char *argv[])
{
    pthread_t p, q;
    pthread_create(&p, NULL, thread_P, NULL);
    pthread_create(&q, NULL, thread_Q, NULL);
    pthread_exit(NULL);
}

§Lock free

A non-blocking algorithm is lock-free if there is guaranteed system-wide progress

The above program is not considered as lock free, because it contains a live lock. (It seems it’s not so easy to construct one non-blocking, but not lock free program.) One simple example of lock free example could be:

#include <pthread.h>
#include <stdbool.h>

extern int counter;

int counter = 0;

static void inc(int *c)
{
    int old = *c;
    while(!__atomic_compare_exchange_n(c, &old, old+1,
            false, __ATOMIC_SEQ_CST, __ATOMIC_SEQ_CST)) {
        old = *c;
    }
}

void* thread_P(void * arg)
{
    while(__atomic_load_n(&counter, __ATOMIC_SEQ_CST) < 100) {
        inc(&counter);
    }
    return NULL;
}

void* thread_Q(void * arg)
{
    while(__atomic_load_n(&counter, __ATOMIC_SEQ_CST) < 100) {
        inc(&counter);
    }
    return NULL;
}

int main(int argc, char *argv[])
{
    pthread_t p, q;
    pthread_create(&p, NULL, thread_P, NULL);
    pthread_create(&q, NULL, thread_Q, NULL);
    pthread_exit(NULL);
}

It’s possible that thread q is unlucky that the CAS in inc always fails. Even though one thread suffers from starvation, but the system as a whole still makes some progress.

§Wait free

and wait-free if there is also guaranteed per-thread progress

static void inc(int *c)
{
    __atomic_add_fetch(c, 1, __ATOMIC_SEQ_CST);
}

We just need to change the inc function to make it wait free. Now, each thread is guaranteed to make some progress.

§Reference