Hyperperiodic tasks and their scheduling: a new model for the control and monitoring of real-time systems
Chakib Chraibi · 1994
Real-time computer systems refer to computer systems that must perform computations in response to real-world requests or events in a time frame determined by processes in an environment external to the computer. In the so-called hard real-time systems, not meeting the timing constraints of an accepted processing request is considered a system failure and might have severe consequences. This makes regular monitoring of the environment and timely processing of sensed information the most fundamental operation for a real-time system. Hard real-time systems are commonly structured as a set of periodic and nonperiodic tasks with well-defined deadlines. In order to achieve the timing correctness of the system, the goal is then to generate a valid schedule that executes all tasks within their timing requirements. A typical use of periodic tasks is to read sensor data and update the state of the environment. However, the periodic sampling rate is constant regardless of the nature of the process under control (e.g,, discrete or continuous) and the computer processing utilization. Furthermore, periodic sampling may produce distances between consecutive data sensing that are greater than the length of the period. In this dissertation, we propose a new tasking model for real-time sensing and control called hyperperiodic tasks. A hyperperiodic task is one that can be scheduled more frequently when there is a light load on the system, but always recurs at least as frequently as a given hyperperiod. The hyperperiod thus represents the maximum time interval between completions of two consecutive requests of the task. After comparing this new tasking model to the classical models, we derive necessary and sufficient conditions, as well as a preemptive algorithm for the scheduling of hyperperiodic tasks in a single-processor system. Then, we analyze several strategies for the joint scheduling of hyperperiodic and, respectively, aperiodic and periodic tasks. We also study the scheduling of hyperperiodic tasks in a multiprocessor environment using different bin-packing and load balancing methods. Applications to telemetry and multimedia are finally explored as a further research.