Real-Time Scheduling — Rate Monotonic & Earliest Deadline First

In real-time systems, the correctness of a task depends not only on its logical result but also on the time it takes to deliver that result. These systems often control physical processes—like automotive systems, medical equipment, or industrial automation—where delays or failures to meet deadlines can cause significant issues.

To manage such environments, we use real-time scheduling algorithms like Rate Monotonic (RM) and Earliest Deadline First (EDF).

What is Real-Time Scheduling?

Real-time scheduling refers to the method of allocating CPU time to tasks with strict timing constraints. It is used in real-time operating systems (RTOS) where tasks must complete within their deadlines.

There are two types of real-time systems:

• Hard Real-Time: Missing a deadline is unacceptable (e.g., pacemakers).
• Soft Real-Time: Occasional deadline misses are tolerable (e.g., video streaming).

Real-time scheduling ensures tasks are executed in a predictable, deadline-aware manner.

Rate Monotonic Scheduling (RMS)

Definition: A fixed-priority algorithm where priority is inversely proportional to the period of a task. Tasks with shorter periods (i.e., more frequent) are given higher priority.

Key Characteristics:

• Suitable for periodic tasks (those that repeat at regular intervals).
• Priorities are assigned once and do not change.
• Proven to be optimal among fixed-priority scheduling algorithms for such tasks.

How It Works:

• Suppose you have three tasks with periods of 10ms, 20ms, and 40ms.
• The 10ms task gets the highest priority, and the 40ms task the lowest.
• If a higher-priority task becomes ready, it preempts the lower-priority task.

Pros:

• Easy to implement.
• Good for static environments.

Cons:

• Not suitable for aperiodic or sporadic tasks.
• Less flexible under dynamic conditions.

Earliest Deadline First (EDF)

Definition: A dynamic-priority scheduling algorithm where the task with the earliest deadline is always given the highest priority.

Key Characteristics:

• Suitable for both periodic and aperiodic tasks.
• Deadlines are reassessed dynamically at each scheduling point.
• EDF is optimal for uniprocessor systems: if a set of tasks can be scheduled by any algorithm, EDF will succeed.

How It Works:

• Each time a task arrives or completes, the scheduler checks deadlines.
• It selects the task whose deadline is soonest and runs it first.
• This continues as tasks arrive, ensuring all deadlines are respected (if feasible).

Pros:

• Highly efficient use of CPU.
• Flexibly handles dynamic workloads.

Cons:

• Requires constant monitoring and recalculation of deadlines.
• More complex than RM.

Comparison: RM vs. EDF