A desirable property of any real-time system is the guarantee that it will perform at least beyond some pre-specified thresholds defined by system designers. This is usually not a concern under normal situations where analysis has been done offline to ensure system performance based on the regular workload. However, in response to an event such as user’s input or changing environment, the load of the system may dynamically change in such a way that a temporal overload condition occurs. The challenge, then, is to provide some mechanism to guarantee the minimum performance level under such circumstances.
Many periodic real-time task models have been proposed to extend timing requirements beyond the hard and soft deadlines based on the observation that jobs can be dropped without severely affecting performance ([1], [8]). Despite the success of such models in alleviating overload situations, it is sometimes more suitable to execute jobs less often instead of dropping them or allocating fewer cycles.
The work in [9] was among the first to address this type of requirements. Seto, et al. considered the problem of finding a feasible set of task periods as a non-linear programming problem which seeks to optimize a specific form of control performance measure [10]. Cervin et al. used optimization theory to solve the period selection problem online by adaptively adjusting task periods while optimizing a specific form of control performance [5]. Buttazzo and his colleagues proposed an elegant and flexible framework known as the elastic task model [2] where deadline misses are avoided by increasing tasks periods. The work in [4] extends the basic elastic task model to handle cases where the computation time is unknown, [3] incorporated a mechanism to handle resource constraints within the elastic framework, and [7] uses a control performance metric as a cost function to find an optimal sampling interval for each task.
This project focuses its attention on the elastic task model where the selection of task periods is central. The existing elastic scheduling algorithm determines task periods based on an elegant analogy between spring systems and task scheduling in which a task’s resistance to changing its period is viewed as a spring’s resistance to being compressed. In accordance with the principle of least action found in classical mechanics, this suggests that the elastic task model is really attempting to minimize some overall measure of task set’s energy, whose precise nature was not made clear in the original work.
The objective of this project was to generalize Buttazzo's original algorithm [6] to handle a wider class of scheduling problems. The project had several contributions. First, it introduced a general framework which formulates a trade-off between task set schedulability and a specific performance metric (such as task utilization) as an optimization problem. Such a framework allows for real-time systems under temporal overloads to graciously adapt by adjusting their performance level. Second, it proved the optimality of the existing task compression algorithm in [4]. Said algorithm allows for the period selection problem for tasks with deadlines equal periods to be solved optimally in an online manner. Third, the framework is further generalized to consider situations where task deadlines are less than task periods. Fourth, it provides and motivates the use of a framework for solving the deadline selection problem, which can be applied to some control systems with pre-determined sampling time. Finally, the framework can be used to solve other problems where the schedulability-performance trade-off is central. In this regard, generalized elastic scheduling may shed greater light on how best to implement event-triggered feedback control systems [11-12]