Transcript L17_Distributed

Distributed Computing
Introduction to Operating Systems: Module 17
Distributed Computing
 Process
Management
 Scheduling
 Synchronization
 Deadlock
 Message
Passing
 Send/receive
 Publish/subscribe
 Remote
(message bus)
Procedure Calls
 Stub/skeleton
 Registration
Scheduling
 Explicit

The application programmer is responsible for assigning a
computer to the schedulable unit
 Transparent
The OS seamlessly assigns a computer to the schedulable unit
 Normally this is the only computer which executes the work until
it is completed

 Load
Balancing
Migrate processes to improve performance
 The cost of migration is steep!

Process Migration
 Transfer
of sufficient amount of the state of a process from
one machine to another

The process executes on the target machine
 Load
sharing
Move processes from heavily loaded to lightly load systems
 Load can be balanced to improve overall performance

 Communications
performance
Processes that interact intensively can be moved to the same node
 Move process to where the data reside when the data is large

 Availability

Long-running process moves when its machine will be down
Initiation of Migration
 Operating

system
When goal is load balancing
 Process

When goal is to reach a particular resource
Hardware
 Data
 Another process

 What
is Migrated?
Must destroy the process on the source system and create it on the
target system
 Process control block and any links must be moved

What is Migrated?
 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 too expensive
 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
What is Migrated?
 Eager
(dirty): Transfer only that portion of the
address space that is in main memory and have
been modified
 Additional
virtual pages are transferred on demand
 Source machine is involved for the life of the process
 Copy-on-reference:
Pages are only brought over on
reference
 Variation
of eager (dirty)
 Has lowest initial cost of process migration
Negotiation of Migration
 Migration
policy is responsibility of Starter utility
 Starter utility is also responsible for long-term
scheduling and memory allocation
 Decision to migrate must be reached jointly by two
Starter processes (one on the source and one on the
destination)
Eviction
 System
evict a process that has been migrated to it
 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
Synchronization
 Time-stamped
messages
 Each
message contains local time of its source
 Time of receipt is combined with the time stamp to
determine relative order of activities
 What
if local times are out of synch?
 Use a virtual time stamp
 Lamport,
Ricart algorithms
 Semaphore without shared memory
 More
complicated than we are prepared to address in an
undergraduate course
Distributed Mutual Exclusion (DME)
 Uses
timed stamped messages
 Lamport's
timestamp, Ricart's algorithm
 Assumptions
 The
system consists of n processes; each process Pi
resides at a different processor
 Each process has a critical section that requires mutual
exclusion
 Requirement
 If
Pi is executing in its critical section, then no other
process Pj is executing in its critical section
Time-Stamping
 Each
system on the network maintains a counter
which functions as a clock
 Each site has a numerical identifier
 When a message is received, the receiving system
sets is counter to one more than the maximum of its
current value and the incoming time-stamp
(counter)
Time-Stamping
 If
two messages have the same time-stamp, they are
ordered by the number of their sites
 For this method to work, each message is sent from
one process to all other processes
 Ensures
all sites have same ordering of messages
 For mutual exclusion and deadlock all processes must
be aware of the situation
DME: Fully Distributed Approach
 When
process Pi wants to enter its critical section, it
generates a new timestamp, TS, and sends the message
request (Pi, TS) to all other processes in the system.
TS = MAX(TS_ARRAY) + 1
 Like bakery algorithm

 When
process Pj receives a request message, it may reply
immediately or it may defer sending a reply back
 When process Pi receives a reply message from all other
processes in the system, it can enter its critical section
 After exiting its critical section, the process sends reply
messages to all its deferred requests
DME: Fully Distributed Approach
 The
decision whether process Pj replies immediately to a
request(Pi, TS) message or defers its reply is based on three
factors:
If Pj is in its critical section, then it defers its reply to Pi
 If Pj does not want to enter its critical section, then it sends a
reply immediately to Pi
 If Pj wants to enter its critical section but has not yet entered it,
then it compares its own request timestamp with the timestamp
TS

If its own request timestamp is greater than TS, then it sends a reply
immediately to Pi (Pi asked first)
 Otherwise, the reply is deferred

Benefits of Fully Distributed Approach
 Freedom
from deadlock is ensured
 Freedom from starvation is ensured, since entry to the
critical section is scheduled according to the timestamp
ordering. The timestamp ordering ensures that processes
are served in a first-come, first served order.
 The number of messages per critical-section entry is
2 x (n – 1)

This is the minimum number of required messages per
critical-section entry when processes act independently and
concurrently
Three Undesirable Consequences
 The
processes need to know the identity of all other
processes in the system, which makes the dynamic addition
and removal of processes more complex
 If one of the processes fails, then the entire scheme
collapses

This can be dealt with by continuously monitoring the state of all
the processes in the system
 Processes
that have not entered their critical section must
pause frequently to assure other processes that they intend
to enter the critical section

This protocol is therefore suited for small, stable sets of
cooperating processes
Deadlock in Resource Allocation
 Mutual
exclusion
 Hold and wait
 No preemption
 Circular wait
Deadlock Prevention
 Circular-wait
condition can be prevented by
defining a linear ordering of resource types
 Hold-and-wait condition can be prevented by
requiring that a process request all of its required
resource at one time, and blocking the process until
all requests can be granted simultaneously
Deadlock Avoidance
 Distributed
 Every
deadlock avoidance is impractical
node must keep track of the global state of the
system
 The process of checking for a safe global state must be
mutually exclusive
 Checking for safe states involves considerable
processing overhead for a distributed system with a
large number of processes and resources
Distributed Deadlock Detection
 Each
site only knows about its own resources
 Deadlock
may involve distributed resources
control – one site is responsible for
deadlock detection
 Hierarchical control – lowest node above the nodes
involved in deadlock
 Distributed control – all processes cooperate in the
deadlock detection function
 Centralized
Message Passing
 Send/Receive
paradigm
 Works
much the same as in single system
 Can be synchronous or asynchronous
 Publish/Subscribe
 Agents
publish (broadcast) messages to “subjects”
 Agents subscribe to subjects
 Normally asynchronous, with little fault tolerance
Sockets
 Defined
as an “endpoint for communication”
 Concatenation of IP Address + Port
 All Ports < 1024 are considered “well-known”
- TELNET uses port 23
- FTP uses port 21
- HTTP server uses port 80
Remote Procedure Calls (RPC)
 Sockets
 RPCs
 Client
are considered low-level.
offer a higher-level form of communication
makes procedure call to “remote” server
using ordinary procedure call mechanisms
Remote Method Invocation (RMI)
 Java’s
OO version of RPCs
 A thread
 An
may invoke a method on a remote object
object is considered “remote” if it resides in a
separate Java Virtual Machine
RPC versus RMI
 RPC’s
 RMI
Support Procedural Programming Style
Supports Object-Oriented Programming Style
 Parameters
to RPCs are Ordinary Data Structures
 Parameters
to RMI are Objects
Stubs and Skeletons
 “Stub”
is a proxy for the remote object – resides on
client
 The stub “marshalls” the parameters and sends
them to the server
 “Skeleton” is on server side
 Skeleton “unmarshalls” the parameters and delivers
them to the server
Marshalling Parameters


Local (non-remote) objects
are passed by copy using
object serialization
Remote objects are passed
by reference
 Remote objects are
declared by specifying
an interface that extends
java.rmi.Remote
 Every method must
throw
java.rmi.Remote
Exception
CORBA
 RMI
is Java-to-Java Technology
 CORBA is middleware that allows heterogeneous
client and server applications to communicate
 Interface Definition Language (IDL) is a generic
way to describe an interface to a service a remote
object provides
 Object Request Broker (ORB) allows client and
server to communicate through IDL.
 Internet InterORB Protocol (IIOP) is a protocol
specifying how the ORBs can communicate.
Cobra Model
Registration Services
 Registration
Service Allows Remote Objects to
“register” Their Services.
 RMI,
CORBA Require Registration Services