Safety Verification of Rate-Monotonic Least-Splitting Real-Time Scheduler on Multiprocessor System

Document Type : Bioinformatics-Naghibzadeh

Authors

• Amin Rezaeian
• Abolfazl Ghavidel
• Yasser Sedaghat

Ferdowsi University of Mashhad

10.22067/cke.v1i2.58792

Abstract

In real-time task scheduling on multiprocessor systems, partitioning approach has received the attention of many researchers because of its higher least upper bound utilization of safe systems. Semi-partitioning allows some tasks to be split into subtasks and each subtask to be assigned to a different processor. Though task splitting improves the performance of systems, by counting each subtask as a separate task, it increases the effective number of tasks to be scheduled, which in turn, raises the execution overhead. This research is on semi partitioning of tasks and assigning each partition to a separate processor to be scheduled by the well-known scheduler Rate Monotonic (RM). Using our algorithm, we do not need to define release time for subtasks of a task to assure their non-concurrent execution and the number of effective tasks, in turn, is reduced. It is theoretically proven that with the proposed semi partitioning and RM scheduling algorithm, all processors may safely run their tasks according to their deadlines. Further, experimental results on 3000 randomly generated task sets indicates that not only is utilization factor boosted, but the number of broken tasks also is decreased.

Keywords

• Rate-Monotonic Least Splitting
• Semi-Partitioning
• Hard real-time
• Multiprocessor Scheduling

---

References

[1] C.L. Liu, "Scheduling algorithms for multiprocessors in a hard real-time environment". JPL Space Programs Summary, vol. 37-60, 1969, pp. 28–31.

[2] K. Lakshmanan, R. Rajkumar and J. Lehoczky, "Partitioned fixed-priority preemptive scheduling for multi-core processors", in Real-Time Systems, 2009. ECRTS’09. 21st Euromicro Conference on. IEEE, pp. 239–248, 2009.

[3] ‎M.R‎. ‎Gary and D.S‎. ‎Johnson: "Computers and Intractability; A Guide to the Theory of NP-Completeness" (W. H. Freeman & Co.), 1979.

[4] ‎N. Guan‎, ‎M. Stigge‎, ‎W. Yi‎ ‎and G. Yu‎, ‎"Fixed-priority multiprocessor‎ ‎scheduling with liu and layland's utilization bound", in Real-Time and‎ ‎Embedded Technology and Applications Symposium (RTAS)‎, ‎2010 16th IEEE. IEEE‎, ‎pp‎. ‎165–174, ‎2010‎‎.

[5] ‎‎B. Andersson and E. Tovar‎, "Multiprocessor scheduling with few preemptions", ‎in Embedded and Real-Time Computing Systems and Applications‎, 2006. ‎Proceedings. 12th IEEE International Conference on. IEEE, pp. 322–334, 2006.

[6] J. Anderson‎, ‎V. Bud‎ ‎and U. Devi‎, "An edf-based scheduling algorithm for‎ ‎multiprocessor soft real-time systems", in Real-Time Systems‎‎.‎(ECRTS 2005)‎. ‎Proceedings‎. ‎17th Euromicro Conference on, 2005, pp. 199–208, ‎2005.

[7] Burns, R. I. Davis, P. Wang and F. Zhang, "Partitioned edf scheduling for multiprocessors using a c=d task splitting scheme", Real-Time Systems, vol. 48, no. 1, pp. 3–33, 2012.

[8] S. Kato and N. Yamasaki, "Portioned edf-based scheduling on multiprocessors", in Proceedings of the 8th ACM international conference on Embedded software. ACM, 2008, pp. 139–148.

[9] S. Kato, N. Yamasaki and Y. Ishikawa, "Semi-partitioned scheduling of sporadic task systems on multiprocessors", in Real-Time Systems, 2009. ECRTS’09. 21st Euromicro Conference on. IEEE, pp. 249–258, 2009.

[10] N. Guan and W. Yi, "Fixed-priority multiprocessor scheduling: Critical instant, response time and utilization bound", in Parallel and Distributed Processing Symposium Workshops & PhD Forum (IPDPSW), 2012 IEEE 26th International. IEEE, pp. 2470–2473, 2012.

[11] S. Kato and N. Yamasaki, "Portioned static-priority scheduling on multiprocessors", in Parallel and Distributed Processing, 2008. IPDPS 2008. IEEE International Symposium on. IEEE, pp. 1–12, 2008.

[12] S. Kato and N. Yamasaki, "Semi-partitioned fixed-priority scheduling on multiprocessors", in Real-Time and Embedded Technology and Applications Symposium, 2009. RTAS 2009. 15th IEEE. IEEE, pp. 23–32, 2009.

[13] L. Liu and J. W. Layland, "Scheduling algorithms for multiprogramming in a hard-real-time environment", Journal of the ACM (JACM), vol. 20, no. 1, 1973, pp. 46–61.

[14] R. I. Davis and A. Burns, "A survey of hard real-time scheduling for multiprocessor systems", ACM Computing Surveys (CSUR), vol. 43, no. 4, p. 35, 2011.

[15] M. Naghibzadeh, P. Neamatollahi, R. Ramezani, A. Rezaeian and T. Dehghani, "Efficient semi-partitioning and rate-monotonic scheduling hard real-time tasks on multi-core systems", in Industrial Embedded Systems (SIES), 2018 8th IEEE International Symposium on. IEEE, 2013, pp. 85–88.

[16] M. Naghibzadeh, "A modified version of rate-monotonic scheduling algorithm and its' efficiency assessment", in Object-Oriented Real-Time Dependable Systems, 2002. (WORDS 2002). Proceedings of the Seventh International Workshop on, 2002, pp. 289-294.

[17] M. Naghibzadeh and K.H. Kim "The yielding-first rate-monotonic scheduling approach and its efficiency assessment", International Journal of Computer System Science & Engineering, pp. 173-180, 2003.

[18] E. Bini and G. C. Buttazzo, "Measuring the performance of schedulability tests", Real-Time Systems, vol. 30, no. 1-2, pp. 129–154, 2005.

[19] R. I. Davis and A. Burns, "Improved priority assignment for global fixed priority pre-emptive scheduling in multiprocessor real-time systems", Real-Time Systems, vol. 47, pp. 1-40, 2011.

[20] Ghavidel, M. Hajibegloo, A. Savadi and Y. Sedaghat, "LTS: Linear task scheduling on multiprocessor through equation of the line", in Computer Architecture and Digital Systems (CADS), 2015 18th CSI International Symposium on, pp. 1-6, 2015.