Part 3 of 7 · 2 min read
Spinlock
In plain words: A single toilet has a sign on the door: vacant or occupied. People outside check the sign again and again until it shows vacant, then go in and turn the sign. For this to work, checking and turning must be one act, or two people can enter together. The analogy stops in one place: a person waiting may do something else in the meantime, while a spinning thread uses its processor.
A spinlock is a lock in which a thread that cannot get the lock keeps testing it in a loop, using the processor all the time, until it succeeds. It uses one variable: 0 for free and 1 for held. Test-and-set makes the check and the claim one atomic step:
static int lock_word; /* 0 free, 1 held */
void spin_lock(void) {
while (__atomic_exchange_n(&lock_word, 1, __ATOMIC_ACQUIRE))
; /* old value 1: someone has it, try again */
}
void spin_unlock(void) {
__atomic_store_n(&lock_word, 0, __ATOMIC_RELEASE);
}
__atomic_exchange_n stores 1 and returns the old value. If the old value was 0, the lock was free, and the thread now owns it. If it was 1, someone else owns it, and the thread stores 1 again (no change) and retries. Compare with the lock variable of page 1: there, reading and setting were separate steps and two threads both passed. Here the exchange is one step, and exactly one thread sees 0.
| Step | Thread A | Thread B | lock_word |
|---|---|---|---|
| 1 | exchange: old 0, new 1, enters | 1 | |
| 2 | exchange: old 1, new 1, loops | 1 | |
| 3 | exchange: old 1, loops | 1 | |
| 4 | releases: store 0 | 0 | |
| 5 | exchange: old 0, new 1, enters | 1 |
Checked against the requirements of page 1: it gives mutual exclusion, and progress (a free lock is taken). It does not give bounded waiting: when the lock is released, any spinning thread may win, so an unlucky thread can lose again and again.
The names ACQUIRE and RELEASE are the ordering guarantees: acquiring the lock prevents later accesses from moving before it, and releasing prevents earlier accesses from moving after it. They keep the work of the critical section inside the lock, the reordering problem of page 1.
Spinlock
A spinlock is a lock in which a thread that finds the lock held repeatedly tests it in a tight loop, using processor time, until the lock becomes free, and which relies on an atomic instruction such as test-and-set to take the lock without a race.
Example: a thread that sees the exchange return 1 loops and tries again until the holder stores 0.
Check yourself:
1. What value does the exchange return when the lock is free?
2. Which of the three requirements does a plain spinlock not guarantee?
3. What do ACQUIRE and RELEASE prevent?