Resource Management

1
A process may be migrated because:
[Link] node does not have the required resources local node has to be
shut down

2.A process may also be executed remotely if the expected turnaround

time will be better.

From a user's point of view, the set of available resources in a

distributed system acts like a single virtual system.
Resource Management (contd.)

It is the responsibility of the resource manager of the

distributed operating system to
: Control the assignment of resources to processes
: Route the processes to suitable nodes of the system
according to these assignments

A resource can be
logical, such as a shared file, or

physical, such as a CPU

Resource Management
Resource manager schedules the processes in a
distributed system to make use of the system
resources in manner to optimize

Resource usage
Response time
Network congestion and
Scheduling overhead
Introduction
DS are characterized by
❖ Resource multiplicity
❖ System transparency
Every distributed system consists of a number of
resources interconnected by a network.
Process migration
When a user submits a process for execution, it becomes
the responsibility of the resource manager of the
distributed system to control the assignment of resources
to processes and to route the processes to suitable nodes of
the system according to these assignments.

5
Introduction
A resource manager schedules the processes in a DS to
optimise
❖ Resource usage
❖ response time
❖ Network congestion
❖ Scheduling overhead
1. Task assignment approach
2. Load balancing approach
3. Load sharing approach

6
Desirable features of global scheduling algorithm

❖ No a priori knowledge about the process

❖ Dynamic in nature
❖ Quick decision making capability
❖ Balanced system performance and scheduling overhead
❖ Stability
❖ Scalability
❖ Fault tolerance
❖ Fairness of service

7
Task Assignment
A process is considered to be composed of multiple tasks
Approach
Goal – to find an optimal assignment policy for the tasks of
an individual process.
Assumptions
❖ A process has been split into tasks.
❖ Amount of computation required by each task is known
❖ Speed of each processor is known
❖ The cost of processing each task on every node is known
❖ IPC cost between every pair of tasks is known
❖ Availability of resources at each node, requirement
of resources by each process, etc are known
❖ Reassignment of tasks is generally not possible
8
Task Assignment
The tasks of a process are assigned to nodes so as to achieve
Approach
some goals
❖ Minimization of IPC cost
❖ Quick turnaround time for the complete process
❖ A high degree of parallelism
❖ Efficient utilization of system resources in general

9
Task Assignment
Finding an optimal assignment
Approach

10
Task Assignment
Finding an optimal assignment
Approach

11
Task Assignment
Finding an optimal assignment
Approach

12
Task Assignment
Finding an optimal assignment
Approach

13
Load Balancing
These algorithms are based on intuition that, for better resource
Approach
utilization, it is desirable for the load in a distributed system to be
balanced evenly.
Performance from user point of view – response time of
processes
Performance from resource point of view – total system
throughput
Basic goal – maximize the total system throughput

14
Load Balancing
Taxonomy of Load balancing
Approach
algorithms

15
Load Balancing
Taxonomy of Load balancing
Approach
algorithms

❖ Static versus Dynamic

❖ Deterministic versus probabilistic
❖ Centralized versus Distributed
❖ Cooperative versus Noncooperative

16
Design issues - Load Balancing Algorithms
Designing a good load-balancing algorithm is a difficult task
because of the following Issues:
❖ Load estimation policy
❖ Process transfer policy
❖ State information exchange policy
❖ Location policy
❖ Priority assignment policy
❖ Migration limiting policy
Local process and remote process

21
Design issues - Load Balancing Algorithms
Load estimation policy
❖ How to measure the workload of a particular node?
❖ These parameters could includetime dependent and
node- dependent factors such as the following:
•Total number of processes on the node at the time of load estimation
• sum of remaining service time
• CPU utilization of nodes
CPU utilization – no of CPU cycles actually executed per unit
of real time.
- By setting up a timer to periodically observe the
CPU state(idle/busy)

22
Design issues - Load Balancing Algorithms
Process transfer policy
❖ Idea – transfer of some processes from heavily loaded nodes
to the lightly loaded nodes
❖ Policy – to decide a node is heavily/lightly loaded
❖ Threshold policy – static and dynamic
❖ Static policy – predefined threshold value depending on
processing capability.
❖ This threshold value does not vary with the dynamic changes in
workload at local or remote nodes.
❖ Advantage – Exchange of state information among
nodesis not required in deciding threshold value.

23
Design issues - Load Balancing Algorithms
Process transfer policy
❖ Dynamic policy – the threshold value of a node ni is calculated
as average workload of all nodes * constant ci (predefined
constant)
❖ The value of ci depends on processing capability of ni wrt that of all
other nodes.
❖ The overhead involved in the use of state information exchange
policy makes its applicability questionable!!

24
Design issues - Load Balancing Algorithms
Process transfer policy

25
Design issues - Load Balancing Algorithms
Process transfer policy

State transition diagram of the load of a node in case of double-threshold policy

26
Design issues - Load Balancing Algorithms
Process transfer policy
❖ The high-low policy guarantees a predefined level of
performance to the node owners.
❖ A process will not be transferred to another node unless it is
worthwhile.
❖ A remote process will not be accepted unless there is enough
excess capacity to handle it.

The process transfer policy decides about a transfer of a process

from node to another.

27
Design issues - Load Balancing Algorithms
Location policy
❖ The selection of destination node for processexecution
is decided by location policy of a scheduling algorithm.
❖ The main location policies proposed are –
❖ Threshold
❖ Shortest
❖ Binding
❖ Pairing

28
Design issues - Load Balancing Algorithms
State information exchange policy
❖ The proper selection of state information exchange policy is
essential.
❖ The transmission improves the ability of the algorithm to balance the
load.
❖ It raises the expected queuing time due to increase in the utilization
of the communication channel.
❖ The proposed policies are –
❖ Periodic broadcast
❖ Broadcast when state changes
❖ On demand exchange
❖ Exchange by polling

29
Design issues - Load Balancing Algorithms
Priority assignment policy
❖ When process migration is supported by distributed operating
system, it is necessary to device a priority assignment rule for
scheduling both local and remote processes at a particular
node.
❖ Priority assignment rules
❖ Selfish
❖ Altruistic
❖ Intermediate

30
Design issues - Load Balancing Algorithms
Migration limiting policy
❖ Another important policy to decide about the total number of
times a process should be allowed to migrate.
❖ Uncontrolled
❖ A process may be migrated any number of times.
❖ This policy has the unfortunate property of causing instability.
❖ Controlled
❖ Use migration count parameter k.
❖ The value of k may be decided either statically or dynamically.
❖ The value of k may depend on the characteristics of a process.

31
Load Sharing
Several researchers believe that load balancing, with its implication of
Approach
attempting to equalize workload on all the nodes of the system, is not
an appropriate objective. This is because the overhead involved in
gathering state information to achieve this objective is normally very
large, especially in distributed systems having a large number of nodes.
Moreover, load balancing in the strictest sense is not achievable
because the number of processes in a node is always fluctuating and the
temporal unbalance among the nodes exists at every moment, even if
the static (average) load is perfectly balanced.
For the proper utilization of the resources of a distributed system, it is
not required to balance the load on all the nodes. Rather, it is necessary
and sufficient to prevent the nodes from being idle while some other
nodes have more than two processes.
This rectification is often called dynamic load sharing instead of
dynamic load balancing.

32
Design issues - Load Sharing
Algorithms
Load sharing algorithms also requires proper decisions regarding
❖ Load estimation policy
❖ Process transfer policy
❖ State information exchange policy
❖ Location policy
❖ Priority assignment policy
❖ Migration limiting policy
Load sharing algorithms only attempt to ensure that no node
is idle while the other is heavily loaded.
They do not attempt to balance the average workload on all nodes
of the system.

33
Design issues - Load Sharing
Algorithms
Load estimation policy
Process transfer policy
Location policy
❖ Sender-Initiated Location policy
❖ Receiver-Initiated Location policy
State information exchange policy
❖ Broadcast when state changes
❖ Poll when state changes
Priority assignment policy
Migration limiting policy

34
Summary
In the task assignment approach, the process assignment
decisions are basically based on a priori knowledge of the
characteristics of both the processes to be executed and the
system.
The basic task assignment model deals with the assignment of
tasks to the various nodes of the system in such a manner so as to
minimize interprocess communication costs and improve the
turnaround time for the complete task force.
The task assignment approach has limited applicability because it
works on the assumption that the characteristics of all the
processes to be scheduled are known in advance and also because
task assignment algorithms are generally not dynamic in nature.

35
Summary
In load balancing approach, the process assignment approach attempts
to equalise the average workload on all the nodes of the system.
The basic problem associated with the dynamic load-balancing
algorithms is to decide about the amount of global state information to
be used.
The results of the efforts made have shown that attempting to gather a
large amount of information to describe the current global state of the
system more accurately is not always beneficial.
Hence, the degree of global knowledge in an algorithm must be
normalised to the complexity of the performance objective of the
algorithm.
This relationship and normalisation are the topics of current research.

36
Summary
In load sharing approach, the process assignment decisions
attempt to keep all nodes busy.
Since load sharing approach do not attempt to balance the load on
all nodes, they are simpler and easier to implement as compared
to load balancing algorithms.

37
Process Management
Three important concepts

1. Processor allocation

2. Process migration

3. Threads
Process Management
Process migration
Relocation of a process from its current location (the
source node) to another node (the destination node).
Process Management
Process migration
Process migration involves the following major steps:

1. Selection of a process that should be migrated

2. Selection of the destination node to which the

selected process should be migrated

3. Actual transfer of the selected process to the

destination node
Process Management
Process migration
Desirable Features of a Good Process Migration
Mechanism
A good process migration mechanism must possess

Transparency
Minimal interferences
Minimal residue dependencies
Efficiency
Robustness
Communication between co processes
Process Management
Process migration
Desirable Features of a Good Process Migration Mechanism

Transparency

Object access level

System call & interprocess communication level

Process Management
Process migration
Desirable Features of a Good Process Migration Mechanism

Minimal Interference
Minimizing the freezing time of the process

Minimal Residual Dependencies

No residual dependency should be left on the previous

node
Process Management
Process migration
Desirable Features of a Good Process Migration Mechanism

Efficiency
• The time required for migrating a process
• The cost of locating an object (includes the migrated
process)
• The cost of supporting remote execution once the
process is migrated

All these costs should be kept to minimum as far as

practicable.
Process Management
Process migration
Desirable Features of a Good Process Migration Mechanism

Robustness

Communication between Coprocesses of a Job

Co processes be able to directly communicate with

each other irrespective of their locations
Process Management
Process Migration Mechanisms
Four major sub activities involved in it are as follows:
1. Freezing the process on its source node and
restarting it on its destination node
2. Transferring the process's address space from its
source node to its destination node
3. Forwarding messages meant for the migrant process
4. Handling communication between cooperating
processes that have been separated (placed on different
nodes) as a result of process migration
Process Management
Process Migration Mechanisms

Mechanisms for Freezing and Restarting a Process

Immediate and Delayed Blocking of the Process

Fast and Slow I/O Operations

Information about Open Files

Reinstating the Process on its Destination Node

Process Management
Process Migration Mechanisms
Address Space Transfer Mechanisms
Migration of a process involves the transfer of the
following types of information from the source node to
the destination node:

• Process's state

• Process's address space