Distributed Scheduling

1 February 8, 2022
References:
• Mukesh Singhal, Niranjan Shivaratri. “Advanced concepts in
operating systems”. Tata McGraw Hill publication.

2 February 8, 2022
Introduction
Distributed systems offer a tremendous processing
capacity.
however, in order to realize this tremendous computing
capacity, and take full advantage of it, good resource
allocation schemes are needed.
A distributed scheduler is a resource management
components of a distributed operating system that
focuses on judiciously and transparently redistributing
the load of the system among the computers such that
overall performance of the system is maximized.
3 February 8, 2022
Introduction
Due to random arrival of tasks and their random CPU
service time requirements, there is a good possibility that
several computers are heavily loaded (hence suffering
from performance degradation), while others are idle or
lightly loaded.

4 Ms.Reema Patel, Distributed Computing, M.Tech.-I, SVNIT, 2010 February 8, 2022

Introduction

5 February 8, 2022
Introduction
 Goal: To improve the performance of distributed system by appropriately
transferring work from heavily loaded computer to idle or lightly loaded
computer.

Performance of a system
 One of the metric is average response time of task which is the length of the
time interval between its origination and completion.
 Minimizing the average response time is often the goal of load distributing.
Defining a proper characterization of a load at node is very important,
as load distributing decisions are based on the load measured at one or
more nodes.
The mechanism used to measure load imposes minimal overhead.

6 February 8, 2022
Issues in Load Distributing
Several central issues in load distributing
1. Load:
 CPU queue length are good indicators of load .

 As a result , when all the tasks that the node has accepted have arrived , the
node can become overloaded and require further task transfers to reduce its
load.

 Prevention- Artificially increment CPU queue length at a node whenever the node
accepts a remote task.

 Use timeout to avoid anomalies when task transfers fail.

 After the timeout, if the task has not yet arrived, the CPU queue length is
decremented.

7 February 8, 2022
Issues in Load Distributing
2. Classification of load distributing algorithms:

Broadly characterized as:

Static
Decision is hard wired in the algorithm, using a
priory knowledge of the system.
They make no use of system state information (the
loads at nodes).

8 February 8, 2022
Classification of load distributing algorithms
Dynamic
Make use of system state information to make load
distributing decisions
They collect, store and analyze the system state
information.
Impose overhead to the system
Adaptive
Special class of dynamic algorithm
 they adapt their activities by dynamically changing the
parameters of the algorithm to suit the changing system
state
9 February 8, 2022
Issues in Load Distributing
3. Load distributed algorithms can further be classified as Load
balancing vs. Load sharing algorithms

 Both types of algorithms attempt to reduce the likelihood of an

unshared state by transferring tasks to lightly loaded nodes.
 Unshared state : A state in which one computer lies idle while at the same
time tasks argue for service at another computer

• Load balancing algo:

 Attempt to equalize the loads at all computers

10 February 8, 2022
Load balancing vs. Load sharing
• Task transfer are not instantaneous because of communication delays.
• Delays in transferring a task increase the duration of unshared state.
• To avoid lengthy unshared states, blocking task transfers from
overloaded computers to computers that are likely to become idle shortly
can be used.

11 February 8, 2022
Issues in Load Distributing
4. Preemptive vs. Non-preemptive transfers:

 Preemptive:
 Transfer of a task that is partially executed

• Non preemptive:
 Transfer of a task that has not yet started execution

 Information about the environment in which the task will execute must
be transferred to the receiving node. Ex: user’s current working
directory, privileges inherited by the task

12 February 8, 2022
Requirements for Load Distributing
 Scalability: It should work in large distributed system

 Location transparency: It should hide the location of processes.

 Determinism: A transferred process must produce the same results it

would produce if it was not transferred.

 Preemption: Remotely executed processes should be preempted and

migrated elsewhere on demand.

 Heterogeneity: It should be able to distinguish among different

processors.

13 February 8, 2022
Components of Load Distributing algorithm
• Four components
Transfer policy
 Determines whether a node is in a suitable state to participate in a task
transfer
Selection policy
 determines which task should be transferred
Location policy
 determines to which node a task selected for transfer should be sent
Information policy
 responsible for motivating the collection of system state information

14 February 8, 2022
Transfer policy
 A large number of the transfer policies are threshold policies.

Better to decide the sender and receiver.

when a new task originates at a node, and the load at the node exceeds
a threshold T, the transfer policy decides that the node is sender.
If the load at a node falls below, the transfer policy decides that the
node can be a receiver for a remote task.

15 February 8, 2022
Selection Policy
 Selects a task for transfer, once the transfer policy decides that the node
is a sender
 Simplest approach: to select the newly originated task
 Overhead incurred in task transfer should be compensated by the
reduction in the response time realized by the task
 Bryant and Finkel propose another approach - a task is selected for
transfer only if its response time will be improved upon transfer.
 Factors to consider:
Overhead incurred by transfer should be minimal. For example, a task
of small size carries less overhead.
Number of location dependent system calls made by the selected task
should be minimal

16 February 8, 2022
Location Policy
 To find suitable nodes to share load (sender or receiver)
 Widely used method : polling- a node polls another node to find out
whether it is suitable node for load sharing
 Either serially or in parallel (e.g., multicast)
 Either randomly or on a nearest-neighbor basis
 Alternative to polling
 Broadcast a query to find out if any node is available for load sharing

17 February 8, 2022
Information Policy
 To decide when, where and what information about the states of other
nodes on the system should be collected
 One of three types:
 Demand driven
 Node collects the state of the other nodes only when it becomes either a sender or a
receiver
 dynamic policy
 can be sender-initiated or receiver-initiated

18 February 8, 2022
Information Policy
Periodic
 Nodes exchange load information periodically

State change driven

 Nodes distribute state information whenever their state changes by a
certain degree
 Centralized policy- nodes send the state information to a centralized
collection points and decentralized policy- nodes send the information to
peers.

19 February 8, 2022
Types of Scheduler

20 February 8, 2022
Sender-Initiated algorithms
 Load distributing activity is initiated by an overloaded node (sender) that
attempts to send a task to an underloaded node (receiver).

 Transfer Policy: A Threshold policy based on CPU queue length used by the
algorithms
 A node is identified as a sender if a new task originating at the node makes the queue
length exceed a threshold T.

 Selection Policy: These sender-initiated algorithms consider only newly arrived

task will be transferred.

21 February 8, 2022
Sender-Initiated algorithms
• Location policy:

1. Random :
Node is randomly selected & task is simply transferred.
No information exchange to assist in decision making
Problem – useless task transfers may occur when a task is
transferred to a node that is already heavily loaded.
Solution – limit the number of times a task can be transferred
It provides significant performance improvement over no load
sharing

22 February 8, 2022
Sender-Initiated algorithms
• Location policy:
2. Threshold :

 The problem of useless task transfer can be avoided using

polling (selected a random)
 Node is polled to determine whether it is a receiver
 The number of polls is limited by a parameter called PollLimit
to keep the overhead low
 A sender node will not poll any node more than once during one
searching session of PollLimit polls
 If no suitable node is found, then the sender node must execute
the task
 It provides significant performance improvement over the
random location policy
 Flowchart

23 February 8, 2022
Sender-Initiated algorithms

24 February 8, 2022
Sender-Initiated algorithms
• Location policy:

3. Shortest :
It makes effort to choose the best receiver for a task
Number of nodes (=PollLimit) are selected at random and are polled
to determine their queue length
Node with shortest queue length is selected
The destination node will execute the task regardless of its queue
length at the time of arrival of the transferred task.
Performance improvement is marginal indicating that more detailed
state information does not necessarily result in significant
improvement in system performance

25 February 8, 2022
Sender-Initiated algorithms
 Information Policy
Demand driven

 Stability
All three approaches for location policy cause system instability at
high system loads.
In highly loaded system, probability of finding receiver is very low,
When the load due to work arriving and due to the load sharing
activity exceeds the system’s serving capacity, instability occurs.

26 February 8, 2022
Receiver-Initiated Algorithms
 Load distributing activity is initiated from an under-loaded node
(receiver) that is trying to obtain a task from an overloaded node
(sender).

 Transfer Policy:
 Threshold policy based on CPU queue length
 Transfer policy is triggered when a task departs

 Selection Policy:
 Any of the approaches as discussed earlier.

27 February 8, 2022
Receiver-Initiated Algorithms
 Location Policy:

Randomly selected node is polled

Above procedure is repeated until a node that can transfer a task (i.e.,a
sender) is found or a static PollLimit number of tries have failed to
find a sender
If all polls fail to find a sender, the node waits until another task
completes or until a predetermined period is over before initiating the
search for a sender

28 February 8, 2022
Receiver-Initiated Algorithms

29 February 8, 2022
Receiver-Initiated Algorithms
 Information Policy:
Demand driven because the polling activity starts only after a node
becomes a receiver

 Stability:
They do not cause system instability
Very little wastage of CPU cycles at high system loads
At low system loads, more receiver initiated polls do not cause system
instability as spare CPU cycles are available

 Drawback:
Most transfers are preemptive and therefore expensive

30 February 8, 2022
Symmetrically Initiated Algorithms
 In symmetrically initiated algorithm, both senders and receivers search for
receivers and senders, respectively, for task transfers.

 These algorithms have the advantages of both sender and receiver initiated
algorithms.

 At low system loads, the sender-initiated component is more successful in

finding under-loaded nodes. At high system loads, the receiver-initiated
component is more successful in finding overloaded nodes.

 As in sender-initiated algorithms, cause system instability at high system loads.

 Receiver-initiated algorithms, a preemptive task transfer is necessary.

31 February 8, 2022
Symmetrically Initiated Algorithms
 Transfer Policy:
 Threshold policy which uses two adaptive thresholds
 Thresholds are equidistant from the node’s estimate of the average load
across all nodes

 Example
 Node’s estimate of the average load = 2
 Lower threshold = 1
 Upper threshold =3

• A node whose load is greater than upper threshold  a sender

• A node whose load is less than lower threshold  a receiver.
• Nodes that have loads between these thresholds lie within the acceptable range,
so they are neither senders nor receivers.

32 February 8, 2022
Symmetrically Initiated Algorithms
 Location Policy: It has two components
 Sender-Initiated Components
 Receiver Initiated Components

 Sender-initiated component:
 Sender:
 Broadcast TooHigh message
 Set TooHigh timeout alarm
 Listen for an Accept message until timeout expires

 Receiver:
 Receive TooHigh message
 Send Accept message to sender
 Sets AwaitingTask timeout alarm
 Increases its load value before accepting a task. Why????
 If Awaiting Task timeout expires without the arrival of transferred task , the load value at the
receiver is decreased.

33 February 8, 2022
Symmetrically Initiated Algorithms
 On receiving an Accept message, if the node is still a sender, it chooses the
best process to transfer and transfer it to the node that responded.

 On expiration of TooHigh timeout, if no Accept message is received,

 Sender guesses that its estimate of the average system load is too low ( since
no node has a load much lower)
 Hence, it broadcasts a ChangeAverage message to increase the average load
estimate at the other nodes.

34 February 8, 2022
Symmetrically Initiated Algorithms
 Receiver-initiated component
 broadcasts a TooLow message
 Sets a TooLow timeout alarm
 listening for a TooHigh message

 If a TooHigh message is received, the receiver performs the same actions that
it does under sender-initiated negotiation

 If the TooLow timeout expires before receiving any TooHigh message, the
receiver broadcasts a ChangeAverage message to decrease the average load
estimate at the other nodes

35 February 8, 2022
Symmetrically Initiated Algorithms
 Selection policy: This algorithm can make use of any of the approaches
discussed earlier.
 Information policy: The information policy is demand-driven.
 Key Points:

1. The average system load is determined individually at each node, imposing

little overhead.
2. Acceptable range determines the responsiveness of the algorithm.

36 February 8, 2022