Definition
Real-Time Scheduling
Real-time scheduling refers to scheduling techniques used in systems where the correctness of the result depends not only on the logical outcome but also on the time at which the result is produced.
Types of Real-Time Systems
- Hard Real-Time: Missing a deadline results in a total system failure (e.g., medical devices, flight control).
- Soft Real-Time: Missing a deadline is undesirable but acceptable; performance degrades but the system survives (e.g., video streaming).
Earliest Deadline First (EDF)
Earliest Deadline First (EDF) is a dynamic scheduling strategy that prioritises the task with the nearest completion deadline.
- Selection Function: Choose the task with the earliest deadline.
- Decision Mode: Preemptive.
- Performance: Guaranteed to be optimal for uniprocessor systems; if any algorithm can schedule a set of tasks without missing deadlines, EDF can as well.
Schedulability Test
For a set of periodic tasks, where each task has an execution time and a period (equal to its deadline), the system is schedulable if the processor utilisation is less than or equal to 1:
Static vs. Dynamic Priorities
- Static Priorities: Assigned before runtime based on task characteristics (e.g., Rate Monotonic Scheduling, where shorter periods get higher priority).
- Dynamic Priorities: Determined during execution based on factors like deadlines (e.g., EDF).