Reliability-driven scheduling for real-time tasks with precedence constraints in heterogeneous distributed systems

Xiao Qin
Griffith University, Australia
xqin@cse.unl.edu

Hong Jiang
Department of Computer Science and Engineering
University of Nebraska-Lincoln
Lincoln, NE 68588-0115, (jiang@cse.unl.edu)

Some work has been done in the past in scheduling tasks in real-time distributed systems, considering schedulability as the main objective function to be maximized. Since real-time distributed systems are more complex than centralized systems, the complexity of such system could increase the potential for system failures. This is even more pronounced in a heterogeneous system where processors operate at different speeds and communication channels have different bandwidths. Hence, reliability should also be regarded as the objective function to be maximized. In this paper, we describe a two-phase scheme to determine a scheduling of tasks with precedence constraints that employs a reliability measure as one of the objectives in a real-time and heterogeneous distributed system. We devise a new off-line scheduling of communicating tasks, based on the concept of reliability cost, to schedule real-time tasks for maximized reliability. The simulation results show that, for task graphs with precedence constraints in a heterogeneous distributed system, our heuristic performs significantly better than the two heuristics presented that do not consider reliabiliy cost. Furthermore, the results suggested that higher computational heterogeneity is conducive to improving the schedulability of the reliability cost-driven (RCD) algorithm, while the opposite is true for the two non-RCD algorithms.

KEY WORDS: Reliability cost, Real-time, Scheduling, Heterogeneous distributed systems, Performance

in Proceedings of the International Conference Parallel and Distributed Computing and Systems 2000, (PDCS 2000), November 6-9, 2000, in Las Vegas, USA

---