Lock-free vs Spin-lock

Given a piece of code, how do you know if it's lock-based or lock-free? Let's first see two examples. Both of them are multi-thread programs accessing a shared variable and incrementing it.

Here is the version by using lock-free programming.

lock_free.c

#include <pthread.h>
#include <stdatomic.h>
#include <stdio.h>

_Atomic int count = 0;
void *adding(void *input) {
    int val;
    for (int i = 0; i < 1000000; i++) {
        do {
            val = count;
        } while (!atomic_compare_exchange_weak(&count, &val, val + 1));
    }
    pthread_exit(NULL);
}

int main() {
    pthread_t tid[10];
    for (int i = 0; i < 10; i++)
        pthread_create(&tid[i], NULL, adding, NULL);
    for (int i = 0; i < 10; i++)
        pthread_join(tid[i], NULL);
    printf("the value of count is %d\n", count);
}

Here is the version of spin-lock for the same purpose.

#include <pthread.h>
#include <stdatomic.h>
#include <stdio.h>

int count = 0;
_Atomic int lock = 0;
void *adding(void *input) {
    int expected = 0;
    for (int i = 0; i < 1000000; i++) {
        while (!atomic_compare_exchange_weak(
            &lock, &expected, 1)) // if the lock is 0(unlock), then set it to 1(lock)
            expected = 0; // if the CAS fails, the expected will be set to 1, so we need
                          // to change it to 0 again.
        count++;
        lock = 0;
    }
    pthread_exit(NULL);
}

int main() {
    pthread_t tid[10];
    for (int i = 0; i < 10; i++)
        pthread_create(&tid[i], NULL, adding, NULL);
    for (int i = 0; i < 10; i++)
        pthread_join(tid[i], NULL);
    printf("the value of count is %d\n", count);
}

Let's see the result and performance of the above two programs (averaged on 10 runs).

Lock-free:

the value of count is 10000000

Below is the running time:

0.761794856 seconds time elapsed

7.129865000 seconds user
0.010098000 seconds sys

Spin-lock:

the value of count is 10000000

Below is the running time:

2.644530873 seconds time elapsed

25.960686000 seconds user
 0.000000000 seconds sys

From the above result, we could see that the lock-free program is better than the spin-lock program. For the lock-free program, the key code is from line 9 to 11; for the spin-lock program, the key code is from line 10 to 15. They're both loops and look very similar. How come they perform differently?

Let's see by an example.

Lock-free:

Spin-lock

There are 4 threads modifying the shared variable count, and they try to get access to the shared variable count and increment it. From the above two images, we could see that in the lock-free program, while thread 1 is accessing the shared variable count, other threads could also get access to the count and make progress for the program.

However, for the lock-based program, while thread 1 is accessing the shared variable count, it holds the lock and other threads could not access the count but only busy-wait. So, here, we could see the difference between them.

For the lock-free program, every thread could get access to the shared object and make progress for the program no matter whether another thread is accessing the shared object or not, though sometimes there could be conflict (e.g. Thread 1 should redo its work). However, for the lock-based program, if one thread is accessing the shared object, other threads would be blocked and have no way to get access to the shared object. This is also the reason why the above lock-free program is faster than the lock-based program.