An Evaluation of Real-Time Scheduling Algorithms on an Embedded RTOS

Abstract

Real-time embedded systems must complete their tasks within strict deadlines, and the scheduling algorithm of the operating system determines whether those deadlines are met as the processor becomes more heavily loaded. The two classic algorithms, rate-monotonic scheduling with fixed priorities and earliest-deadline-first scheduling with dynamic priorities, offer different guarantees and overheads. This paper presents an evaluation of these scheduling algorithms on an embedded real-time operating system, measuring the deadline miss ratio for periodic task sets as the processor utilization increases. Both algorithms were implemented on a preemptive real-time kernel running on a microcontroller, and identical task sets were executed under each. Earliest-deadline-first met all deadlines up to full processor utilization, missing only marginally beyond it, whereas rate-monotonic began missing deadlines well before full utilization, in line with its lower theoretical bound. The dynamic algorithm therefore used the processor more fully at the cost of slightly higher run-time overhead. The results confirm on real hardware the theoretical advantage of earliest-deadline-first for utilization, while highlighting the simplicity and predictability that keep rate-monotonic attractive in practice. KEYWORDS: Real-time systems, scheduling, RTOS, rate-monotonic, earliest-deadline-first, embedded systems