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