w3 msg, wisisz, wydzial informatyki, studia zaoczne inzynierskie, rozproszone systemy operacyjne

Message Passing

Interprocess communication (IPC) basically requires information sharing among two or more processes. Two basic methods for information sharing are as follows:

·        original sharing, or shared-data approach;

·        copy sharing, or message-passing approach.

Two basic interprocess communication paradigms: the shared data approach and message passing approach.

In the shared-data approach, the information to be shared is placed in a common memory area that is accessible to all processes involved in an IPC.

In the message-passing approach, the information to be shared is physically copied from the sender process’s space to the address space of all the receiver processes, and this is done by transmitting the data to be copied in the form of messages (message is a block of information).

A message-passing system is a subsystem of 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. It enables processes to communicate by exchanging messages and allows programs to be written by using simple communication primitives, such as send and receive.

Simplicity

A message passing system should be simple and easy to use. It should be possible to communicate with old and new applications, with different modules without the need to worry about the system and network aspects.

Uniform Semantics

In a distributed system, a message-passing system may be used for the following two types of interprocess communication:

·        local communication, in which the communicating processes are on the same node;

·        remote communication, in which the communicating processes are on different nodes.

Semantics of remote communication should be as close as possible to those of local communications. This is an important requirement for ensuring that the message passing is easy to use.

Efficiency

An IPC protocol of a message-passing system can be made efficient by reducing the number of message exchanges, as far as practicable, during the communication process. Some optimizations normally adopted for efficiency include the following:

·        avoiding the costs of establishing and terminating connections between the same pair of processes for each and every message exchange between them;

·        minimizing the costs of maintaining the connections;

·        piggybacking of acknowledgement of previous messages with the next message during a connection between a sender and a receiver that involves several message exchanges.

Correctness

Correctness is a feature related to IPC protocols for group communication. Issues related to correctness are as follows:

·        atomicity;

·        ordered delivery;

·        survivability.

Atomicity ensures that every message sent to a group of receivers will be delivered to either all of them or none of them. Ordered delivery ensures that messages arrive to all receivers in an order acceptable to the application. Survivability guarantees that messages will be correctly delivered despite partial failures of processes, machines, or communication links.

Other features:

·        reliability;

·        flexibility;

·        security;

·        portability.

Issues in IPC by Message Passing

A message is a block of information formatted by a sending process in such a manner that it is meaningful to the receiving process. It consists of a fixed-length header and a variable-size collection of typed data objects. The header usually consists of the following elements:

·     Address. It contains characters that uniquely identify the sending and receiving processes in the network.

·     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. This element also has two parts. The type part 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.

A typical message structure

Synchronization

A central issue in the communication structure is the synchronization imposed on the communicating processes by the communication primitives. The semantics used for synchronization may by broadly classified as blocking and nonblocking types. A primitive is said to have nonblocking semantics if its invocation does not block the execution of its invoker (the control returns almost immediately to the invoker); otherwise a primitive is said to be of the blocking type.

In case of a blocking send primitive, after execution of the send statement, the sending process is blocked until it receives an acknowledgement from the receiver that the message has been received. On the other hand, for nonblocking send primitive, 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.

In the case of blocking receive primitive, after execution of the receive statement, the receiving process is blocked until it receives a message. On the other hand, for a nonblocking receive primitive, 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.

An important issue in a nonblocking receive primitive is how the receiving process knows that the message has arrived in the message buffer. One of the following two methods is commonly used for this purpose:

·        Polling. In this method, 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.

A variant of the nonblocking receive primitive is the conditional receive primitive, which also returns control to the invoking process almost immediately, either with a message or with an indicator that no message is available.

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 asynchronous. The main drawback of synchronous communication is that it limits concurrency and is subject to communication deadlocks.

Synchronous mode of communication with both send and receive primitives having blocking-type semantics

Buffering

In the standard message passing model, messages can be copied many times: from the user buffer to the kernel buffer (the output buffer of a channel), from the kernel buffer of the sending computer (process) to the kernel buffer in the receiving computer (the input buffer of a channel), and finally from the kernel buffer of the receiving computer (process) to a user buffer.

Null Buffer (No  Buffering)

In this case, there is no place to temporarily store the message.  Hence one of the following implementation strategies may be used:

·        The message remains in the sender process’s address space and the execution of the send is delayed until the receiver executes the corresponding receive.

·        The message is simply discarded and the time-out mechanism is used to resend the message after a timeout period. The sender may have to try several times before succeeding.

              The three types of buffering strategies used in interprocess communication

Single-Message Buffer

In single-message buffer strategy, a buffer having a capacity to store a single message is used on the receiver’s node. This strategy is usually used for synchronous communication, an application module may have at most one message outstanding at a time.

Unbounded-Capacity Buffer

In the asynchronous mode of communication, since a sender does not wait for the receiver to be ready, there may be several pending messages that have not yet been accepted by the receiver. Therefore, an unbounded-capacity message-buffer that can store all unreceived messages is needed to support asynchronous communication with the assurance that all the messages sent to the receiver will be delivered.

Finite-Bound Buffer

Unbounded capacity of a buffer is practically impossible. Therefore, in practice, systems using asynchronous mode of communication use finite-bound buffers, also known as multiple-message buffers. In this case message is first copied from the sending process’s memory into the receiving process’s mailbox and then copied from the mailbox to the receiver’s memory when the receiver calls for the message.

When the buffer has finite bounds, a strategy is also needed for handling the problem of a possible buffer overflow. The buffer overflow problem can be dealt with in one of the following two ways:

·        Unsuccessful communication. In this method, message transfers simply fail, whenever there is no more buffer space and an error is returned.

·       Flow-controlled communication. The second method is to use flow control, which means that the sender is blocked until the receiver accepts some messages, thus creating space in the buffer for new messages. This method introduces a synchronization between the sender and the receiver and may result in unexpected deadlocks. Moreover, due to the synchronization imposed, the asynchronous send does not operate in the truly asynchronous mode for all send commands.  

Almost all networks have an upper bound of data that can be transmitted at a time. This size is known as maximum transfer unit (MTU). A message whose size is greater than MTU has to be fragmented into multiples of the MTU, and then each fragment has to be sent separately. Each packet is known as a datagram. Messages larger than the MTU are sent in miltipackets, and are known as multidatagram messages.

Encoding and Decoding of Messages

A message data should be meaningful to the receiving process. This implies that, ideally, the 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. However, even in homogenous systems, it is very difficult to achieve this goal mainly because of two reasons:

·        An absolute pointer value loses its meaning when transferred from one process address space to another.

·        Different program objects occupy varying amount of storage space. To be meaningful, a message must normally contain several types of program objects, such as long integers, short integers, variable-length character strings, and so on.

In transferring program objects in their original form, they are first converted to a stream form that is suitable for transmission and placed into a message buffer. The process of reconstruction of program object from message data on the receiver side is known as decoding of message data. One of the following two representations may by used for the encoding and decoding of a message data:

·        In tagged representation the type of each program object along with its value is encoded in the message.

·        In untagged representation the message data only contains program object. No information is included in the message data to specify the type of each program object.

Another important issue in message-based communication is addressing (or naming) of the parties involved in an interaction. For greater flexibility a message-passing system usually supports two types of process addressing:

·        Explicit addressing. The process with which communication is desired is explicitly named as a parameter in the communication primitive used.

·        Implicit addressing...