Real-Time Scheduling Explained: Implementing RMS & EDF with Code Examples

Real-time scheduling is crucial in embedded systems to ensure tasks execute within strict timing constraints. Rate Monotonic Scheduling (RMS) and Earliest Deadline First (EDF) are widely used scheduling algorithms. This blog overviews both and demonstrates their implementation with hands-on examples.

Understanding Rate Monotonic Scheduling (RMS)

RMS is a fixed-priority scheduling algorithm where shorter periodic tasks get higher priority. It is widely used for hard real-time systems.

Example: Consider three tasks with different periods:

Task	Execution Time	Period
T1	1 ms	4 ms
T2	2 ms	5 ms
T3	1 ms	10 ms

In RMS, T1 gets the highest priority, followed by T2, then T3.

Code Implementation :

• Task1: Processes sensor data and executes every 1 second.
• Task2: Handles communication with an external device and executes every 500 milliseconds.
• Task3: Logs system status and executes every 2 seconds.
• Priorities: Task1 has the highest priority (3), Task2 has medium priority (2), and Task3 has the lowest priority (1).
• pdMS_TO_TICKS: Converts time in milliseconds to RTOS ticks, ensuring accurate task delays according to the system tick rate.

What is pdMS_TO_TICKS?

pdMS_TO_TICKS(milliseconds) is a macro in FreeRTOS that converts a time delay in milliseconds into system ticks. RTOS operates based on a system tick timer, which determines how often the scheduler runs. Since tasks use tick-based delays, pdMS_TO_TICKS ensures that delays are correctly converted based on the tick rate (configTICK_RATE_HZ).

Example Calculation:

• • If configTICK_RATE_HZ is set to 1000 ticks per second (1ms per tick), then:
    • pdMS_TO_TICKS(1000) = 1000 ticks (1-second delay)
    • pdMS_TO_TICKS(500) = 500 ticks (0.5-second delay)
  • If configTICK_RATE_HZ is set to 500 ticks per second (2ms per tick), then:

• pdMS_TO_TICKS(1000) = 500 ticks

• pdMS_TO_TICKS(500) = 250 ticks

 

Here, higher priority values indicate higher priority tasks. RMS ensures the highest priority task runs first.

Understanding Earliest Deadline First (EDF)

EDF is a dynamic-priority scheduling algorithm where tasks are prioritized based on their deadlines. The task with the earliest deadline executes first.

Example: Tasks with deadlines:

Task	Execution Time	Deadline
T1	2 ms	5 ms
T2	1 ms	4 ms
T3	2 ms	6 ms

At any given moment, the task with the closest deadline runs first.

Code Implementation (Simplified)

Here, tasks are sorted by deadline, ensuring the task with the earliest deadline executes first.

Conclusion

Both RMS and EDF have their advantages:

• Use RMS when task periods are fixed and system predictability is required.
• Use EDF when tasks have variable deadlines and flexibility is needed.