Revisiting the Schedule Graph Generation for the Exact and Sustainable Analysis of Non-preemptive Scheduling

Marek Vlk, Marek Jaroš, Zdeněk Hanzálek · 2024

Read Revisiting the Schedule Graph Generation for the Exact and Sustainable Analysis of Non-preemptive Scheduling by Marek Vlk, Marek Jaroš, Zdeněk Hanzálek (2024) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2411-00877.txt.

Description

Abstract This paper addresses the problem of scheduling non-preemptive tasks with release jitter and execution time variation on a uniprocessor. We show that the schedulability analysis based on schedule graph generation, proposed by Nasri and Brandenburg [RTSS 2017], produces negative results when it could be easily avoided by slightly reformalizing the notion of non-work-conserving policies.

Catalog record

CREATORMarek Vlk, Marek Jaroš, Zdeněk Hanzálek
YEAR2024
COLLECTIONPAPERS
FORMATTXT
FILE SIZE52 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2411-00877

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Revisiting the Schedule Graph Generation for the Exact and Sustainable Analysis of Non-preemptive Scheduling Marek Vlk, Marek Jaroš, Zdeněk Hanzálek Abstract This paper addresses the problem of scheduling non-preemptive tasks with release jitter and execution time variation on a uniprocessor. We show that the schedulability analysis based on schedule graph generation, proposed by Nasri and Brandenburg [RTSS 2017], produces negative results when it could be easily avoided by slightly reformalizing the notion of non-work-conserving policies. In this work, we develop a schedulability analysis that constructs the schedule graph using new job-eligibility rules and is exact and sustainable for both work-conserving and enhanced formalization of non-work-conserving policies. Besides, the experimental evaluation shows that our schedulability analysis is substantially faster. keywords online scheduling, release jitter, schedulability analysis, schedule abstraction graph 1 Introduction Ensuring the temporal correctness of safety-critical real-time systems is a fundamental challenge, often addressed through response-time analysis (RTA). The primary objective of RTA is to ascertain the worst-case response time (WCRT) for a set of jobs scheduled by a given policy on computing resources. A real-time system is schedulable if the WCRT of each job does not exceed its deadline. However, the complexity of the RTA problem escalates, particularly for periodic tasks scheduled by a job-level fixed-priority policy, even on a uniprocessor platform, rendering most variations of the problem \mathcal{NP} -hard Ekberg (2020) or co- \mathcal{NP} -hard Baruah and Goossens (2004) . This computational intractability not only poses formidable theoretical challenges but also hampers the practical application of these scheduling policies in real-world safety-critical systems. As such, there is a pressing need to delve into innovative approaches that not only address the inherent complexity but also pave the way for more efficient and scalable analyses, thereby facilitating the dependable design and implementation of safety-critical real-time systems. While there are efficient algorithms for scheduling preemptive tasks Park and Cho (2004) , the difficulty of scheduling non-preemptive tasks with release jitter and execution time variation lies in the fact that it may exhibit anomalies, i.e., the scenario deemed worst-case does not result in a deadline miss, but a different scenario does. A schedulability analysis is sustainable if any problem instance deemed schedulable by the analysis is schedulable not only for the worst-case but for all conceivable scenarios Baruah and Burns (2006) . 1.1 Related Work The conventional methods employed for sustainable schedulability analyses involve a pessimistic over-approximation of the true worst-case scenario with contrived situations that may be unrealistic at runtime. For instance, in the traditional RTA applied to non-preemptive fixed-priority scheduling Davis et al. (2007) ; Tindell et al. (1994) , the bound on the response time of a task is derived assuming that, in the worst case, a job experiences maximal blocking from lower-priority jobs and maximal interference from higher-priority jobs, which may be overly pessimistic for periodic tasks. On the contrary, the potential for exact and sustainable analysis results is offered by alternative approaches that are based on model checking (e.g., Guan et al. (2007) ; Sun and Lipari (2016) ) or exhaustive exploration of all system states Burmyakov et al. (2015) ; Baker and Cirinei (2007) ; Bonifaci and Marchetti-Spaccamela (2012) . Nonetheless, these approaches grapple with significant state-space explosion issues, making them impractical even for small problem instances. Recently, a new branch of research emerged, centered around the concept of the schedule graph Nasri and Brandenburg (2017) . The schedule graph (or schedule abstraction graph) abstracts the space of available decisions that can be taken by a given scheduler when dispatching a set of jobs onto a resource. This exploration of decision space involves constructing a combinatorial graph where nodes correspond to the state of the resource after the execution of a set of jobs, and whose edges correspond to possible scheduling decisions (which is to determine a job to be processed next) that shape the transition of the system states. Throughout the construction of the graph, the response time of each job dispatched along an edge is examined. Upon completing the graph, the method thus yields the minimum and maximum response time for each job across all scenarios. Since their seminal work on a uniprocessor Nasri and Brandenburg (2017) , the notion of the schedule graph has been extended to global scheduling (multiple processors) Nasri et al. (2018) and global scheduling with precedences Nasri et al. (2019) ; Nogd et al. (2020) . The methodology has been improved by a so-called partial order reduction, which is applicable to the problems both with Ranjha et al. (2022) and without Ranjha et al. (2023) precedences. A key strength of the schedule graph lies in its ability to accommodate non-work-conserving policies, known for their significant schedulability advantages Nasri and Kargahi (2014) ; Nasri and Fohler (2016) . However, Nasri and Brandenburg (2017) is the only work addressing the non-work-conserving policies using the schedule graph. The authors devised a schedule graph generation algorithm that is exact and sustainable for both work-conserving and non-work-conserving policies. Despite these claims, our investigation has revealed instances where the schedulability analysis used with non-work-conserving policies produces negative results when it could be easily avoided by slightly reformalizing the notion of non-work-conserving policies. 1.2 Outline and Contributions of this Paper We revisit the schedulability analysis for non-preemptive tasks on a uniprocessor proposed in Nasri and Brandenburg (2017) . We refer to the approach presented in Nasri and Brandenburg (2017) as Schedule Graph Analysis with Single Eligibility (SGA-SE). We extend the ideas of SGA-SE and enhance the concept of non-work-conserving policies such that the set of schedulable instances is enlarged. Our new algorithm will be distinguished by being referred to as Schedule Graph Analysis with Multiple Eligibility (SGA-ME). The contributions of this paper are: • discovered easily avoidable pessimism in the schedulability analysis for non-work-conserving policies presented in Nasri and Brandenburg (2017) , • definitions of certainly-eligible and possibly-eligible jobs that lead to a new algorithm for the schedulability analysis that is exact and sustainable for both work-conserving and enhanced formalization of non-work-conserving policies, • the new algorithm implementation that is by an order of magnitude faster than Nasri and Brandenburg (2017) . To maximize the transparency and reproducibility of our results, all the source codes of our implementation and the benchmarking instances are publicly available 1 1 1 https://github.com/redakez/ettt-scheduling . The rest of the paper is organized as follows. Section 2 formally describes the problem. Section 3 focuses on the schedulability analysis whose performance is evaluated in Section 4 . The paper concludes in Section 5 . 2 Problem Description This section gives a formal description of the problem. All variables defined in Section 2 are integers. All proposed algorithms in later sections also work with integer values only. 2.1 Definition of Tasks and Jobs The problem is given by a set of tasks \mathcal{T}=(\mathcal{T}_{1},\dots,\mathcal{T}_{n}) , where each task \mathcal{T}_{i} is specified by period \tau_{i} , the earliest release time r^{min}_{i} , the latest release time r^{max}_{i}\geq r^{min}_{i} , best-case execution time C^{min}_{i} , worst-case execution time C^{max}_{i}\geq C^{min}_{i} , deadline d_{i} and priority p_{i}\geq 0 . Each task \mathcal{T}_{i} consists of a set of jobs J_{i,1},\dots,J_{i,h_{i}} , where J_{i,j} is the j-th job of task \mathcal{T}_{i} and h_{i} is the last job of task \mathcal{T}_{i}

Read the complete text