Message Passing

CHAPTER 2

REFERENCE BOOK:
DISTRIBUTED OPERATING SYSTEM CONCEPT & DESIGN BY PRADEEP K. SINHA

Prof.M.S.Koli
DEPARTMENT OF COMPUTER SCIENCE & ENGINEERING
SKN SINHGAD COLLEGE OF ENGINEERING PANDHARPUR
Subject: Distributed System Chapter 2: Message Passing

Chapter No. 2

 Introduction

 Desirable features of good message passing system

 Issues in IPC by Message passing

 Synchronization

 Buffering

 Multidatagram messages

 Encoding and decoding of message data

 Process addressing

 Failure Handling

 Group communication

 Case Study: RMI, CORBA.

Subject: Distributed System Chapter 2: Message Passing

o A process is a program in execution.

o When we say that two computers of a distributed system are
communicating with each other, we mean that two processes, one
running on each computer, are in communication with each other.
o In a distributed system, processes executing on different computers
often need to communicate with each other to achieve some common
goal.
o Each computer of a distributed system may have a resource manager
process to monitor the current status of usage of its local resources,
and the resource managers of all the computers might communicate
with each other from time to time to dynamically balance the system
load among all the computers.
o Interprocess communication basically requires information sharing
among two or more processes.
o The two basic methods for information sharing are as follows:
o Original Sharing or Shared data approach
o Copy Sharing or Message Passing Approach
o Shared Data Approach:
o The information to be shared is placed in a common memory area
that is accessible to all the processes involved in an IPC

Fig. 1.1 Shared Data Approach

o Message Passing Approach

o The information to be shared is physically copied from the sender
process's address space to the address spaces of all the receiver
processes.
o Information is shared in the form of messages.
Subject: Distributed System Chapter 2: Message Passing

Fig. 1.2 Message Passing Approach

o “A message-passing system is a subsystem of a distributed

operating system that provides a set of message-based IPC
protocols and does so by shielding the details of complex network
protocols and multiple heterogeneous platforms from
programmers.”
o It enables processes to communicate by exchanging messages and
allows programs to be written by using simple communication
primitives, such as send and receive.

2.1 Simplicity

o It must be straightforward to construct new application to

communicate with exiting system.
o It should be easy for programmer to designate the different module to
send and received message between them.
o Clean and simple semantic of the IPC protocol make it to build
distributed system application.
2.2 Uniform Semantics
o Message passing can be used for the following two type of inter process
communication,
o Local Communication: Communicating process are on same node.
o Remote Communicating: Communicating process are on the different
node.
Subject: Distributed System Chapter 2: Message Passing
Subject: Distributed System Chapter 2: Message Passing

o The semantics of remote communicating should be as close as to the

local Communication.
2.3 Efficiency
o If the message-passing system is not efficient, interprocess
communication may become so expensive that application designers
will strenuously try to avoid its use in their applications
o An IPC protocol of the message passes system can be made efficient by
reducing the number of message exchange, during the communicating
process. Some optimization includes,
1) Avoid the cast of the establishing and terminating connection between
the same pair of the process for each and every message exchange
between them,
2) Minimizing the cast of the maintaining the connection
3) Piggybacking of the acknowledgement of the previous message during
connection,
2.4 Reliability
o Distributed system may suffer from events such as node crashes or
communicating link failure,
o This result in the loss of message,
o A reliable IPC protocol can cope with failure problems and guarantee
the delivery of a message lost message can be handled by
acknowledgement and the retransmission on the basis of time outs
o Duplicate message can be send in the events of the failure or because
of timeouts,
o A reliable IPC protocol is also capable of the detecting and handled
duplicates,
o It can be handled by assigning sequence number to message,
2.5 Flexibility
o Many applications do not require atomicity or ordered delivery of
messages
o Example: A client may multicast a request message to a group of
servers and offer the job to the first server that replies.
o Not all applications require the same degree of reliability and
correctness of the IPC protocols.
Subject: Distributed System Chapter 2: Message Passing

o Example: In adaptive routing, it may be necessary to distribute the

information regarding queuing delays in different parts of the
network.
o The IPC primitives should be such that the users have the flexibility to
choose and specify the types and levels of reliability and correctness
requirements of their applications.
o IPC primitives must also have the flexibility to permit any kind of
control flow between the cooperating processes, including synchronous
and asynchronous send/receive.
2.6 Correctness
o Correctness is a feature related to IPC protocols for group
communication
o Issues related to correctness are as follows
o Atomicity: every message sent to a group of receivers will be
delivered to either all of them or none of them.
o Ordered Delivery: Ensures that messages arrive at all receivers in
an order acceptable to the application.
o Survivability: guarantees that messages will be delivered correctly
despite partial failures of processes, machines, or communication
links.
2.7 Security
o A good message-passing system must also be capable of providing a
secure end-to-end communication.
o A message in transit on the network should not be accessible to any
user other than those to whom it is addressed and the sender.
o Steps necessary for secure communication include the following:
 Authentication of the receiver(s) of a message by the sender
 Authentication of the sender of a message by its receiver(s)
 Encryption of a message before sending it over the network
2.8 Portability
o Two aspect of the probability in the message passing system,
1) It should be possible to easily construct a new IPC facility another
system by reusing the basis design of existing system,
Subject: Distributed System Chapter 2: Message Passing

2) Heterogeneity must be considered while designing message passing

system,

f f

fixed-length header and a variable-size collection of typed data objects.

Figure: Typical message structure

Address.
It contains characters that uniquely identify the sending and receiving
processes in the network. It has a two part one is sending process address
and another is receiving process address.
Sequence number.
This is the message identifier (ID), which is very useful for identifying
lost messages and duplicate messages in case of system failures.
Structural information.
It has two part, the first part i.e. is type specifies whether the data to
be passed on to the receiver is included within the message or the message
only contains a pointer to the data, which is stored somewhere outside the
contiguous portion of the message. The second part of this element specifies
the length of the variable-size message data.
In a message-oriented IPC protocol, the sending process determines
the actual contents of a message and the receiving process is aware of how
to interpret the contents.
In the design of an IPC protocol for a message-passing system, the following
important issues need to be considered
 Who is the sender?
Subject: Distributed System Chapter 2: Message Passing

 Who is the receiver?

 Is there one receiver or many receivers?
 Is the message guaranteed to have been accepted by its receiver(s)?
 Does the sender need to wait for a reply?
 What should be done if a catastrophic event such as a node crash or a
communication link failure occurs during the course of
communication?
 What should be done if the receiver is not ready to accept the
message: Will the message be discarded or stored in a buffer? In the
case of buffering, what should be done if the buffer is full?If there are
several outstanding messages for a receiver, can it choose the order in
which to service the outstanding messages?
These issues are addressed by the semantics of the set of communication
primitives provided by the IPC protocol.

o A flexible message-passing system usually provides both blocking and

nonblocking primitives for send and receive so that users can choose the
most suitable one to match the specific needs of their applications.
o Non-Blocking:
o A primitive is said to have nonblocking semantics if its invocation does
not block the execution of its invoker
o Non- Blocking Send Primitives: After execution of the send statement,
the sending process is allowed to proceed with its execution as soon as
the message has been copied to a buffer.
o Non- Blocking Receive Primitives: The receiving process proceeds with
its execution after execution of the receive statement, which returns
control almost immediately just after telling the kernel where the message
buffer is.
o How the receiving process knows that the message has arrived in the
message buffer?
Subject: Distributed System Chapter 2: Message Passing

 Polling:
 A test primitive is provided to allow the receiver to check the buffer
status.
 The receiver uses this primitive to periodically poll the kernel to
check if the message is already available in the buffer.
 Interrupt:
 In this method, when the message has been filled in the buffer and
is ready for use by the receiver, a software interrupt is used to
notify the receiving process.
 This method permits the receiving process to continue with its
execution without having to issue unsuccessful test requests.
 This method is highly efficient and allows maximum parallelism, its
main drawback is that user-level interrupts make programming
difficult.

Fig. 4.1 Synchronization Semantics

o Blocking:
o A primitive is said to have blocking semantics if its invocation block the
execution of its invoker
o Blocking Send Primitives: After execution of the send statement, the
sending process is blocked until it receives an acknowledgment from the
receiver that the message has been received.
o The sending process could get blocked forever in situations where the
potential receiving process has crashed or the sent message has
been lost on the network due to communication failure.
Subject: Distributed System Chapter 2: Message Passing

o Blocking send primitives often use a timeout value that specifies an

interval of time after which the send operation is terminated with an
error status.
o Blocking Receive Primitives: After execution of the receive statement,
the receiving process is blocked until it receives a message
o The receiving process could be blocked forever in a situations where the
potential sending process has crashed or the expected message has
been lost on the network due to communication failure.
o A timeout value may also be used with a blocking receive primitive to
prevent the receiving process from getting blocked.
o When both the send and receive primitives of a communication between two
processes use blocking semantics, the communication is said to be
synchronous otherwise it is asynchronization.

Fig 4.2 Synchronous mode of communication with send and receive

primitives
o The sending process sends a message to the receiving process, then waits
for an acknowledgment.
o After executing the receive statement, the receiver remains blocked until it
receives the message sent by the sender.
o On receiving the message, the receiver sends an acknowledgment message
to the sender.
o The sender resumes execution only after receiving this acknowledgment
message
Subject: Distributed System Chapter 2: Message Passing

o Difference Between Synchronous and Asynchronous

o Synchronous communication is simple & easy to implement than
asynchronous
o Synchronous process is reliable because it assures the sending process
that its message has been accepted before the sending process resumes
execution
o The main drawback of synchronous communication is that it limits
concurrency and is subject to communication deadlocks.
o Synchronous communication is less flexible than asynchronous
communication because the sending process always has to wait for an
acknowledgment from the receiving process even when this is not
necessary.
Subject: Distributed System Chapter 2: Message Passing

 What is Datagram ?
o A datagram is a basic transfer unit associated with a packet-switched
network & provide a connectionless communication service across a
packet-switched network.
o Each packet is known as datagram.
 How much data at a time we can transmit ?
o Almost all networks have an upper bound on the size of data that can
be transmitted at a time. This size is known as the maximum transfer
unit (MTU) of a network.
o The message whose size is greater than MTU fragmented into
multiples of the MTU & each fragment sent separately.
 Messages smaller than the MTU of the network can be sent in a single
packet and are known as single-datagram messages. 
 Messages larger than the MTU of the network have to be fragmented and
sent in multiple packets known as multidatagram message. 
 The disassembling of a multidatagram message into multiple packets on the
sender side and the reassembling of the packets on the receiver side is
usually the responsibility of the message-passing system.

 Message send by sender process should be understood by receiving

process
 Structure of program objects should be preserved while they are being
transmitted from the address space of the sending process to the address
space of the receiving process.
 This obviously is not possible in a heterogeneous system in which the
sending and receiving processes are on computers of different
architectures.
Subject: Distributed System Chapter 2: Message Passing

 Following are the two reasons because of that it is also difficult to

implement in homogeneous systems.
a) An absolute pointer value loses its meaning when transferred
from one process address space to another. So required other
form of representation
o Example : To transmit a tree object, each element of the tree must
be copied in a leaf record and properly aligned in some fixed order
in a buffer before it can be sent to another process.
o The leaf records themselves have no meaning in the address space
of the receiving process, but the tree can be regenerated easily from
them.
o To facilitate such regeneration, object-type information must be
passed between the sender and receiver, indicating not only that a
tree object is being passed but also the order in which the leaf
records are aligned.
b) Different program objects occupy varying amount of storage
space.
o A message must normally contain several types of program objects,
such as long integers, short integers, variable-length character
strings etc.
o To make the message meaningful to the receiver, there must be
some way for the receiver to identify which program object is stored
where in the message buffer and how much space each program
object occupies
 What is Encoding & Decoding ?
o Transmitting program objects in to stream form that is suitable for
transmission & placing into message buffer called encoding of
message data.
o This conversion take place at sender side.
o The process of reconstruction of program objects from message
data on the receiver side is known as decoding of the message
data.
 Encoding & Decoding representation ways
a) Tagged Representation:
Subject: Distributed System Chapter 2: Message Passing

o Each program object along with its value is encoded in the

message.
o In this method, it is a simple matter for the receiving process to
check the type of each program object in the message because of
the self-describing nature of the coded data format.
b) Untagged Representation :
o Message data contain only program object.
o In this method, the receiving process must have a prior knowledge
of how to decode the received data because the coded data format
is not self-describing.
 Example :
o Untagged representation used in Sun XDR (eXternal Data
Representation) developed by Sun in 1990 & Courier developed by
Xerox in 1981
o Tagged representation is used in the ASN.1 (Abstract Syntax
Notation) standard developed by CCITF in 1985 & Mach
distributed operating system developed by Fitzgerald and Rashid in
1986.
 Tagged representation is more expensive than untagged representation,
both in terms of the quantity of data transferred and the processing time
needed at each side to encode and decode the message data.
Subject: Distributed System Chapter 2: Message Passing
Subject: Distributed System Chapter 2: Message Passing

Another important issue in message-based communication is

addressing (or naming) of the parties involved in an interaction : To whom

does the sender wish to send its message and, conversely, from whom does

the receiver wish to accept a message ?

Types of Addressing :
1) Explicit Addressing: The process with which communication is
desired is explicitly named as a parameter in the communication
primitive used.
send (process_id, message)
receive(process_id message)
These two primitives will send & receive message to and from process
identified by process_id.
2) Implicit Addressing : A process willing to communicate does not
explicitly name a process for communication.
send_any(service_id, message)
Sender names the service instead of process. This type of process
addressing is also known as functional addressing because the
address used in the communication primitive identifies a service
rather than a process.
receive_any(process_id, message)
This type of primitive is again useful in client-server communications
when the server is meant to service requests of all clients that are
authorized to use its
service.

Methods for Processing Addressing:

A simple method to identify a process is by a combination of
machine_id and local_id i.e machine_id@local_id.
Feature: No global coordination is needed because local_id need to be
Subject: Distributed System Chapter 2: Message Passing

unique only for one machine and it can be generated in local machine
without consultation with other machine.
Limitation: it does not allow a process to migrate from one machine
to' another if such a need arises.
Solution: processes can be identified by a combination of the
following three fields: machine_ld, local_id, and machine_id.

a) The first field identifies the node on which the process is created
b) The second field is a local identifier generated by the node on which
the process is created.
c) The third field identifies the last known location (node) of the
process.
This method of process addressing is known as link-based process
addressing.
Process: The kernel of the sending machine delivers the message to
the machine whose machine_id is specified in the third field of the
receiving process's address. If the value of the third field is equal to
the first field, the message will be sent to the node on which the
process was created. If the receiving process was not migrated, the
message is delivered to it by using the local_id information in the
process identifier. On the other hand, if the receiving process was
migrated, the link information left for it on that node is used to
forward the message to the node to which the receiving process was
migrated from this node.
It suffer from two drawbacks:
a) The overload of locating a process may be large if the process has
migrated several times during its lifetime.
b) It may not be possible to locate a process if an intermediate node on
which the process once resided during its lifetime is down.
Described above two methods are nontransparent due to need to specify the
machine identifier. Hence a location-transparent process-addressing
mechanism is more desirable for a message-passing system.
Subject: Distributed System Chapter 2: Message Passing

A centralized process identifier allocator that maintains a counter can be

used for this purpose.
Two Level Naming Scheme: (location transferring in process addressing)
Each process has two identifiers: a high-level name that is machine
independent (an ASCII string) and a low-level name that is machine
dependent.
A name server is used to maintain a mapping table that maps high-
level names of processes to their low-level names.
Working:
The kernel of the sending machine first contacts the name server
(whose address is well known to all machines) to get the low-level name of
the receiving process from its high-level name. Using the low-level name, the
kernel sends the message to the proper machine, where the receiving kernel
delivers the message to the receiving process. The sending kernel also
caches the high-level name to low-level name mapping information of the
receiving process in a local cache for future use, so that the name server
need not be contacted when a message has to be sent again to the receiving
process.
The name server approach also suffers from the problems of poor
reliability and poor scalability because the name server is a centralized
component of the system. One way to overcome these problems is to
replicate the name server.

Node crash and communication link failure are the two basic types of partial
failure. This problem may lead to following problems
1) Loss of request message:
This may happen either due to the failure of communication
link between the sender and receiver or because the receiver's node is
down at the time the request message reaches there.
Subject: Distributed System Chapter 2: Message Passing

Figure: Request message lost

2) Loss of response message:
This may happen either due to the failure of communication link
between the sender and receiver or because the sender's node is down
at the time the response message reaches there.

Figure: Response message is lost

3) Unsuccessful execution of the request
This happens due to the receiver's node crashing while the request is
being processed.
Subject: Distributed System Chapter 2: Message Passing

Solution:
To cope with this problem, a reliable IPC protocol of message passing
system is designed based on internal retransmission of message after time
out.
The kernel of the sending machine is responsible for retransmitting
the message after waiting for a timeout period if no acknowledgment is
received from the receiver's machine within this time. The kernel of the
sending machine frees the sending process only when the acknowledgment
is received.
a) Four – Message reliable IPC Protocol for client – server
communication

a) The client sends a request message to the server.

b) When the request message is received at the server's machine, the kernel
of that machine returns an acknowledgment message to the kernel of the
client machine. If the acknowledgment is not received within the timeout
period, the kernel of the client machine retransmits the request message.
c) When the server finishes processing the client's request, it returns a reply
message (containing the result of processing) to the client.
Subject: Distributed System Chapter 2: Message Passing

d) When the reply message is received at the client's machine, the kernel of
that machine returns an acknowledgment message to the kernel of the
server machine. If the acknowledgment message is not received within the
timeout period, the kernel of the server machine retransmits the reply
message.
b) Three-message reliable IPC protocol for client-server communication