New thread priority management
sebastian.huber at embedded-brains.de
Wed Sep 21 07:08:25 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 embedded-brains.de
PGP : Public key available on request.
Diese Nachricht ist keine geschäftliche Mitteilung im Sinne des EHUG.
More information about the devel