Applying the Framework

• The theory gives competitive behavior with up to O(log n) reassignments per job.
• It assumes that any job can move to any machine at any time.
• We developed the Enhanced Mosix Strategy. It breaks from the theory by observing the same limits on reassignment that the Mosix system’s implementation imposes.

Previous slide

Next slide

Back to first slide

View graphic version

In the original theory, the system can reassign jobs whenever a job completes and leaves the system. It reassigns a job from machine m to machine n if the marginal cost for putting the job on n is less than half the marginal cost paid when the job was originally assigned to m.

We elected to change this. Instead of keeping track of the original cost for a job, we reassign jobs to greedily minimize the system cost at the time of the decision. This can result in more reassignments per job. However, the cost for job reassignment on a system like Mosix is actually quite small.