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)