Adaptive Real-Time Scheduling in Distributed Environments

Distributed computing environments have become the dominant operation environment in many control and communications embedded applications. This increasing popularity is due to what this environment offers in the sense of improved performance through multi-processing, connectivity through geographical location distribution, scalability and portability through modularity, availability and reliability through resource replication, and cost effectiveness. Distributed embedded applications require a wide range of Quality of Service (QoS) guarantees from the underlying system. QoS guarantees range from best effort performance required by non-real-time and soft real-time applications to the prior guarantee to meet all timing requirements and deadlines requested by hard real-time applications. To provide timing guarantees for real-time distributed applications, both individual nodes’ operating systems as well as the network management system must collaborate to provide an end-to-end QoS enforcement of the global system’s timing feasibility.

We developed a framework for scheduling and dispatching a distributed set of hard real-time tasks with relative timing constraints. The proposed algorithm combines the scheduling of computation and communication resources. It provides guarantees for satisfying timing constraints for hard real-time tasks while maintaining flexibility to adapt to run-time variations. We extend the time-based parametric scheduling method (Gerber et al., 1995; Saksena, 1994; Choi and Agrawala, 1997) to make it applicable to a distributed real-time task set. Our scheduling approach verifies the schedulability of hard real-time tasks off-line and generates parametric calendars for dispatching
task instances at run-time. We also present a novel distributed dispatching mechanism that uses the parametric calendars to maximize the available slack-time at any given time. The increased slack time enhances the system’s responsiveness to aperiodic and sporadic tasks and boosts the system’s robustness in face of unexpected load variations. The dispatching mechanism incorporates novel synchronization and external-event handling methods to coordinate distributed resource sharing and concurrent task execution.

The schedulability verification process is performed off-line and assumes that the task-to-node assignment, timing constraints, and communication parameters of all hard real-time tasks are known prior to run-time. Using this information, the scheduler constructs the distributed scheduling problem (figure a). The scheduler starts by validating the feasibility of all end-to-end communication constraints (figure b). Next, it maps the distributed problem into a single-node parametric scheduling problem (figure c). This is done by generating a global order for all the tasks in the system, and then using this order to create a unified global constraint graph. Then, the scheduler applies the cyclic parametric scheduling methodology (parametric scheduling for periodic tasks) to the single-node problem to verify its feasibility (figure 6.c). Finally, it maps the schedulability results back to the distributed task set. For feasible systems, the scheduler calculates parametric calendars for dispatching task instances at run-time (figure d).