spinlock
**Spin Locks and Backoff Strategies** are the **lightweight mutual exclusion primitives where a thread repeatedly checks (spins on) a lock variable until it becomes available, rather than sleeping and being woken by the OS** — providing the lowest possible lock acquisition latency for short critical sections where the expected wait time is less than the cost of a context switch, but requiring careful backoff strategies to avoid devastating cache coherence traffic that can reduce multi-core performance by 10-100× under contention.
**Spin Lock vs. Mutex**
| Property | Spin Lock | OS Mutex |
|----------|----------|----------|
| Wait mechanism | Busy-waiting (CPU spinning) | Sleep + wakeup (syscall) |
| Latency (uncontended) | ~10-20 ns | ~100-200 ns |
| Latency (contended) | Varies (can be very high) | ~1-10 µs |
| CPU usage while waiting | 100% (burns CPU) | 0% (sleeping) |
| Best for | Short critical sections (< 1 µs) | Long or I/O-bound sections |
| Context switches | None | 2 per lock/unlock cycle |
**Test-and-Set (TAS) Spin Lock**
```c
typedef atomic_int spinlock_t;
void spin_lock(spinlock_t *lock) {
while (atomic_exchange(lock, 1) == 1)
; // Spin until we get 0 (unlocked)
}
void spin_unlock(spinlock_t *lock) {
atomic_store(lock, 0);
}
```
- Problem: Every spin iteration does atomic_exchange → write to cache line → invalidates all other cores' copies → massive coherence traffic.
**Test-and-Test-and-Set (TTAS)**
```c
void spin_lock_ttas(spinlock_t *lock) {
while (1) {
while (atomic_load(lock) == 1) // Test (read-only, cached)
; // Spin on local cache — no bus traffic
if (atomic_exchange(lock, 1) == 0) // Test-and-Set
return; // Got the lock
}
}
```
- Inner loop reads from local cache → no coherence traffic while lock is held.
- Only attempt atomic exchange when lock appears free → much less traffic.
- Still: When lock is released, all waiting threads simultaneously attempt exchange → "thundering herd."
**Backoff Strategies**
| Strategy | How | Effect |
|----------|-----|--------|
| No backoff | Spin continuously | Maximum contention |
| Fixed delay | Wait constant time | Reduces contention but not adaptive |
| Linear backoff | Wait i × base_delay | Moderate improvement |
| Exponential backoff | Wait 2^i × base_delay (capped) | Best general-purpose |
| Randomized | Wait random(0, max_delay) | Avoids synchronization of retries |
```c
void spin_lock_backoff(spinlock_t *lock) {
int delay = MIN_DELAY;
while (1) {
while (atomic_load(lock) == 1) ; // Test (local cache)
if (atomic_exchange(lock, 1) == 0)
return; // Got it
// Backoff: wait before retrying
for (volatile int i = 0; i < delay; i++) ;
delay = min(delay * 2, MAX_DELAY); // Exponential backoff
}
}
```
**Advanced: MCS Queue Lock**
- Each thread spins on its own cache line (not a shared variable).
- Threads form a queue → predecessor signals successor → no thundering herd.
- O(1) coherence traffic per lock acquisition regardless of contention.
- Used in Linux kernel (qspinlock), Java (AbstractQueuedSynchronizer).
**Performance Under Contention**
| Lock Type | 2 Threads | 16 Threads | 64 Threads |
|-----------|----------|-----------|------------|
| TAS | 30 ns | 500 ns | 5 µs |
| TTAS | 25 ns | 200 ns | 2 µs |
| TTAS + exp. backoff | 25 ns | 150 ns | 500 ns |
| MCS queue | 40 ns | 100 ns | 120 ns |
| OS mutex | 150 ns | 2 µs | 5 µs |
**CPU Hints**
- x86: ``_mm_pause()`` in spin loop → reduce power, hint to CPU that spinning.
- ARM: ``__yield()`` → same purpose.
- Linux: ``cpu_relax()`` macro → architecture-portable spin hint.
Spin locks are **the lowest-latency synchronization primitive but demand respect for cache coherence** — the difference between a naive TAS lock and a properly implemented MCS queue lock under contention can be 40× in throughput, making spin lock algorithm choice a critical performance decision for any lock-heavy parallel application on multi-core systems.