Priority Inversion in Practice

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:

  1. It really is that slow.
  2. Priority inversion is happening.

The diagrams below show the main thread waiting for the lock while a background thread holds it.

Priority Inversion in Practice: Background (figure 1) Priority Inversion in Practice: Background (figure 2)

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
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
{
pthread_rwlock_wrlock(&_rwlock);

qos_class_t oldQos = qos_class_self();
BOOL needRecover = NO;

// Temporarily boost thread priority
if (_enablePriorityInversionProtection && oldQos < QOS_CLASS_USER_INTERACTIVE) {
int ret = pthread_set_qos_class_self_np(QOS_CLASS_USER_INTERACTIVE, 0);
needRecover = (ret == 0);
}

......

pthread_rwlock_unlock(&_rwlock);

// Restore priority
if (_enablePriorityInversionProtection && needRecover) {
pthread_set_qos_class_self_np(oldQos, 0);
}

return result;
}

One thing to note: this has to be done with pthread APIs. NSThread APIs do not work here.

1
2
3
4
5
// NSThread.h
// To be deprecated; use qualityOfService below
@property double threadPriority API_AVAILABLE(macos(10.6), ios(4.0), watchos(2.0), tvos(9.0));
// read-only after the thread is started
@property NSQualityOfService qualityOfService API_AVAILABLE(macos(10.10), ios(8.0), watchos(2.0), tvos(9.0));

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
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
for (int j = 0; j < 2000; ++j) {
NSOperationQueue *operation = [[NSOperationQueue alloc] init];
operation.maxConcurrentOperationCount = 1;
operation.qualityOfService = NSQualityOfServiceUserInitiated;
// if (j % 100 == 0) {
// operation.qualityOfService = NSQualityOfServiceBackground;
// }
[operation addOperationWithBlock:^{
// qos_class_t oldQos = qos_class_self();
// pthread_set_qos_class_self_np(QOS_CLASS_USER_INITIATED, 0);

NSTimeInterval start = CFAbsoluteTimeGetCurrent();
double sum = 0;
for (int i = 0; i < 100000; ++i) {
sum += sin(i) + cos(i) + sin(i*2) + cos(i*2);
}
start = CFAbsoluteTimeGetCurrent() - start;
if (j % 100 == 0) {
printf("%.8f\n", start * 1000);
}
// pthread_set_qos_class_self_np(oldQos, 0);
}];
}

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.

Priority Inversion in Practice: Bounded priority inversion (figure 3)

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.

Priority Inversion in Practice: Unbounded priority inversion (figure 4)

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 Inversion in Practice: Priority ceiling protocol (figure 5)

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.

Priority Inversion in Practice: Priority inheritance (figure 6)

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:

  1. Shorten the critical section.
  2. Avoid using critical resources that block high-priority work.
  3. 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_async
    • dispatch_async() automatically propagates the QoS from the calling thread, but it translates User Interactive to User Initiated so 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_block with dispatch_block_create(),
  • the QoS of the destination queue or thread for dispatch_async or IPC.

The scheduler uses these inputs to decide which priority a block should run with.

  1. If no thread is synchronously waiting for that block, the block runs at the priority computed above.
  2. 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:

  1. pthread mutex, os_unfair_lock, and higher-level APIs built on top of them:
    1. dispatch_once uses os_unfair_lock.
    2. NSLock, NSRecursiveLock, @synchronized, and similar APIs are based on pthread mutex.
  2. dispatch_sync and dispatch_wait.
  3. 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
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
// types_internal.h
struct pthread_mutex_s {
long sig;
_pthread_lock lock;
union {
uint32_t value;
struct pthread_mutex_options_s options;
} mtxopts;
int16_t prioceiling;
int16_t priority;
#if defined(__LP64__)
uint32_t _pad;
#endif
union {
struct {
uint32_t m_tid[2]; // thread id of thread that has mutex locked
uint32_t m_seq[2]; // mutex sequence id
uint32_t m_mis[2]; // for misaligned locks m_tid/m_seq will span into here
} psynch;
struct _pthread_mutex_ulock_s ulock;
};
#if defined(__LP64__)
uint32_t _reserved[4];
#else
uint32_t _reserved[1];
#endif
};

Let’s verify whether the thread priority changes.

1
2
3
4
5
6
7
8
9
10
11
12
// printThreadPriority prints the priority information of the current thread
void printThreadPriority() {
thread_t cur_thread = mach_thread_self();
mach_msg_type_number_t thread_info_count = THREAD_INFO_MAX;
thread_info_data_t thinfo;
kern_return_t kr = thread_info(cur_thread, THREAD_EXTENDED_INFO, (thread_info_t)thinfo, &thread_info_count);
if (kr != KERN_SUCCESS) {
return;
}
thread_extended_info_t extend_info = (thread_extended_info_t)thinfo;
printf("pth_priority: %d, pth_curpri: %d, pth_maxpriority: %d\n", extend_info->pth_priority, extend_info->pth_curpri, extend_info->pth_maxpriority);
}

Lock the mutex on a background thread, then have the main thread request it:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
dispatch_async(dispatch_get_global_queue(DISPATCH_QUEUE_PRIORITY_BACKGROUND, 0), ^{
printf("begin : \n");
printThreadPriority();
printf("queue before lock \n");
pthread_mutex_lock(&_lock); // ensure backgroundQueue gets the lock first
printf("queue lock \n");
printThreadPriority();
dispatch_async(dispatch_get_main_queue(), ^{
printf("before main lock\n");
pthread_mutex_lock(&_lock);
printf("in main lock\n");
pthread_mutex_unlock(&_lock);
printf("after main unlock\n");
});
sleep(10);
printThreadPriority();
printf("queue unlock\n");
pthread_mutex_unlock(&_lock);
printf("queue after unlock\n");
});
1
2
3
4
5
6
7
8
9
10
11
begin : 
pth_priority: 4, pth_curpri: 4, pth_maxpriority: 63
queue before lock
queue lock
pth_priority: 4, pth_curpri: 4, pth_maxpriority: 63
before main lock
pth_priority: 47, pth_curpri: 47, pth_maxpriority: 63
queue unlock
in main lock
after main unlock
queue after unlock

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
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
dispatch_async(dispatch_get_global_queue(DISPATCH_QUEUE_PRIORITY_BACKGROUND, 0), ^{
printf("begin : \n");
printThreadPriority();
printf("queue before lock \n");
os_unfair_lock_lock(&_unfair_lock); // ensure backgroundQueue gets the lock first
printf("queue lock \n");
printThreadPriority();
dispatch_async(dispatch_get_main_queue(), ^{
printf("before main lock\n");
os_unfair_lock_lock(&_unfair_lock);
printf("in main lock\n");
os_unfair_lock_unlock(&_unfair_lock);
printf("after main unlock\n");
});
sleep(10);
printThreadPriority();
printf("queue unlock\n");
os_unfair_lock_unlock(&_unfair_lock);
printf("queue after unlock\n");
});
1
2
3
4
5
6
7
8
9
10
11
begin : 
pth_priority: 4, pth_curpri: 4, pth_maxpriority: 63
queue before lock
queue lock
pth_priority: 4, pth_curpri: 4, pth_maxpriority: 63
before main lock
pth_priority: 47, pth_curpri: 47, pth_maxpriority: 63
queue unlock
in main lock
after main unlock
queue after unlock

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
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
struct pthread_rwlock_s {
long sig;
_pthread_lock lock;
uint32_t
unused:29,
misalign:1,
pshared:2;
uint32_t rw_flags;
#if defined(__LP64__)
uint32_t _pad;
#endif
uint32_t rw_tid[2]; // thread id of thread that has exclusive (write) lock
uint32_t rw_seq[4]; // rw sequence id (at 128-bit aligned boundary)
uint32_t rw_mis[4]; // for misaligned locks rw_seq will span into here
#if defined(__LP64__)
uint32_t _reserved[34];
#else
uint32_t _reserved[18];
#endif
};

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 the os_unfair_lock API (via the ulock syscalls). With pthread 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 their owner and can use turnstiles. Otherwise, we pass NULL as the tstore to the shims so they wait on the global waitq.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
// libpthread/kern/kern_synch.c
int
ksyn_wait(ksyn_wait_queue_t kwq, kwq_queue_type_t kqi, uint32_t lockseq,
int fit, uint64_t abstime, uint16_t kwe_flags,
thread_continue_t continuation, block_hint_t block_hint)
{
thread_t th = current_thread();
uthread_t uth = pthread_kern->get_bsdthread_info(th);
struct turnstile **tstore = NULL;
int res;

assert(continuation != THREAD_CONTINUE_NULL);

ksyn_waitq_element_t kwe = pthread_kern->uthread_get_uukwe(uth);
bzero(kwe, sizeof(*kwe));
kwe->kwe_count = 1;
kwe->kwe_lockseq = lockseq & PTHRW_COUNT_MASK;
kwe->kwe_state = KWE_THREAD_INWAIT;
kwe->kwe_uth = uth;
kwe->kwe_thread = th;
kwe->kwe_flags = kwe_flags;

res = ksyn_queue_insert(kwq, kqi, kwe, lockseq, fit);
if (res != 0) {
return res;
}

PTHREAD_TRACE(psynch_mutex_kwqwait, kwq->kw_addr, kwq->kw_inqueue,
kwq->kw_prepost.count, kwq->kw_intr.count);

if (_kwq_use_turnstile(kwq)) {
// pthread mutexes and rwlocks both (at least sometimes) know their
// owner and can use turnstiles. Otherwise, we pass NULL as the
// tstore to the shims so they wait on the global waitq.
tstore = &kwq->kw_turnstile;
}
......
}

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
2
3
4
5
6
7
8
9
10
11
12
13
#define KSYN_WQTYPE_MTX         0x01
#define KSYN_WQTYPE_CVAR 0x02
#define KSYN_WQTYPE_RWLOCK 0x04
#define KSYN_WQTYPE_SEMA 0x08

static inline bool
_kwq_use_turnstile(ksyn_wait_queue_t kwq)
{
// If we had writer-owner information from the
// rwlock then we could use the turnstile to push on it. For now, only
// plain mutexes use it.
return (_kwq_type(kwq) == KSYN_WQTYPE_MTX);
}

In _pthread_find_owner, we can also see that the owner of a read-write lock is 0.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
void
_pthread_find_owner(thread_t thread,
struct stackshot_thread_waitinfo * waitinfo)
{
ksyn_wait_queue_t kwq = _pthread_get_thread_kwq(thread);
switch (waitinfo->wait_type) {
case kThreadWaitPThreadMutex:
assert((kwq->kw_type & KSYN_WQTYPE_MASK) == KSYN_WQTYPE_MTX);
waitinfo->owner = thread_tid(kwq->kw_owner);
waitinfo->context = kwq->kw_addr;
break;
/* Owner of rwlock not stored in kernel space due to races. Punt
* and hope that the userspace address is helpful enough. */
case kThreadWaitPThreadRWLockRead:
case kThreadWaitPThreadRWLockWrite:
assert((kwq->kw_type & KSYN_WQTYPE_MASK) == KSYN_WQTYPE_RWLOCK);
waitinfo->owner = 0;
waitinfo->context = kwq->kw_addr;
break;
/* Condvars don't have owners, so just give the userspace address. */
case kThreadWaitPThreadCondVar:
assert((kwq->kw_type & KSYN_WQTYPE_MASK) == KSYN_WQTYPE_CVAR);
waitinfo->owner = 0;
waitinfo->context = kwq->kw_addr;
break;
case kThreadWaitNone:
default:
waitinfo->owner = 0;
waitinfo->context = 0;
break;
}
}

Now replace the lock with a read-write lock and verify whether the theory is correct:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
pthread_rwlock_init(&_rwlock, NULL);
dispatch_async(dispatch_get_global_queue(DISPATCH_QUEUE_PRIORITY_BACKGROUND, 0), ^{
printf("begin : \n");
printThreadPriority();
printf("queue before lock \n");
pthread_rwlock_rdlock(&_rwlock); // ensure backgroundQueue gets the lock first
printf("queue lock \n");
printThreadPriority();
dispatch_async(dispatch_get_main_queue(), ^{
printf("before main lock\n");
pthread_rwlock_wrlock(&_rwlock);
printf("in main lock\n");
pthread_rwlock_unlock(&_rwlock);
printf("after main unlock\n");
});
sleep(10);
printThreadPriority();
printf("queue unlock\n");
pthread_rwlock_unlock(&_rwlock);
printf("queue after unlock\n");
});
1
2
3
4
5
6
7
8
9
10
11
begin : 
pth_priority: 4, pth_curpri: 4, pth_maxpriority: 63
queue before lock
queue lock
pth_priority: 4, pth_curpri: 4, pth_maxpriority: 63
before main lock
pth_priority: 4, pth_curpri: 4, pth_maxpriority: 63
queue unlock
queue after unlock
in main lock
after main unlock

As a result, read-write locks do not boost the owner thread.

dispatch_sync

The result for dispatch_sync is easy to verify:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
// Current thread is the main thread
dispatch_queue_attr_t qosAttribute = dispatch_queue_attr_make_with_qos_class(DISPATCH_QUEUE_SERIAL, QOS_CLASS_BACKGROUND, 0);
_queue = dispatch_queue_create("com.demo.test", qosAttribute);
printThreadPriority();
dispatch_async(_queue, ^{
printf("dispatch_async before dispatch_sync : \n");
printThreadPriority();
});
dispatch_sync(_queue, ^{
printf("dispatch_sync: \n");
printThreadPriority();
});
dispatch_async(_queue, ^{
printf("dispatch_async after dispatch_sync: \n");
printThreadPriority();
});
1
2
3
4
5
6
7
pth_priority: 47, pth_curpri: 47, pth_maxpriority: 63 
dispatch_async before dispatch_sync :
pth_priority: 47, pth_curpri: 47, pth_maxpriority: 63
dispatch_sync:
pth_priority: 47, pth_curpri: 47, pth_maxpriority: 63
dispatch_async after dispatch_sync:
pth_priority: 4, pth_curpri: 4, 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
2
3
4
5
6
7
8
9
10
11
12
// Current thread is the main thread
dispatch_queue_attr_t qosAttribute = dispatch_queue_attr_make_with_qos_class(DISPATCH_QUEUE_SERIAL, QOS_CLASS_BACKGROUND, 0);
_queue = dispatch_queue_create("com.demo.test", qosAttribute);
printf("main thread\n");
printThreadPriority();
dispatch_block_t block = dispatch_block_create(DISPATCH_BLOCK_INHERIT_QOS_CLASS, ^{
printf("sub thread\n");
sleep(2);
printThreadPriority();
});
dispatch_async(_queue, block);
dispatch_wait(block, DISPATCH_TIME_FOREVER);

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
2
3
4
5
6
7
8
9
10
main thread
pth_priority: 47, pth_curpri: 47, pth_maxpriority: 63
sub thread
pth_priority: 47, pth_curpri: 47, pth_maxpriority: 63

If dispatch_wait(block, DISPATCH_TIME_FOREVER) is commented out, the output is:
main thread
pth_priority: 47, pth_curpri: 47, pth_maxpriority: 63
sub thread
pth_priority: 4, pth_curpri: 4, pth_maxpriority: 63

Note that dispatch_wait is a macro / generic entry point that can accept dispatch_block_t, dispatch_group_t, and dispatch_semaphore_t. Here the practical meaning is closer to dispatch_block_wait, which is the one that can adjust priority and avoid inversion.

1
2
3
4
5
6
7
8
9
10
intptr_t
dispatch_wait(void *object, dispatch_time_t timeout);
#if __has_extension(c_generic_selections)
#define dispatch_wait(object, timeout) \
_Generic((object), \
dispatch_block_t:dispatch_block_wait, \
dispatch_group_t:dispatch_group_wait, \
dispatch_semaphore_t:dispatch_semaphore_wait \
)((object),(timeout))
#endif

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_lock or 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
2
3
4
5
6
7
8
__block NSString *taskName = nil;
dispatch_semaphore_t sema = dispatch_semaphore_create(0);
[self.connection.remoteObjectProxy requestCurrentTaskName:^(NSString *task) {
taskName = task;
dispatch_semaphore_signal(sema);
}];
dispatch_semaphore_wait(sema, DISPATCH_TIME_FOREVER);
return taskName;
  1. If this runs on the main thread, the current priority is QOS_CLASS_USER_INTERACTIVE.
  2. The async work triggered from the main thread gets elevated to QOS_CLASS_USER_INITIATED.
  3. 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
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
static auto findGCDAntiPatternWithSemaphore() -> decltype(compoundStmt()) {

const char *SemaphoreBinding = "semaphore_name";
auto SemaphoreCreateM = callExpr(allOf(
callsName("dispatch_semaphore_create"),
hasArgument(0, ignoringParenCasts(integerLiteral(equals(0))))));

auto SemaphoreBindingM = anyOf(
forEachDescendant(
varDecl(hasDescendant(SemaphoreCreateM)).bind(SemaphoreBinding)),
forEachDescendant(binaryOperator(bindAssignmentToDecl(SemaphoreBinding),
hasRHS(SemaphoreCreateM))));

auto HasBlockArgumentM = hasAnyArgument(hasType(
hasCanonicalType(blockPointerType())
));

auto ArgCallsSignalM = hasAnyArgument(stmt(hasDescendant(callExpr(
allOf(
callsName("dispatch_semaphore_signal"),
equalsBoundArgDecl(0, SemaphoreBinding)
)))));

auto HasBlockAndCallsSignalM = allOf(HasBlockArgumentM, ArgCallsSignalM);

auto HasBlockCallingSignalM =
forEachDescendant(
stmt(anyOf(
callExpr(HasBlockAndCallsSignalM),
objcMessageExpr(HasBlockAndCallsSignalM)
)));

auto SemaphoreWaitM = forEachDescendant(
callExpr(
allOf(
callsName("dispatch_semaphore_wait"),
equalsBoundArgDecl(0, SemaphoreBinding)
)
).bind(WarnAtNode));

return compoundStmt(
SemaphoreBindingM, HasBlockCallingSignalM, SemaphoreWaitM);
}

Xcode exposes this analyzer through the Performance Anti-Patterns with Grand Central Dispatch build setting.

Priority Inversion in Practice: dispatch_semaphore (figure 7)

dispatch_group behaves similarly to semaphore: when you call enter(), the system does not know who will eventually call leave(), 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
2
3
4
5
6
7
__block BOOL auth = NO;
dispatch_semaphore_t semaphore = dispatch_semaphore_create(0);
[KTAuthorizeService requestAuthorizationWithType:KTPermissionsTypeCamera completionHandler:^(BOOL allow) {
auth = allow;
dispatch_semaphore_signal(semaphore);
}];
dispatch_semaphore_wait(semaphore, DISPATCH_TIME_FOREVER);

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.

Priority Inversion in Practice: A real deadlock case caused by semaphores (figure 8)

There are usually two ways to fix this:

  1. Use a synchronous API.
1
2
BOOL auth = [KTAuthorizeService authorizationWithType:KTPermissionsTypeCamera];
// do something next
  1. Use an asynchronous callback and do not block the current thread.
1
2
3
4
[KTAuthorizeService requestAuthorizationWithType:KTPermissionsTypeCamera completionHandler:^(BOOL allow) {
BOOL auth = allow;
// do something next via callback
}];

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
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
struct turnstile {
struct waitq ts_waitq;
turnstile_inheritor_t ts_inheritor;
union {
struct turnstile_list ts_free_turnstiles;
SLIST_ENTRY(turnstile) ts_free_elm;
};
struct priority_queue_sched_max ts_inheritor_queue;
union {
struct priority_queue_entry_sched ts_inheritor_links;
struct mpsc_queue_chain ts_deallocate_link;
};
SLIST_ENTRY(turnstile) ts_htable_link;
uintptr_t ts_proprietor;
os_refcnt_t ts_refcount;
_Atomic uint32_t ts_type_gencount;
uint32_t ts_port_ref;
turnstile_update_flags_t ts_inheritor_flags;
uint8_t ts_priority;

#if DEVELOPMENT || DEBUG
uint8_t ts_state;
queue_chain_t ts_global_elm;
thread_t ts_thread;
thread_t ts_prev_thread;
#endif
};

Priority values

The priority numbers in the experiments are Mach-level user thread priorities. A quick reference from Mac OS X and iOS Internals:

  1. User thread priorities are 0~63.
    1. NSQualityOfServiceBackground maps to 4.
    2. NSQualityOfServiceUtility maps to 20.
    3. NSQualityOfServiceDefault maps to 31.
    4. NSQualityOfServiceUserInitiated maps to 37.
    5. NSQualityOfServiceUserInteractive maps to 47.
  2. Kernel thread priorities are 80~95.
  3. Realtime thread priorities are 96~127.
  4. 64~79 are reserved by the system.
Priority Inversion in Practice: Priority values (figure 9)

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

  1. WWDC18 What’s New in LLVM - actorsfit
  2. https://developer.apple.com/videos/play/wwdc2015/718
  3. https://developer.apple.com/forums/thread/124155
  4. https://developer.apple.com/library/archive/documentation/Cocoa/Conceptual/Multithreading/CreatingThreads/CreatingThreads.html
  5. https://developer.apple.com/library/archive/documentation/Performance/Conceptual/EnergyGuide-iOS/PrioritizeWorkWithQoS.html
  6. https://github.com/llvm-mirror/clang/blob/google/stable/lib/StaticAnalyzer/Checkers/GCDAntipatternChecker.cpp
  7. Don’t use dispatch semaphores where mutexes (or dispatch queues) would suffice
  8. Concurrency Problems Written by Scott Grosch
  9. https://www.jianshu.com/p/af64e05de503
  10. https://pubs.opengroup.org/onlinepubs/7908799/xsh/pthread_rwlock_wrlock.html
  11. Understanding and Using Locks in iOS
  12. The Unsafe OSSpinLock
  13. https://blog.actorsfit.com/a?ID=00001-499b1c8e-8a7f-4960-a1c1-c8e2f42c08c6
  14. https://objccn.io/issue-2-1/#Priority-Inversion
  15. Introduction to RTOS - Solution to Part 11 (Priority Inversion)
  16. https://threadreaderapp.com/thread/1229999590482444288.html#
  17. Deep Dive into iOS Locks
  18. Threads can infect each other with their low priority
-------------本文结束 感谢您的阅读-------------
If this article helped you, your support encourages me to keep writing.

Title:Priority Inversion in Practice

Author:lingyun

Published:2022-11-23 17:53

Updated:2026-10-07 00:00

Original link:https://tsuijunxi.github.io/en/2022/11/23/priority-inversion-in-practice/

License: Attribution-NonCommercial-NoDerivatives 4.0 International Please keep the original link and author when sharing.