Abstract
Hard real- time multiprocessor scheduling has seen, in recent years, the flourishing of semi-partitioned scheduling algorithms. This category of scheduling schemes combines elements of partitioned and global scheduling for the purposes of achieving efficient utilization of the system’s processing resources with strong schedulability guarantees and with low dispatching overheads. The sub-class of slot-based “task-splitting” scheduling algorithms, in particular, offers very good trade-offs between schedulability guarantees (in the form of high utilization bounds) and the number of preemptions/migrations involved. However, so far there did not exist unified scheduling theory for such algorithms; each one was formulated in its own accompanying analysis. This article changes this fragmented landscape by formulating a more unified schedulability theory covering the two state-of-the-art slot-based semi-partitioned algorithms, S-EKG and NPS-F (both fixed job-priority based). This new theory is based on exact schedulability tests, thus also overcoming many sources of pessimism in existing analysis. In turn, since schedulability testing guides the task assignment under the schemes in consideration, we also formulate an improved task assignment procedure. As the other main contribution of this article, and as a response to the fact that many unrealistic assumptions, present in the original theory, tend to undermine the theoretical potential of such scheduling schemes, we identified and modelled into the new analysis all overheads incurred by the algorithms in consideration. The outcome is a new overhead-aware schedulability analysis that permits increased efficiency and reliability. The merits of this new theory are evaluated by an extensive set of experiments.
Similar content being viewed by others
Notes
We use the term multiprocessor rather than multicore, because a lot of that work applies not only to multicore but also to other multiprocessor systems.
Specifically, we only cover the main variant of NPS-F, which splits tasks between no more than two processors.
We focus on S-EKG and not in EDF-SS, because latter is a version of the former that explores different bin-packing heuristics for assigning task-to-processors.
That proof assumed implicit-deadline tasks; proof for arbitrary deadlines has not yet been published. In any case, in this work, we set \(\Omega \) accordingly.
Available online at http://gmplib.org/
The bursty periodic arrival model was introduced in Audsley et al. 1993.
References
Altmeyer S, Davis RI, Maiza C (2012) Improved cache related pre-emption delay aware response time analysis for fixed priority pre-emptive systems. Real-Time Syst 48(5):499–526
Anderson J, Srinivasan A (2004) Mixed pfair/erfair scheduling of asynchronous periodic tasks. J Comput Syst Sci 68(1):157–204
Anderson J, Bud V, Devi U (2005) An EDF-based scheduling algorithm for multiprocessor soft real-time systems. In: Proceedings of the 17th IEEE Euromicro Conference on Real-Time Systems (ECRTS’05). Palma de Mallorca, Balearic Islands, Spain, , pp 199–208
Andersson B, Bletsas, K (2008) Sporadic multiprocessor scheduling with few preemptions. In: Proceedings of the 20th IEEE Euromicro Conference on Real-Time Systems (ECRTS’08). Prague, Czech Republic, pp 243–252
Andersson B, Tovar E (2006) Multiprocessor scheduling with few preemption. In: Proceedings of the 12th IEEE International Conference on Embedded and Real-Time Computing Systems and Application (RTCSA’06). Sydney, Australia (2006), pp 322–334
Andersson B, Bletsas K, Baruah S (2008) Scheduling arbitrary-deadline sporadic tasks on multiprocessors. In: Proceedings of the 29th IEEE Real-Time Systems Symposium (RTSS’08). Barcelona, Spain, pp 385–394
Audsley N, Burns A, Richardson M, Tindell K, Wellings AJ (1993) Applying new scheduling theory to static priority pre-emptive scheduling. Softw Eng J 8(5):284–292
Banakar R, Steinke S, Lee BS, Balakrishnan M, Marwedel P (2002) Scratchpad memory: design alternative for cache on-chip memory in embedded systems. In: Proocedings of the 10th ACM International Symposium on Hardware/Software Codesign (CODES’02). Estes Park, Colorado, pp 73–78
Baruah S, Mok A, Rosier L (1990) Preemptively scheduling hard-real-time sporadic tasks on one processor. In: Proceedings of the 11st IEEE Real-Time Systems Symposium (RTSS’90). Lake Buena Vista, Florida, USA, pp 182–190
Baruah S, Cohen N, Plaxton G, Varvel D (1994) Proportionate progress: a notion of fairness in resource allocation. Algorithmica 15:600–625
Bastoni A (2011) Towards the integration of theory and practice in multiprocessor real-time scheduling. Ph.D. thesis, University of Rome “Tor Vergata”
Bastoni A, Brandenburg B, Anderson J (2010) Cache-related preemption and migration delays: empirical approximation and impact on schedulability. In: Proceedings of the 6th International Workshop on Operating Systems Platforms for Embedded Real-Time Applications (OSPERT’10). Brussels, Belgium, pp 33–44
Bastoni A, Brandenburg BB, Anderson JH (2010) An empirical comparison of global, partitioned, and clustered multiprocessor EDF schedulers. In: Proceedings of the 31st IEEE Real-Time Systems Symposium (RTSS’10). IEEE Computer Society, San Diego, CA, USA, pp 14–24
Bastoni A, Brandenburg B, Anderson J (2011) Is semi-partitioned scheduling practical? In: Proceedings of the 23rd IEEE Euromicro Conference on Real-Time Systems (ECRTS’11). Porto, Portugal, pp 125–135
Bletsas K, Andersson B (2009) Notional processors: an approach for multiprocessor scheduling. In: Proceedings of the 15th IEEE Real-Time and Embedded Technology and Applications Symposium (RTAS’09). San Francisco, CA, USA, pp 3–12
Bletsas K, Andersson B (2009) Preemption-light multiprocessor scheduling of sporadic tasks with high utilisation bound. In: Proceedings of the 30th IEEE Real-Time Systems Symposium (RTSS’09). Washington, DC, USA, pp. 385–394
Bletsas K, Andersson B (2011) Preemption-light multiprocessor scheduling of sporadic tasks with high utilisation bound. Real-Time Syst 47(4):319–355
Burns A, Davis RI, Wang P, Zhang F (2012) Partitioned EDF scheduling for multiprocessors using a C=D task splitting scheme. Real-Time Syst 48(1):3–33
Calandrino J, Leontyev H, Block A, Devi U, Anderson J (2006) Litmus\(^{\text{ rt }}\) : a testbed for empirically comparing real-time multiprocessor schedulers. In: Proceedings of the 27th IEEE Real-Time Systems Symposium (RTSS’06). Rio de Janeiro, Brazil, pp 111–126
Coffman E, Garey M, Johnson D (1997) Approximation algorithms for NP-hard problems. chap. Approximation algorithms for bin packing: a survey. PWS Publishing Co., Boston, MA, USA, pp 46–93
Davis R, Burns A (2009) A survey of hard real-time scheduling algorithms and schedulability analysis techniques for multiprocessor systems. Technical report YCS-2009-443, University of York, Department of Computer, Science
George L, Rivierre N, Spuri M (1996) Preemptive and nonpreemptive real-time uniprocessor scheduling. Tech. Rep. 2966, INRIA, France
Hoang H, Buttazzo G, Jonsson M, Karlsson S (2006) Computing the minimum EDF feasible deadline in periodic systems. In: Proceedings of the 12th IEEE International Conference on Embedded and Real-Time Computing Systems and Applications (RTCSA’06), pp 125–134
Inc., A.: AMD Opteron Processor. http://products.amd.com/en-us/OpteronCPUDetail.aspx?id=645
Ju L, Chakraborty S, Roychoudhury A (2007) Accounting for cache-related preemption delay in dynamic priority schedulability analysis. In: Proceedings of the IEEE Design, Automation Test in Europe Conference Exhibition (DATE’07). Nice, France, pp 1–6
Kato S, Yamasaki N (2007) Real-time scheduling with task splitting on multiprocessors. In: Proceedings of the 13th IEEE International Conference on Embedded and Real-Time Computing Systems and Applications (RTCSA’07). Daegu, Korea, pp 441–450
Kato S, Yamasaki N (2008) Portioned EDF-based scheduling on multiprocessors. In: Proceedings of the 8th ACM/IEEE International Conference on Embedded Software (EMSOFT’08). Atlanta, GA, USA, pp 139–148
Kato S, Yamasaki N (2009) Semi-partitioned scheduling of sporadic task systems on multiprocessors. In: Proceedings of the 21st Euromicro Conference on Real-Time Systems (ECRTS’09). Dublin, Ireland, pp 239–248
Lakshmanan K, Rajkumar R, Lehoczky J (2009) Partitioned fixed-priority preemptive scheduling for multi-core processors. In: Proceedings of the 21st Euromicro Conference on Real-Time Systems (ECRTS 09). Dublin, Ireland, pp 239–248
Liu CL, Layland JW (1973) Scheduling algorithms for multiprogramming in a hard-real-time environment. J ACM 20(1):46–61
Lunniss W, Altmeyer S, Maiza C, Davis R (2013) Integrating cache related pre-emption delay analysis into EDF scheduling. In: Proceedings of the 19th IEEE Real-Time and Embedded Technology and Applications Symposium (RTAS’13). Philadelphia, PA, USA, pp 75–84
PREEMPT-RT: Real-time Linux wiki (2012). https://rt.wiki.kernel.org/
Puaut I, Pais C (2007) Scratchpad memories vs locked caches in hard real-time systems: a quantitative comparison. In: Proceedings of the Conference on Design, Automation and Test in Europe (DATE’07). Nice, France, pp 1484–1489
Ripoll I, Crespo A, Mok A (1996) Improvement in feasibility testing for real-time tasks. Real-Time Syst 11(1):19–39
Sousa PB, Andersson B, Tovar E (2010) Implementing slot-based task-splitting multiprocessor scheduling. Technical report HURRAY-TR-100504, CISTER, Polytechnic Institute of Porto (ISEP-IPP)
Sousa PB, Andersson B, Tovar E (2011a) Implementing slot-based task-splitting multiprocessor scheduling. In: Proceedings of 6th IEEE International Symposium on Industrial Embedded Systems (SIES’11). Vasteras, Sweden, pp 256–265
Sousa PB, Bletsas K, Andersson B, Tovar E (2011b) Practical aspects of slot-based task-splitting dispatching in its schedulability analysis. In: Proceedings of the 17th IEEE International Conference on Embedded and Real-Time Computing Systems and Applications (RTCSA’11). Toyama, Japan, pp 224–230
Sousa PB, Bletsas K, Tovar E, Andersson B (2011b) On the implementation of real-time slot-based task-splitting scheduling algorithms for multiprocessor systems. In: Proceedings of the 13th Real-Time Linux Workshop (RTLWS’13). Real-Time Linux Foundation, Prague, Czech Republic, pp 207–218
Sousa PB, Pereira N, Tovar E (2012) Enhancing the real-time capabilities of the Linux kernel. In: 24th Euromicro Conference on Real-Time Systems (ECRTS’12)—work-in-progress session. Pisa, Italy
Spuri M (1996) Analysis of deadline scheduled real-time systems. Tech. rep, INRIA
Zhang F, Burns A (2009) Improvement to quick processor-demand analysis for EDF-scheduled real-time systems. In: Proceedings of the 21st IEEE Euromicro Conference on Real-Time Systems (ECRTS’ 09), pp 76–86
Acknowledgments
This work was partially supported by National Funds through FCT (Portuguese Foundation for Science and Technology) and by ERDF (European Regional Development Fund) through COMPETE (Operational Programme ‘Thematic Factors of Competitiveness’), within project(s) FCOMP-01-0124-FEDER-037281 (CISTER), FCOMP-01-0124-FEDER-020447 (REGAIN); by FCT and the EU ARTEMIS JU funding, within project ARTEMIS/0003/2012, JU grant number 333053 (CONCERTO); by the European Union, under the Seventh Framework Programme (FP7/2007-2013), grant agreement number 611016 (P-SOCRATES), by FCT and ESF (European Social Fund) through POPH (Portuguese Human Potential Operational Program), under PhD grant SFRH/BD/46199/2008.
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Sousa, P.B., Bletsas, K., Tovar, E. et al. Unified overhead-aware schedulability analysis for slot-based task-splitting. Real-Time Syst 50, 680–735 (2014). https://doi.org/10.1007/s11241-014-9204-x
Published:
Issue Date:
DOI: https://doi.org/10.1007/s11241-014-9204-x