Document Open Access Logo

Improving the Schedulability and Quality of Service for Federated Scheduling of Parallel Mixed-Criticality Tasks on Multiprocessors

Author Risat Mahmud Pathan

PDF
Thumbnail PDF

File

LIPIcs.ECRTS.2018.12.pdf
  • Filesize: 0.61 MB
  • 22 pages

Document Identifiers

Author Details

Risat Mahmud Pathan
  • Chalmers University of Technology, Sweden

Funding

This research has been funded by the MECCA project under the ERC grant ERC-2013-AdG 340328-MECCA.

Cite As Get BibTex

Risat Mahmud Pathan. Improving the Schedulability and Quality of Service for Federated Scheduling of Parallel Mixed-Criticality Tasks on Multiprocessors. In 30th Euromicro Conference on Real-Time Systems (ECRTS 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 106, pp. 12:1-12:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018) https://doi.org/10.4230/LIPIcs.ECRTS.2018.12

Abstract

This paper presents federated scheduling algorithm, called MCFQ, for a set of parallel mixed-criticality tasks on multiprocessors. The main feature of MCFQ algorithm is that different alternatives to assign each high-utilization, high-critical task to the processors are computed. Given the different alternatives, we carefully select one alternative for each such task so that all the other tasks can be successfully assigned on the remaining processors. Such flexibility in choosing the right alternative has two benefits. First, it has higher likelihood to satisfy the total resource requirement of all the tasks while ensuring schedulability. Second, computational slack becomes available by intelligently selecting the alternative such that the total resource requirement of all the tasks is minimized. Such slack then can be used to improve the QoS of the system (i.e., never discard some low-critical tasks). Our experimental results using randomly-generated parallel mixed-critical tasksets show that MCFQ can schedule much higher number of tasksets and can improve the QoS of the system significantly in comparison to the state of the art.

Subject Classification

ACM Subject Classification
  • Computer systems organization → Real-time systems
Keywords
  • mixed-criticality systems
  • real-time systems
  • multiprocessor scheduling
  • federated scheduling

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. P. Axer, S. Quinton, M. Neukirchner, R. Ernst, B. Dobel, and H. Hartig. Response-time analysis of parallel fork-join workloads with real-time constraints. In Proc. of ECRTS, 2013. Google Scholar
  2. S. Baruah. Semantics-preserving implementation of multirate mixed-criticality synchronous programs. In Proc. of RTNS, 2012. Google Scholar
  3. S. Baruah. Improved multiprocessor global schedulability analysis of sporadic dag task systems. In Proc. of ECRTS, 2014. Google Scholar
  4. S. Baruah, V. Bonifaci, G. DAngelo, H. Li, A. Marchetti-Spaccamela, S. Van Der Ster, and L. Stougie. The Preemptive Uniprocessor Scheduling of Mixed-Criticality Implicit-Deadline Sporadic Task Systems. In Proc. of ECRTS, 2012. URL: http://dx.doi.org/10.1109/ECRTS.2012.42.
  5. S. Baruah, A. Burns, and Z. Guo. Scheduling mixed-criticality systems to guarantee some service under all non-erroneous behaviors. In Proc. of ECRTS, 2016. URL: http://dx.doi.org/10.1109/ECRTS.2016.12.
  6. S. Baruah, B. Chattopadhyay, H. Li, , and I. Shin. Mixed-criticality scheduling on multiprocessors. Real-Time Syst., 50(1):142-177, 2014. URL: http://dx.doi.org/10.1007/s11241-013-9184-2.
  7. S. Baruah, A. Eswaran, and Z. Guo. MC-Fluid: Simplified and Optimally Quantified. In Proc. of RTSS, 2015. URL: http://dx.doi.org/10.1109/RTSS.2015.38.
  8. S. Baruah, Haohan Li, and L. Stougie. Towards the Design of Certifiable Mixed-criticality Systems. In Proc. of RTAS, 2010. URL: http://dx.doi.org/10.1109/RTAS.2010.10.
  9. S. Baruah and S. Vestal. Schedulability Analysis of Sporadic Tasks with Multiple Criticality Specifications. In Proc. of ECRTS, pages 147-155, 2008. Google Scholar
  10. Sanjoy Baruah, Vincenzo Bonifaci, Alberto Marchetti-Spaccamela, Leen Stougie, and Andreas Wiese. A generalized parallel task model for recurrent real-time processes. In Proc. of RTSS, 2012. Google Scholar
  11. Sanjoy Baruah, Alan Burns, and Robert Davis. Response-time analysis for mixed criticality systems. In Proc. of RTSS, 2011. Google Scholar
  12. V. Bonifaci, A. Marchetti-Spaccamela, S. Stiller, and A. Wiese. Feasibility analysis in the sporadic dag task model. In Proc. of ECRTS, 2013. Google Scholar
  13. A. Burns and S. Baruah. Towards a more practical model for mixed criticality systems. In Proc. of WMC, RTSS, 2013. Google Scholar
  14. A. Burns and R. Davis. Mixed-criticality systems: A review. In (available online), Tenth Edition, January, 2018. URL: http://www-users.cs.york.ac.uk/~burns/review.pdf.
  15. Hoon Sung Chwa, Jinkyu Lee, Kieu-My Phan, A. Easwaran, and Insik Shin. Global edf schedulability analysis for synchronous parallel tasks on multicore platforms. In Proc. of ECRTS, 2013. Google Scholar
  16. François Dorin, Pascal Richard, Michaël Richard, and Joël Goossens. Schedulability and sensitivity analysis of multiple criticality tasks with fixed-priorities. Real-Time Systems, 46:305-331, 2010. Google Scholar
  17. P. Ekberg and Wang Yi. Bounding and shaping the demand of mixed-criticality sporadic tasks. In Proc. of the ECRTS, 2012. Google Scholar
  18. Oliver Gettings, Sophie Quinton, and Robert I. Davis. Mixed criticality systems with weakly-hard constraints. In Proc. of RTNS, 2015. URL: http://dx.doi.org/10.1145/2834848.2834850.
  19. Nan Guan, Pontus Ekberg, Martin Stigge, and Wang Yi. Effective and Efficient Scheduling of Certifiable Mixed-Criticality Sporadic Task Systems. In Proc. of RTSS, 2011. URL: http://dx.doi.org/10.1109/RTSS.2011.10.
  20. Mathieu Jan, Lilia Zaourar, and Maurice Pitel. Maximizing the execution rate of low-criticality tasks in mixed criticality systems. In Proc. of WMC, RTSS, 2013. URL: http://www-users.cs.york.ac.uk/~robdavis/wmc2013/paper6.pdf.
  21. X. Jiang, X. Long, N. Guan, and H. Wan. On the decomposition-based global edf scheduling of parallel real-time tasks. In Proc. of RTSS, 2016. Google Scholar
  22. K. Lakshmanan, S. Kato, and R. Rajkumar. Scheduling parallel real-time tasks on multi-core processors. In Proc. of RTSS, 2010. Google Scholar
  23. J. Lee, K. M. Phan, X. Gu, J. Lee, A. Easwaran, I. Shin, and I. Lee. MC-Fluid: Fluid Model-Based Mixed-Criticality Scheduling on Multiprocessors. In Proc. of RTSS, 2014. URL: http://dx.doi.org/10.1109/RTSS.2014.32.
  24. Haohan Li and S. Baruah. An algorithm for scheduling certifiable mixed-criticality sporadic task systems. In Proc. of RTSS, pages 183-192, 2010. Google Scholar
  25. J. Li, J. J. Chen, K. Agrawal, C. Lu, C. Gill, and A. Saifullah. Analysis of federated and global scheduling for parallel real-time tasks. In Proc. of ECRTS, 2014. Google Scholar
  26. J. Li, J. J. Chen, K. Agrawal, C. Lu, C. Gill, and A. Saifullah. Mixed-criticality federated scheduling for parallel real-time tasks. Real-Time Systems, 53(5):760-811, Sep 2017. URL: http://dx.doi.org/10.1007/s11241-017-9281-8.
  27. J. Li, D. Ferry, S. Ahuja, K. Agrawal, C. Gill, and C. Lu. Mixed-criticality federated scheduling for parallel real-time tasks. In Proc. of RTAS, April 2016. URL: http://dx.doi.org/10.1109/RTAS.2016.7461340.
  28. Jing Li, K. Agrawal, Chenyang Lu, and C. Gill. Analysis of global edf for parallel tasks. In Proc. of ECRTS, 2013. Google Scholar
  29. Di Liu, Jelena Spasic, Gang Chen, Nan Guan, Songran Liu, Todor Stefanov, and Wang Yi. EDF-VD Scheduling of Mixed-Criticality Systems with Degraded Quality Guarantees. In Proc. of RTSS, 2016. URL: http://dx.doi.org/10.1109/RTSS.2016.013.
  30. Guangdong Liu, Ying Lu, Shige Wang, and Zonghua Gu. Partitioned multiprocessor scheduling of mixed-criticality parallel jobs. In 2014 IEEE 20th International Conference on Embedded and Real-Time Computing Systems and Applications, pages 1-10, Aug 2014. URL: http://dx.doi.org/10.1109/RTCSA.2014.6910497.
  31. A. Melani, M. Bertogna, V. Bonifaci, A. Marchetti-Spaccamela, and G.C. Buttazzo. Response-time analysis of conditional dag tasks in multiprocessor systems. In Proc. of ECRTS, 2015. Google Scholar
  32. G. Nelissen, V. Berten, J. Goossens, and D. Milojevic. Techniques optimizing the number of processors to schedule multi-threaded tasks. In Proc. of ECRTS, pages 321-330, July 2012. URL: http://dx.doi.org/10.1109/ECRTS.2012.37.
  33. OpenMP. Openmp application program interface. version 4.0. 2013. Google Scholar
  34. R. Pathan. Improving the quality-of-service for scheduling mixed-criticality systems on multiprocessors. In Proc. of ECRTS, 2017. Google Scholar
  35. A. Saifullah, K. Agrawal, Chenyang Lu, and C. Gill. Multi-core real-time scheduling for generalized parallel task models. In Proc. of RTSS, 2011. Google Scholar
  36. H. Su, N. Guan, and D. Zhu. Service guarantee exploration for mixed-criticality systems. In Proc. of RTCSA, 2014. URL: http://dx.doi.org/10.1109/RTCSA.2014.6910499.
  37. H. Su and D. Zhu. An elastic mixed-criticality task model and its scheduling algorithm. In Proc. of DATE, 2013. URL: http://dx.doi.org/10.7873/DATE.2013.043.
  38. S. Vestal. Preemptive Scheduling of Multi-criticality Systems with Varying Degrees of Execution Time Assurance. In Proc. of RTSS, pages 239-243, 2007. URL: http://dx.doi.org/10.1109/RTSS.2007.47.
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact