Difficulty: Advanced
What is a spinlock? How is it implemented with test-and-set, and when is it better than a mutex that puts the thread to sleep?
Spinlocks come up in interviews at companies that work close to the hardware, like Qualcomm, Intel and Samsung, and they are a great way to test whether you understand the cost of blocking. Here is the intuition. Suppose you are waiting for a friend to finish a quick phone call. You could go home and take a nap, and hope to be woken up later, or you could stand right there and glance at them every second. If the call will last five seconds, standing is better, because a nap plus the trip home takes longer than the wait. If the call will last an hour, standing wastes your time. A spinlock is standing and checking; a sleeping mutex is going home for a nap.
A spinlock is a lock where a thread that cannot acquire it loops continuously, testing the lock variable until it becomes free. This is busy waiting. It burns CPU cycles while waiting, but it avoids the cost of putting the thread to sleep and waking it later, which involves system calls, scheduler work and a context switch. If the lock hold time is shorter than the cost of a context switch, spinning wins.
To implement it correctly you need atomic hardware instructions, because a naive check-then-set would itself be a race. The classic primitive is test-and-set: atomically read the old value of a memory word and set it to 1, returning the old value. The lock loop is: while (test_and_set(&lock) == 1) { spin }. If it returns 0, the lock was free and we now own it. Unlock is simply setting the variable to 0. Another primitive is compare-and-swap (CAS): atomically set a variable to a new value only if it currently equals an expected value. On x86 these map to xchg and lock cmpxchg instructions. Well-optimized spinlocks use test-and-test-and-set: spin on a normal read (served from the local cache without bus traffic) and only attempt the atomic operation when the lock looks free. They also use a pause instruction inside the loop and exponential backoff to reduce cache-line bouncing.
Where are spinlocks appropriate? In operating system kernels, on multiprocessor machines, for very short critical sections, for example protecting a scheduler run queue or interrupt handler data. In an interrupt handler you cannot sleep at all, so a spinlock is the only choice. On a single-core machine, spinning is pointless because the lock holder cannot run while you spin, unless you disable preemption; kernels handle this by turning spinlocks into preemption-disable operations on uniprocessor builds.
When are they wrong? In user space with long critical sections, or when the lock holder can be preempted while holding the lock, because everyone else spins uselessly for an entire time slice. This is called lock-holder preemption. Hybrid adaptive mutexes, used in Solaris and modern pthread and Java implementations, spin briefly, then fall back to sleeping.
Also mention fairness. A plain test-and-set spinlock is unfair and can starve a thread. Ticket locks and queue-based locks (MCS) provide FIFO ordering and reduce contention.
Summarize with the rule: spin when the expected wait is shorter than a context switch and you have multiple cores; sleep otherwise.
#include <stdatomic.h>
#include <pthread.h>
#include <stdio.h>
atomic_flag lock = ATOMIC_FLAG_INIT;
long counter = 0;
void spin_lock(void) { while (atomic_flag_test_and_set(&lock)) { /* spin */ } }
void spin_unlock(void) { atomic_flag_clear(&lock); }
void *work(void *arg) {
for (int i = 0; i < 500000; i++) {
spin_lock();
counter++; /* very short critical section */
spin_unlock();
}
return NULL;
}
int main(void) {
pthread_t a, b;
pthread_create(&a, NULL, work, NULL);
pthread_create(&b, NULL, work, NULL);
pthread_join(a, NULL);
pthread_join(b, NULL);
printf("counter = %ld\n", counter);
return 0;
}atomic_flag_test_and_set atomically sets the flag and returns its old value; the loop exits only for the thread that saw it clear.
spinlock, test-and-set, compare-and-swap, busy waiting, atomic operations