Integrated Scheduling of Tasks and Messages in Distributed Real-Time Systems

Abstract

The demand for more and more complex real-time applications which require high computational needs with timing constraints, and geographical distribution of computational entities (tasks) of these applications, have led to the choice of distributed systems as a natural candidate for supporting such real-time applications, due to their potential for high performance and reliability. The distributed real-time system considered here consists of uniprocessor or multiprocessor nodes connected through a multihop network. Scheduling of tasks in such a system involves scheduling of dynamically arriving tasks within a node(local scheduling), migration of tasks across the network(global scheduling) if it is not possible to schedule them locally, and (iii) scheduling of messages on communication links(message scheduling)to support inter-task communication and task migration. Most of the existing schemes on scheduling in distributed real-time systems have addressed each of these issues in isolation. Moreover, these schemes consider the load on the processors at a node as the basis to migrate tasks from a heavily loaded node(sender) to a lightly loaded node(receiver). We believe that the identification of a receiver node should be based not only on the load of its processors, but also on the availability of a path, which satisfies the bandwidth required for the task migration, from the sender to that receiver. In this paper, we present an integrated framework for scheduling dynamically arriving real-time tasks in distributed real-time systems. Our proposal consists of (i) algorithms for global scheduling and (ii) interactions among the three schedulers in a way to improve the schedulability of the system. The effectiveness of the proposed framework has been