A Close Look at a Spinlock

You're referring to a Linux Futex, which is a user-space construct.

In kernel-level code, for areas of the kernel that must use real spinlocks, they do not fallback to the equivalent of a Futex because that would mean the current thread of execution would be swapped out and kernel-level spinlocks are designed for critical sections that cannot be swapped out. In critical sections of the kernel that can be swapped out, you'd use a Mutex which does the equivalent of a user-level Futex (and swap out) when the Mutex is contended.

FreeBSD has "adaptive locks" in the kernel, but the logic works the other way: A sleep mutex might spin for a while before sleeping. Going the other way wouldn't work because there's some contexts (e.g. in a lightweight interrupt handler) where you can't sleep.

Actually, many mutex implementations first spin in a loop and only then enter wait state. One prominent example is Windows' CRITICAL_SECTION (where the spin count is even configurable). However, I would never call it a spinlock. A mutex might contain a spinlock but not vice versa. After all, the defining property of a spinlock is that it never goes to sleep. One use case outside kernel programming is to protect shared resources in (soft) real time applications where the use of mutexes are forbidden (e.g. real time audio programming). Often you can use atomic variables or lockfree queues instead, but sometimes a spinlock is the only practical solution.

What you describe isn't a spinlock then. It's a regular blocking IPC primitive with an optimization layer that can busy-wait a bit.

As the term is pervasively used in industry, "spinlocks" always imply locking against other physical hardware, and that can't be done without spinning (I mean, you could fall back to blocking, but then the blocking implementation in the kernel would have to lock its own data structures to effect the scheduling; it's a chicken and egg problem). They usually, but not quite always, imply protection against asynchronous interrupts or signals too.

True spinlocks in user space are rarely a good idea. You would use a spinlock in the first place because you assume that the critical section is short, but the kernel often gets in the way of that assumption. The thread in the critical section can run out of its time slice, or there’s an interrupt etc. etc.

And once this happens, you now have a descheduled thread that owns the lock and a spinning thread waiting to acquire it, which is a recipe for priority inversion. As far as the kernel can tell, it’s the spinning thread that’s doing some important work so it has no reason to preempt it and schedule the waiting thread, which is exactly the wrong thing to do in this situation.

The OS schedules threads that it wants to run. When you consider which thread to schedule, don't schedule a thread that is waiting for a lock that isn't free yet.

Google for how the Linux Futex works. In short it's done by task switching after double checking the spinlock is still held. The kernel can do such a thing without the threat of a race condition because it can ensure no other task is running that would modify the spinlock state.

The kernel knows about mutexes, and so the thread waiting on the lock won't be scheduled again until the mutex has been released. Whether the lock can be acquired depends on the scheduler and how many other threads are waiting on the same lock.

To have a thread block on a lock, you need to keep track of the fact that the thread is waiting on that lock, and then when the lock is unlocked, wake that thread (or at least one thread that's blocked on it).

That could be a wait queue, or it could be keeping track of what lock (if any) a thread is blocked on and iterating all threads to see if anything is blocked (this is relatively easy to implement, but not great if you have many threads), or ???. If you're running SMP or a re-entrant kernel, you need to be careful about how you do your checks so you don't have race conditions; you don't want a thread blocked on an unlocked lock.

>But say in your OS now you want the thread to go to sleep until it’s available.. how is actually implemented without spinning and using CPU?

If you're facing such low-latency constraints that you need a spinlock, you wouldn't want the thread to sleep, instead you'd pin the core and have the dedicated core constantly spinning. That's how it's done in HFT. You can use a fancy network card like SolarFlare with efvi_drivers to bypass the kernel completely for network IO (spin waiting on the network card). Basically you need to treat the kernel like it's a paedophile trying to molest your children, and do everything you can to stop it touching your low-latency threads.

Your program has to use a kernel level synchronisation primitive that supports blocking by sleeping, like a pipe, if you don't want to spin.