A SIMULATION STUDY OF DYNAMIC TASK SCHEDULING WITH RESOURCE REQUIREMENTS IN DISTRIBUTED HARD REAL-TIME SYSTEMS

Abstract

Loosely coupled real time distributed systems are becoming more prevalent in applications such as nuclear power plants and process control. These systems contain many tasks which have severe real-time constraints. In fact, these applications require that these tasks have execution deadlines that must be met and are thus said to have hard real-time constraints. Ln_pr_actice many solutions for scheduling used today assume complete and prior knowledge of the task sets,including their deadlines, worst case computation times, precedence relations, and resource requirements. Incor.porati.ng a-ll this knowledge in a static way makes the system inflexible and costly as each system is unique. In this -dissertation the performance of a flexible scheduling algorithm for loosely coupled distributed systems that does not require complete and prior knowledge, is not compute-bound, and quickly adapts to the dynamics of the entire distributed system is studied through simulation. This approach of scheduling in a loosely coupled real-time systems assumes that each node contains a local scheduler, a global scheduler and a dispatcher. At first a heuristic approach for solving the problem of _dynamic scheduling of tasks_loca1-1y in a real-time system where tasks have deadli-nes and resource requirements has been developed. The crux of this approach lies in the heuristic func-tio-n used to select the task to be scheduled next. The heuristic function is composed of three weighted factors. These factors explicitly consider information about real-time constraints of tasks and their utilization of resources. Then a set of heuristic algorithms to schedule tasks that have deadlines and resource requirements in a distributed system have been developed. These algorithms are dynamic and function in decentralized manner. When a task arrives at a node, if an attempt by the local scheduler fails, the scheduling components on individual nodes cooperate to determine which other node in the system has sufficient resourc-e surplus to guarantee the task. Here four algorithms of cooperation are evaluated. They differ in the way a node treats a task that cannot be guaranteed locally. They are 1) Random Scheduling algorithm, 2) Focused Addressing algorithm, 3) Bidding algorithm, and 4) Flexible algorithm. Simulation studies were performed to compare the performance of these algorithms relative to each other as well -as with respect to the baselines.