Distributed scheduling for a changing environment
Phillip Krueger · Minds at UW (University of Wisconsin) · 1988
Scheduling for distributed computing systems is significantly more complex than that for single-processor systems. In addition to allocating the resources local to a node among the processes residing at that node, a distributed scheduler controls which processes reside at each node. This latter element of distributed scheduling is referred to as load distributing. The activities required for load distributing, most notably transferring processes between nodes, may carry substantial resource overhead. Consequently, the performance benefits that can potentially be achieved through these actions must be weighed against the performance costs that arise as a result of their overhead. In some instances, the cost of an action may exceed its benefit. If many of these ineffective actions are undertaken, overall performance is degraded and the stability of the system is threatened. Therefore, the degree of load distributing that is strived for must be carefully chosen, with the goal of performing as many effective actions as possible, while avoiding those that are ineffective. Unfortunately, as we show, the degree of load distributing that provides the best performance, and the range in degree that maintains system stability, are dependent on characteristics of the system and its workload that may change over time. To be robust over the wide range of system environments that may occur over periods of minutes, hours or days, a load distributing algorithm must adapt in degree. The focus of this dissertation is on the edge of such adaptive load distributing algorithms. Recognizing the diversity of performance objectives and resources available to load distributing algorithms, no attempt is made to design a single algorithm that is in some sense 'general-purpose'. Instead, a framework is developed for adding adaptivity to existing algorithms. As examples, this framework is applied to dissimilar load distributing algorithms with differing performance objectives. Using simulation, the resulting adaptive algorithms are found to improve performance and maintain systems stability over a substantially broader range of system environments.