Co-scheduling aperiodic real-time tasks with end-to-end firm and soft deadlines in two-stage systems
- PDF / 4,154,722 Bytes
- 61 Pages / 439.37 x 666.142 pts Page_size
- 120 Downloads / 175 Views
Co‑scheduling aperiodic real‑time tasks with end‑to‑end firm and soft deadlines in two‑stage systems Chang Leng1 · Ying Qiao1 · Xiaobo Sharon Hu2 · Hongan Wang1
© Springer Science+Business Media, LLC, part of Springer Nature 2020
Abstract This paper investigates scheduling methods for two-stage real-time systems (2S-RTSs) that execute aperiodic tasks with firm and soft end-to-end deadlines. 2S-RTSs are often used to capture task execution in reactive systems where the first stage is responsible for detecting and preprocessing irregularly occurring external events and the second stage for taking certain actions to react to the identified situations. Since aperiodic tasks have no regular arrival patterns, it is more appropriate for such 2S-RTS to adopt an online scheduler to make scheduling decisions according to the current system state. We prove that the 2S-RTS scheduling problem is NP-hard, and present a novel share-based heuristic scheduling algorithm, referred to as HS-2S-RTS, to accomplish efficient online scheduling. Different from traditional optimal schedulers that aim to ensure all hard and soft deadline constraints, the goal of HS-2S-RTS consists of ensuring all firm deadline constraints and maximizing the minimum processor share assigned to soft tasks. Since the processor resource assigned to soft tasks is optimized without affecting firm deadline constraints, the schedulability of both firm and soft tasks can be improved. To reduce the actual run-time overhead, we further propose a quasi-shared-based scheduling algorithm, referred to as qHS-2S-RTS, that can achieve equivalent scheduling performance to HS-2S-RTS. We also design a new admission control algorithm for HS-2S-RTS and qHS-2S-RTS, called HSAC-2S-RTS. Simulation results validate our theoretical analysis that qHS-2S-RTS and HS-2S-RTS are able to satisfy all feasible firm deadline constraints while improving the schedulability of soft tasks. Keywords Co-scheduling firm and soft real-time tasks · Two-stage system · End-toend schedule · Processor share assignment
* Chang Leng [email protected] Extended author information available on the last page of the article
13
Vol.:(0123456789)
Real-Time Systems
1 Introduction This paper considers two-stage real-time systems (2S-RTSs). By two-stage systems, we mean that the execution of sub-tasks in the second stage is triggered by the completion of relevant sub-tasks in the first stage. This system model can be found in many reactive systems that must react in real time to external events generated by the environment or affiliated devices (Lano 1995). A typical reactive system has two stages: the first stage detects external events to decide if the situations of interests occur (i.e., monitoring continuously arriving events, discerning situations of interests implied by the sequence of events); the second stage takes certain actions in response to the identified situations. To increase system efficiency and facilitate system evolution, these two stages are usually de-coupled by encapsulating th
Data Loading...
