If a scheduler change breaks userland apps, that sounds like a scheduler bug to me... Any word on whether there is going to be a rollback/further scheduler changes to make spinlocks useful again?
There will not. QOS was a very large and intentional change, and it's critical to getting great performance out of iOS and to make the fanless MacBook work at all.
In general, Apple has never encouraged anyone to use spinlocks, and as I mentioned at the end, as long as your critical section is really tiny and CPU-bound you're unlikely to actually have a problem in practice. Note that spinlocks have always had a problem with priority inversion (OSSpinLock's back-off algorithm is just to call syscall_thread_switch with a 1ms delay every 1024 iterations, which is not bad but doesn't solve all priority inversions anyway).
> since threads spinning on a spinlock are always runnable, this means that if there's enough high-QOS threads waiting on a lock held by a lower-QOS thread, the thread that owns the lock will never execute.
Is this true? OSSpinLock (at least on OS X) calls thread_switch for 1ms every 1024 iterations (which as far as I understand is basically sleeping[1]). Presumably it's not runnable while it's sleeping?
After 100 * 1024 iterations it will also ask to be throttled to the lowest priority for 1ms, again with thread_switch.
I didn't go into OSSpinLock specifics because I didn't want the distraction. The naive spinlock shown in the post certainly is always runnable. OSSpinLock's behavior helps with priority inversions, but it doesn't solve the issue with QOS. If there's enough threads of a high QOS blocked on an OSSpinLock it can still livelock. Only truly unbounded backoff can solve that in all cases, but that can lead to high-QOS threads being delayed for a long time (according to the Apple engineer it could result in "tens of seconds" of delay, which is obviously not acceptable for a high-QOS thread).
Why not "just" fall back to a mutex after enough spinning? I guess this would require an extra branch in the unlocking function (to check whether there are threads blocked in the kernel that need to be woken up), but that doesn't sound too awful especially as the branch would very rarely be taken. (It would sort of break OSSpinLock's ABI though. Sort of.)
(rewritten after looking up Linux's adaptive mutex)
Assuming you mean something like http://stackoverflow.com/a/25168942/582, you basically need a full mutex anyway, so I'm not sure why you wouldn't just use a mutex directly. I don't think you can really implement this adaptive mutex in userland because you can't just use a spinlock + a mutex (you'd have to lock the mutex every time anyway, which defeats the point of having the spinlock) and syscalls are not considered public API (the kernel is allowed to change syscalls between versions, libc/libsystem is the only public API for them).
I don't understand. Could you explain this in more detail?
In Linux, adaptive mutexes are implemented entirely in userspace with futex as the primitive syscall. This is because atomic CAS (cmpxchg, ldrex/strex, etc) suffices to ensure synchronization during the spinning.
syscalls aren't public API on Darwin platforms (e.g. iOS, OS X). The only supported interface to syscalls is libc/libsystem. And I'm not aware of any equivalent to futex. So AFAIK there's no way to implement a userspace mutex that isn't just a wrapper around a system-provided mutex (e.g. pthread_mutex, or a serial libdispatch queue). And if you're wrapping pthread_mutex, adding a spinlock doesn't provide any benefit.
FWIW, libdispatch itself definitely uses Mach SPI. For example, skimming through the source, it calls thread_switch() using a non-public option (there's 3 non-public options to thread_switch now, two of which are intended for dealing with the QOS issues that my article talked about; the private os_lock_handoff_s that the objc runtime uses internally uses one called SWITCH_OPTION_OSLOCK_WAIT and libdispatch appears to use the other, SWITCH_OPTION_OSLOCK_DEPRESS, as well as the third option which was added just for libdispatch called SWITCH_OOPTION_DISPATCH_CONTENTION).
Agreed. This is one of those areas that most mobile developers are better off with a little less rope to hang themselves.
The expression hurry up and wait comes to mind. I would rather have a thread sleeping while it waits for slightly less perceptual performance than a thread spinning and chewing through my battery because it's waiting as fast as it can.
The article suggests that new Macbook/OS X might be just as bad, but the linked twitter thread (https://twitter.com/Catfish_Man/status/676851988596809728) makes the situation there sound rather less serious. The issue appears to be slow progress, rather than a total lack of it.
(I had the same problem years ago with somebody's spinlocks on Windows running on a single-CPU system; the obvious functions to yield a timeslice will yield only to a thread of equal or higher priority, meaning you can starve a lower-priority thread. But even when this happens, the lower-priority thread does get a timeslice eventually - which sounds like the OS X situation.)
I wonder why they're writing a new KVO library, given that KVO is very awkward in Swift. Something like ReactiveCocoa's PropertyType/MutablePropertyType is a much safer approach.
19 comments
[ 3.2 ms ] story [ 51.6 ms ] threadIn general, Apple has never encouraged anyone to use spinlocks, and as I mentioned at the end, as long as your critical section is really tiny and CPU-bound you're unlikely to actually have a problem in practice. Note that spinlocks have always had a problem with priority inversion (OSSpinLock's back-off algorithm is just to call syscall_thread_switch with a 1ms delay every 1024 iterations, which is not bad but doesn't solve all priority inversions anyway).
Is this true? OSSpinLock (at least on OS X) calls thread_switch for 1ms every 1024 iterations (which as far as I understand is basically sleeping[1]). Presumably it's not runnable while it's sleeping?
After 100 * 1024 iterations it will also ask to be throttled to the lowest priority for 1ms, again with thread_switch.
[1] http://web.mit.edu/darwin/src/modules/xnu/osfmk/man/thread_s...
AKA an adaptive mutex.
Assuming you mean something like http://stackoverflow.com/a/25168942/582, you basically need a full mutex anyway, so I'm not sure why you wouldn't just use a mutex directly. I don't think you can really implement this adaptive mutex in userland because you can't just use a spinlock + a mutex (you'd have to lock the mutex every time anyway, which defeats the point of having the spinlock) and syscalls are not considered public API (the kernel is allowed to change syscalls between versions, libc/libsystem is the only public API for them).
FWIW pthread mutexes were sped up 2-2.5x in "new OSs" to compensate for spinlocks being illegal (https://twitter.com/catfish_man/status/676852111527706624).
I don't understand. Could you explain this in more detail?
In Linux, adaptive mutexes are implemented entirely in userspace with futex as the primitive syscall. This is because atomic CAS (cmpxchg, ldrex/strex, etc) suffices to ensure synchronization during the spinning.
FWIW, libdispatch itself definitely uses Mach SPI. For example, skimming through the source, it calls thread_switch() using a non-public option (there's 3 non-public options to thread_switch now, two of which are intended for dealing with the QOS issues that my article talked about; the private os_lock_handoff_s that the objc runtime uses internally uses one called SWITCH_OPTION_OSLOCK_WAIT and libdispatch appears to use the other, SWITCH_OPTION_OSLOCK_DEPRESS, as well as the third option which was added just for libdispatch called SWITCH_OOPTION_DISPATCH_CONTENTION).
That obviously breaks the whole system, spinlocks or not (threads doing long CPU-bound computations will block everything else).
You can cause pretty bad performance by running too long in user-interactive or in OpenCL, so, like, don't do that.
The expression hurry up and wait comes to mind. I would rather have a thread sleeping while it waits for slightly less perceptual performance than a thread spinning and chewing through my battery because it's waiting as fast as it can.
(I had the same problem years ago with somebody's spinlocks on Windows running on a single-CPU system; the obvious functions to yield a timeslice will yield only to a thread of equal or higher priority, meaning you can starve a lower-priority thread. But even when this happens, the lower-priority thread does get a timeslice eventually - which sounds like the OS X situation.)