Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

A Close Look at a Spinlock

blog.regehr.org

Post reply on HN
Print view View original

11–20 of 30 posts

Re: A Close Look at a Spinlock

#11

Post by cperciva »

asdfasgasdgasdg wrote: post #2

One thing I was surprised to learn about spinlocks is that not all spinlocks are spinlocks! At at least one company I have worked for, spinlocks are actually just locks that are biased to spin, but still fall back to kernel-based locking and scheduling eventually. Likewise, that company's main mutex class spins for a while before locking. When I asked why the rationale was something like, "If a spinlock is ever held…

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.

Re: A Close Look at a Spinlock

#12

Post by spacechild1 »

asdfasgasdgasdg wrote: post #2

One thing I was surprised to learn about spinlocks is that not all spinlocks are spinlocks! At at least one company I have worked for, spinlocks are actually just locks that are biased to spin, but still fall back to kernel-based locking and scheduling eventually. Likewise, that company's main mutex class spins for a while before locking. When I asked why the rationale was something like, "If a spinlock is ever held…

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.

Re: A Close Look at a Spinlock

#13

Post by ajross »

asdfasgasdgasdg wrote: post #2

One thing I was surprised to learn about spinlocks is that not all spinlocks are spinlocks! At at least one company I have worked for, spinlocks are actually just locks that are biased to spin, but still fall back to kernel-based locking and scheduling eventually. Likewise, that company's main mutex class spins for a while before locking. When I asked why the rationale was something like, "If a spinlock is ever held…

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.

Re: A Close Look at a Spinlock

#14

Post by lovecg »

asdfasgasdgasdg wrote: post #2

One thing I was surprised to learn about spinlocks is that not all spinlocks are spinlocks! At at least one company I have worked for, spinlocks are actually just locks that are biased to spin, but still fall back to kernel-based locking and scheduling eventually. Likewise, that company's main mutex class spins for a while before locking. When I asked why the rationale was something like, "If a spinlock is ever held…

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.

Re: A Close Look at a Spinlock

#15

Post by dataflow »

lovecg wrote: post #14
asdfasgasdgasdg wrote: post #2

One thing I was surprised to learn about spinlocks is that not all spinlocks are spinlocks! At at least one company I have worked for, spinlocks are actually just locks that are biased to spin, but still fall back to kernel-based locking and scheduling eventually. Likewise, that company's main mutex class spins for a while before locking. When I asked why the rationale was something like, "If a spinlock is ever held…

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 ac…

Spins are so short and well-defined that I wonder why the kernel doesn't just examine a handful of instructions around the program counter and guess if the thread is spinning or not before scheduling it for another time slice. Seems like a really nice and simple kind of heuristic to implement.

Re: A Close Look at a Spinlock

#16

Post by toast0 »

sydthrowaway wrote: post #4

One thing I don’t get is how blocking is implemented once you have basic mutual exclusion working? Lets say you try to take the lock, but you spin, waiting for it. 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?

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.

Re: A Close Look at a Spinlock

#17

Post by asdfasgasdgasdg »

CyberRabbi wrote: post #3
asdfasgasdgasdg wrote: post #2

One thing I was surprised to learn about spinlocks is that not all spinlocks are spinlocks! At at least one company I have worked for, spinlocks are actually just locks that are biased to spin, but still fall back to kernel-based locking and scheduling eventually. Likewise, that company's main mutex class spins for a while before locking. When I asked why the rationale was something like, "If a spinlock is ever held…

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,…

I was referring to https://github.com/abseil/abseil-cpp/blob/master/absl/base/i...

Re: A Close Look at a Spinlock

#18

Post by comex »

ajross wrote: post #13
asdfasgasdgasdg wrote: post #2

One thing I was surprised to learn about spinlocks is that not all spinlocks are spinlocks! At at least one company I have worked for, spinlocks are actually just locks that are biased to spin, but still fall back to kernel-based locking and scheduling eventually. Likewise, that company's main mutex class spins for a while before locking. When I asked why the rationale was something like, "If a spinlock is ever held…

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 t…

Yes, but it's not so uncommon for "spinlocks" to evolve into not-actually-spinlocks while keeping the name. In the Linux kernel, `spinlock_t` is actually a mutex if `PREEMPT_RT` is enabled [1]. And Darwin has some code to do this in userspace [2], although I'm not sure if it's actually used.

[1] https://www.kernel.org/doc/html/latest/locking/locktypes.htm...

[2] https://github.com/apple/darwin-libplatform/blob/main/src/os...

Re: A Close Look at a Spinlock

#19

Post by monocasa »

dataflow wrote: post #15
lovecg wrote: post #14

Earlier quoted context omitted.

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 ac…

Spins are so short and well-defined that I wonder why the kernel doesn't just examine a handful of instructions around the program counter and guess if the thread is spinning or not before scheduling it for another time slice. Seems like a really nice and simple kind of heuristic to implement.

Oh jeeze, I don't think there'd be anything simple about having to divine facts about user space by the code flow graph near the interrupted instruction on basically every thread switch.
Post reply on HN