Load-balancing heuristics and process behavior

Abstract

Dynamic load balancing in a system of loosely-coupled homogeneous processors may employ both judicious initial placement of processes and migration of existing processes to processors with fewer resident processes. In order to predict the possible benefits of these dynamic assignment techniques, we analyzed the behavior (CPU, disk, and memory use) of 9.5 million Unix* processes during normal use. The observed process behavior was then used to drive simulation studies of particular dynamic assignment heuristics. Let F (·) be the probability distribution of the amount of CPU time used by an arbitrary process. In the environment studied we found: (1- F ( x )) ≉ rx ^{- c} , 1.05< c F (·) is far enough from exponential to make exponential models of little use. With a foreground-background process scheduling policy in each processor, simple heuristics for initial placement and processor migration can significantly improve the response ratios of processes that demand exceptional amounts of CPU, without harming the response ratios of ordinary processes.