Real-Time Operating Systems (RTOS)

A Real-Time Operating System (RTOS) fundamentally differs from a general-purpose operating system (GPOS) in its primary design objective. While a GPOS (such as Linux or Windows) is optimized to maximize overall system throughput and ensure fairness among competing processes, an RTOS is engineered to guarantee determinism and strict adherence to timing constraints.

In real-time environments, calculating the correct logical result is only half the requirement; the result must be produced within a specific, absolute timeframe. A logically correct answer delivered late constitutes a critical system failure.

Hard vs. Soft Real-Time Constraints

Real-time systems are categorized by the severity of the consequences when a execution deadline is missed:

1. Hard Real-Time Systems: Missing a single deadline results in catastrophic failure, physical damage, or loss of life. These systems must guarantee that deadlines are met in all execution scenarios.
2. Firm Real-Time Systems: Missing a deadline renders the computed result useless, but does not cause localized safety failures.
3. Soft Real-Time Systems: Missing a deadline degrades the quality of service, but the system continues to operate, and late results still retain partial value.

The following code snippets illustrate the structural difference between handling a hard real-time safety critical check and a soft real-time data buffer:

/* Example of Hard Real-Time Constraint: Pacemaker Pulse Monitoring */
void monitor_cardiac_state(void) {
    uint32_t start_tick = get_system_ticks();

    if (detect_arrhythmia()) {
        trigger_ventricular_stimulus();

        /* Hard deadline: Stimulus delivery must complete in under 2ms */
        uint32_t duration = get_system_ticks() - start_tick;
        if (duration > MS_TO_TICKS(2)) {
            /* Catastrophic deadline miss: activate hardware fail-safe */
            activate_backup_hardware_pacemaker();
        }
    }
}

/* Example of Soft Real-Time Constraint: Frame Decoding for VoIP / Video */
void render_video_frame(Frame* frame) {
    if (get_buffer_fill_level() > MAX_BUFFER_LIMIT) {
        /* Drop frame: degrades playback quality slightly, but the app continues */
        drop_frame(frame);
        return;
    }
    decode_and_draw_to_screen(frame);
}

Deterministic Scheduling

To achieve timing guarantees, an RTOS employs scheduling algorithms that prioritize predictability over throughput. GPOS schedulers dynamically adjust process priorities to prevent starvation, but RTOS schedulers execute tasks according to strict, predictable rules.

1. Strict Priority-Based Preemptive Scheduling: Tasks are assigned static priorities based on design-time constraints. The scheduler guarantees that the ready task with the highest priority is always allocated the CPU.
2. Rate Monotonic Scheduling (RMS): A mathematical priority assignment algorithm where tasks with shorter cycle periods (higher frequency) are assigned higher static priorities.

The following C program demonstrates a typical periodic task definition in a real-time kernel (such as FreeRTOS) utilizing strict priority-based scheduling:

#include "FreeRTOS.h"
#include "task.h"

/* Deterministic sensor task running at 50 Hz (every 20 ms) */
void vSensorTask(void *pvParameters) {
    TickType_t xLastWakeTime;
    const TickType_t xPeriod = pdMS_TO_TICKS(20);

    /* Initialize wake time with current system tick */
    xLastWakeTime = xTaskGetTickCount();

    for (;;) {
        /* Suspend task until exactly 20ms has elapsed since xLastWakeTime */
        vTaskDelayUntil(&xLastWakeTime, xPeriod);

        /* Perform physical sensor read and process telemetry */
        poll_gyroscope_data();
    }
}

int main(void) {
    /* Initialize task with high priority (5) */
    xTaskCreate(vSensorTask, "GyroTask", 2048, NULL, 5, NULL);
    
    /* Start the preemptive real-time scheduler */
    vTaskStartScheduler();
    return 0;
}

The Priority Inversion Problem

Deterministic priority-based scheduling introduces a vulnerability known as priority inversion. This occurs when a high-priority task is blocked from executing while a lower-priority task runs.

Consider a scenario with three tasks: High priority ($T_H$), Medium priority ($T_M$), and Low priority ($T_L$).

1. $T_L$ executes and acquires a lock (mutex) on a shared memory bus.
2. $T_H$ awakes, preempts $T_L$, and attempts to acquire the same shared memory bus.
3. Since the resource is locked, $T_H$ blocks, allowing $T_L$ to resume running so it can release the lock.
4. Before $T_L$ can finish, $T_M$ (a long CPU-bound task that does not need the shared bus) awakes. Since $T_M$ has higher priority than $T_L$, the scheduler preempts $T_L$ and runs $T_M$.
5. As a result, $T_H$ is blocked waiting for $T_L$, which cannot run because it is preempted by $T_M$.

$T_H$ (the most critical task) is now indirectly blocked by $T_M$, subverting the priority hierarchy.

Priority Inheritance

To resolve priority inversion, kernels implement Priority Inheritance. When a high-priority task ($T_H$) blocks on a resource held by a low-priority task ($T_L$), the kernel temporarily elevates the priority of $T_L$ to match the priority of $T_H$. This prevents medium-priority tasks ($T_M$) from preempting $T_L$. Once $T_L$ releases the resource, its priority returns to its original base level, allowing $T_H$ to run immediately.

Exercise: Applying RM Scheduling

Analyze the application of Rate Monotonic Scheduling in the system scenario below:

References & Further Reading

For detailed design specifications and examples of scheduling and real-time kernels, refer to the following sources:

• Buttazzo, G. C. (2011). Hard Real-Time Computing Systems: Predictable Scheduling Algorithms and Applications (3rd ed.). Springer. (Detailing Rate Monotonic and Earliest Deadline First scheduling).
• Liu, J. W. (2000). Real-Time Systems. Prentice Hall. (Covering formal scheduling proofs and priority inversion remedies).
• FreeRTOS Developer Documentation: Task Co-routines and Scheduling. Real Time Engineers Ltd.
• NASA Pathfinder Priority Inversion Report. National Aeronautics and Space Administration (documenting the 1997 Mars Pathfinder priority inversion incident and VxWorks patch).