Suggest a scheme for balancing the load on a set of computers. You should discuss: i) what user or system requirements are met by such a scheme; ii) to what categories of applications it is suited; iii) how to measure load and with what accuracy; and iv) how to monitor load and choose the location for a new process. Assume that processes may not be migrated. How would your design be affected if processes could be migrated between computers? Would you expect process migration to have a significant cost?

Question

What will be an ideal response?

Answer 1

The following brief comments are given by way of suggestion, and are not intended to be comprehensive:
i) Examples of requirements, which an implementation might or might not be designed to meet: good
interactive response times despite load level; rapid turnaround of individual compute-intensive jobs;
simultaneous scheduling of a set of jobs belonging to a parallel application; limit on load difference between
least- and most-loaded computers; jobs may be run on otherwise idle or under-utilized workstations; high
throughput, in terms of number of jobs run per second; prioritization of jobs.
ii) A load-balancing scheme should be designed according to a job profile. For example, job behaviour (total
execution time, resource requirements) might be known or unknown in advance; jobs might be typically
interactive or typically compute-intensive or a mixture of the two; jobs may be parts of single parallel
programs. Their total run-time may on average be one second or ten minutes. The efficacy of load balancing
is doubtful for very light jobs; for short jobs, the system overheads for a complex algorithm may outweigh the
advantages.
iii) A simple and effective way to measure a computer’s load is to find the length of its run queue. Measuring
load using a crude set of categories such as LIGHT and HEAVY is often sufficient, given the overheads of
collecting finer-grained information, and the tendency for loads to change over short periods.
iv) A useful approach is for computers whose load is LIGHT to advertise this fact to others, so that new jobs
are started on these computers.
Because of unpredictable job run times, any algorithm might lead to unbalanced computers, with a temporary
dearth of new jobs to place on the LIGHT computers. If process migration is available, however, then jobs can
be relocated from HEAVY computers to LIGHT computers at such times. The main cost of process migration
is address space transfer, although techniques exist to minimise this [Kindberg 1990]. It can take in the order
of seconds to migrate a process, and this time must be short in relation to the remaining run times of the
processes concerned.