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);
}

{
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;
}

{
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[])
{
}
``````

## 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;
}
}

{
inc(&counter);
}
return NULL;
}

{
inc(&counter);
}
return NULL;
}

int main(int argc, char *argv[])
{
}
``````

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)
{
We just need to change the `inc` function to make it wait free. Now, each thread is guaranteed to make some progress.