Mor Harchol-Balter

EECS Department
University of California, Berkeley
Technical Report No. UCB/CSD-94-826
August 1994

http://www2.eecs.berkeley.edu/Pubs/TechRpts/1994/CSD-94-826.pdf

The two decisions defining any dynamic load balancing strategy are:
1. How do we choose a new host (target host) for the migrated process to run on?
2. How do we select which processes to migrate?

Previous load balancing literature has either assumed the process CPU lifetime distribution function is exponential, or has been vague about its properties, and this has greatly influenced the way in which the above two questions have been answered. In this paper we first determine the lifetime distribution function and then explicitly use it in our load balancing strategy.

Our measurements of Unix processes show that the lifetime distribution function varies widely among different workloads, however a rule of thumb (which is far more accurate than assuming an exponential distribution) is
Pr[lifetime > a | lifetime > b ] { = b/a if b >= 1 second > b/a if 2^-6 < b < 1 second

In particular Pr[lifetime > T seconds | lifetime >= 1 second ] = 1/T.

In answering question 1 above, we find that measurements of the loads on all potential target hosts become very stale during the time it takes to migrate the process to its new host. Our solution to this problem is: rather than measure the current load on all potential target hosts, we use our lifetime distribution function to compute the expected future load (i.e. the load T seconds from now, where T is the time until the migrated process arrives at the new host, and is ready to run).

In answering question 2 above, we first analyze previous approaches, for example migrating newborn processes (this solution stems from the misconception that process lifetimes are exponentially distributed). Our lifetime distribution function shows that newborn processes have less than 20% chance of even living for a period equal to the time they spent migrating. We show that we can get away with only migrating processes whose lifetimes exceed four seconds and still have a significant load balancing effect.

BibTeX citation:

@techreport{Harchol-Balter:CSD-94-826,
    Author = {Harchol-Balter, Mor},
    Title = {Process Lifetimes are Not Exponential, more like 1/T: Implications on Dynamic Load Balancing},
    Institution = {EECS Department, University of California, Berkeley},
    Year = {1994},
    Month = {Aug},
    URL = {http://www2.eecs.berkeley.edu/Pubs/TechRpts/1994/5286.html},
    Number = {UCB/CSD-94-826},
    Abstract = {The two decisions defining any dynamic load balancing strategy are:   <br />1. How do we choose a new host (target host) for the migrated process to run on?   <br />2. How do we select which processes to migrate?   <p>Previous load balancing literature has either assumed the process CPU lifetime distribution function is exponential, or has been vague about its properties, and this has greatly influenced the way in which the above two questions have been answered. In this paper we first determine the lifetime distribution function and then explicitly use it in our load balancing strategy. <p>Our measurements of Unix processes show that the lifetime distribution function varies widely among different workloads, however a rule of thumb (which is far more accurate than assuming an exponential distribution) is   <br />Pr[lifetime > a | lifetime > b ] { = b/a if b >= 1 second > b/a if 2^-6 < b < 1 second   <p>In particular Pr[lifetime > <i>T</i> seconds | lifetime >= 1 second ] = 1/T.   <p>In answering question 1 above, we find that measurements of the loads on all potential target hosts become very stale during the time it takes to migrate the process to its new host. Our solution to this problem is: rather than measure the current load on all potential target hosts, we use our lifetime distribution function to compute the expected future load (i.e. the load <i>T</i> seconds from now, where <i>T</i> is the time until the migrated process arrives at the new host, and is ready to run). <p>In answering question 2 above, we first analyze previous approaches, for example migrating newborn processes (this solution stems from the misconception that process lifetimes are exponentially distributed). Our lifetime distribution function shows that newborn processes have less than 20% chance of even living for a period equal to the time they spent migrating. We show that we can get away with only migrating processes whose lifetimes exceed four seconds and still have a significant load balancing effect.}
}

EndNote citation:

%0 Report
%A Harchol-Balter, Mor
%T Process Lifetimes are Not Exponential, more like 1/T: Implications on Dynamic Load Balancing
%I EECS Department, University of California, Berkeley
%D 1994
%@ UCB/CSD-94-826
%U http://www2.eecs.berkeley.edu/Pubs/TechRpts/1994/5286.html
%F Harchol-Balter:CSD-94-826