#2412 closed enhancement (fixed)

Improved priority inheritance implementation

Reported by: Sebastian Huber Owned by: Sebastian Huber
Priority: high Milestone: 5.1
Component: score Version:
Severity: normal Keywords:
Cc: Blocked By:
Blocking:

Description (last modified by Sebastian Huber)

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. On SMP configurations OMIP shall be used.
  • 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 from one scheduler instance shall wait in priority order. The highest priority thread shall be dequeued first.
  • The highest priority waiting thread of each scheduler instance 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.
  • Deadlock shall be detected. In case a deadlock would occur an error status shall be returned or a fatal error shall be generated.
  • Deadlocks at application level shall not lead to a deadlock at operating system level.

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.

Possible implementation

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

typedef struct Thread_Priority_node {
  Priority_Control current_priority;
  Priority_Control real_priority;
  struct Thread_Priority_node *owner;
  RBTree_Node Node;
  RBTree_Control Inherited_priorities;
} Thread_Priority_node;

typedef struct {
  ...
  Thread_Priority_node *priority_nodes; /* One per scheduler instances */
  ...
} 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 corresponding scheduler is notified.

The biggest issue is the locking on SMP configurations in case of recursive minimum updates.

Somehow we must connect this to the scheduler helping protocol for OMIP. We may have to replace the return value based scheduler operations with a pre-context-switch action. Due to some recent implementation changes the run-time of the _Thread_Dispatch() function is no longer average-case performance critical.

Change History (14)

comment:1 Changed on Sep 7, 2015 at 6:01:03 AM by Sebastian Huber

Description: modified (diff)

comment:2 Changed on Jul 5, 2016 at 7:53:12 AM by Sebastian Huber

Owner: set to Sebastian Huber
Status: newassigned

comment:3 Changed on Jul 5, 2016 at 7:53:28 AM by Sebastian Huber

Component: Generalcpukit

comment:4 Changed on Jul 5, 2016 at 7:53:37 AM by Sebastian Huber

Type: defectenhancement

comment:5 Changed on Jul 27, 2016 at 8:56:15 AM by Sebastian Huber <sebastian.huber@…>

In f4d1f307926b6319e5d3b325dbe424901285dec1/rtems:

score: Split _Thread_Change_priority()

Update #2412.
Update #2556.
Update #2765.

comment:6 Changed on Jul 27, 2016 at 8:56:26 AM by Sebastian Huber <sebastian.huber@…>

In ac8402ddd6e4a8eb6defb98220d39d4c20a6f025/rtems:

score: Simplify _Thread_queue_Boost_priority()

Raise the priority under thread queue lock protection and omit the
superfluous thread queue priority change, since the thread is extracted
anyway. The unblock operation will pick up the new priority.

Update #2412.
Update #2556.
Update #2765.

comment:7 Changed on Jul 27, 2016 at 8:56:36 AM by Sebastian Huber <sebastian.huber@…>

In 3a58dc863157bb21054a144c1a21b690544c0d23/rtems:

score: Priority inherit thread queue operations

Move the priority change due to priority interitance to the thread queue
enqueue operation to simplify the locking on SMP configurations.

Update #2412.
Update #2556.
Update #2765.

comment:8 Changed on Jul 27, 2016 at 8:56:46 AM by Sebastian Huber <sebastian.huber@…>

In 1fcac5adc5ed38fb88ce4c6d24b2ca2e27e3cd10/rtems:

score: Turn thread lock into thread wait lock

The _Thread_Lock_acquire() function had a potentially infinite run-time
due to the lack of fairness at atomic operations level.

Update #2412.
Update #2556.
Update #2765.

comment:9 Changed on Jul 27, 2016 at 8:56:57 AM by Sebastian Huber <sebastian.huber@…>

In d79df38c2bea50112214ade95776cb90d693e390/rtems:

score: Add deadlock detection

The mutex objects use the owner field of the thread queues for the mutex
owner. Use this and add a deadlock detection to
_Thread_queue_Enqueue_critical() for thread queues with an owner.

Update #2412.
Update #2556.
Close #2765.

comment:10 Changed on Sep 21, 2016 at 7:05:43 AM by Sebastian Huber <sebastian.huber@…>

In 300f6a481aaf9e6d29811faca71bf7104a01492c/rtems:

score: Rework thread priority management

Add priority nodes which contribute to the overall thread priority.

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.

A thread changes its priority now immediately, e.g. priority changes are
not deferred until the thread releases its last resource.

Replace the _Thread_Change_priority() function with

  • _Thread_Priority_perform_actions(),
  • _Thread_Priority_add(),
  • _Thread_Priority_remove(),
  • _Thread_Priority_change(), and
  • _Thread_Priority_update().

Update #2412.
Update #2556.

comment:11 Changed on Dec 23, 2016 at 2:11:26 PM by Sebastian Huber

Priority: normalhigh

comment:12 Changed on Feb 1, 2017 at 6:59:27 AM by Sebastian Huber

Resolution: fixed
Status: assignedclosed
Version: 4.5

comment:13 Changed on May 11, 2017 at 7:31:02 AM by Sebastian Huber

Milestone: 4.124.12.0

comment:14 Changed on Nov 9, 2017 at 6:27:14 AM by Sebastian Huber

Milestone: 4.12.05.1

Milestone renamed

Note: See TracTickets for help on using tickets.