Message Passing (OS)

operating-systems concurrency

Definition

Message Passing

Message passing is a method of inter-process communication that allows processes to communicate and synchronise their actions without sharing a common address space. It is particularly essential in distributed systems, where processes reside on different physical machines.

In a message-passing system, communication is achieved through two primary operations:

• send(destination, message)
• receive(source, message)

Message Types

Messages can be categorised based on how they are updated and consumed:

• Event Messages: Inform the receiver about the occurrence of a specific event. These must be stored in a queue to ensure every event is processed exactly once.
• State Messages: Represent the current state of a variable or system (e.g., current temperature). A new state message typically overwrites the previous one in the buffer, as only the most recent value is relevant.

Atomicity

A message is an atomic data structure. When a sender sends a message, the system ensures that the entire payload is transferred consistently. This provides inherent mutual exclusion for the data contained within the message, as the receiver is guaranteed to see a complete and consistent set of data.

Synchronisation

The communication can be either blocking (synchronous) or non-blocking (asynchronous):

• Blocking Send: The sender is blocked until the message is received by the destination.
• Non-blocking Send: The sender resumes execution immediately after sending.
• Blocking Receive: The receiver blocks until a message is available.
• Non-blocking Receive: The receiver retrieves either a valid message or a null value immediately.

Addressing

• Direct Addressing: The sender and receiver must explicitly name each other.
• Indirect Addressing: Messages are sent to and received from shared data structures, such as a mailbox or port.

Mutual Exclusion using Message Passing

Message passing can be used to implement mutual exclusion by using a shared mailbox as a “token” repository.

1. Initialise a mailbox mutex with a single “token” message.
2. A process wishing to enter its critical section performs a blocking receive on the mutex mailbox.
3. Upon exiting the critical section, the process performs a non-blocking send to return the token to the mailbox.

loop
    receive(mutex, msg); // Acquire token
    // --- Critical Section ---
    send(mutex, msg);    // Release token
    // --- Remainder Section ---
end loop;

This approach ensures that only the process currently holding the “token” message can execute within its critical section, effectively creating a distributed lock.