Feasibility Analysis and Design of Real-Time Systems
Nasro Min‐Allah · 2008
This work presents a collection of feasibility conditions for the online analysis of periodic task systems, mainly, under fixed priority scheduling policy. The first proposed test called enhanced time demand analysis (ETDA) is an efficient algorithm that confines testing schedulability of task to a reduced set of actual points as compared to the classic time demand analysis (TDA). The hybrid test (HT) is another exact condition constituted by combining sufficient condition and necessary and sufficient condition, taken from existing literature, which greatly reduces the analysis time of periodic task sets. To further reduce the analysis time of these systems a promising alternative is shown to be the replacement of the current highest priority first approach with lowest priority first(LPF) order. The effect of making the task deadlines harmonic is also observed and a couple of exact conditions are evolved with this formulation. The first condition is focusing on testing task feasibility at a single scheduling point, while the second test provides a utilization based exact test with $O(n)$ complexity. Both are intended for systems having harmonic deadlines. Most of the current scheduling techniques are based on theassumption that the number of priority levels supported by the underlying hardware is infinite. However, due to many considerations such as economic, enormous systems do exist, where the number of priority levels is limited and this area of limited priority remains relatively unexplored, in contrast to unlimited counter part. In order to accommodate such systems, transformation mechanism are used to convert an unlimited priority feasible task system into the one that can be executed with limited priority levels, however this transformation comes at the price; the newly created set might become infeasible. Care is required for such transformation so that the feasibility of the original set should be guaranteed even with limited priority levels by acquiring the lower number of priority levels required. The mechanism is explained in detail in this work and the feasibility of the unlimited priority feasible task set is kept intact with limited . Power consumption is an important issue in the design of latest real-time embedded systems, where the core processor consumes a large amount of the total system energy. On one front, the complex requirements of latest devices make them power hungry while on the other front the improvement in battery technologies is prohibited due to its fundamental limitations. Since no breakthrough is expected in near future, the focus is shifted to utilizing the battery power more efficiently. Much research is focused on the power reduction of the current dynamic voltage scaling enabled processor at the expense of system responsiveness. In latest devices, especially in interactive hand held devices, responsiveness is of higher importance than energy saving. Hence, a useful scheduling policy should account for system responsiveness as well as power reduction. A solution is also proposed for handling mixed workload such that system performance is bounded by its deadline, in addition to a survey of DVS techniques into real-time scheduling theory. In the last part of the thesis, we endeavor to present the concept of generalized bound of task schedulability to chalk out the specification requirements of a system under investigation in a formal way. Since schedulability of a periodic system is sensitive to task parameter, multiple parameters are exploited by the system designer at design time for maximizing some objective function such as increasing processor utilization or reducing the power consumptions of the systems. These parameters include task period, deadline and execution times. The task periods are usually set by the system requirements, but deadline and computation times can be modified in order to improve system performance. Under priority based scheduling, such sensitivity analysis has focused on changing the task execution times and deadlines, however no optimal solution is known as yet, prior to this work. We transform the given list of inequalities linked through logical OR conditions into a single inequality. This inequality becomes a constraint of task schedulability, which can be solved with nonlinear programming techniques for obtaining optimal task execution times that can be applied at design time for minimizing some objective function such as energy consumption or system utilization. The generalized bound provides the facility of finding the optimal values for execution times or processor speed for converting a non-feasible task set into a feasible one.