Exploiting Process Lifetime Distributions for Dynamic Load Balancing

We propose a preemptive migration scheme that assumes no prior knowledge about the behavior of processes, and show that it significantly outperforms more traditional non-preemptive migration schemes. Our scheme migrates a process only if the process' expected remaining lifetime justifies the cost of migration. To quantify this heuristic, we perform empirical studies on the distribution of process lifetimes and the distribution of memory use (which dominates migration cost) for a variety of workloads. We use these results to derive a robust criterion for selecting processes for migration. Using a trace-driven simulation based on actual job arrival times and lifetimes, we show that under our preemptive policy the mean slowdown of all processes is 40% less than under an optimistic non-preemptive migration scheme that uses name lists. Furthermore, the preemptive policy reduces the number of severely delayed processes by a factor of ten, compared with the non-preemptive scheme.

ICSI Technical Report TR-95-021

Technical Report