Evaluation of Scheduling Algorithms for Embedded FreeRTOS-Based Systems
Resumo
Dynamic priority real-time scheduling (DPS), such as Earliest-Deadline First (EDF), offers high levels of system schedulability, implying that under this scheduling policy system processing capacity can be utilized in an optimized way. However, this schedulability gain can be compromised due to overheads associated with managing dynamic priority queues, making the use of DPS less appealing in low processing capacity embedded systems. In this paper we assess the overheads associated with two different implementations of EDF in FreeRTOS running on an ARM-M4 architecture, comparing them against Rate-Monotonic scheduling (RMS), a classic fixed-priority policy. The two EDF implementations differ from each other by the manner priority queues are implemented, based either on min-heap (EDF-H) or on multiple linked lists (EDF-L). Runtime overheads and schedulability are taken into consideration for different types of task sets and system loads. Results indicate that the higher overheads of EDF-H may lead to poor performance with respect to RMS in some scenarios. Even presenting slightly higher overheads than RMS, EDF-L was shown to perform consistently better in all considered experiments.
Referências
S. K. Baruah L. E. Rosier and R. R. Howell "Algorithms and complexity concerning the preemptive scheduling of periodic real-time tasks on one processor" Real-Time Systems vol. 2 no. 4 pp. 301-324 1990.
D. Faggioli M. Trimarchi and F. Checconi "An implementation of the earliest deadline first algorithm in linux" ACM Symposium on Applied Computing pp. 1984-1989 2009.
A. Stahlhofen and D. Zobel "Linux sched deadline vs. martop-edf" IEEE International Conference on Embedded and Ubiquitous Computing pp. 168-172 2015.
G. C. Buttazzo "Rate monotonic vs. EDF: Judgment day" Real-Time Systems vol. 29 no. 1 pp. 5-26 2005.
G. Buttazzo "Efficient edf implementation for small embedded systems" Workshop on Operating Systems Platforms for Embedded Real-Time applications 2006.
K.-M. Cho C.-H. Liang J.- Y. Huang and C.-S. Yang "Design and implementation of a general purpose power-saving scheduling algorithm for embedded systems" IEEE International Conference on Signal Processing Communications and Computing pp. 1-5 2011.
R. Barry Mastering the FreeRTOS™ Real Time Kernel Wiley 2016.
F. E. Paez J. M. Urriza R. Cayssials and J. D. Orozco "Freertos user mode scheduler for mixed critical systems" IEEE Argentine Conference on Embedded Systems pp. 37-42 2015.
R. Kase Efficient scheduling library for freertos 2016.
R. Belagali S. Kulkarni V. Hegde and G. Mishra "Implementation and validation of dynamic scheduler based on 1st on freertos" IEEE International Conference on Electrical Electronics Communication Computer and Optimization Techniques pp. 325-330 2016.
V. M. Anas Toma and J.-J. Chen "Implementation and evaluation of multi-mode real-time tasks under different scheduling algorithms" Operating Systems Platforms for Embedded Real-Time applications 2018.
"Datasheet ARM-M4 STM32F4 family. Rev.B" STMicroelectronics 2016 [online] Available: https://www.st.com/resource/en/datasheet/dm00037051.pdf.
Who we are 2020 [online] Available: https://www.st.com/content/st_com/en/about/st_company_information/who-we-are.
R. M. Pathan "Design of an efficient ready queue for earliest-deadline-first (edf) scheduler" Design Automation Test in Europe Conference Exhibition. Operating Systems Platforms for Embedded Real-Time applications pp. 293-296 2016.
T. H. Cormen C. E. Leiserson R. L. Rivest and C. Stein Introduction to Algorithms Massachusetts Institute of Technology 2009.
N. Audsley A. Burns M. Richardson K. Tindell and A. Wellings "Applying new scheduling theory to static priority pre-emptive scheduling" Software Engineering Journal vol. 8 no. 5 pp. 284-292 1993.
R. Barry License freertos 2020.
"FreeRTOS support architectures" STmicroelectronics 2020 [online] Available: https://www.st.com/en/embedded-software/freertos-kernel.html.
R. M. Pathan "Unifying fixed- and dynamic-priority scheduling based on priority promotion and an improved ready queue management technique" IEEE Real-Time and Embedded Technology and Applications Symposium pp. 209-220 2015.
G. C. Buttazzo Hard Real-Time Computing Systems Springer US 2011.
P. Emberson R. Stafford and R. Davis "Techniques for the synthesis of multiprocessor tasksets" WATERS pp. 6-11 2010.
