L6 –

DISTRIBUTED
PROCESS
MANAGEMENT

BMCS3003 DISTRIBUTED
SYSTEMS AND PARALLEL
COMPUTING

1
This Photo by Unknown Author is licensed under CC BY-SA
  Distributed Scheduling Algorithm Choices

 Scheduling Algorithm Approaches

CONTENTS
 Distributed Coordination

2
 INTRODUCTION
• Need for good resource allocation scheme for
DS
• Distributed scheduler:
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 the overall performance of a system is
maximized.
• More suitable for LANs than WANs
3
 PROCESS MIGRATION

• Transfer of sufficient amount of the state of

a process from one computer to another
• The process executes on the target
machine

4
 MOTIVATION

• Process migration is desirable in

distributed computing for several reasons
including:
– Load sharing
– Communications performance
– Availability
– Utilizing special capabilities

5
 LOAD SHARING

• Move processes from heavily loaded to

lightly load systems
– Significant improvements are possible
– Must be careful that the communications
overhead does not exceed the performance
gained.

6
COMMUNICATIONS PERFORMANCE
• Processes that interact intensively can be
moved to the same node to reduce
communications cost
• May be better to move process to the data
than vice versa
– Especially when the data is larger than the
size of the process

7
AVAILABILITY AND SPECIAL CAPABILITIES

• Availability
– Long-running process may need to move
because of faults or down time
– OS must have advance notice of fault
• Utilizing special capabilities
– Process can take advantage of unique
hardware or software capabilities

8
 MIGRATION ISSUES

• For process migration to work we need to

satisfy a few issues:
– Who initiates the migration?
– What is involved in a Migration?
– What portion of the process is migrated?
– What happens to outstanding messages and
signals?

9
 WHO INITIATES MIGRATION?

• Depends on the goal or reason for

migration
• OS initiates
– if the goal is load balancing.
– May be transparent to process
• Process initiates
– If the goal is to access a particular resource
– Process must be aware of the distributed
system
10
 WHAT IS INVOLVED IN
MIGRATION?
• Must destroy the process on the source
system and create it on the target system
– Process movement, not replication.
• Process image and process control block
and any links must be moved

11
EXAMPLE OF PROCESS MIGRATION
 WHAT IS MIGRATED?

• Moving the process control block is simple

• Several strategies exist for moving the
address space and data including:
– Eager (All)
– Precopy
– Eager (dirty)
– Copy-on-reference
– Flushing

13
 EAGER (ALL)

• Transfer entire address space

– No trace of process is left behind
– If address space is large and if the process
does not need most of it, then this approach
my be unnecessarily expensive (taking
minutes)
• Checkpoint/restart capability is useful.

14
 PRECOPY

• Process continues to execute on the

source node while the address space is
copied
– Pages modified on the source during precopy
operation have to be copied a second time
– Reduces the time that a process is frozen and
cannot execute during migration

15
 EAGER (DIRTY)

• Transfer only that portion of the address

space that is in main memory and have
been modified
– Any additional blocks of the virtual address
space are transferred on demand
• The source machine is involved
throughout the life of the process
– Maintains page and/or segment table entries.

16
 COPY-ON-REFERENCE

• Variation of Eager(Dirty)
• Pages are only brought over when
referenced
– Has lowest initial cost of process migration

17
 FLUSHING

• Pages are cleared from main memory by

flushing dirty pages to disk
• Pages are accessed as needed from disk
– Relieves the source of holding any pages of
the migrated process in main memory

18
  If the process is not using much address space while on
the target machine then better to use
 Eager (dirty)

CHOOSING A  Copy-on-reference
 Flushing
STRATEGY
 Otherwise use
 Eager (All)
 Precopy

19
DISCUSSION

 If the file is initially on the same system as the process to be

migrated and if the file is locked for exclusive access by that
process, what strategy is recommended?

20
WHAT HAPPENS TO MESSAGES AND SIGNALS?

• Need to have a way to temporarily store

outstanding messages and signals during
the migration activity and then direct them
to the new destination.
– May need to maintain forwarding details at the
initial site to ensure outstanding messages
and signals get through

21
 DECISION TO MIGRATE

• Decision to migrate may be made by a

single entity
– OS may decide based on load monitoring
module
– Process may decide based on resource
needs
• Some systems let the target system
participate in the decision.
– Negotiated migration
22
 MIGRATION BY NEGOTIATION

• Migration policy is responsibility of a

Starter utility
– Starter utility is also responsible for long-term
scheduling and memory allocation
• Migration decision must be reached jointly
by two Starter processes
– one on the source and one on the destination

23
NEGOTIATION OF PROCESS MIGRATION

24
 EVICTION

• Destination system may refuse to accept

the migration of a process to itself
• If a workstation is idle, process may have
been migrated to it
– Once the workstation is active, it may be
necessary to evict the migrated processes to
provide adequate response time

25
PREEMPTIVE VS.
NONPREEMPTIVE TRANSFERS

 Previous points related to preemptive processes

 Process has been created and may have begun
executing
 Nonpreemptive process transfers involve processes which have
not yet begun
 So have no state to transfer
 Useful in load balancing.

26
 DISTRIBUTED GLOBAL STATE

• Operating system cannot know the current

state of all process in the distributed
system
• A process can only know the current state
of all processes on the local system
• Remote processes only know state
information that is received by messages

27
DISTRIBUTED COORDINATION

28
 EVENT ORDERING

◼ Happened-before relation (denoted by →).

If A and B are events in the same process, and A was
executed before B, then A → B.
If A is the event of sending a message by one process
and B is the event of receiving that message by another
process, then A → B.
If A → B and B → C then A → C.

29
RELATIVE TIME FOR THREE CONCURRENT PROCESSES

30
 IMPLEMENTATION OF →

◼ Associate a timestamp with each system event. Require that for every pair
of events A and B, if A → B, then the timestamp of A is less than the
timestamp of B.
◼ Within each process Pi a logical clock, LCi is associated. The logical clock
can be implemented as a simple counter that is incremented between any
two successive events executed within a process.
◼ A process advances its logical clock when it receives a message whose
timestamp is greater than the current value of its logical clock.
◼ If the timestamps of two events A and B are the same, then the events are
concurrent. We may use the process identity numbers to break ties and to
create a total ordering.

31
 EXAMPLE

• Bank account is distributed over two

branches
• The total amount in the account is the sum
at each branch
• At 3 PM the account balance is
determined
• Messages are sent to request the
information

32
EXAMPLE 1

33
 EXAMPLE 2

• If at the time of balance determination, the

balance from branch A is in transit to
branch B
• The result is a false reading

34
 EXAMPLE 3

• All messages in transit must be examined

at time of observation
• Total consists of balance at both branches
and amount in message

35
 SOME TERMS

• Channel
– Exists between two processes if they
exchange messages
• State
– Sequence of messages that have been sent
and received along channels incident with the
process

36
 SOME TERMS

• Snapshot
– Records the state of a process
• Global state
– The combined state of all processes
• Distributed Snapshot
– A collection of snapshots, one for each
process

37
INCONSISTENT
GLOBAL STATE

38
CONSISTENT GLOBAL STATE

39
 DISTRIBUTED SNAPSHOT ALGORITHM

• Records a consistent global state

• Assumes messages are delivered in order
that they were sent
– And no messages are lost
– TCP satisfies requirements
• Uses a special control message
– Marker

40
DISTRIBUTED SCHEDULING ALGORITHM CHOICES
 Level of scheduling
 local scheduling
 global scheduling

 Load distribution goals

 load balancing
 load sharing

41
A TAXONOMY
OF
DISTRIBUTED
SCHEDULING
ALGORITHMS

42
  Goal – To transfer load from heavily loaded computers to idle or
lightly loaded computers
 Broadly characterized as :
CLASSIFICATION  Static: Decision is hard wired in the algorithm using apriori knowledge of the
system
OF GLOBAL  Dynamic: Make use of system state information to make load distributing
SCHEDULING decisions
 Adaptive: Special class of dynamic algorithm, they adopt their activities by
dynamically changing the parameters of the algorithm to suit the changing
system state

44
 LOAD BALANCING VS. LOAD SHARING

• unshared state :
– A state in which one computer lies idle while at the same
time tasks contend for service at another computer
• to reduce the likelihood of unshared state
• Load balancing algorithms
– Attempt to equalize the loads at all computers
– Higher overhead than load sharing algo
• anticipatory task transfer
– To reduce the duration of unshared state

45
DISTRIBUTED PROCESS MANAGEMENT ISSUES

46
 DEADLOCK PREVENTION
◼ Resource-ordering deadlock-prevention – define a global
ordering among the system resources.
 Assign a unique number to all system resources.
 A process may request a resource with unique number i only if it
is not holding a resource with a unique number grater than i.
 Simple to implement; requires little overhead.

◼ Banker’s algorithm – designate one of the processes in the system

as the process that maintains the information necessary to carry out
the Banker’s algorithm.
 Also implemented easily, but may require too much overhead
 TIMESTAMPED DEADLOCK-PREVENTION SCHEME

◼ Each process Pi is assigned a unique priority number

◼ Priority numbers are used to decide whether a process Pi

should wait for a process Pj; otherwise Pi is rolled back.

◼ The scheme prevents deadlocks. For every edge Pi → Pj in the wait-for graph,
Pi has a higher priority than Pj. Thus a cycle cannot exist.
 WAIT-DIE SCHEME

◼ Based on a nonpreemptive technique.

◼ If Pi requests a resource currently held by Pj, Pi is allowed to wait

only if it has a smaller timestamp than does Pj (Pi is older than Pj).
Otherwise, Pi is rolled back (dies).

◼ Example: Suppose that processes P1, P2, and P3 have

timestamps 5, 10, and 15 respectively.
 if P1 request a resource held by P2, then P1 will wait.
 If P3 requests a resource held by P2, then P3 will be rolled back.
 WOULD-WAIT SCHEME

◼ Based on a preemptive technique; counterpart to the wait-die

system.

◼ If Pi requests a resource currently held by Pj, Pi is allowed to wait only if

it has a larger timestamp than does Pj (Pi is younger than Pj). Otherwise
Pj is rolled back (Pj is wounded by Pi).

◼ Example: Suppose that processes P1, P2, and P3 have timestamps

5,10 and 15 respectively
 If P1 requests a resource held by P2, then the resource will be preempted from P2
and P2 will be rolled back.
 If P3 requests a resource held by P2, then P3 will wait.
TWO LOCAL WAIT-FOR GRAPHS
GLOBAL WAIT-FOR GRAPH
 FULLY DISTRIBUTED APPROACH
◼ All controllers share equally the responsibility for detecting
deadlock.
◼ Every site constructs a wait-for graph that represents a part of the
total graph.
◼ We add one additional node Pex to each local wait-for graph.
◼ If a local wait-for graph contains a cycle that does not involve
node Pex, then the system is in a deadlock state.
◼ A cycle involving Pex implies the possibility of a deadlock. To
ascertain whether a deadlock does exist, a distributed deadlock-
detection algorithm must be invoked.
53
AUGMENTED LOCAL WAIT-FOR GRAPHS

54
AUGMENTED LOCAL WAIT-FOR GRAPH IN SITE

55
 ELECTION ALGORITHMS
◼ Determine where a new copy of the coordinator should be restarted.
◼ Assume that a unique priority number is associated with each active process
in the system, and assume that the priority number of process Pi is i.
◼ Assume a one-to-one correspondence between processes and sites.
◼ The coordinator is always the process with the largest priority number. When
a coordinator fails, the algorithm must elect that active process with the
largest priority number.
◼ Two algorithms, the bully algorithm and a ring algorithm, can be used to elect a
new coordinator in case of failures.
 BULLY ALGORITHM

◼ Applicable to systems where every process can send a message to

every other process in the system.

◼ If process Pi sends a request that is not answered by the coordinator

within a time interval T, assume that the coordinator has failed; Pi
tries to elect itself as the new coordinator.

◼ Pi sends an election message to every process with a higher

priority number, Pi then waits for any of these processes to answer
within T.
 BULLY ALGORITHM (CONT.)

◼ If no response within T, assume that all processes with

numbers greater than i have failed; Pi elects itself the new
coordinator.

◼ If answer is received, Pi begins time interval T´, waiting to

receive a message that a process with a higher priority
number has been elected.

◼ If no message is sent within T´, assume the process with

a higher number has failed; Pi should restart the algorithm
 BULLY ALGORITHM (CONT.)
◼ If Pi is not the coordinator, then, at any time during execution, Pi
may receive one of the following two messages from process Pj.
 Pj is the new coordinator (j > i). Pi, in turn, records this information.
 Pj started an election (j > i). Pi, sends a response to Pj and begins its own
election algorithm, provided that Pi has not already initiated such an election.

◼ After a failed process recovers, it immediately begins execution of the same

algorithm.

◼ If there are no active processes with higher numbers, the recovered process
forces all processes with lower number to let it become the coordinator process,
even if there is a currently active coordinator with a lower number.
 RING ALGORITHM

◼ Applicable to systems organized as a ring (logically or physically).

◼ Assumes that the links are unidirectional, and that processes send their
messages to their right neighbors.

◼ Each process maintains an active list, consisting of all the priority numbers
of all active processes in the system when the algorithm ends.

◼ If process Pi detects a coordinator failure, I creates a new active list that is

initially empty. It then sends a message elect(i) to its right neighbor, and adds
the number i to its active list.
 RING ALGORITHM (CONT.)

◼ If Pi receives a message elect(j) from the process on the

left, it must respond in one of three ways:

1. If this is the first elect message it has seen or sent, Pi creates a

new active list with the numbers i and j. It then sends the
message elect(i), followed by the message elect(j).
 If i  j, then the active list for Pi now contains the numbers of all the
active processes in the system. Pi can now determine the largest
number in the active list to identify the new coordinator process.
 If i = j, then Pi receives the message elect(i). The active list for Pi
contains all the active processes in the system. Pi can now
determine the new coordinator process.
 REACHING AGREEMENT
◼ There are applications where a set of processes wish to agree on a
common “value”.

◼ Such agreement may not take place due to:

 Faulty communication medium
 Faulty processes
 Processes may send garbled or incorrect messages to other processes.
 A subset of the processes may collaborate with each other in an attempt to
defeat the scheme.
 FAULTY COMMUNICATIONS

◼ Process Pi at site A, has sent a message to process Pj at site B; to proceed,

Pi needs to know if Pj has received the message.
◼ Detect failures using a time-out scheme.
 When Pi sends out a message, it also specifies a time interval during which it is
willing to wait for an acknowledgment message form Pj.
 When Pj receives the message, it immediately sends an acknowledgment to Pi
 If Pi receives the acknowledgment message within the specified time interval, it
concludes that Pj has received its message. If a time-out occurs, Pj needs to
retransmit its message and wait for an acknowledgment.
 Continue until Pi either receives an acknowledgment, or is notified by the system that B is
down.
 FAULTY COMMUNICATIONS (CONT.)
◼ Suppose that Pj also needs to know that Pi has received its
acknowledgment message, in order to decide on how to proceed.

 In the presence of failure, it is not possible to accomplish this task

 It is not possible in a distributed environment for processes Pi and Pj to agree completely
on their respective states.
 FAULTY PROCESSES (BYZANTINE GENERALS PROBLEM)
◼ Communication medium is reliable, but processes can fail in unpredictable
ways.
◼ Consider a system of n processes, of which no more than m are faulty.
Suppose that each process Pi has some private value of Vi.
◼ Devise an algorithm that allows each nonfaulty Pi to construct a vector Xi =
(Ai,1, Ai,2, …, Ai,n) such that::
 If Pj is a nonfaulty process, then Aij = Vj.
 If Pi and Pj are both nonfaulty processes, then Xi = Xj.
◼ Solutions share the following properties.
 A correct algorithm can be devised only if n  3 x m + 1.
 The worst-case delay for reaching agreement is proportionate to m + 1 message-
passing delays.
 FAULTY PROCESSES (CONT.)
◼ An algorithm for the case where m = 1 and n = 4 requires two rounds of
information exchange:
 Each process sends its private value to the other 3 processes.
 Each process sends the information it has obtained in the first round to all other
processes.
◼ If a faulty process refuses to send messages, a nonfaulty process can
choose an arbitrary value and pretend that that value was sent by that
process.
◼ After the two rounds are completed, a nonfaulty process Pi can construct its
vector Xi = (Ai,1, Ai,2, Ai,3, Ai,4) as follows:
 Ai,j = Vi.
 For j  i, if at least two of the three values reported for
process Pj agree, then the
majority value is used to set the value of Aij. Otherwise, a default value (nil) is used.