Subject : Distributed Computing
(CSC802)
Module 4.0 - Resource and Process
Management
By : Shrutika Khobragade (PHCET)
1
Contents
4.1 Desirable Features of global Scheduling algorithm,
Task assignment approach, Load balancing approach,
load sharing approach
4.2 Introduction to process management, process
migration, Threads, Virtualization, Clients, Servers,
Code Migration
2
Module 4.1
Desirable Features of global
Scheduling algorithm
3
Desirable Features of global
Scheduling algorithm
1) No priori knowledge about the processes
User does not want to specify information about characteristic and requirements
2) Dynamic in Nature
Decision should be based on the changing load of nodes and not on fixed static policy
3) Decision - making capabilities
Algorithm must make quick decision about the assignment of task to nodes of system
4) Balancing System performance and Scheduling overhead
Great amount of information gives more intelligent decision, but increases overhead
5) Stability
Unstable when all processes are migrating without accomplishing any useful work It
occurs when the nodes turn from lightly-loaded to heavily-loaded state and vice versa
4
Desirable Features of global
Scheduling algorithm
6) Scalability
A scheduling algorithm should be capable of handling small as well as large
networks
7) Fault Tolerance
Should be capable of working after the crash of one or more nodes of the
system
8) Fairness of Service
More users initiating equivalent processes expect to receive the same quality
of service
5
Module 4.1
Task assignment approach,
Load balancing approach, load
sharing approach
6
Task assignment approach
Main assumptions
Processes have been split into tasks
Computation requirement of tasks and speed of
processors are known
Cost of processing tasks on nodes are known
Communication cost between every pair of tasks are
known
Resource requirements and available resources on node
are known
Reassignment of tasks are not possible
7
Task assignment approach
Basic idea: Finding an optimal assignment to achieve
goals such as the following:
Minimization of IPC costs
Quick turnaround time of process
High degree of parallelism
Efficient utilization of resource
8
Load balancing approach
9
Load balancing approach
Static versus Dynamic
Static algorithms use only information about the average
behaviour of the system
Static algorithms ignore the current state or load of the
nodes in the system
Dynamic algorithms collect state information and react to
system state if it changed
Static algorithms are much more simpler
Dynamic algorithms are able to give significantly better
performance
10
Load balancing approach
Deterministic versus Probabilistic
Deterministic algorithms use the information about the
properties of the nodes and the characteristic of
processes to be scheduled
Probabilistic algorithms use information of static
attributes of the system (e.g. number of nodes,
processing capability, topology) to formulate simple
process placement rules
Deterministic approach is difficult to optimize
Probabilistic approach has poor performance
11
Load balancing approach
Centralized versus Distributed
Centralized approach collects information to server
node and makes assignment decision
Distributed approach contains entities to make
decisions on a predefined set of nodes
Centralized algorithms can make efficient decisions,
have lower fault-tolerance
Distributed algorithms avoid the bottleneck of
collecting state information and react faster
12
Load balancing approach
Cooperative versus Non cooperative
In Non cooperative algorithms entities act as
autonomous ones and make scheduling decisions
independently from other entities
In Cooperative algorithms distributed entities cooperate
with each other
Cooperative algorithms are more complex and involve
larger overhead
Stability of Cooperative algorithms are better
13
Issues in designing Load-balancing
algorithms
Load estimation policy - determines how to estimate the workload
of a node
Process transfer policy - determines whether to execute a process
locally or remote
State information exchange policy - determines how to exchange
load information among nodes
Location policy - determines to which node the transferable
process should be sent
Priority assignment policy - determines the priority of execution
of local and remote processes
Migration limiting policy - determines the total number of times a
process can migrate
14
Load estimation policy- I.
for Load-balancing algorithms
To balance the workload on all the nodes of the system, it is
necessary to decide how to measure the workload of a
particular node
Some measurable parameters (with time and node dependent
factor) can be the following:
Total number of processes on the node
Resource demands of these processes
Instruction mixes of these processes
Architecture and speed of the node’s processor
Several load-balancing algorithms use the total number of
processes to achieve big efficiency
15
Load estimation policy - II.
for Load-balancing algorithms
In some cases the true load could vary widely depending on
the remaining service time, which can be measured in several
way:
Memory less method assumes that all processes have the
same expected remaining service time, independent of the
time used so far
Past repeats assumes that the remaining service time is equal
to the time used so far
Distribution method states that if the distribution service
times is known, the associated process’s remaining service
time is the expected remaining time conditioned by the time
already used
16
Load estimation policy - III.
for Load-balancing algorithms
None of the previous methods can be used in modern
systems because of periodically running processes and
daemons
An acceptable method for use as the load estimation
policy in these systems would be to measure the CPU
utilization of the nodes
Central Processing Unit utilization is defined as the
number of CPU cycles actually executed per unit of real
time
It can be measured by setting up a timer to periodically
check the CPU state (idle/busy)
17
Process transfer policy - I.
for Load-balancing algorithms
Most of the algorithms use the threshold policy to decide
on whether the node is lightly-loaded or heavily-loaded
Threshold value is a limiting value of the workload of node
which can be determined by
-Static policy: predefined threshold value for each node
depending on processing capability
-Dynamic policy: threshold value is calculated from average
workload and a predefined constant
Below threshold value node accepts processes to execute,
above threshold value node tries to transfer processes to a
lightly-loaded node
18
Process transfer policy - II.
for Load-balancing algorithms
Single-threshold policy may lead to unstable algorithm
because under loaded node could turn to be overloaded
right after a process migration
To reduce instability double-threshold policy has been
proposed which is also known as high-low policy
19
Process transfer policy - III.
for Load-balancing algorithms
Double threshold policy
When node is in overloaded region new local processes
are sent to run remotely, requests to accept remote
processes are rejected
When node is in normal region new local processes run
locally, requests to accept remote processes are rejected
When node is in under loaded region new local
processes run locally, requests to accept remote
processes are accepted
20
Other policies..
State information exchange policy
Location policy
Priority assignment policy
Migration limiting policy
21
Load sharing approach
Several researchers believe that load balancing, with its
implication of attempting to equalize workload on all the nodes of
the system, is not an appropriate objective.
This is because the overhead involved in gathering the state
information to achieve this objective is normally very large,
especially in distributed systems having a large number of nodes.
In fact, for the proper utilization of resources of a distributed
system, it is not required to balance the load on all the nodes.
It is necessary and sufficient to prevent the nodes from being idle
while some other nodes have more than two processes.
This rectification is called the Dynamic Load Sharing instead of
Dynamic Load Balancing.
22
Load sharing approach
It is simpler to decide about most of these policies in
case of load sharing, because load sharing algorithms
do not attempt to balance the average workload of all
the nodes of the system.
Rather, they only attempt to ensure that no node is idle
when a node is heavily loaded.
The priority assignments policies and the migration
limiting policies for load-sharing algorithms are the
same as that of load-balancing algorithms.
23
Module 4.2
4.2 Introduction to process
management, process migration,
Threads, Virtualization, Clients,
Servers, Code Migration
24
Introduction to Process Management
Process: An operating system abstraction representing
an instance of a running computer program.
Consists of data, stack, register contents, and the state
specific to the underlying OS
Can have one or more threads of control
Consists of their own stack and register contents, but
share a process’s address space and signals
25
Introduction to Process Management
Conventional OS: deals with the mechanisms and policies for
sharing the processor of the system among all processes
Distributed operating system: To make best possible use of the
processing resources of the entire system by sharing them among all
processes
Three concepts to achieve this goal:
Processor allocation: Deals with the process of deciding which
process should be assigned to which processor
Process migration: Deals with the movement of a process from its
current location to the processor to which it has been assigned
Threads: Deals with fine-grained parallelism for better utilization of
the processing capability of the system
26
Process Migration
Process Migration
The act of transferring a process between two machines during its execution
Relocation of a process from its current location (the source node) to
another node (the destination node)
Problems with Process Migration
Lack of compelling commercial argument for OS vendors to support
process migration
Complexity of adding transparent migration
Goals of Process Migration
Dynamic load distribution
Fault resilience
Improved system administration
Data access locality
27
Process Migration
Two types:
Pre emptive process migration - Process may be migrated
during the course of its execution
Non pre emptive process migration - Process may be
migrated before it starts executing on its source node
Involves three steps:
Selection of a process that should be migrated
Selection of the destination node to which the selected
process should be migrated
Actual transfer of the selected process to the destination
node
28
Mechanisms of Process Migration
Four major sub activities
Freezing and restarting the process
Transfer of process’s address space
Forwarding messages meant for the migrant process
Handling communication between cooperating
processes
29
Threads
30
State associated with execution
environments and threads
31
Java thread constructor and
management methods
Thread(ThreadGroup group, Runnable target, String name)
Creates a new thread in the SUSPENDED state, which will belong to group
and be identified as name; the thread will execute the run() method of target.
setPriority(int newPriority), getPriority() Set and return the thread’s priority.
run() A thread executes the run() method of its target object, if it has one, and
otherwise its own run() method (Thread implements Runnable).
start() Change the state of the thread from SUSPENDED to RUNNABLE.
sleep(int millisecs) Cause the thread to enter the SUSPENDED state for the
specified time.
yield() Causes the thread to enter the READY state and invoke the scheduler.
destroy() Destroy the thread.
32
Virtualization
Memory virtualization
– Process feels like it has its own address space
Storage virtualization
– Logical view of disks “connected” to a machine
– External pool of storage
CPU/Machine virtualization
– Each process feels like it has its own CPU
– Created by OS pre emption and scheduler
33
Virtualization
Storage Virtualization
Dissociate knowledge of physical disks
Software between the computer and the disks manages the view of storage.
• Examples:
– Make four 500 GB disks appear as one 2 TB disk
– Make one 500 GB disk appear as two 200 GB disks and one 100 GB disk,
with each of the 200 GB virtual disks available to different servers while the
100 GB disk can be shared by all.
– Have all writes get mirrored to a backup disk
Virtualization software translates read-block/writeblock requests for logical
devices to readblock/write-block requests for physical devices
34
Virtualization
Storage virtualization
– Logical view of disks “connected” to a machine
– Separate logical view from physical storage
– External pool of storage
35
Machine Virtualization
Privileged vs. unprivileged instructions
Regular applications use unprivileged instructions
– Easy to virtualize
If regular applications execute privileged instructions,
they trap
– VM catches the trap and emulates the instruction
36
Code Migration
Code migration is when programs are moved from
one machine to another, often moving parts of its
execution environment along with it.
The intent is for the transferred program to continue
execution on the target machine
37
Code Migration
Reasons for Migrating Code
Code migration in distributed systems took place in the form of process
migration in which an entire process was moved from one machine to
another.
Moreover, due to the heterogeneity of the underlying platforms and
computer networks, performance improvement through code migration is
often based on qualitative reasoning instead of mathematical models.
Consider, for example, a client-server system in which the server manages
a huge database. If a client application needs to do many database
operations involving large quantities of data, it may be better to ship part
of the client application to the server and send only the results across the
network
38
Code Migration
Support for code migration can also help improve performance by
exploiting parallelism
Besides improving performance, the most important one is that of
flexibility.
Dynamic Download-
The important advantage of this model of dynamically downloading
client side software, is that clients need not have all the software
preinstalled to talk to servers.
Instead, the software can be moved in as necessary, and likewise,
discarded when no longer needed.
Another advantage is that as long as interfaces are standardized, we
can change the client-server protocol and its implementation as
often as we like.
39
Code Migration
40
Models of code Migration
To get a better understanding of the different models for code
migration, we use a framework described in (Fugetta et al., 1998).
In this framework, a process consists of three segments.
The code segment is the part that contains the set of instructions
that make up the program that is being executed.
The resource segment contains references to external resources
needed by the process, such as files, printers, devices, other
processes, and so on.
Finally, an execution segment is used to store the current
execution state of a process, consisting of private data, the stack,
and the program counter.
41
Code Migration
42
Thank you ..
43