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.hu...@embedded-brains.de
PGP     : Public key available on request.

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

devel mailing list

Reply via email to