Modeling, assignment and scheduling of tasks in distributed real-time systems.
D.-T. Peng · Deep Blue (University of Michigan) · 1990
This thesis presents an integrated approach to the modeling, assignment and scheduling of tasks in distributed real-time systems. It is important to rigorously analyze and design such a system because any incorrect operation may lead to a serious consequence, such as loss of human lives. A new performance measure, called the system hazard, or the maximum normalized task response time, is used. The system hazard is a better measure than simply meeting task deadlines because it also indicates how early tasks can be completed before their deadlines. For a single processor with only independent periodic tasks, optimal scheduling algorithms with respect to the system hazard are derived for both static and dynamic cases. Two best bounds of processor utilization for these optimal algorithms are also computed. The scheduling of dependent periodic tasks in a distributed system is treated as a Multi-Project scheduling problem (MPSP). The MPSP is solved by a branch-and-bound (B&B) algorithm where dominance properties and lower-bound costs are derived for an optimal scheduling. Demonstrative examples and computational experiences are given. Based on the exact system hazard of a complete assignment, an optimal solution to the problem of allocating (or assigning and scheduling) periodic tasks to the processing nodes (PNs) of a distributed real-time system is carried out. The solution approach used is another B&B algorithm. Following the allocation of tasks, a continuous-time Markov Chain (CTMC) model is constructed for the concurrent execution of the assigned tasks. Tasks in each PN are first decomposed into activities. The activities and precedence constraints among them are then modeled by a Generalized Stochastic Petri Net (GSPN), from which a sequence of homogeneous CTMCs is built. The CTMC model is useful for the study of various design and analysis issues in distributed real-time systems, such as a combined task and message scheduling problem (TMSP). Using the CTMC model, the TMSP is formulated as a Semi-Markov Decision Process to minimize the expected number of tasks missing deadlines. Optimal centralized and sub-optimal decentralized solutions to the TMSP are derived using the dynamic programming technique.