Aarushi Karunakaran
Independent Researcher
India
Abstract
In real-time operating systems (RTOS), task scheduling algorithms are critical to guarantee timely completion of periodic and aperiodic tasks. This manuscript evaluates classical scheduling algorithms—Rate Monotonic (RM), Earliest Deadline First (EDF), Deadline Monotonic (DM), and Least Laxity First (LLF)—under workloads representative of embedded control systems prevalent up to 2018. Using simulation tools available prior to 2018, we measure response time, deadline miss rate, CPU utilization, and throughput across varying task sets. Statistical analysis demonstrates trade-offs between predictability and utilization: RM and DM offer deterministic behavior at lower utilization, whereas EDF and LLF achieve higher utilization with greater scheduling overhead. Methodology involves generating synthetic task sets with utilization densities from 40% to 90%, simulating on an ideal single-core RTOS model, and collecting performance metrics. Results show EDF achieves up to 92% utilization with deadline miss rates below 2% for utilizations up to 80%, while RM maintains zero misses only up to 69% utilization. Research gaps include analysis of overhead on real hardware, mixed criticality task sets, and energy-aware scheduling. Conclusions stress that algorithm selection must balance utilization goals and system overhead, recommending EDF for high-utilization scenarios and RM/DM for safety-critical low-overhead applications.
Keywords
Rate Monotonic, Earliest Deadline First, Deadline Monotonic, Least Laxity First, task scheduling, deadline miss rate, CPU utilization, real-time operating system
REFERENCES
Liu, C. L., & Layland, J. W. (1973). Scheduling algorithms for multiprogramming in a hard-real-time environment. Journal of the ACM, 20(1), 46–61.
Lehoczky, J. P., Sha, L., & Ding, Y. (1989). The rate monotonic scheduling algorithm: Exact characterization and average case behavior. Proceedings of the IEEE Real-Time Systems Symposium, 166–171.
Mok, A. K. L., & Chen, D. (1983). A multiframe model for real-time tasks. Proceedings of the IEEE Real-Time Systems Symposium, 22–27.
Audsley, N., Burns, A., Richardson, M., Wellings, A., & Davis, R. (1993). Applying new scheduling theory to static priority pre-emptive scheduling. Software Engineering Journal, 8(5), 284–292.
Tindell, K., Burns, A., & Wellings, A. (1994). Calculating controller area network (CAN) message response times. Proceedings of the Real-Time Systems Symposium, 259–263.
Baruah, S., Howell, R., & Rosier, L. (1990). Algorithms and complexity concerning the preemptive scheduling of periodic, real-time tasks on one processor. Real-Time Systems, 2(4), 301–324.
Baker, T. P. (2003). Multiprocessor EDF and deadline monotonic scheduling algorithms. Proceedings of the IEEE Real-Time Systems Symposium, 166–175.
Buttazzo, G. C. (2005). Hard Real-Time Computing Systems: Predictable Scheduling Algorithms and Applications (3rd ed.). Springer.
