New thread priority management

Sebastian Huber sebastian.huber at
Wed Sep 21 07:07:52 UTC 2016


I checked in a patch set today that reworks the thread priority 
management. This improves the priority inheritance protocol for example.

Previously, each thread used a resource count that reflects the count of 
mutexes owned by the thread. A thread could temporarily get a higher 
priority via priority inheritance due to mutexes which it owned 
directly. However, it did keep this temporary high priority until it 
released its last mutex (resource count changes from 1 to 0). So, in 
case of nested mutexes, it could have a high priority even though it 
already released the corresponding mutex.

Lets consider this scenario. We have a file system instance protected by 
one mutex (e.g. JFFS2) and a dynamic memory allocator protected by 
another mutex. A low priority thread performs writes some log data into 
a file, thus it acquires the file system instance mutex. The file system 
allocates dynamic memory. Now a high priority thread interrupts and 
tries to allocate dynamic memory. The allocator mutex is already owned, 
so the priority of the low priority thread is raised to the priority of 
the high priority thread. The memory allocation completes and the 
allocator mutex is released, since the low priority thread still owns 
the file system instance mutex it continues to execute with the high 
priority (the high priority thread is not scheduled). It may now perform 
complex and long file system operations (e.g. garbage collection, polled 
flash erase and write functions) with a high priority.

In the new implementation the thread priorities are tracked accurately 
and priority changes take place immediately, e.g. priority changes are 
not deferred until the thread releases its last resource. The actual 
priority of a thread is now an aggregation of priority nodes. The thread 
priority aggregation for the home scheduler instance of a thread 
consists of at least one priority node, which is normally the real 
priority of the thread.  The locking protocols (e.g. priority ceiling 
and priority inheritance), rate-monotonic period objects and the POSIX 
sporadic server add, change and remove priority nodes.

Priority inheritance works now recursively, e.g. a thread T0 owns mutex 
A, a thread T1 owns mutex B and waits for mutex A, a thread T2 which 
wants to obtain mutex B inherits its priority to the direct owner thread 
T1 and the indirect owner thread T0.

In addition timeouts are supported (nothing new, however, this is quite 
complex on SMP configurations) and we have a deadlock detection.

All these features are not for free. The additional storage space is 
negligible and affects only the thread control block and the thread 
stack. A non-recursive mutex object with support for priority 
inheritance consists of an SMP spin lock and two pointers (e.g. 12 bytes 
on a 32-bit machine in case of MCS spin locks). The implementation of 
the common case of a mutex obtain/release with no previous owner/waiting 
thread is next to optimal. The run-time of mutex obtain/release 
operations depends now on the mutex dependency graph, which is defined 
by the application. Complex and deeply nested mutex dependencies lead to 
long mutex obtain/release sequences. However, also without the accurate 
priority tacking in the scenario of complex dependencies, the overall 
run-time behaviour is pretty bad due to production of parasitic high 
priority threads or incomplete priority inheritance. Complex 
dependencies are a problem itself and it is the duty of an application 
designer to avoid them.

Sebastian Huber, embedded brains GmbH

Address : Dornierstr. 4, D-82178 Puchheim, Germany
Phone   : +49 89 189 47 41-16
Fax     : +49 89 189 47 41-09
E-Mail  : sebastian.huber at
PGP     : Public key available on request.

Diese Nachricht ist keine geschäftliche Mitteilung im Sinne des EHUG.

More information about the users mailing list