Real-time scheduling algorithms are crucial for managing tasks in time-sensitive systems. They ensure critical operations are completed within strict deadlines. This topic covers fixed and dynamic priority scheduling, preemption, and time-triggered approaches.
We'll explore Rate Monotonic Scheduling, Earliest Deadline First, and Deadline Monotonic Scheduling. We'll also dive into preemptive vs non-preemptive scheduling, and time-triggered methods like Cyclic Executive and Time-Triggered Architecture. These concepts are key to understanding real-time system design.
Fixed vs Dynamic Priority Scheduling
Rate Monotonic Scheduling (RMS)
- Assigns fixed priorities to tasks based on their periods
- Tasks with shorter periods are assigned higher priorities
- Assumes tasks are periodic, independent, and have deadlines equal to their periods
- Optimal fixed-priority scheduling algorithm for periodic tasks with deadlines equal to periods
- Guarantees schedulability if the total CPU utilization is less than or equal to a specific bound (Liu and Layland bound)
Earliest Deadline First (EDF) and Deadline Monotonic Scheduling (DMS)
- EDF is a dynamic-priority scheduling algorithm that assigns priorities based on the absolute deadlines of tasks
- Tasks with earlier absolute deadlines are assigned higher priorities
- Optimal dynamic-priority scheduling algorithm for periodic and sporadic tasks
- DMS is a fixed-priority scheduling algorithm that assigns priorities based on the relative deadlines of tasks
- Tasks with shorter relative deadlines are assigned higher priorities
- Optimal fixed-priority scheduling algorithm for periodic tasks with arbitrary deadlines
Fixed-Priority vs Dynamic-Priority Scheduling
- Fixed-priority scheduling assigns priorities to tasks statically before execution (RMS, DMS)
- Dynamic-priority scheduling assigns priorities to tasks dynamically during execution based on their current state (EDF)
- Fixed-priority scheduling is simpler to implement and analyze but may result in lower CPU utilization
- Dynamic-priority scheduling can achieve higher CPU utilization but is more complex to implement and analyze
- The choice between fixed-priority and dynamic-priority scheduling depends on the system requirements, task characteristics, and available resources
Preemption in Scheduling
Preemptive Scheduling
- Allows a higher-priority task to interrupt (preempt) the execution of a lower-priority task
- The preempted task is suspended, and its context is saved
- Enables responsive execution of high-priority tasks and better CPU utilization
- Requires context switching overhead and careful synchronization to avoid race conditions and priority inversion
- Examples: most modern operating systems (Linux, Windows, macOS)
Non-Preemptive Scheduling
- Once a task starts executing, it runs to completion without being interrupted by other tasks
- Simpler to implement and analyze compared to preemptive scheduling
- Avoids context switching overhead and reduces the need for synchronization primitives
- May result in longer response times for high-priority tasks and potential priority inversion
- Suitable for systems with short, deterministic tasks or when preemption is not allowed (e.g., in certain embedded systems)
Time-Triggered Approaches
Cyclic Executive
- A simple, time-triggered approach to real-time scheduling
- Tasks are executed in a fixed, predefined order within a major cycle
- The major cycle is divided into minor cycles, each containing a subset of tasks
- Tasks are scheduled based on their time slots in the minor cycles
- Provides predictable and deterministic behavior but lacks flexibility and scalability
- Suitable for small, static systems with well-defined timing requirements (automotive embedded systems)
Time-Triggered Architecture (TTA)
- A comprehensive time-triggered approach for distributed real-time systems
- Relies on a global time base synchronized across all nodes in the system
- Communication and task execution are triggered by the progression of time
- Provides a predictable and composable system architecture
- Supports fault tolerance through redundancy and error containment
- Requires careful design and configuration to ensure correct timing and synchronization
- Used in safety-critical applications (aerospace, automotive, industrial control systems)