Fun with Futex

Summary

Fun with Futex Implementing an optimized lock in Linux requires some Operating System help. You can only get so far by doing everything in user-land. We are going to take a look how one can implement a simple spin lock in C (just like the spin lock in Go I implemented a while back) and then a slightly more elaborate lock using operating system’s primitives. The idea behind a mutex (mutual exclusion) is straightforward: we want some part of the code to be accessed only by a single thread at a time. If the resource a thread is trying to access (the critical zone) is already being accessed by something else: wait. The trick about implementing them is how you to do wait part! As usual, for the ones allergic to rambling, you can jump directly to the final code on GitHub. Behold the spin lock! The simplest way to wait in a mutex to “spin”. in other words: retry until your condition is met. Here’s a first pass implementation of our mutex in C: typedef struct { atomic_bool locked; } spin_lock_t; void lock(spin_lock_t *lock) { while (atomic_exchange(&lock->locked, true)) { // spin! } } void unlock(spin_lock_t *lock) { atomic_store(&lock->locked, false); } You don’t really need more than that for a simple spin lock. And it probably won’t differ too much in implementation in other programming languages with similar tomic constructs. atomic_exchange returns the old value from locked. If that value was false, it means that the lock was free, and the caller thread can claim it. If the value was true, then the lock is already in use by another thread, thus the caller must wait! To test this out, I wrote the following test harness. We start three threads, and each thread tries to increment the counter, acquiring the lock for each increment. Note that this is not a great example for locks, in a real scenario you will likely use an atomic for the increment. This is just a simple example and shouldn’t be a distraction from the actual implementation I’m interested in: the mutex! unsign...