Self-Learning Earliest Deadline First Scheduler in Linux

Abstract

This paper explains a novel adaptive scheduling policy named as “Self-Learning Earliest Deadline First” (SL-EDF) in Linux for real-time embedded applications. This scheduling policy eliminates the major limitation of SCHED_DEADLINE, the existing EDF policy in Linux. In Linux, scheduling policies do the task prioritization and assignment of tasks to a free processor in any real-time application. The proposed scheduler is a major improvement in terms of core utilization in multicore processors and also eliminates deadline misses for all tasks. With the SL-EDF policy, the core utilization is achievable up to the maximum value of “ONE”. In this scheduling SL-EDF scheduler, any new task is assigned to the free core after ensuring that the core utilization will not exceed ONE. This paper elaborates the proposed design and implementation of the SL-EDF scheduler and improvement over existing EDF for better performance in multicore, real-time systems using Linux as Operating System.

Introduction

Objective:

The research aims to improve real-time task scheduling on multicore processors by overcoming the limitations of the existing Linux SCHED_DEADLINE (EDF) policy. It introduces a new Self-Learning EDF (SL-EDF) policy that dynamically updates the worst-case execution time (WCET) during runtime to enhance task scheduling accuracy and minimize deadline misses.

Background:

• Multicore processors are increasingly used in embedded real-time systems to reduce power consumption and size.

• Linux, as an open-source OS, is widely used, but its real-time scheduling policies (like SCHED_DEADLINE based on Earliest Deadline First) have significant limitations:

  • Static WCET values do not adapt to runtime interference from co-running tasks.

  • Leads to inefficient CPU utilization, task throttling, and missed deadlines.

Literature Review Highlights:

• EDF (Earliest Deadline First) is the most deadline-sensitive policy in Linux but struggles with:

  • Scalability

  • Runtime overhead

  • Static task parameters leading to deadline violations

• Studies highlight the need for adaptive scheduling mechanisms that respond to runtime variations in task execution due to multicore interference.

Proposed Method – SL-EDF (Self-Learning EDF):

• Key Innovation: Dynamically measures and updates WCET at runtime based on actual task execution.

• During each hyper-period (LCM of task periods), tasks are monitored, and WCET is calculated based on the maximum observed execution time.

• Core assignment ensures total utilization remains under 100% (Σ(Ci/Ti) < 1), preventing CPU overload.

System Model & Core Utilization:

• Considers N tasks running on M cores.

• Defines utilization per core and ensures it remains under 1 to avoid deadline violations.

SL-EDF Workflow:

1. Measure execution time in every task instance.

2. Use the highest observed time in a hyper-period as WCET.

3. Dynamically allocate tasks to cores based on updated WCET to prevent overutilization.

4. Scheduling decisions adapt in the next hyper-period using learned data.

Implementation in Linux:

• SL-EDF is implemented as a kernel module.

• A user-space process writes execution time data to a procfs interface.

• A kernel thread periodically reads this data and updates task parameters using sched_setattr() system call.

• Ensures accurate, adaptive scheduling using real-time feedback.

Experimental Setup:

• Testbed: Intel 8-core Xeon processor running Linux 5.19.

• 10 real-time threads (T0–T9) with varying execution times and periods.

• OS processes confined to core 0; real-time threads assigned to cores 1–7.

• Compared performance under SCHED_DEADLINE and SL-EDF.

Results and Observations:

• SL-EDF consistently reduced core utilization below 100%, preventing CPU overload.

• Fewer deadline misses observed with SL-EDF due to more accurate task scheduling.

• SL-EDF better accommodates runtime variations and maintains system stability.

Example Results:

• SL-EDF proves superior in ensuring tasks meet deadlines by adjusting scheduling dynamically based on runtime behavior.

Conclusion

The proposed SL-EDF scheduler improves existing EDF scheduling in terms of core utilisation and ensures zero deadline misses to real-time tasks of any real-time embedded application program. In the existing EDF policy, the execution time is initialised in the program, and the task to core assignment is based on this value. Here, the actual run time of the tasks is estimated while the tasks of the application program are executed. This enables the developer/user to port application programs to any hardware platform without modification. .

References

[1] Chang S, Zhao X, Liu Z, Deng Q. Real-Time scheduling and analysis of parallel tasks on heterogeneous multi-cores. Journal of Systems Architecture [Internet]. 2020 May 1; 105:101704. Available from: https://doi.org/10.1016/j.sysarc.2019.101704 [2] Liang Y, Li H, Shen F, Xu Q, Hua S, Zhu S. Adaptive Multi-Core Real- Time Scheduling Based on Reinforcement Learning. 2024 IEEE 18th International Conference on Control & Automation (ICCA). 2024 Jun 18;148–53. Available in: https://doi.org/10.1109/ICCA62789.2024.10591927 [3] Muhuri PK, Rauniyar A, Nath R. On arrival scheduling of real-time precedence constrained tasks on multi-processor systems using genetic algorithm. Future Generation Computer Systems. 2019 Apr; 93:702–26. Available in: https://doi.org/10.1016/j.future.2018.10.013 [4] Tang S, Anderson JH, Luca Abeni. On the Defectiveness of SCHED_DEADLINE w.r.t. Tardiness and Affinities, and a Partial Fix. 2021 Apr 7;46–56. Available in: https://doi.org/10.1145/3453417.3453440 [5] Stevanato A, Cucinotta T, Luca Abeni, Bristot D. An Evaluation of Adaptive Partitioning of Real-Time Workloads on Linux. CINECA IRIS Institutional Research Information System (Sant’Anna School of Advanced Studies). 2021 Jun 1;53–61. Available in: https://doi.org/10.1109/isorc52013.2021.00018 [6] Liu X, Liu P, Yan X, Zou C, Xia R, Zhou H, et al. Energy Optimization and Fault Tolerance to Embedded System Based on Adaptive Heterogeneous Multi-Core Hardware Architecture. HAL (Le Centre pour la Communication ScientifiqueDirecte). 2018 Jul 1;316–23. Available in: https://doi.org/10.1109/qrs-c.2018.00063 [7] Saez S, Vila J, Crespo A, Garcia A. A hardware scheduler for complex real-time systems. 2003 Jan 20; Available in: https://doi.org/10.1109/isie.1999.801754 [8] Minaeva A, Zden?kHanzálek. Survey on Periodic Scheduling for Time-triggered Hard Real-time Systems. ACM Computing Surveys. 2021 Mar 5;54(1):1–32. Available in: https://doi.org/10.1145/3431232 [9] Günzel M, Chen KH, Chen JJ. EDF-Like Scheduling for Self-Suspending Real-Time Tasks. arXiv (Cornell University). 2021 Jan 1; Available in: https://doi.org/10.48550/arxiv.2111.09725 [10] Vestal S. Techniques for Multiprocessor Global Schedulability Analysis. 2007 Dec 1; Available in : https://doi.org/10.1109/rtss.2007.35 [11] Tang S, Sergey Voronov, Anderson JH. Extending EDF for Soft Real-Time Scheduling on Unrelated Multiprocessors. 2021 Dec 1;253–65. Available in: https://doi.org/10.1109/rtss52674.2021.00032 [12] Lee S, Park S, Lee J. Improved Low Time-Complexity Schedulability Test for Non preemptive EDF on a Multiprocessor. IEEE Embedded Systems Letters. 2021 Dec 9;14(2):87–90. Available in: https://doi.org/10.1109/les.2021.3133901

Copyright

Copyright © 2025 P. Balakrishnan, Rajesh M., Rajesh R.. This is an open access article distributed under the Creative Commons Attribution License, which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited.