Message Passing

Overview

Message passing refers to a means of communication between:

• different threads within a process
• different processes running on the same compute node
• different processes running on different nodes

When messages are passed between two different processes we speak of inter-process communication, or IPC.

Message passing can be used as a more process-oriented approach to synchronization than the “data-oriented” approaches used in providing mutual exclusion for shared resources.

There are several dimensions to consider in message passing systems:

• Is communication synchronous or asynchronous?
• Is naming symmetric or asymmetric?
• Do we name the parties or do we name the channels?/li>
• Is the messaging client-server-ish or a free-for-all bulletin board?

Simple Message Passing

One party is the sender (usually denoted $P$) and the other is the receiver ($Q$).

Symmetric Naming

Both sender and receiver know each other by name. Here are some examples of syntax you might see:

Asymmetric Naming

Generally, the sender will know the name of the receiver, but the receiver is happy to receive from anyone. The sender can pass its own id inside the message if it wants.

Synchronous Communication

$P$ and $Q$ have to wait for each other (one blocks until the other is ready).

Like a telephone call.

Asynchronous Communication

The underlying system buffers the messages so $P$ and $Q$ don’t have to wait for each other. This is less efficient due to the overhead of managing the buffer.

Like sending a letter, email, or text message.

Message Synchronization Types

There are several kinds of sends:

Notation	Name	Description
	Synchronous	Caller will wait indefinitely for the receiver to become ready.
	Balking	Sender gives up immediately if receiver is not already waiting to receive.
	Timeout	Sender will wait for a time before giving up if the receiver never becomes ready.
	Asynchronous	Sender will not wait for the receiver to become ready, it just sends and continues execution. Also known as non-blocking.
	Yield	Sender completely gives up control to the receiver. This can be a procedure call in a single-threaded environment, or a yield among coroutines.
	Unspecified	Sender simply messages the receiver but we don’t care how.

Client-Server Communication

Communication follows the client-server paradigm when the receiver (server) does care about the sender and is normally responsible for sending a reply message.

Knowledge of the sender can be implemented by:

• Making the sender id a parameter to the receive operation
• Passing in the sender id as part of the message

Client-Server communication is basically synchronous, using the rendezvous as a primitive for building up more sophisticated communication mechanisms, including asynchronous ones.

Rendezvous

The client blocks while the server computes and sends back the reply.

If the computation may take a long time, and the client has useful work to do, the rendezvous action should be kept short and some other way can be found to get the result back to the client.

Note that because the client blocks while the response is sent back, we say message exchange is atomic.

Callback

The client calls the server with the input data and its id and doesn’t block. Sometime later, the server will call the client and pass the result.

Receipt

The client calls the server, passing in the input data and receiving (immediately) a receipt from the server; later, the client contacts the server again, using the receipt to get the result. (Supposedly, dry cleaners and old-school photo developers work this way.)

Mailbox

The client gives the server the address of the mailbox where it wants the result to go; the client retrieves the result later.

A mailbox can also be used to send the input data to the server:

Relay

A relay implements a fully asynchronous, no-wait send, and is used only when no reply is necessary. The relay blocks on behalf of the client.

Buffer

This one is classic.

Channels

Instead of considering the identities of the processes as central, some systems view the communication channel as the named entity through which information is passed.

One example is the occam language. In this language, channels must be laid out at compile time, making client-server programming (in which a server can serve multiple clients) difficult.

Go is another popular languages featuring channels. In Go, channels are first-class citizens.

Unix Pipes

A pipe is similar to a mailbox, but:

• It’s for untyped data only
• It’s really an abstraction for an I/O device (using Unix read and write system calls)

Pipes are inherited by forked processes. Be careful when communicating with children; you might read your own message.

Also note that Windows has named pipes too. And furthermore, some programming languages have pipes in their APIs.

Operating System Message Passing

Back in the old days, System V Unix introduced arbitrary typed messages and the following system calls:

These are considered pretty low-level, and today there are many modern alternatives, including:

• POSIX Message Queues. Cleaner API using mq_open(), mq_send(), mq_receive(). Better standardization across Unix-like systems.
• Unix Domain Sockets. Flexible and powerful, supported across all Unix-like systems. Can use standard socket interfaces for local IPC.
• D-Bus. A higher-level message bus system, widely used in Linux desktop environments. It supports structured messages and service discovery.
• Memory-mapped files. With appropriate synchronization, can be used for efficient inter-process communication. Often better performance for large data.
• Named Pipes (FIFOs). A simpler interface for stream-based communication, allowing processes to communicate without needing to know each other’s names.
• Modern Messaging Libraries. Libraries like ZeroMQ and RabbitMQ support much higher-level distributed messaging capabilities, like publish/subscribe, request/reply, and more.

In Programming Languages

Notes on different languages follow. Feel free to add your own.

• occam uses dedicated channels; names of both the sender and receiver are required. Most efficient. Least flexible.
• Linda uses broadcast communication only. Neither the sender or the receiver name each other. This is like a bulletin board.
• In Ada, only the receiver, not the sender is named. This is like the telephone without caller id.

Recall Practice

Here are some questions useful for your spaced repetition learning. Many of the answers are not found on this page. Some will have popped up in lecture. Others will require you to do your own research.

1. Message passing is a form of communication generally distinguished from what other common form?
   Shared memory
2. What are three environments in which message passing can be used?
   Between threads within a process, between processes on the same compute node, and between processes on different nodes.
3. What is inter-process communication (IPC)?
   IPC refers to communication between different processes.
4. In asymmetric naming, the ______________ generally knows the name of the ______________, but not vice-versa.
   sender; receiver
5. What is the difference between synchronous and asynchronous communication?
   Synchronous communication requires both parties to be ready to communicate at the same time, while asynchronous communication allows one party to send a message without waiting for the other party to be ready.
6. Synchronous communication is like a ______________, while asynchronous communication is like sending a ______________.
   telephone call; letter/email/text
7. What are the different kinds of message passing calls?
   Synchronous, balking, timeout, asynchronous, and yield.
8. What is a rendezvous in the context of client-server communication?
   The client blocks while waiting for the server to process a request and send back a response.
9. How does callback message passing work?
   The client sends a request to the server and does not block; later, the server calls back the client with the result.
10. What is a receipt in message passing?
    The client sends a request to the server and receives a receipt immediately; later, it uses the receipt to retrieve the result.
11. What is a mailbox in message passing?
    A mailbox is a storage location where messages can be sent and retrieved later, allowing the client to specify where it wants the result to go.
12. What is a relay in message passing?
    A relay allows a client to send a message without waiting for a response, effectively blocking on behalf of the client.
13. What is a buffer in message passing?
    A buffer is a storage area that temporarily holds messages sent between processes, allowing for asynchronous communication.
14. What is a channel in message passing?
    A channel is a named entity through which information is passed, focusing on the communication medium rather than the identities of the processes.
15. What is a pipe in the context of message passing?
    A pipe is a unidirectional communication channel for untyped data, often used for inter-process communication in Unix-like systems.
16. What are some modern alternatives to System V Unix message passing?
    POSIX Message Queues, Unix Domain Sockets, D-Bus, memory-mapped files, named pipes (FIFOs), and modern messaging libraries like ZeroMQ and RabbitMQ.
17. What is the main difference between occam and Linda in terms of message passing?
    occam uses dedicated channels with both sender and receiver names required, while Linda uses broadcast communication without requiring names for either party.

Summary