Dynamic Time-Based Scheduling for Hard Real-Time Systems

Abstract

In traditional time-based scheduling schemes for real-time systems time line is explicitly managed to obtain a feasible schedule that satisfies all timing constraints. In the schedule the task attributes, such as task start time, are statically decided off-line and used without modification throughout system operation time. However, for dynamic real-time systems, in which new tasks may arrive during the operation, or tasks may have relative constraints based on information only known at run-time, such static schemes may lack the ability to accommodate dynamic changes. Clearly a solution of dynamic real-time scheduling has to reflect the knowledge about tasks and their execution characteristics. In this dissertation we present a {\em dynamic time-based scheduling scheme} and show its applicability for three problem domains. In dynamic time-based scheduling scheme attributes of task instances in the schedule may be represented as functions parameterized with information available at task dispatching time. These functions are called {\em attribute functions} and may denote any attribute of a task instance, such as lower and upper bound of its start time, its execution mode, etc. Flexible resource management becomes possible in this scheme by utilizing the freedom provided by the scheme. First, we study the problem of dynamic dispatching of tasks, reflecting relative timing constraints among tasks. The relative constraints may be defined across the boundary of two consecutive scheduling windows as well as within one scheduling window. We present the solution approach with which we are not only able to test the schedulability of a task set, but also able to obtain maximum slack time by postponing static task executions at run-time. Second, new framework is formulated for designing real-time control systems in which the assumption of fixed sampling period is relaxed. That is, sampling time instants are found adaptively based on physical system state such that a new cost function value is minimized which incorporates computational costs. We show, for linear time-invariant control systems, that the computation requirement can be reduced while maintaining the quality of control. Third, acceptance tests are found for dynamically arriving aperiodic tasks, and for dynamically arriving sporadic tasks, respectively, under the assumption that an Earliest Deadline First scheduling policy is used for resolving resource contention between dynamic and static(dynamic) tasks. Dynamic time-based scheduling scheme can be applied as solution approaches for these problems as will be shown in this dissertation, and its effectiveness will be demonstrated. Also cross-referenced as UMIACS-TR-97-81