Mutex Gate with priority inheritance.
GateMutexPri is a mutex gate (it can only be held by one thread at a time) which implements priority inheritance in order to prevent priority inversion. Priority inversion occurs when a high priority task has its priority effectively 'inverted' because it is waiting on a gate held by a low priority task.
When multiple tasks wait on this gate, they will receive the gate in order of priority (higher priority tasks will receive the gate first). This is because the queue of tasks waiting on a GateMutexPri is sorted by priority, not FIFO.
Problem: Priority Inversion
The following example demonstrates priority inversion.
A system has three tasks, Low, Med, and High, each with the priority
suggested by its name. Task Low runs first and acquires the gate. Task High
is scheduled and preempts Low. Task High tries to acquire the gate, and
waits on it. Next, task Med is scheduled and preempts task Low. Now task
High must wait for both task Med and task Low to finish before it can
continue. In this situation, task Low has in effect lowered task High's
priority to that of Low.
Solution: Priority Inheritance
To guard against priority inversion, GateMutexPri implements priority
inheritance: when task High tries to acquire a gate that is owned by task
Low, task Low's priority will be temporarily raised to that of High, as
long as High is waiting on the gate. Task High will "donate" its priority
to task Low.
When multiple tasks wait on the gate, the gate owner will receive the
highest priority of any of the tasks waiting on the gate.
Caveats
Priority inheritance is not a complete guard against priority inversion.
Tasks only donate priority on the call to gate, so if a task has its
priority raised while waiting on a gate, that priority will not carry
through to the gate owner.
This can occur in situations involving multiple gates. A system has four
tasks: VeryLow, Low, Med, and High, each with the priority suggested by its
name. Task VeryLow runs first and acquires gate A. Task Low runs next and
acquires gate B, then waits on gate A. Task High runs and waits on gate B.
Task High has donated its priority to task Low, but Low is blocked on
VeryLow, so priority inversion occurs despite the use of the gate.
The solution to this problem is to design around it. If gate A may be
needed by a high-priority, time-critical task, then it should be a design
rule that no task holds this gate for a long time, or blocks while holding
this gate.
Miscellaneous
Calls to enter() may block, so this gate can only be used in the task
context.
GateMutexPri is non-deterministic on calls to gate because it keeps the
queue of waiting tasks sorted by priority.
Calling Context
Function | Hwi | Swi | Task |
Main | Startup |
@link GateMutexPri_Params_init @endlink | Y
| Y | Y | Y | Y
|
@link GateMutexPri_query @endlink | Y
| Y | Y | Y | Y
|
@link GateMutexPri_construct @endlink | Y
| Y | Y | Y | N
|
@link GateMutexPri_create @endlink | N*
| N* | Y | Y | N
|
@link GateMutexPri_delete @endlink | N*
| N* | Y | Y | N
|
@link GateMutexPri_destruct @endlink | Y
| Y | Y | Y | N
|
@link GateMutexPri_enter @endlink | N
| N | Y | Y** | N
|
@link GateMutexPri_leave @endlink | N
| N | Y | Y** | N
|
Definitions: - Hwi: API
is callable from a Hwi thread.
- Swi: API is callable from a
Swi thread.
- Task: API is callable from a Task thread.
- Main: API is callable during any of these phases:
-
In your module startup after this module is started (e.g.
GateMutexPri_Module_startupDone() returns true).
- During
xdc.runtime.Startup.lastFxns.
- During main().
- During
BIOS.startupFxns.
- Startup: API is callable during any
of these phases:
- During xdc.runtime.Startup.firstFxns.
- In your module startup before this module is started (e.g.
GateMutexPri_Module_startupDone() returns false).
- *:
Assuming blocking Heap is used for creation.
- **: Must be
used in enter/leave pairs.
|