A Comparative Study on the Schedulability of the EDZL Scheduling Algorithm on Multiprocessors
Source abstract
Abstract
As multiprocessor (or multicore) real-time systems become popular, there has been much research on multiprocessor real-time scheduling algorithms. This work evaluates EDZL (Earliest Deadline until Zero Laxity), a scheduling algorithm for real-time multiprocessor systems. First, we compare the performance of EDZL schedulability tests. We measure and compare the ratio of task sets admitted by each test. We also investigate the dominance between EDZL schedulability tests and discover that the union of the demand-based test and the utilization-based test is an effective combination. Second, we compare the schedulability of EDZL and EDF(k). We prove that the union of the EDZL schedulability tests dominates the EDF(k) schedulability test, i.e., the union of the EDZL schedulability tests can admit all task sets admitted by the EDF(k) schedulability test. We also compare the schedulability of EDZL and EDF(k) through scheduling simulation by measuring the ratio of successfully scheduled task sets. EDZL can successfully schedule 7.0% more task sets than EDF(k).
Source: crossref · Quality: baseline
Research context
OpenAlex topics: Real-Time Systems Scheduling · Embedded Systems Design Techniques · Distributed systems and fault tolerance
SciVX discovery tags are terminology-based. OpenAlex topics are source-provided classifications.
Affiliations
Department of Computer Engineering, Konkuk University, Chungju 27478, Republic of Korea
Funding
Konkuk University
References (41)
Show source-provided references
1. Proportionate progress: A notion of fairness in resource allocation10.1007/BF01940883 ↗
2. Andersson, B., and Tovar, E. (2006, January 16–18). Multiprocessor scheduling with few preemptions. Proceedings of the 12th IEEE International Conference on Embedded and Real-Time Computing Systems and Applications (RTCSA’06), Sydney, QLD, Australia.10.1109/RTCSA.2006.45 ↗
3. Cho, H. (2006, January 5–8). An Optimal Real-Time Scheduling Algorithm for Multiprocessors. Proceedings of the 27th IEEE Real-Time Systems Symposium, Rio de Janeiro, Brazil.10.1109/RTSS.2006.10 ↗
4. Mixed Pfair/ERfair scheduling of asynchronous periodic tasks10.1016/j.jcss.2003.08.002 ↗
5. Baruah, S.K., Gehrke, J.E., and Plaxton, C.G. (1995, January 25–28). Fast scheduling of periodic tasks on multiple resources. Proceedings of the 9th International Parallel Processing Symposium, Santa Barbara, CA, USA.
6. DP-Fair: A unifying theory for optimal hard real-time multiprocessor scheduling10.1007/s11241-011-9130-0 ↗
7. Efficient real-time scheduling algorithms for multiprocessor systems
8. Comparison of deadline-based scheduling algorithms for periodic real-time tasks on multiprocessor10.1093/ietisy/e88-d.3.658 ↗
9. Alhussian, H., and Zakaria, N. (2015, January 24–27). An Efficient Zero-Laxity Based Real-Time Multiprocessor Scheduling Algorithm. Proceedings of the 5th International Conference on IT Convergence and Security (ICITCS), Kuala Lumpur, Malaysia.10.1109/ICITCS.2015.7292943 ↗
10. Earliest virtual deadline zero laxity scheduling for improved responsiveness of mobile GPUs10.5573/JSTS.2017.17.1.162 ↗
11. Investigating the schedulability of periodic real-time tasks in virtualized cloud environment10.1109/ACCESS.2019.2900288 ↗
12. Incorporating zero-laxity policy into mixed-criticality multiprocessor real-time systems10.1587/transfun.E101.A.1888 ↗
13. Chen, T.Y., Wei, H.W., Leu, J.S., and Shih, W.K. (2011, January 12–14). EDZL scheduling for large-scale cyber service on real-time cloud. Proceedings of the 2011 IEEE International Conference on Service-Oriented Computing and Applications (SOCA), Irvine, CA, USA.10.1109/SOCA.2011.6166234 ↗
14. Wu, P., Majeed, S., and Ryu, M. (2016, January 23–25). Two approaches towards EDZL scheduling for performance asymmetric multiprocessors. Proceedings of the 2016 IEEE International Conference on Network Infrastructure and Digital Content (IC-NIDC), Beijing, China.10.1109/ICNIDC.2016.7974548 ↗
15. Baek, H., and Lee, J. (2019). Task-level re-execution framework for improving fault tolerance on symmetry multiprocessors. Symmetry, 11.10.3390/sym11050651 ↗
16. Piao, X., Han, S., Kim, H., Park, M., Cho, Y., and Cho, S. (2006, January 24–26). Predictability of earliest deadline zero laxity algorithm for multiprocessor real-time systems. Proceedings of the Ninth IEEE International Symposium on Object and Component-Oriented Real-Time Distributed Computing (ISORC’06), Gyeongju, Republic of Korea.
17. Wei, H.W., Chao, Y.H., Lin, S.S., Lin, K.J., and Shih, W.K. (2007, January 21–24). Current Results on EDZL Scheduling for Multiprocessor Real-Time Systems. Proceedings of the 13th IEEE International Conference on Embedded and Real-Time Computing Systems and Applications (RTCSA 2007), Daegu, Republic of Korea.10.1109/RTCSA.2007.34 ↗
18. EDZL scheduling analysis10.1007/s11241-008-9061-6 ↗
19. EDZL schedulability analysis in real-time multicore scheduling10.1109/TSE.2012.75 ↗
20. Demand-based schedulability analysis for real-time multi-core scheduling10.1016/j.jss.2013.09.029 ↗
21. Priority-driven scheduling of periodic task systems on multiprocessors10.1023/A:1025120124771 ↗
22. Scheduling Algorithms for Multiprogramming in a Hard-Real-Time Environment10.1145/321738.321743 ↗
23. Audsley, N.C., Burns, A., Richardson, M.F., and Wellings, A.J. (1991, January 15–17). Real-Time scheduling: The deadline-monotonic approach. Proceedings of the IEEE Workshop on Real-Time Operating Systems and Software, Atlanta, GA, USA.10.1016/S1474-6670(17)51283-5 ↗
24. Carpenter, J., Funk, S., Holman, P., Srinivasan, A., Anderson, J., and Baruah, S. (2004). Handbook of Scheduling: Algorithms, Models, and Performance Analysis, Chapman Hall/CRC Press.
25. Rate-monotonic scheduling on uniform multiprocessors10.1109/TC.2003.1214344 ↗
26. Baruah, S., and Goossens, J. (2008, January 15–18). Deadline monotonic scheduling on uniform multiprocessors. Proceedings of the International Conference on Principles of Distributed Systems, Brussels, Belgium.10.1007/978-3-540-92221-6_8 ↗
27. Mok, A. (1988, January 12–13). Task Management Techniques for Enforcing ED Scheduling on a Periodic Task Set. Proceedings of the 5th IEEE Workshop on Real-Time Software and Operating Systems, Washington, DC, USA.
28. Funk, S.H. (2004). EDF Scheduling on Heterogeneous Multiprocessors. [Ph.D. Thesis, University of North Carolina at Chapel Hill].
29. On a Real-Time Scheduling Problem10.1287/opre.26.1.127 ↗
30. Deadline-based scheduling of periodic task systems on multiprocessors10.1016/S0020-0190(02)00231-4 ↗
31. Optimal utilization bounds for the fixed-priority scheduling of periodic task systems on identical multiprocessors10.1109/TC.2004.16 ↗
32. Davis, R.I., and Burns, A. (2011, January 11–14). FPZL schedulability analysis. Proceedings of the 17th IEEE Symposium Real-Time and Embedded Technology and Applications, Chicago, IL, USA.10.1109/RTAS.2011.31 ↗
33. FPSL, FPCL and FPZL schedulability analysis10.1007/s11241-012-9149-x ↗
34. Zero-laxity based real-time multiprocessor scheduling10.1016/j.jss.2011.07.002 ↗
35. Real time scheduler for multiprocessor systems based on continuous control using Timed Continuous Petri Nets10.1016/j.ifacol.2021.04.036 ↗
36. Global EDF-based scheduling with laxity-driven priority promotion10.1016/j.sysarc.2011.01.002 ↗
37. Anderson, J.H., and Srinivasan, A. (2000, January 19–21). Early-release fair scheduling. Proceedings of the 12th Euromicro Conference on Real-Time Systems (Euromicro RTS 2000), Stockholm, Sweden.
38. Levin, G., Funk, S., Sadowski, C., Pye, I., and Brandt, S. (2010, January 6–9). DP-FAIR: A simple model for understanding optimal multiprocessor scheduling. Proceedings of the 2010 22nd Euromicro Conference on Real-Time Systems, Brussels, Belgium.10.1109/ECRTS.2010.34 ↗
39. Nelissen, G., Berten, V., Nélis, V., Goossens, J., and Milojevic, D. (2012, January 11–13). U-EDF: An unfair but optimal multiprocessor scheduling algorithm for sporadic tasks. Proceedings of the 2012 24th Euromicro Conference on Real-Time Systems, Pisa, Italy.10.1109/ECRTS.2012.36 ↗
40. Regnier, P., Lima, G., Massa, E., Levin, G., and Brandt, S. (December, January 29). Run: Optimal multiprocessor real-time scheduling via reduction to uniprocessor. Proceedings of the 2011 IEEE 32nd Real-Time Systems Symposium, Washington, DC, USA.10.1109/RTSS.2011.17 ↗
41. A new algorithm for scheduling periodic, real-time tasks10.1007/BF01553887 ↗