Background
I recently investigated a wave of production stalls around read-write
locks. The suspicious stacks all came from
NSOperationQueue, and the relevant worker threads were
marked QOS:BACKGROUND. The lock owners appeared to be
alive, but they were not getting enough CPU time, which eventually
caused the main thread to hit the 8-second watchdog threshold.
Why would a thread that already owns a lock take so long to finish? There are two likely explanations:
- It really is that slow.
- Priority inversion is happening.
The diagrams below show the main thread waiting for the lock while a background thread holds it.
How to deal with it
In this case, the low-priority thread holding the read-write lock is scheduled too late, gets preempted, or simply runs out of time slices. Meanwhile, the high-priority thread continues to wait for the lock. This is classic priority inversion.
Since iOS 8, Apple has exposed QualityOfService, which
maps roughly to thread priority. Different QoS classes receive different
CPU, network, and disk resource treatment, so QoS can influence
scheduling behavior.
Option 1:
Remove QoS settings from NSOperationQueue
Apple gives a clear warning in the Threading Programming Guide:
It is generally a good idea to leave the priorities of your threads at their default values. Increasing the priorities of some threads also increases the likelihood of starvation among lower-priority threads. If your application contains high-priority and low-priority threads that must interact with each other, the starvation of lower-priority threads may block other threads and create performance bottlenecks.
The practical takeaway is simple: avoid raising thread priority arbitrarily, especially when high- and low-priority threads compete for the same critical resource. In some cases, removing the QoS override is enough to solve the problem.
Option 2: Temporarily raise the worker thread priority
The pthread_rwlock_rdlock(3pthread) documentation says:
Realtime applications may encounter priority inversion when using read-write locks. The problem occurs when a high priority thread “locks” a read-write lock that is about to be “unlocked” by a low priority thread, but the low priority thread is preempted by a medium priority thread. This scenario leads to priority inversion; a high priority thread is blocked by lower priority threads for an unlimited period of time. During system design, realtime programmers must take into account the possibility of this kind of priority inversion. They can deal with it in a number of ways, such as by having critical sections that are guarded by read-write locks execute at a high priority, so that a thread cannot be preempted while executing in its critical section.
That guidance is written for realtime systems, but it points to a
useful workaround. In our case, once a thread acquires
_rwlock through pthread_rwlock_wrlock, we
temporarily boost its QoS, then restore the original QoS after releasing
the lock.
1 | { |
One thing to note: this has to be done with pthread
APIs. NSThread APIs do not work here.
1 | // NSThread.h |
Demo verification
To verify whether manual priority adjustment helps, I ran a local
demo. It creates 2000 operations to keep the CPU busy, sets
the queue QoS to NSQualityOfServiceUserInitiated, and
downgrades every 100th operation to
NSQualityOfServiceBackground. Each operation runs the same
expensive work, and the 10 selected operations are
measured.
1 | for (int j = 0; j < 2000; ++j) { |
Measured results:
Normal case: average time per task is
11.8190561. After lowering the operation priority:94.70210189. After lowering the priority and restoring it inside the block:15.04005137(still a bit slower than the normal case, which is worth thinking about).
The demo shows that manual priority boosting can greatly reduce the time spent in low-priority tasks. When a lock is involved, that directly shortens the time the main thread remains blocked.
A deeper look at priority inversion
Does every lock need the same manual priority boost? Will the system automatically adjust thread priority? If so, can it cover all locks? To answer these questions, we need to understand priority inversion more carefully.
What is priority inversion?
Priority inversion happens when a low-priority process or thread owns
a synchronization resource, while a high-priority process or thread is
waiting for that resource. As a result, the high-priority thread is
delayed behind the low-priority one. Depending on the blocking pattern,
priority inversion is usually split into
Bounded priority inversion and
Unbounded priority inversion.
The diagrams below are adapted from Introduction to RTOS - Solution to Part 11 (Priority Inversion).
Bounded priority inversion
Here, the high-priority task (Task H) is blocked by the
low-priority task (Task L) that owns the lock. The blocking
time is bounded by how long Task L stays in the critical
section. As long as Task L holds the lock,
Task H stays blocked, and the low-priority task effectively
runs ahead of the high-priority one.
Unbounded priority inversion
If a medium-priority task (Task M) preempts
Task L while Task L is holding the lock, the
bounded case turns into an unbounded one. Task M can keep
taking CPU time away from Task L, which means
Task H may remain blocked for an arbitrarily long time.
Common solutions
There are two classic ways to deal with unbounded priority inversion:
Priority ceiling protocol
Each critical resource is assigned a ceiling priority. When a task enters the critical section, the system temporarily raises that task to the ceiling priority. When the task leaves the critical section, its original priority is restored. The ceiling is chosen as the maximum priority of all tasks that may use the resource.
In the figure, the lock ceiling is 3. When
Task L holds the lock, it is boosted to priority
3, the same as Task H, which prevents
Task M from running until Task L and
Task H are done with the lock.
Priority inheritance
With priority inheritance, if a high-priority task is waiting for a lock owned by a low-priority task, the low-priority owner temporarily inherits the higher priority so it can run sooner and release the resource. After the lock is released, the original priority is restored.
Both approaches restore the low-priority task’s priority when the
lock is released. But they only prevent
Unbounded priority inversion; they cannot eliminate
Bounded priority inversion, because Task H
still has to wait for Task L to finish the critical
section.
Ways to reduce or avoid bounded inversion include:
- Shorten the critical section.
- Avoid using critical resources that block high-priority work.
- Use a dedicated queue to manage the resource instead of a lock.
Priority inheritance must be transitive. For example, if
T1 is blocked by a resource owned by T2, and
T2 is itself blocked by a resource owned by
T3, then T3 must inherit the highest priority
from T1 through T2. Otherwise, another thread
with priority between T2 and T3 could preempt
T3, causing an inversion relative to T1.
How do we avoid priority inversion?
QoS propagation
iOS mainly uses two mechanisms to propagate QoS across threads or queues:
dispatch_asyncdispatch_async()automatically propagates the QoS from the calling thread, but it translatesUser InteractivetoUser Initiatedso that non-main threads do not get that highest priority.- QoS is captured when the block is submitted. If the destination queue does not have a QoS or does not lower the QoS, the captured value is used.
- XPC-based inter-process communication.
The QoS propagation rules are more complex and depend on:
- the current thread’s QoS,
- the arguments used when creating a
dispatch_blockwithdispatch_block_create(), - the QoS of the destination queue or thread for
dispatch_asyncor IPC.
The scheduler uses these inputs to decide which priority a block should run with.
- If no thread is synchronously waiting for that block, the block runs at the priority computed above.
- If there is synchronous waiting between threads, the scheduler may adjust priorities to avoid inversion.
When can the system trigger inversion avoidance?
If the current thread is blocked by work running on another thread, and the system knows which thread owns that work, it can boost the relevant owner and avoid inversion. If the system does not know the owner, it cannot decide whom to boost.
APIs that record owner information include:
pthread mutex,os_unfair_lock, and higher-level APIs built on top of them:dispatch_onceusesos_unfair_lock.NSLock,NSRecursiveLock,@synchronized, and similar APIs are based onpthread mutex.
dispatch_syncanddispatch_wait.xpc_connection_send_with_message_sync.
Using these APIs allows the system to activate priority inversion avoidance when inversion happens.
Basic API verification
Next, let’s verify the APIs mentioned above.
Test environment: iOS 15.2 simulator
pthread mutex
The pthread_mutex_s structure has an m_tid
field that records the owner thread ID.
1 | // types_internal.h |
Let’s verify whether the thread priority changes.
1 | // printThreadPriority prints the priority information of the current thread |
Lock the mutex on a background thread, then have the main thread request it:
1 | dispatch_async(dispatch_get_global_queue(DISPATCH_QUEUE_PRIORITY_BACKGROUND, 0), ^{ |
1 | begin : |
You can see that the low-priority background thread starts at
priority 4, and once the main thread requests the lock, the
owner gets boosted to 47.
os_unfair_lock
os_unfair_lock replaces OSSpinLock and
solves the inversion problem by putting waiting threads to sleep instead
of busy-waiting. It stores the owner thread ID internally and donates
priority to the owner while threads are waiting.
Let’s verify it:
1 | dispatch_async(dispatch_get_global_queue(DISPATCH_QUEUE_PRIORITY_BACKGROUND, 0), ^{ |
1 | begin : |
The result is the same as pthread mutex.
pthread_rwlock_t
The pthread_rwlock_init documentation says:
Caveats: Beware of priority inversion when using read-write locks. A high-priority thread may be blocked waiting on a read-write lock locked by a low-priority thread. The microkernel has no knowledge of read-write locks, and therefore can’t boost the low-priority thread to prevent the priority inversion.
In other words, the kernel cannot identify the read-write lock owner
and boost its priority. The definition of pthread_rwlock_s,
however, contains an rw_tid field that records the thread
holding the write lock. That raises an interesting question: if the
structure records an owner, why can it not participate in priority
inheritance?
1 | struct pthread_rwlock_s { |
This Hacker News thread mentions:
xnu supports priority inheritance through “turnstiles”, a kernel-internal mechanism which is used by default by a number of locking primitives (list at [1]), including normal
pthread mutexes (though not read-write locks [2]), as well as theos_unfair_lockAPI (via the ulock syscalls). Withpthread mutexes, you can actually explicitly request priority inheritance by calling pthread_mutexattr_setprotocol [3] with PTHREAD_PRIO_INHERIT; the Apple implementation supports it, but currently ignores the protocol setting and just gives all mutexes priority inheritance.
In short: XNU uses the kernel-internal
turnstile mechanism for priority inheritance, and this
mechanism is applied to pthread mutex and
os_unfair_lock.
Following that clue leads to _kwq_use_turnstile in
ksyn_wait. The comment describes read-write locks somewhat
cautiously and adds “at least sometimes”.
pthread mutexes and rwlocks both (at least sometimes) know theirownerand can use turnstiles. Otherwise, we pass NULL as the tstore to the shims so they wait on the global waitq.
1 | // libpthread/kern/kern_synch.c |
The implementation of _kwq_use_turnstile resolves the
ambiguity: only KSYN_WQTYPE_MTX enables
turnstile-based priority inheritance. A read-write lock
uses KSYN_WQTYPE_RWLOCK, so it does not take this path.
1 |
|
In _pthread_find_owner, we can also see that the owner
of a read-write lock is 0.
1 | void |
Now replace the lock with a read-write lock and verify whether the theory is correct:
1 | pthread_rwlock_init(&_rwlock, NULL); |
1 | begin : |
As a result, read-write locks do not boost the owner thread.
dispatch_sync
The result for dispatch_sync is easy to verify:
1 | // Current thread is the main thread |
1 | pth_priority: 47, pth_curpri: 47, pth_maxpriority: 63 |
The queue is low priority (QOS_CLASS_BACKGROUND). Both
the dispatch_sync work item and the earlier
dispatch_async item get boosted to priority
47, while the later dispatch_async item runs
at priority 4.
dispatch_wait
1 | // Current thread is the main thread |
The queue is a low-priority queue
(QOS_CLASS_BACKGROUND). When the current main thread waits
through dispatch_wait, the output is as follows, and the
low-priority task is boosted to priority 47:
1 | main thread |
Note that
dispatch_waitis a macro / generic entry point that can acceptdispatch_block_t,dispatch_group_t, anddispatch_semaphore_t. Here the practical meaning is closer todispatch_block_wait, which is the one that can adjust priority and avoid inversion.
1 | intptr_t |
The mysterious semaphore
dispatch_semaphore
I used to think binary semaphores and mutexes were basically the
same. In practice, dispatch_semaphore has no QoS concept
and does not track the owner thread. So when a high-priority thread
waits on it, the kernel has no idea which thread should be boosted. If
the lock owner has a lower priority than the waiter, the high-priority
thread can wait forever.
This is a warning from the system:
Semaphores are for signaling (same as condition variables, events) while mutexes are for mutual exclusion. Technically, you can also use semaphores for mutual exclusion (a mutex can be thought as a binary semaphore) but you really shouldn’t. Right, but libdispatch doesn’t have a mutex. It has semaphores and queues. So if you’re trying to use libdispatch and you don’t want the closure-based aspect of queues, you might be tempted to use a semaphore instead. Don’t do that, use
os_unfair_lockor pthread_mutex (or a higher-level construct like NSLock) instead.
That is a pretty strong hint: semaphores are dangerous if you use them as locks.
Apple’s example:
1 | __block NSString *taskName = nil; |
- If this runs on the main thread, the current priority is
QOS_CLASS_USER_INTERACTIVE. - The async work triggered from the main thread gets elevated to
QOS_CLASS_USER_INITIATED. - The main thread is blocked by the semaphore, but the async task that signals it runs at a lower priority, so priority inversion may happen.
Clang even has a static checker for this pattern.
1 | static auto findGCDAntiPatternWithSemaphore() -> decltype(compoundStmt()) { |
Xcode exposes this analyzer through the Performance Anti-Patterns with Grand Central Dispatch build setting.
dispatch_groupbehaves similarly tosemaphore: when you callenter(), the system does not know who will eventually callleave(), so it cannot know the owner either. Therefore it does not participate in priority donation.
A real deadlock case caused by semaphores
I once wrote code like this to synchronously wait for camera permission on the main thread:
1 | __block BOOL auth = NO; |
After launch, this stack remained one of the most common apparent deadlocks in production. Once I understood that semaphores cannot participate in priority inheritance, the pattern finally made sense.
There are usually two ways to fix this:
- Use a synchronous API.
1 | BOOL auth = [KTAuthorizeService authorizationWithType:KTPermissionsTypeCamera]; |
- Use an asynchronous callback and do not block the current thread.
1 | [KTAuthorizeService requestAuthorizationWithType:KTPermissionsTypeCamera completionHandler:^(BOOL allow) { |
But what if you really need to turn an async API into a sync one,
while also avoiding priority inversion? dispatch_block_wait
only accepts the simplest dispatch_block_t form, and cannot
handle parameterized or returning blocks. So if the callback is more
complicated, this approach breaks down. Is there a cleaner solution? I
will leave that question open for now.
Some concepts
Turnstile
Earlier I mentioned that XNU uses turnstile for priority
inheritance. Here is a simplified mental model.
There are many synchronization objects in XNU, such as
lck_mtx_t. To solve priority inversion, each
synchronization object would need its own separate structure to track
all related state, including the queue of blocked threads. If every sync
object allocated such a structure permanently, memory usage would be
huge.
XNU solves this with the turnstile mechanism. The key
idea is that one thread cannot block on multiple synchronization objects
at the same time. Therefore each sync object only needs a pointer to a
turnstile, and the turnstile itself can be
allocated on demand. It stores everything needed for the lock, such as
the blocked thread queue and the owner pointer. turnstiles
are dynamically allocated from a pool, and the pool grows with the
number of active threads. The number of turnstiles is therefore bounded
and manageable. The first blocked thread allocates the turnstile; once
no threads are waiting anymore, the turnstile is returned to the
pool.
1 | struct turnstile { |
Priority values
The priority numbers in the experiments are Mach-level user thread priorities. A quick reference from Mac OS X and iOS Internals:
- User thread priorities are
0~63.NSQualityOfServiceBackgroundmaps to4.NSQualityOfServiceUtilitymaps to20.NSQualityOfServiceDefaultmaps to31.NSQualityOfServiceUserInitiatedmaps to37.NSQualityOfServiceUserInteractivemaps to47.
- Kernel thread priorities are
80~95. - Realtime thread priorities are
96~127. 64~79are reserved by the system.
Summary
This article walked through the main ideas behind priority inversion and the common ways to handle it, then studied several iOS locking primitives in detail. With a deeper understanding, we can avoid unnecessary priority inversion and reduce deadlock-like stalls.
Source note: this article also appears on WeChat: Priority Inversion in Practice.
References
- WWDC18 What’s New in LLVM - actorsfit
- https://developer.apple.com/videos/play/wwdc2015/718
- https://developer.apple.com/forums/thread/124155
- https://developer.apple.com/library/archive/documentation/Cocoa/Conceptual/Multithreading/CreatingThreads/CreatingThreads.html
- https://developer.apple.com/library/archive/documentation/Performance/Conceptual/EnergyGuide-iOS/PrioritizeWorkWithQoS.html
- https://github.com/llvm-mirror/clang/blob/google/stable/lib/StaticAnalyzer/Checkers/GCDAntipatternChecker.cpp
- Don’t use dispatch semaphores where mutexes (or dispatch queues) would suffice
- Concurrency Problems Written by Scott Grosch
- https://www.jianshu.com/p/af64e05de503
- https://pubs.opengroup.org/onlinepubs/7908799/xsh/pthread_rwlock_wrlock.html
- Understanding and Using Locks in iOS
- The Unsafe OSSpinLock
- https://blog.actorsfit.com/a?ID=00001-499b1c8e-8a7f-4960-a1c1-c8e2f42c08c6
- https://objccn.io/issue-2-1/#Priority-Inversion
- Introduction to RTOS - Solution to Part 11 (Priority Inversion)
- https://threadreaderapp.com/thread/1229999590482444288.html#
- Deep Dive into iOS Locks
- Threads can infect each other with their low priority