A model for distributed dynamic progress management
Li-Wen Chen · 1991
The problem of paradoxical performance behavior is a fundamental problem for distributed load management. This performance behavior can cause the concurrent programs not performance portable across different performance environments. We proposed a conceptual model, called virtual architecture, that provides the platform for programmers to design and tune their programs. This model allows the programmers to plan how their programs should progress on a virtual architecture. Distributed load management should support progress portability. In virtual architecture model, the operating system is engaged in progress management instead of load balancing. The operating system will do its best to maintain balanced progress for a concurrent program in any performance environment. As a result, same event ordering can be maintained and the effect of any changes in the performance environment can be smoothly distributed to the whole program. A new kind of operating system, called the Virtual Time Operating System (VTOS), that supports the notions of virtual architecture and progress portability is proposed. We cover the following topics: representation of virtual clocks, neighborhood partitioning, virtual time scheduling, and load/progress management policies based on virtual time. A testbed, called the KLOX testbed, that includes these features is implemented in order to verify our approach. We implement a KLOX kernel that supports transparent process migration. We conduct a number of experiments on the KLOX testbed. Four synthetic benchmarks are provided: Multiple Pipeline, Tree Merge, Tree Broadcast, and Client-server. We emulate seven different real machine architectures by controlling the amount of available processor cycles in each processor. Our experiments show that traditional load balancing policies can cause paradoxical performance behavior, and the progress management policy that support virtual architecture can prevent the paradoxical performance behavior. The VTSDB policy performs very well for most of the experiments we performed compared to the rest of the load/progress management policies. The PUB policy can perform well only when the performance-critical processes always consume more processor cycles than the non-performance-critical ones. (Abstract shortened with permission of author.)