ANALYTIC MODELS OF ADAPTIVE LOAD SHARING SCHEMES IN DISTRIBUTED REAL-TIME SYSTEMS

In a distributed real-time system, nonuniform task arrivals may tempor arily overload some nodes while leaving some other nodes idle. As a re sult, some of the tasks on an overloaded node may miss their deadlines even if the overall system has the capacity to meet the deadlines of all tasks. In a companion paper [1], we proposed, without any modeling analysis, a decentralized, dynamic load sharing (LS) scheme as a solu tion to this problem. In this paper, we develop analytic queueing mode ls to comparatively evaluate the proposed LS scheme as well as three o ther schemes: no LS, LS with random selection of a receiver node, and LS with perfect information. The evolution of a node's load state is m odeled as a continuous-time semi-Markov process, where cumulative exec ution time (CET), rather than the commonly-used queue length (QL), is employed to describe the workload of a node. Not only fundamental diff erences among the different LS schemes are addressed in the analytic m odels, but also implementation overheads are taken into account Severa l metrics relevant to real-time performance are derived from these mod els: in particular, we evaluate the probability of a task missing its deadline, called the probability of dynamic failure. The proposed sche me is compared against other LS schemes using these performance metric s. The validity of analytic models is checked with simulations. Both a nalytic and simulation results indicate that by using judicious exchan ge/use of state information and Bayesian decision mechanism, the propo sed scheme makes a significant improvement over other existing LS sche mes in minimizing the probability of dynamic failure.