A novel view on bounding execution demand under mixed-criticality EDF
- PDF / 1,921,556 Bytes
- 40 Pages / 439.37 x 666.142 pts Page_size
- 53 Downloads / 154 Views
A novel view on bounding execution demand under mixed‑criticality EDF Mitra Mahdiani1 · Alejandro Masrur1 Accepted: 30 September 2020 © The Author(s) 2020
Abstract In this paper, we are concerned with scheduling a mix of high-criticality (HI) and low-criticality (LO) tasks under Earliest Deadline First (EDF) on one processor. To this end, the system implements two operation modes, LO and HI mode. In LO mode, HI tasks execute for no longer than their optimistic execution budgets and are scheduled together with the LO tasks. The system switches to HI mode, where all LO tasks are prevented from running, when one or more HI tasks run for longer than expected. Since these mode changes may happen at arbitrary points in time, it is difficult to find an accurate bound on carry-over jobs, i.e., those HI jobs that were released before, but did not finish executing at the point of the transition. To overcome this problem, we propose a technique that works around the computation of carry-over execution demand. Basically, the proposed technique separates the schedulability analysis of the transition between LO and HI mode from that of stable HI mode. We prove that a transition from LO to HI mode is feasible, if an equivalent task set derived from the original is schedulable under plain EDF. On this basis, we can apply approximation techniques such as, e.g., the well-known Devi’s test to derive further tests that trade off accuracy versus complexity/runtime. Finally, we perform a detailed comparison with respect to weighted schedulability on synthetic data illustrating benefits by the proposed technique. Keywords Real-time scheduling · Admission control · Mixed criticality · EDF-VD · Resource efficiency · Weighted schedulability
1 Introduction There is increasingly important trend in domains such as automotive systems, avionics, and medical engineering towards integrating functions with different levels of criticality onto a common hardware platform. This allows for a reduction of costs * Mitra Mahdiani [email protected]‑chemnitz.de 1
Department of Computer Science, TU Chemnitz, Chemnitz, Germany
13
Vol.:(0123456789)
Real-Time Systems
and complexity, however, it leads to mixed-criticality (MC) systems that require careful design and analysis. In particular, it must be guaranteed that high-criticality (HI) functions/tasks are not affected by low-criticality (LO) tasks that share the same resources. In this paper, we are concerned with scheduling a mix of HI and LO tasks under EDF and on one processor—however, a discussion for more levels of criticality is presented in the appendix. In particular, we make use of Vestal’s task model (Vestal 2007). That is, LO tasks are modeled by only one worst-case execution time (WCET) (apart from inter-arrival time and deadline), while HI tasks are characterized by an optimistic and by a conservative WCET to account for potential increases in execution demand (Vestal 2007). In this context, a standard real-time scheduling requires guaranteeing that LO and HI tasks meet
Data Loading...
