A spinlock is a special type of lock, where the waiter spins, looping on a memory read until the lock is acquired. Also called a busy-waiting lock.
Spinlock implementations requires atomic memory exchange to function properly.
Implementation Example
As an example of why, imagine you have the following code:
// assume that 0 is unlocked
int lock = 0;
void acquire(){
while(lock == 1){
// spin
}
lock = 1;
}
void release(){
lock = 0;
}
The above is a minimal implementation of a spinlock. But would it actually work?
The idea is that two threads trying to acquire would check the lock integer, the first one to get to it would set the lock integer to one, and the second one would run the while loop as long as that condition is true (in other words, it spins, or busy-waits).
When the first thread finishes, it releases the lock, sets the integer to zero, and our waiting thread breaks out of the loop and sets the lock to one, blocking any other waiting threads and goes on to do whatever it needs to do.
Reasoning for Atomicity
The code doesn’t particularly do anything useful, but the idea here is valid. However, it suffers from one crucial deficit, which is that what happens if both acquire the lock at exactly the same time?
In SM213, we could imagine that the acquire code translates to something like the following:
wait: ld $lock, r1
ld (r1), r1
ld $-1, r2
add r1, r2
beq r2 $wait # check again next cycle
# otherwise st 1 to lock and execute
What happens if the first thread is at line 4 when the second thread is at line 2? Both threads would load zero into register one, and would set the lock to one and execute like its no big deal, since they both evaluated the lock to be 0.
Because of this, we need an instruction that makes it impossible for two threads to be in between reading the value at r1 and setting its value to one. This is where the need for an atomic memory exchange instruction came from.
What it effectively does is reduce those lines of code where two threads mistakenly acquire the same value from memory by making it all one instruction. In one instruction, you read from that place in memory, and you store another value there.
That way, you get this:
ld $lock, r1
ld $1, r0
loop: xchg (r1), r0 # new atomic exchange instruction
beq r0, held
br loop
held:
In which case the previous problem becomes effectively impossible, since the atomicity of the instruction makes it so that if a thread has a lock with value zero, every other thread has to have read a one.
I like to think of it like those things at banks that spin, where one side is always facing you or it is facing the teller. Apparently they’re called rotary pass through trays. Or an airlock.
Issues with Spinlocks
Spinlocks suffer from multiple issues which make them generally less attractive than the other alternative locks. One of them is that the atomic memory exchange instructions are generally pretty costly. Turns out that condensing a few lines of assembly into one and ensuring it is the only instruction touching the memory in question when it executes comes with quite a bit of overhead in comparison to the usual non-atomic instructions.
The other is that busy waiting is generally considered a bit wasteful, since you block the entirety of the thread from doing anything and it will still occupy the CPU. If the machine has a single core/CPU, then you’re effectively polling.
Spinlocks are still used for a variety of things though, and are quite easy to implement.