Module 3:

Distributed Scheduling
Introduction:
• A distributed scheduler is a resource management component 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.
• Because wide Area network have high communication delays distributing scheduling is more
suitable for distributed system based on local area networks
Motivation:
• The need for load distributing arises in such environment where random arrival of tasks
and their random CPU service time requests.
• There is a good possibility that several computers are heavily loaded while others are idle or
lightly loaded.
• System performance can potentially be improved by appropriately transferring the load from
heavy loaded computers to idle or lightly loaded computers.
• Minimizing the average response time is often the goal of load distributing.
Issues in load distributing:
1. Load:
• Defining a proper load index is very important as load distributing decisions are based
on the load measured at one or more nodes.
• Measuring the load should be efficient and imposes minimal overhead
• Resource queue and particularly the CPU queue length are good indicators of load because
they correlate well with the task response time.
• The number of processes/tasks waiting in the ready queue to get CPU time for execution.
• Task transfer should take place.
• In few, CPU utilization is used as load indicator especially in interactive environment.
• This required background process that monitors CPU utilization that becomes overhead.
2. Classification of load distributing algorithms:
• The basic function of a load distributing algorithm is to transfer loads from heavily loaded
computer to idle or lightly loaded computers.
• Load distributing algorithms can be broadly categorized as static or dynamic or adaptive.
• Dynamic load distributing algorithms use system state information (The loads at the
nodes) to make load distributing decisions.
• Dynamic loading are Able to exploit short term fluctuations in the system to improve
performance however dynamic load distributing algorithm and overhead in the collection
storage and analysis of system state information.
• Static algorithms make no such use of information. In static load distributing algorithms
decisions are hard wired in the algorithm using a priori knowledge of the system.
• The decisions are fixed beforehand and are already built into the algorithm.
• The algorithm does not change its behavior during execution based on current system
conditions.
• Adaptive load distributing algorithm are special class of dynamic load
distributing algorithm in that they adapt their activities by dynamically
changing the parameters of the algorithm to suit the changing system state
• For example, dynamic algorithm may continue to collect the system state
irrespective of system load An adaptive algorithm on the other hand may
discontinue the collection of the system state if the overall system load is high to
avoid imposing additional overhead on the system
[Link] balancing vs. Load sharing:
• Load distributing algorithm can be further classified as load balancing and load sharing
based on their load distributing principle.
• Load Balancing algorithm attempts to equalize loads at all computers because load
balancing algorithm transfer tasks at higher rate than load sharing algorithm.
• Load sharing algorithm attempts to reduce the workload on overloaded computers by
transferring tasks to lightly loaded computers because load sharing algorithms aim to
improve system performance without necessarily equalizing the load among all computers.
Feature Load balancing Load sharing

Objective Tries to distribute load equally among Tries to avoid some nodes being
all nodes heavily overloaded

Load Condition Continuously balances loads Transfers tasks only when overload
occurs

Complexity More complex Simple

Load Balancing
• A teacher distributes answer paper correction equally:
• Teacher A → 20 papers
• Teacher B → 20 papers
• Teacher C → 20 papers
Load Sharing
• If one teacher has 60 papers and another has none:
• Move some papers only to reduce overload.
• Equal distribution is not necessary.
• Task transfers are not instantaneous because of communication delays and delays that
occur during the collection of the task state.
• Delays in transferring a task increase the duration of unshared state as an idle computer
must wait for the arrival of the transferred task.
• Transferring a task from one node to another before the source node becomes overloaded
or any other node that is likely to become idle – anticipatory task transfer (Overload
prevention method).
4. Preemptive vs. non-preemptive transfers:
• Preemptive task transfers involve the transfer of a task that is partially executed. This
transfer is an expensive operation as the collection of task states can be difficult.
• State consists of virtual memory image a process control block unread input output buffer
and messages.
• Non preemptive task transfer on the other hand involve the transfer of tasks that have not
begun execution and hence do not require the transfer of task state.
• In both types of transfers information about the environment in which the task will execute
must be transferred to the receiving node.
• This information can include the current user working directory privileges inherited tasks etc.
• Non preemptive transfers are also referred to as task placements.
Components of load distributing algorithm:
A load distributing algorithm has four components/poclicies:
1. Transfer policy
2. Selection policy
3. Location policy
4. Information policy

Transfer policy:
• Policy that determines whether a node is in a suitable state to participate in a task transfer.
• 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 a sender.
• If the load of a node falls below threshold The transfer policy decides that a node can be a
receiver for a remote task.
Selection policy:
• Policy that determines which task should be transferred.
• Once the transfer policy decides that the node is a sender selection policy decides which task
to transfer.
• If the selection policy fail to find a suitable task to transfer the node is no longer considered
as a sender until transfer policy decides that the node is a sender again
• The simplest approach is to select newly originated tasks that have caused the node to
become a sender by increasing the load.
• That selected task will be executed in the remote location.
Other factors to consider:
• The overhead incurred by the transfer should be minimal.(Environment states)
• The number of location dependent system calls/ processes made by the selected task should
be minimal. Location dependent calls must be executed at the node where the task originated
because they use resources such as Windows mouse that only exist at the node.
Location policy:
• Decides where the task should be transferred from where in coordination with transfer policy
• The responsibility of location policy is to find suitable nodes senders or receivers to share the
load.
• A widely used method is polling.
• In polling a node polls another node to find suitable node for load balancing
• An alternate to polling is broadcast a query to find out if any node is available for load
sharing.
Information Policy:
• Policy responsible for deciding when information about the states of other nodes in the
system should be collected, where it should be collected from and what information should
be collected.
Most information policies are one of the following three types:
1. Demand driven:
• A node collects the state of other nodes only when it wants to become either a sender or a
receiver decided by transfer and selection policies.
• Demand driven is inherently a dynamic policy as its action depend on system state
• Demand driven policies can be sender initiated or receiver initiated
2. Periodic:
• Nodes exchange load information periodically.
• Based on information collected the transfer policy at a node may decide to transfer the jobs
• Periodic information policy do not adopt their activity to system state.
3. State change driven:
• Nodes disseminate state information whenever their state changes by certain degree.
• A state change driven policy differs from demand driven policy in that it disseminates
information about state of a node rather than collecting information about other nodes
Load distributing Algorithms:
1. Sender initiated algorithms
2. Receiver initiated algorithms
3. Symmetrically initiated algorithms
4. Adaptive algorithms
Sender initiated algorithms
• In Sender initiated algorithms load distributing activity is initiated by node that is
overloaded.
Transfer policy:
• A threshold based on the CPU queue length.
• A node is identified as a sender if a new task originating at the node makes queue length
exceed a threshold (T).
• A node identifies itself as suitable receiver if accepting the task will not cause the node’s
queue length exceed T.
Selection policy:
• Sender initiated algorithms considers only newly originated tasks.
Location policy:
• Random location : that uses no remote state information.
• Has many disadvantages.
• How the transferred task should be treated.
Threshold location:
• Randon transfer can be avoided by polling a node to determine whether it is a receiver.
• If so, the transferred task should be executed regardless of its state when the task actually
arrives.
• The number of poll is limited by a parameter called pollLimit.
• If no suitable receiver node is found within pollLimit polls, then the node at which task
originated should execute the task.

Information policy:
• Polling activity commences when the transfer policy identifies the node as a sender of a task.
• Hence, it can be considered as demand driven type (Not periodics)
Receiver-Initiated algorithms:
• Load distributing activity is initiated from an under-loaded node.

Transfer policy:
• It is a threshold policy where decision is based on CPU queue length.
• The transfer policy is triggered when a task departs/terminates.

Selection policy:
• No much over head.
• Newly originated tasks are usually received.

Information policy:
Demand driven
Symmetrically initiated algorithms:
• Under this algorithm both senders and receivers search for receivers and senders respectively
for task transfer.
• These algorithms have advantages of both sender and receiver initiated algorithms
• At low system load 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.
The above average algorithm:
• This algorithm tries to maintain the load at each node within an accepted range of the system
average.

Example:
• If a node’s estimate of the average load is 2 then lower threshold is equal to 1 and upper
threshold is equal to 3.
• A node whose load is less than the lower threshold is considered as receiver while a node
whose load is greater than the upper threshold is considered as a sender.
• nodes that have loads between these thresholds lie within acceptable range so they are neither
senders nor receivers.
Sender initiated components:
• A sender broadcast a toohigh message, set toohigh time out alarm and wait for an accept
message until the timeout expires.
• A receiver that receives a toohigh cancels its toolow time out Send an accept message to the
source of toohigh message.
• Increasing its load value prevents from receiving too many tasks
• On receiving an accept message if the node is still a sender it chooses the best task to transfer
and transfers it to the node that responded.
• On expiration of toohigh timeout if no accept message has been received the sender infers
that it estimate of the average system load is too low.
• Changeaverage message will be sent to re calculate the overall average.
Receiver initiated components:
• A node on becoming a receiver broadcasts a toolow message sets a toolow timeout alarm and
start listening for too high message.
• If a toohigh message is received the receiver performs the same action that it does under
sender initiated negotiation.
• If toolow timeout expires before receiving toohigh messages the receiver broadcasts a
changeaverage message to decrease the average load.
Adaptative algorithms:
• Sender /overload, receiver/under loaded or OK (nodes having manageable load)
• Initially each node assumes that every node is a receiver.
• This state is represented at each node by receiver that contain all nodes except itself an empty
sender list and empty OK list

Transfer policy:
• It is based on threshold policy where decisions are based on CPU queue length.
• Distributed shared memory
• DSM is a resource management component of a distributed operating system that implements
the shared memory model in distributed systems which have no physically shared memory.
• The shared memory model provides a virtual address space that is shared among all the
nodes in the distributed system.
Architecture and motivation:
• With DSM program access data in the shared address space just as they access data in
traditional virtual memory.
• Each node can own data stored in the shared address space and ownership can change when
data moves from one node to another.
• When a process accesses data in the shared address space a mapping manager maps the
shared memory address to the physical memory.
• The mapping manager is a layer of software implemented either in the operating system
kernel or as a runtime library routine.
Distributed shared memory :
Advantages of Distributed shared memory:
1. DSM system hide the explicit data movement and provide a simpler abstraction of shared
data Programmers are already well versed with hence it is easier to design and write parallel
algorithms using DSM rather than through explicit message passing.
2. In message passing model data moves between two different address spaces. This makes it
difficult to pass complex data structure between two processes moreover passing data by
reference and passing data structure containing pointers is generally difficult and expensive.
In contrast DSM system always allow complex structure to be passed by reference thus
simplifying the development of algorithm for distributed applications.
3. By moving the entire block or page containing the data reference to the site of reference
instead of moving only the specific piece of data referenced DSM takes the advantage of
locality of reference exhibited by programs and thereby cuts down on the overhead of
communicating over network.
(Locality of Reference is the tendency of a program to access the same memory
locations or nearby memory locations repeatedly within a short period of time.)
Algorithms for Implementing DSM:
Central issues in implementing DSM are:
1. How to keep track of the location of remote data.
2. How to overcome the communication delays and high overhead associated with execution
of communication protocol when accessing remote data.
3. How to make shared data concurrently accessible at several nodes in order to improve
system performance.
The central server algorithm:
• In this a central server maintains all shared data.
• It services the read requests from other nodes or clients by returning the data items to them.
• It updates the data on write requests by client and returns acknowledgement message.
• While central server algorithm is simple to implement it can become a bottleneck.
• To overcome this problem shared data can be distributed among several servers.
• In such a case clients must be able to locate appropriate server for every data access.
[Link] Migration Algorithm:
• Data in the migration algorithm is shipped to the location of the data access request.
• The migration algorithm allows only one node to access a shared data at a time.
• Typically, the whole page block containing the data item migrates instead of an individual
item requested (Locality reference).
• This algorithm uses a tunable parameter that determines the duration for which a node
can possess a shared data item.
The read replication algorithm:
• In the previous approaches only processes on one node could access a shared data at 1
moment.
• The read replication algorithm extends the migration algorithm by replicating data blocks and
allowing multiple nodes to have read access or one node to have read write access.
• Read replication can improve system performance by allowing multiple nodes to access data
concurrently.
• However, the write operation is expensive as all the copies of shared block at various nodes
will either have to be invalidated are updated with the current value to maintain the
consistency of the shared data block.
• DSM must keep track of the location of all the copies of data blocks.
The full replication algorithm:
• It is an extension of read replication algorithm It allows multiple nodes to have both read and
write access to shared data blocks.
• Because many nodes can write shared data concurrently the access to shared data must be
controlled to maintain its consistency.
• One simple way to maintain consistency is to use a gap free sequencer.
• In this scheme on nodes wishing to modify(write) shared data will send the modifications to a
sequencer.
• The sequencer will assign a sequence number and multicast the modification with sequence
number to all the nodes that have a copy of the shared data item.
Design issues:
1. Granularity:
• This refers to the size of the shared memory unit.
• A larger page size of a shared memory unit will take the advantage of locality of reference.
• But larger the page size the greater the chance of contention to access a page by many
processes.
• Smaller page sizes are to cause contention as they reduce their likelihood of false
sharing.(Thrashing)

2. Page replacement:
• In DSM Systems that support data movement Traditional methods such as LRU cannot be
directly used.