Week 7 - Real-Time Scheduling Algorithms

Upon the successful completion of this module, learners will gain a
comprehensive and practical understanding of the fundamental principles, taxonomies, and
critical algorithms employed in real-time scheduling for embedded systems.

This section lays the groundwork by defining what makes a system "real-time" and
introducing the essential terminology and goals of real-time scheduling.

A real-time system is characterized by the requirement that its correctness depends
not only on the logical result of its computation but also on the time at which the
result is produced. The system must respond to events or perform actions within
specified, strict time constraints, known as deadlines. Failure to meet a deadline can
range from a minor inconvenience to a catastrophic failure, depending on the system
type.

Real-time systems are typically classified into three main categories based on the
criticality of their deadlines:

• Hard Real-Time Systems:
• Definition: Missing a deadline is absolutely unacceptable and constitutes a
  system failure, potentially leading to catastrophic consequences (e.g., loss of life, severe environmental damage, massive financial loss).
• Characteristics: Requires strict deterministic behavior. Schedulability
  must be mathematically proven offline. Jitter (variation in task completion time) must be minimized.
• Examples: Flight control systems, medical life-support equipment, automotive engine control, nuclear power plant control, industrial robotics.
• Firm Real-Time Systems:
• Definition: Missing a deadline is undesirable, leading to a degradation in quality of service or performance, but does not result in total system failure. The results of computations delivered after their deadlines may have no value.
• Characteristics: Tolerates occasional deadline misses, but frequent misses are not acceptable.
• Examples: Network routers, multimedia streaming, video conferencing, online gaming.
• Soft Real-Time Systems:
• Definition: Missing a deadline is undesirable but tolerable, causing a degraded but still acceptable performance. The value of a computation decreases after its deadline but may still be useful.
• Characteristics: Prioritizes average performance or throughput over strict determinism.
• Examples: Web browsers, ATM transactions, general-purpose operating systems with multimedia extensions.

To understand scheduling, several key terms are essential:

• Task (or Job): A unit of work that needs to be executed by the processor. In
  real-time systems, an application is often broken down into multiple tasks.
• Release Time (r): The instant in time when a task becomes ready for
  execution. For periodic tasks, this is its arrival time.
• Execution Time (C): The maximum amount of processor time required to
  complete a task's computation without interruption. This is often the
  Worst-Case Execution Time (WCET).
• Deadline (D): The time by which a task must complete its execution.
• Absolute Deadline: The actual calendar time by which a task must
  finish (e.g., "finish by 10:30:00 AM").
• Relative Deadline: The time interval from the task's release time to its
  absolute deadline (e.g., "finish within 100 milliseconds of being
  released").
• Period (T): For periodic tasks, the fixed time interval between consecutive
  releases of the same task.
• Response Time (R): The time elapsed from a task's release time to its
  completion time. For a task to be schedulable, its response time must be less
  than or equal to its deadline (R≤D).
• Latency: The delay between an event and the system's response to that
  event.
• Jitter: The variation in the completion time or response time of a periodic
  task. Minimizing jitter is crucial for many control applications.
• Preemption: The ability of a higher-priority task to interrupt a lower-priority
  task that is currently executing, take control of the processor, and execute
  itself. When the higher-priority task finishes or blocks, the interrupted task can
  resume from where it left off. Most real-time systems rely on preemption for
  responsiveness.
• Context Switching: The process of saving the current state (CPU registers,
  program counter, stack pointer, etc.) of a running task and loading the state of
  a new task when the scheduler decides to switch execution from one task to
  another. This incurs an overhead in terms of CPU cycles.

The primary goals of any real-time scheduling algorithm are:

• Schedulability: The most critical goal. To guarantee that all tasks will meet
  their deadlines under all specified operating conditions. This is often proven
  through a schedulability analysis.
• Resource Utilization: Efficiently using the available processor (CPU) and
  other system resources without causing deadline misses. Aiming for high
  utilization while maintaining schedulability is often desired.
• Predictability: Ensuring that task execution times and response times are
  consistent and within expected bounds, minimizing jitter and unexpected
  delays.
• Fairness (Secondary): While important in general-purpose systems, fairness
  is often secondary to schedulability in real-time systems. Higher-priority tasks
  will inherently get more CPU time.

Real-time tasks exhibit different patterns of arrival and execution. Understanding
these models is fundamental to applying the correct scheduling algorithms and analysis
techniques.

• Periodic Tasks
• Definition: Tasks that are released at regular, fixed time intervals. They are
  the most common and well-understood task model in real-time systems.
• Parameters: Each periodic task i is characterized by:
  • Ci : Worst-Case Execution Time (WCET).
  • Ti : Period (the interval between successive releases).
  • Di : Relative Deadline (usually, Di ≤Ti , often Di =Ti or Di

Scheduling algorithms can be broadly categorized based on several key characteristics,
defining their operational philosophy.

• Static (Offline) vs. Dynamic (Online) Scheduling:
• Static (Offline) Scheduling:
  • Concept: The entire schedule for all tasks is computed and fixed beforehand,
    at design time, based on prior knowledge of all task parameters (periods, execution times, deadlines). The schedule is often stored in a table (e.g., a time table) and executed by a simple dispatcher at runtime.
  • Advantages: Low runtime overhead, high predictability; suitable for very simple or resource-constrained systems, guarantees schedulability if the pre-computed schedule is valid.
  • Disadvantages: Inflexible to changes in the environment or task parameters. Cannot easily handle aperiodic events without specific mechanisms. Requires complete knowledge of all tasks upfront.
  • Example: Clock-driven scheduling systems often use a static approach.
• Dynamic (Online) Scheduling:
  • Concept: The scheduling decisions (which task to run next) are made at runtime, based on the current state of the system and the ready tasks. Priorities might change dynamically based on certain task properties.
  • Advantages: Flexible, can adapt to changing workloads, handles aperiodic events more naturally.
  • Disadvantages: Higher runtime overhead (due to priority recalculations, context switching), can be harder to predict worst-case behavior.
  • Example: Earliest Deadline First (EDF), Least Laxity First (LLF).
• Clock-Driven vs. Event-Driven Scheduling:
• Clock-Driven (Time-Triggered) Scheduling:
  • Concept: Scheduling decisions are made at predefined time instants, usually dictated by a global timer (a "clock tick"). Tasks are typically periodic, and their execution times are synchronized with these ticks.
  • Characteristics: Static scheduling. High predictability. All task parameters must be known.
  • Example: Often used in safety-critical systems like avionics.
• Event-Driven Scheduling:
  • Concept: Scheduling decisions are made only when specific events occur in the system. These events can be task releases, task completions, or external interrupts. The scheduler is invoked in response to these events.
  • Characteristics: Dynamic scheduling. More responsive to unpredictable events.
  • Example: Rate Monotonic (RM), Earliest Deadline First (EDF).
• Preemptive vs. Non-preemptive Scheduling:
• Preemptive Scheduling:
  • Concept: A currently executing task can be interrupted (pre-empted) by a higher-priority task that becomes ready. The interrupted task's state is saved, and it can resume later from where it left off.
  • Advantages: Ensures that higher-priority tasks meet their deadlines quickly, leading to better responsiveness. Most modern RTOS kernels support preemption.
  • Disadvantages: Introduces context switching overhead. Requires careful management of shared resources to avoid priority inversion.
• Non-preemptive Scheduling:
  • Concept: Once a task begins execution, it runs to completion without interruption, even if a higher-priority task becomes ready.
  • Advantages: Simpler to implement, no context switching overhead once a task starts, simplifies resource sharing (no critical sections are truly interrupted).
  • Disadvantages: High-priority tasks might suffer significant delays waiting for lower-priority tasks to finish, making it unsuitable for systems with tight deadlines or frequent high-priority events. Leads to lower overall responsiveness.

In fixed-priority scheduling, each task is assigned a priority that remains constant throughout
its execution. The scheduler always chooses the highest-priority ready task to run.

• Rate Monotonic (RM) Scheduling:
• Principle: Tasks are assigned priorities inversely proportional to their periods.
  That is, tasks with shorter periods (higher rates) are assigned higher
  priorities.
  • Example: If Task A has a period of 50ms and Task B has a period of
    100ms, Task A will be assigned a higher priority than Task B.
• Properties:
  • Optimality: Rate Monotonic is optimal among all fixed-priority
    preemptive scheduling algorithms. This means that if a set of periodic
    tasks can be scheduled by any fixed-priority preemptive algorithm, then it can also be scheduled by Rate Monotonic scheduling. If RM cannot schedule the task set, no other fixed-priority preemptive algorithm can.
  • Static Priorities: Priorities are assigned offline and do not change during
    runtime.
  • Preemptive: A higher-priority task can interrupt a lower-priority task.
• Challenges and Limitations of Rate Monotonic:
• Sub-optimal for Non-Preemptive: RM's optimality applies only to
  preemptive scheduling.
• Priority Inversion: A major challenge when tasks share resources. If
  a high-priority task needs a resource currently held by a lower-priority
  task, the high-priority task might get blocked, leading to priority inversion.
• Aperiodic Task Handling: RM is primarily designed for periodic tasks.
  Handling aperiodic tasks efficiently within an RM framework requires
  special techniques like servers (e.g., Polling Server, Sporadic Server, Deferrable Server, discussed in Section 7.5).