[RTEMS Project] #3359: 4.10: Improved Priority Inheritance Protocol

[RTEMS trac]

#3359: 4.10: Improved Priority Inheritance Protocol
--------------------+-----------------------
 Reporter:  Gedare  |       Owner:  Gedare
     Type:  defect  |      Status:  assigned
 Priority:  normal  |   Milestone:  4.10.3
Component:  score   |     Version:  4.10
 Severity:  normal  |  Resolution:
 Keywords:          |  Blocked By:
 Blocking:          |
--------------------+-----------------------
Description changed by Gedare:

Old description:

> See also #2412.
>
> = Problem
>
> The RTEMS mutexes implement only a very simple approximation of the
> priority inheritance protocol.  The real priority of a thread is only
> restored once it releases its last 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.
>
> = Functional requirements
>
> * The mutex shall use the priority inheritance protocol to prevent
> priority inversion.
>
> * The mutex shall allow vertical nesting (a thread owns multiple
> mutexes).
>
> * The mutex shall allow horizontal nesting (a thread waits for ownership
> of a mutex those owner waits for ownership of a mutex, and so on).
>
> * Threads shall wait in priority order.  The highest priority thread
> shall be dequeued first.
>
> * The highest priority waiting thread shall wait in FIFO order.
>
> * The mutex shall provide an acquire operation with timeout.
>
> * In case a mutex is released, then the previous owner shall no longer
> use the priorities inherited by this mutex.
>
> * In case a mutex acquire operation timeout occurs, then the current
> owner of the mutex shall no longer use the priorities inherited by the
> acquiring thread.
>
> * The order of the mutex release operations may differ from the order of
> the mutex acquire operations.
>
> * Priority changes not originating due to the priority inheritance
> protocol shall take place immediately.
>
> = Performance requirements
>
> * The mutex acquire operation shall use only object-specific locks in
> case the mutex is not owned currently.
>
> * The mutex release operation shall use only object-specific locks in
> case no threads wait for ownership of this mutex.
>
> = Invariants
>
> * A mutex shall be owned by at most one thread.
>
> * A thread shall wait for ownership of at most one mutex.
>
> = Proposed Implementation
>
> Use a recursive data structure to determine the highest priority
> available to a thread for each scheduler instance, e.g.
>
> {{{
> #!c
> typedef struct Thread_Priority_node {
>   Chain_Node Node;
>   Priority_Control current_priority;
>   Priority_Control real_priority;
>   struct CORE_mutex_Control *waiting_to_hold;
>   Chain_Control Inherited_priorities;
> } Thread_Priority_node;
>
> typedef struct {
>   ...
>   Thread_Priority_node Priority_node;
>   ...
> } Thread_Control;
> }}}
>
> Initially a thread has a priority node reflecting its real priority.  The
> Thread_Priority_node::owner is NULL.  The
> Thread_Priority_node::current_priority is set to the real priority.  The
> Thread_Priority_node::Inherited_priorities is empty.
>
> In case the thread must wait for ownership of a mutex, then it enqueues
> its priority node in Thread_Priority_node::Inherited_priorities of the
> mutex owner.
>
> In case the thread is dequeued from the wait queue of a mutex, then it
> dequeues its priority node in Thread_Priority_node::Inherited_priorities
> of the previous mutex owner (ownership transfer) or the current mutex
> owner (acquire timeout).
>
> In case the minimum of Thread_Priority_node::real_priority and
> Thread_Priority_node::Inherited_priorities changes, then
> Thread_Priority_node::current_priority is updated.  In case the
> Thread_Priority_node::owner its not NULL, the priority change propagates
> to the owner, and so on.  In case Thread_Priority_node::current_priority
> changes, the scheduler is notified.

New description:

 See also #2412.

 = Problem

 The RTEMS mutexes implement only a very simple approximation of the
 priority inheritance protocol.  The real priority of a thread is only
 restored once it releases its last mutex.  Lets consider this scenario.
 We have a file system instance protected by one mutex 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.

 = Functional requirements

 * The mutex shall use the priority inheritance protocol to prevent
 priority inversion.

 * The mutex shall allow vertical nesting (a thread owns multiple mutexes).

 * The mutex shall allow horizontal nesting (a thread waits for ownership
 of a mutex those owner waits for ownership of a mutex, and so on).

 * Threads shall wait in priority order.  The highest priority thread shall
 be dequeued first.

 * The highest priority waiting thread shall wait in FIFO order.

 * The mutex shall provide an acquire operation with timeout.

 * In case a mutex is released, then the previous owner shall no longer use
 the priorities inherited by this mutex.

 * In case a mutex acquire operation timeout occurs, then the current owner
 of the mutex shall no longer use the priorities inherited by the acquiring
 thread.

 * The order of the mutex release operations may differ from the order of
 the mutex acquire operations.

 * Priority changes not originating due to the priority inheritance
 protocol shall take place immediately.

 = Performance requirements

 * The mutex acquire operation shall use only object-specific locks in case
 the mutex is not owned currently.

 * The mutex release operation shall use only object-specific locks in case
 no threads wait for ownership of this mutex.

 = Invariants

 * A mutex shall be owned by at most one thread.

 * A thread shall wait for ownership of at most one mutex.

 = Proposed Implementation

 Use a recursive data structure to determine the highest priority available
 to a thread for each scheduler instance, e.g.

 {{{
 #!c
 typedef struct Thread_Priority_node {
   Chain_Node Node;
   Priority_Control current_priority;
   Priority_Control real_priority;
   struct CORE_mutex_Control *waiting_to_hold;
   Chain_Control Inherited_priorities;
 } Thread_Priority_node;

 typedef struct {
   ...
   Thread_Priority_node Priority_node;
   ...
 } Thread_Control;
 }}}

 Initially a thread has a priority node reflecting its real priority.  The
 Thread_Priority_node::owner is NULL.  The
 Thread_Priority_node::current_priority is set to the real priority.  The
 Thread_Priority_node::Inherited_priorities is empty.

 In case the thread must wait for ownership of a mutex, then it enqueues
 its priority node in Thread_Priority_node::Inherited_priorities of the
 mutex owner.

 In case the thread is dequeued from the wait queue of a mutex, then it
 dequeues its priority node in Thread_Priority_node::Inherited_priorities
 of the previous mutex owner (ownership transfer) or the current mutex
 owner (acquire timeout).

 In case the minimum of Thread_Priority_node::real_priority and
 Thread_Priority_node::Inherited_priorities changes, then
 Thread_Priority_node::current_priority is updated.  In case the
 Thread_Priority_node::owner its not NULL, the priority change propagates
 to the owner, and so on.  In case Thread_Priority_node::current_priority
 changes, the scheduler is notified.

--

--
Ticket URL: <http://devel.rtems.org/ticket/3359#comment:1>
RTEMS Project <http://www.rtems.org/>
RTEMS Project