Modern Concurrency & RTOS

RTOS Concepts & Synchronization

The goal of an RTOS is to provide predictable timing and responsiveness. Your knowledge must focus on how concurrency mechanisms support this.

Concept	Explanation	Embedded Relevance
Concurrency	The system deals with many things at once through time-slicing (context switching). It is an illusion of simultaneous execution.	Common in single-core RTOS systems where multiple tasks share one CPU. Main challenge: managing shared data access.
Parallelism	The system does many things at the same time using multiple independent processing units (cores).	Essential in modern multi-core SoCs (e.g., AMD/ARM). Main challenge: cache coherency and synchronization across cores.

Task/Thread Synchronization

Synchronization primitives are essential tools for enforcing Mutual Exclusion (only one task accessing a shared resource) and Inter-Task Communication (ITC).

• Mutex (Mutual Exclusion): Used to protect Critical Sections of code or shared data structures (e.g., a linked list or a hardware register). A task must lock the mutex before entering the critical section and unlock it immediately after.
• Semaphore (Signaling & Counting):
  • Binary Semaphore: Functions like a simple lock (only two states: taken/free) but is often used for signaling between tasks (e.g., an ISR signals a task that data is ready).
  • Counting Semaphore: Used to manage a pool of resources (e.g., a buffer with 5 slots). The count indicates the number of available resources. Tasks wait if the count is zero.
• Condition Variables: Used with a mutex to allow a thread to wait (sleep) until a specific condition becomes true, without continuously polling (wasting CPU cycles). Example: A consumer thread waits on a condition variable until a producer thread adds data to a queue.

Priority Inversion & Mitigation (Crucial RTOS Topic)

Priority Inversion is a classic scheduling failure that violates the core principle of an RTOS: that a high-priority task should always run ahead of lower-priority tasks.

• Definition: A high-priority task ($\text{Task H}$) becomes blocked and waits indefinitely, not by another high-priority task, but by a low-priority task ($\text{Task L}$) which holds a required shared resource (a mutex). A medium-priority task ($\text{Task M}$) then preempts and runs, effectively blocking $\text{Task H}$ through no fault of its own.

  • The priority order is effectively inversed ($\text{L} \rightarrow \text{M} \rightarrow \text{H}$ instead of $\text{H} \rightarrow \text{M} \rightarrow \text{L}$).

• Consequences:

  • In some cases, priority inversion can occur without causing immediate harm—the delayed execution of the high-priority task goes unnoticed, and eventually, the low-priority task releases the shared resource
  • If the high-priority task is left starved of the resources, it might lead to a system malfunction or the triggering of pre-defined corrective measures, such as a watchdog timer resetting the entire system.
  • Because priority inversion results in the execution of a lower-priority task blocking the high-priority task, it can lead to reduced system responsiveness or even the violation of response time guarantees.

• Mitigation Protocols: These protocols temporarily elevate task priority to prevent the inversion:

  • Disabling all interrupts to protect critical sections: Disabling all interrupts creates only two execution levels—preemptible and non-preemptible—so priority inversion, deadlocks, and hangs cannot occur, as critical sections always run to completion.

    • Early UNIX used splx() levels to disable interrupts up to a chosen priority, avoiding full interrupt lockout.
    • On multicore systems, a single shared busy-wait flag is used to lock inter-processor critical sections, effective mainly in simple embedded systems where shared resources are minimal.

  • Priority Inheritance Protocol (PIP): When $\text{Task L}$ blocks $\text{Task H}$, $\text{Task L}$ temporarily inherits the priority of $\text{Task H}$. As soon as $\text{Task L}$ releases the resource, its priority reverts to its original level. This prevents $\text{Task M}$ from preempting $\text{Task L}$.

  • Priority Ceiling Protocol (PCP): The shared resource itself is assigned a ceiling priority (equal to the highest priority of any task that might ever use it). When a task locks the resource, its running priority is immediately raised to this ceiling. This prevents the blocking condition from occurring in the first place.

    • This works well, provided the other high-priority task(s) that try to access the mutex do not have a priority higher than the ceiling priority.

  • Random boosting: Ready tasks holding locks are randomly boosted in priority until they exit the critical section. This solution was used in Microsoft Windows[4] until it was replaced by AutoBoost a form of priority inheritance.[5]

  • Avoid Blocking: Because priority inversion involves a low-priority task blocking a high-priority task, one way to avoid priority inversion is to avoid blocking, for example by using non-blocking algorithms such as read-copy-update.