On Bounding Execution Demand under Mixed-Criticality EDF

ABSTRACT

This paper is concerned with mixed-criticality systems where a set of low-criticality (LO) and high-criticality (HI) tasks share one processor and are scheduled under the EDF algorithm. Basically, the system operates in two modes: LO and HI mode. In LO mode, one HI task may exceed its execution budget, which then causes a change to HI mode in the system. HI tasks are assigned larger execution budgets in HI mode at the cost of the LO tasks --- which are assumed to be discarded. Since these mode changes may happen at arbitrary points in time, it is difficult to find an accurate bound on the amount of carry-over execution demand. That is the execution demand by HI jobs that were released before, but did not finish executing at the point of changing to HI mode. As a consequence, the resulting characterization of the overall execution demand becomes pessimistic. In this paper, to overcome this problem, a technique is proposed that works around the computation of carry-over execution demand and results in a more accurate bound on execution demand under mixed-criticality EDF. In principle, the proposed technique consists in separating the schedulability analysis of stable HI mode from that of the transition between modes and deriving a separate demand bound function for the latter case. The proposed technique results not only in a considerably simpler, but also tighter bound on execution demand under mixed-criticality EDF, in particular, as the number of HI tasks increases. We illustrate this analytically and by a large set of experiments based on synthetic data.

References

1. S. Baruah, V. Bonifaci, G. D'Angelo, H. Li, A. Marchetti-Spaccamela, S. van der Ster, and L. Stougie, "The pre-emptive uniprocessor scheduling of mixed-criticality implicit-deadline sporadic task systems," in Proc. of Euromicro Conference on Real-Time Systems (ECRTS), 2012.
2. P. Ekberg and W. Yi, "Bounding and shaping the demand of mixed-criticality sporadic tasks," in Proc. of Euromicro Conference on Real-Time Systems (ECRTS), 2012.
3. A. Easwaran, "Demand-based scheduling of mixed-criticality sporadic tasks on one processor," in Proc. of Real-Time Systems Symposium (RTSS), Dec. 2013.
4. S. Vestal, "Preemptive scheduling of multi-criticality systems with varying degrees of execution time assurance," in Proc. of Real-Time Systems Symposium (RTSS), 2007.
5. S. Baruah, A. Burns, and R. Davis, "Response-time analysis for mixed criticality systems," in Proc. of Real-Time Systems Symposium (RTSS), 2011.
6. S. Baruah, V. Bonifaci, G. D'Angelo, A. Marchetti-Spaccamela, S. Van Der Ster, and L. Stougie, "Mixed-criticality scheduling of sporadic task systems," in Proc. of European Symposium on Algorithms (ESA), 2011.
7. S. Baruah, V. Bonifaci, G. D'angelo, H. Li, A. Marchetti-Spaccamela, S. Van Der Ster, and L. Stougie, "Preemptive uniprocessor scheduling of mixed-criticality sporadic task systems," Journal of the ACM (JACM), vol. 62, no. 2, 2015.
8. P. Ekberg and W. Yi, "Bounding and shaping the demand of generalized mixed-criticality sporadic task systems" Real-Time Systems (RTS), vol. 50, no. 1, 2014.
9. P. Huang, P. Kumar, G. Giannopoulou, and L. Thiele, "Run and be safe: Mixed-criticality scheduling with temporary processor speedup," in Proc. of Design, Automation and Test in Europe (DATE), March 2015.
10. H. Su and D. Zhu, "An elastic mixed-criticality task model and its scheduling algorithm," in Proc. ofDesign, Automation and Test in Europe (DATE), 2013.
11. T.-W. Kuo and A. K. Mok, "Load adjustment in adaptive real-time systems," in Proc. of Real-Time Systems Symposium (RTSS), 1991.
12. Q. Zhao, Z. Gu, and H. Zeng, "PT-AMC: Integrating Pre-emption Thresholds into Mixed-Criticality Scheduling," in Proc. of Design, Automation and Test in Europe (DATE), 2013, pp. 141--146.
13. Y. Wang and M. Saksena, "Scheduling fixed-priority tasks with pre-emption threshold," in Proc. of Real-Time Computing Systems and Applications (RTCSA), 1999.
14. A. Masrur, D. Müller, and M. Werner, "Bi-level deadline scaling for admission control in mixed-criticality systems," in Proc. of IEEE International Conference on Embedded and Real-Time Computing Systems and Applications (RTCSA), Aug. 2015.
15. S. Baruah, B. Chattopadhyay, H. Li, and I. Shin, "Mixed-criticality scheduling on multiprocessors," Real-Time Systems (RTS), vol. 50, 2013.
16. R. Pathan, "Schedulability analysis of mixed-criticality systems on multiprocessors," in Proc. of Euromicro Conference on Real-Time Systems (ECRTS), 2012.
17. A. Burns and R. Davis, "Mixed criticality systems - a review," Department of Computer Science, University of York, Tech. Rep., 2015.
18. S. Baruah, A. Mok, and L. Rosier, "Preemptively scheduling hard-real-time sporadic tasks on one processor," in Proc. of Real-Time Systems Symposium (RTSS), Dec. 1990.
19. E. Bini and G. Buttazzo, "Biasing effects in schedulability measures," in Proc. of Euromicro Conference on Real-Time Systems (ECRTS), 2004.
20. E. Bini, "Measuring the performance of schedulability tests," Real-Time Systems (RTS), vol. 30, no. 1-2, 2005.

Index Terms

• Computer systems organization

  • Real-time systems

    • Real-time operating systems

    • Real-time system specification