Real-Time Systems, RTOS Scheduling & WCET Questions

Approach (brief)
Use a power-of-two sized circular buffer with 32-bit head/tail indices (volatile). Producers in ISR update head only after writing the byte (write barrier) and notify the consumer using an RTOS from-ISR notify (semaphore/notify handle stored in struct). Consumer runs in task context and blocks on the RTOS primitive when buffer empty. Single-core Cortex-M + 32-bit atomic index read/writes make this lock-free and safe without disabling interrupts.

Struct and implementation:

#include <stdint.h>
#include <stdbool.h>
#include "FreeRTOS.h"
#include "semphr.h"

typedef struct {
    uint8_t *buf;               // buffer memory (size = 2^power)
    uint32_t mask;              // size - 1
    volatile uint32_t head;     // next write index
    volatile uint32_t tail;     // next read index
    SemaphoreHandle_t notify;   // created statically by caller; used for consumer wake
} ringbuf_t;

/* ISR-safe push: returns true if pushed; must be called from ISR context.
   Does not block. Calls xSemaphoreGiveFromISR if notify != NULL. */
bool rb_push_from_isr(ringbuf_t *rb, uint8_t b)
{
    uint32_t head = rb->head;
    uint32_t next = (head + 1) & rb->mask;
    uint32_t tail = rb->tail; /* atomic 32-bit read */

    if (next == tail) {
        return false; /* full */
    }

    rb->buf[head] = b;

    /* compiler/CPU barrier to ensure byte is visible before index update */
    __asm volatile ("" ::: "memory");

    rb->head = next; /* publish new data */

    if (rb->notify) {
        BaseType_t xHigherPriorityTaskWoken = pdFALSE;
        xSemaphoreGiveFromISR(rb->notify, &xHigherPriorityTaskWoken);
        portYIELD_FROM_ISR(xHigherPriorityTaskWoken);
    }

    return true;
}

/* Blocking pop: waits up to timeout ticks. Returns true and writes *b on success. */
bool rb_pop_blocking(ringbuf_t *rb, uint8_t *b, TickType_t timeout)
{
    for (;;) {
        uint32_t tail = rb->tail;
        uint32_t head = rb->head; /* atomic read */

        if (tail != head) {
            *b = rb->buf[tail];

            __asm volatile ("" ::: "memory");

            rb->tail = (tail + 1) & rb->mask;
            return true;
        }

        /* empty: wait for notify or timeout */
        if (rb->notify == NULL) {
            /* no notify available: poll with yield */
            if (timeout == 0) return false;
            vTaskDelay(1);
            if (timeout != portMAX_DELAY) timeout--;
        } else {
            if (xSemaphoreTake(rb->notify, timeout) != pdPASS) return false;
            /* loop to consume any available bytes */
            timeout = 0; /* after wake, don't wait further */
        }
    }
}

Why this is safe

• Single-core Cortex-M + 32-bit aligned index reads/writes are atomic: head/tail updates won't tear.
• Producer (ISR) writes data first, issues a compiler barrier, then updates head — consumer will never read uninitialized byte.
• Consumer reads head before reading buffer and advances tail after reading — avoids races.
• No blocking or RTOS API calls in the ISR other than FromISR variants.
• notify semaphore lets consumer block efficiently; buffer size must be power-of-two and allocated by caller (no dynamic alloc inside).

Overview — goal
Model the embedded scheduler and tasks as timed-automata in UPPAAL to prove: "no deadline is ever missed" (safety property). Use explicit task templates plus a scheduler and an observer. Verify A[] not Missed.

What to model vs. abstract

• Model precisely: task arrival pattern (periodic/sporadic), worst-case execution time (WCET), deadlines, priorities, shared resource locks behavior, preemption points.
• Abstract: internal computation details (represent execution as time delays up to WCET), complex ISR code (model as short high-priority tasks or preemption events), non-functional jitter unless it affects deadlines.

Concrete templates

• Task template: states Idle → Ready → Running → Done. Clock c measures execution; transitions:
  • on release: c := 0, move to Ready
  • start running: record start, use invariant c <= WCET
  • complete when c >= WCET, signal Done and reset
• Scheduler template: single global scheduler that selects highest-priority Ready task; implement preemption by urgent channels and resetting/pausing task clocks. Priority array priority[id]; selection uses integer comparisons.
• Resource locks: model as binary semaphore (owner ID or -1). Lock acquisition is guarded; if unavailable, task waits in Waiting state. Use non-blocking semantics or model priority inheritance explicitly if needed.
• Interrupts: model as very-short, high-priority tasks that can preempt; or model preemption by an interrupt channel that forces current task to move to Preempted.

Timing & priorities

• Use clocks per task (c[id]) and a deadline clock (d[id]) reset at release. Deadline violation location is reachable when d[id] > deadline and task not completed.
• Priorities: integer values; scheduler enforces choose max(priority) among Ready and Interrupts > task priority.
• Use committed/urgent locations for atomic scheduling decisions and context-switch modeling.

Verifying property

• Add observer automaton that enters Missed if any d[id] > D[id] && not Done. Verify A[] not Observer.Missed.

Manage state-space explosion

• Reduce integer bounds (tight WCET, small ranges for counters).
• Use symmetry: parametric arrays and identical-task templates instead of separate models.
• Abstract execution: model execution as two-phase (running vs. non-running) rather than per-instruction.
• Use committed locations and urgent channels to avoid interleavings for atomic scheduler actions.
• Apply assume-guarantee / compositional checks: verify a subset (task + scheduler) then compose.
• Use reduction: disable irrelevant features (e.g., skip priority inheritance initially), iterate refinement.
• Parameter sweep: check representative worst-case phasing (critical instant) from scheduling theory to avoid full state-space when applicable.

Practical tips for embedded context

• Use measured WCETs from target platform; model timer tick granularity matching hardware timer.
• Validate model with small counterexamples on real firmware traces.
• Start with a minimal model (2–3 tasks) and scale using abstractions.

Clarify goals & constraints

• Four ARM cores on an automotive ECU must run multiple hard RT control loops (1 ms and 5 ms), logging/diagnostics concurrently, and occasional non‑critical ML inference. Safety-critical control loops require deterministic timing and certification (ISO 26262). Minimize multicore interference and jitter.

Core assignment (practical partitioning)

• Core0: All 1 ms hard real‑time control tasks (highest criticality). No non‑critical services.
• Core1: 5 ms control tasks and time‑bound coordination with Core0.
• Core2: Logging, diagnostics, and communication stacks (lower criticality). I/O buffering lives here.
• Core3: ML inference and maintenance tasks; can be throttled or offline-updated.

Rationale: Dedicated cores for highest-criticality loops reduce interference and ease WCET/response-time analysis.

Scheduling policy

• Use partitioned fixed-priority preemptive scheduling (FPPS) per core for determinism; assign priorities by rate (RMS) for control tasks. For inter-core coordination, use explicit message passing (lock-free ring buffers) rather than global locks.
• On Core2/Core3 allow time-partitioning (slotted or background with bandwidth enforcement) so ML/logging cannot starve I/O.
• Consider an ARINC-653–style temporal partition or a separation kernel if mixed-criticality certification is required.

Shared bus & memory bandwidth management

• Enforce hardware QoS where available: DDR controller bandwidth reservation, AXI QoS, or IOMMU priorities to cap non‑critical masters (DMA, ML accelerator).
• Use cache partitioning (Intel CAT equivalent if supported) or page coloring to reduce cache contention between Core0/Core1 and others.
• Throttle ML and bulk DMA during critical windows (e.g., during control deadlines) using bandwidth regulators or periodic budget tokens.
• Monitor runtime with PMU/trace to tune reservations; instrument worst-case interference during integration testing.

Interrupt routing & ISR handling

• Route sensor and actuator interrupts for 1 ms loop to Core0 via GIC affinity; route less critical interrupts to Core2.
• Keep ISRs short: only acknowledge/handoff to a deferred handler (thread) that runs at the task’s priority on its assigned core.
• Use edge/level semantics consistently; use MSI/MSI‑X where available to assign interrupts to cores directly.
• Protect against interrupt storms by rate-limiting non-critical IRQs on Core2/Core3.

Inter-core communication

• Use lock-free SPSC/MPSC ring buffers, RCU-style read-side paths for control data; avoid global spinlocks for critical paths.
• Use time-stamped messages and deadlines; prefer explicit synchronization points to simplify WCET analysis.

Certification & verification considerations

• Aim for single-core equivalence per critical partition: with dedicated cores, you can perform per-core WCET and response-time analysis (RTA). Document and bound all interference channels (bus, cache, interrupts).
• Follow ISO 26262: ASIL decomposition, traceability, requirement-driven testing. Use static analysis (MISRA, toolchain qualification), unit/Integration tests, HIL with stress scenarios (max bus contention).
• If high-assurance needed, use a separation kernel or certified RTOS supporting partitioning and determinism (e.g., AUTOSAR OS Classic/Safe profiles or commercial safety RTOS).
• Provide artifacts: timing analysis reports, worst-case interference bounds, justification for QoS settings, failure modes and diagnostics, watchdog strategies, and regression tests.

Trade-offs

• Full isolation via virtualization/separation kernel increases certification ease but adds SW complexity and overhead.
• Static core partitioning is simpler and more certifiable; dynamic load balancing gains utilization but complicates WCET and certification.

This approach prioritizes determinism for 1 ms/5 ms loops, confines interference, uses hardware QoS and software throttles for non‑critical workloads, and provides traceable artifacts required for automotive safety certification.

Brief answer / summary
Fixed-priority preemptive (FP) and dynamic-priority EDF are two common single-core RT scheduling approaches. FP assigns static priorities (e.g., Rate Monotonic), EDF orders ready jobs by earliest absolute deadline. They differ in overload behavior, implementation effort, aperiodic support, and suitability for hard real-time.

Schedulability and overload

• FP: Simple utilization bounds (e.g., RM: n(2^{1/n}-1)) and exact analysis via response-time analysis. Under overload FP favors high-priority tasks; low-priority ones may starve—predictable but asymmetric.
• EDF: Optimal for preemptive uniprocessor periodic task sets (if total utilization ≤100% schedulable). Under overload EDF degrades more gracefully in fairness (misses spread across tasks) but can cause many simultaneous deadline misses—harder to bound which task misses.

Implementation complexity

• FP: Low complexity — fixed priorities, simple ready queues (bitmaps or priority arrays), minimal runtime overhead (suitable for tiny MCUs).
• EDF: Higher runtime cost — priority changes per job, requires efficient deadline-ordered queue (heap or ordered list). On constrained devices you may need optimized data structures or limited EDF variants.

Support for aperiodic tasks

• FP: Use servers (sporadic/deferrable/background) to handle aperiodics; configuration and analysis required to avoid interference.
• EDF: Natural fit for mixed workloads; Earliest-deadline-first servers (Sporadic Server) integrate well and preserve schedulability more directly.

Suitability for hard real-time

• FP: Very predictable; response-time analysis gives firm guarantees per task — preferred when certification or simple analyzability is needed.
• EDF: Superior CPU utilization and optimality, but harder to provide per-task worst-case guarantees under overload and implementation constraints. Use EDF when utilization is tight and system can afford complexity and robust overload policies.

Practical recommendation
On resource-constrained embedded targets or safety-critical apps with cert requirements pick FP (RM/DM). Use EDF when you need maximum CPU efficiency and can implement efficient data structures and clear overload handling (or when many aperiodic jobs exist).

Rules for ISR interaction with an RTOS kernel

• Keep ISRs short and deterministic.
• Never call blocking kernel APIs from an ISR (no mutexes, semphr take with wait).
• Use only RTOS APIs explicitly safe for ISR context (e.g., xSemaphoreGiveFromISR).
• Avoid dynamic heap allocation/free inside ISRs.
• Don’t perform long-running computation, I/O, or blocking polling.
• Minimize stack use and avoid printf/logging unless ISR-safe.

Why certain actions are problematic

• Blocking calls: ISRs run at interrupt priority and cannot block; blocking can deadlock scheduler or violate priority rules.
• Heap allocation: malloc/free may lock heap structures or use blocking primitives — risk of corruption and non-determinism.
• Long computation: extends interrupt latency, delaying other interrupts and breaking real-time guarantees.

Safe deferred-work patterns

1. Deferred queue (producer in ISR, consumer task)

• ISR: push message to ring buffer / lock-free queue; signal task.
• Task: processes items at normal priority.
  Example:

// ISR
BaseType_t xHigherPriorityTaskWoken = pdFALSE;
xQueueSendFromISR(qHandle, &item, &xHigherPriorityTaskWoken);
portYIELD_FROM_ISR(xHigherPriorityTaskWoken);

2. Task notification (fast direct-to-task signaling)

• ISR uses direct notification to wake a specific task and optionally pass a small value.
  Example:

vTaskNotifyGiveFromISR(taskHandle, &xHigherPriorityTaskWoken);
portYIELD_FROM_ISR(xHigherPriorityTaskWoken);

3. Software timer

• ISR arms/starts a one-shot timer or sets a flag; timer callback or task handles heavy work.
  Example:

xTimerStartFromISR(timerHandle, &xHigherPriorityTaskWoken);

Use these patterns to transfer work to thread context where blocking, malloc, and long processing are safe and schedulable.