Optimal work-conserving scheduler synthesis for real-time sporadic tasks using supervisory control of timed discrete-eve
- PDF / 1,560,065 Bytes
- 14 Pages / 595.276 x 790.866 pts Page_size
- 92 Downloads / 151 Views
Optimal work-conserving scheduler synthesis for real-time sporadic tasks using supervisory control of timed discrete-event systems Rajesh Devaraj1 · Arnab Sarkar1 · Santosh Biswas1 Accepted: 14 September 2020 © Springer Science+Business Media, LLC, part of Springer Nature 2020
Abstract Real-time scheduling strategies for safety-critical systems are primarily focused on ensuring correctness, both functional and temporal. In order to provide the desired predictability in such systems, it is often advisable that all timing requirements be guaranteed offline, before putting the system into operation. Formal approaches allow for all necessary and sufficiency conditions corresponding to a feasible schedule to be checked in a systematic manner. This enables formal approaches to act as effective mechanisms for providing timing guarantees required by safety-critical systems. In this work, we develop a scheduler synthesis framework for the optimal work-conserving scheduling of dynamically arriving, sporadic tasks using a formal approach known as “supervisory control of timed discrete-event systems” (SCTDES). The synthesis process starts with the construction of a resource-constraint-aware task execution model and a deadline-constraint-aware timing specification model, for each task in the given real-time system. The system model (i.e., composite task execution model) is then derived and transformed to guarantee work-conserving co-execution of tasks. Such a work-conserving approach enables the synthesis of schedules which avoid processor idling in the presence of ready-to-execute tasks. Next, we use the (transformed) system and specification models to obtain a supervisor which can be used to construct an optimal scheduler for the given real-time system. Finally, the applicability of the proposed scheme for real-world scenarios is shown by presenting a case study on an instrument control system (ICS). Keywords Real-time systems · Sporadic task · Optimal scheduling · Supervisory control · Discrete-event systems
1 Introduction Real-time systems basics Buttazzo (2011): Hard real-time systems must ensure guaranteed temporal behavior under all operating conditions, as deadline misses could result in loss of human life, financial loss, or damage to the environment. Applications in real-time systems are typically modeled as recurrent tasks. Each such task typically represents a piece of code (i.e., program) which is triggered by external events. Each execution instance of the task is referred to as a job. A recurrent task may be periodic, aperiodic or sporadic, based
B
Santosh Biswas [email protected] Rajesh Devaraj [email protected] Arnab Sarkar [email protected]
1
Department of Computer Science and Engineering, Indian Institute of Technology Guwahati, Guwahati, Assam, India
on its arrival pattern. Aperiodic tasks have no restriction on the arrival pattern of their jobs. Sporadic tasks are a special case of aperiodic tasks where consecutive jobs must be separated by a specified minimum inter-arrival time. Perio
Data Loading...
