Issues in Load Distribution
Load
Resource and CPU queue lengths are good indicators of load.
Artificially increment CPU queue length for transferred jobs on their way.
Set timeouts for such jobs to safeguard against transfer failures.
Little correlation between queue length and CPU utilization for interactive jobs: use utilization instead.
Monitoring CPU utilization is expensive
Modeling -- Poisson Process, Markov process, M/M/1 queue, M/M/N
Classification of Algorithms
Static --
decisions hard-wired into algorithm using prior knowledge of system
Dynamic -- use state information to make decisions.
Adaptive -- special case of dynamic algorithms; dynamically change parameters of the
algorithm
Load Sharing vs. Load Balancing
Load Sharing -- reduce the likelihood of
unshared state by transferring tasks to lightly loaded nodes
Load Balancing -- try to make each load have approximately same load
Preemptive vs. Nonpreemptive
Preemptive transfers -- transfer of a task that is partially executed,
expensive due to collection of task's state
Nonpreemptive transfers -- only transfer tasks that have
not begun execution.
Components of Load Distribution
Transfer policy -- threshold based, determine if a process
should be executed remotely or locally
Selection policy -- which task should be picked, overhead in transfer of
selected task should be offset by reduction in its response time
Location policy -- which node to be sent, possibly use polling to find suitable node
Information policy -- when should the information of other nodes
should be collected; demand-driven, or
periodic, or state-change-driven
Demand-driven:
nodes gather information about other nodes
- sender initiated
- receiver initiated
- symmetrically initiated
State-change-driven :
nodes disseminate information when their state changes
Stability -- queueing-theoretic, or algorithmic perspective
Sender Initiated Algorithms
overloaded node-- when a new task makes the queue length ≥ threshold T
underloaded node -- if accepting a task still maintains queue lenght < threshold T
overloaded node attempts to send task to underloaded node
only newly arrived tasks considered for transfers
location policies:
- random -- no information about other nodes
- threshold -- polling to determine if its a receiver ( underloaded )
- shortest -- a # of nodes are polled at random to determine their
queue length
information policy: demand-driven
stability: polling increases activites; render the system unstable at high load
Receiver Initiated Algorithms
initiated by underloaded nodes
underloaded node tries to obtain task from overloaded node
initiate search for sender either on a task departure or after a
predetermined period
information policy: demand-driven
stability: remain stable at high and low loads
disadvantage: most tasks transfer are preemptive
Symmetrically Initiated Algorithms
senders search for receivers --good in low load situations; but
high polling overhead in high load situations
receivers search for senders --
useful in high load situations,
preemptive task transfer facility is necessary
Stable Symmetrically Initiated Algorithms
use the information gathered during polling to classify
nodes in system as either Sender/overload, Receiver/underload,
or OK
