Message Passing (OS)

operating-systems concurrency

Definition

Message Passing

Message passing is a method of inter-process communication allowing processes to communicate and synchronise without sharing an address space. Essential in distributed systems.

Communication uses two operations:

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

Message Types

Event Messages

Inform the receiver about an occurrence. Must be stored in a queue to ensure each event is processed exactly once.

State Messages

Represent current state of a variable (e.g., temperature). New messages overwrite previous ones, as only the most recent value matters.

Properties

Atomicity

A message is an atomic data structure. The system ensures the entire payload is transferred consistently, providing inherent mutual exclusion for the contained data.

Synchronisation Modes

• Blocking Send: Sender waits until message is received
• Non-blocking Send: Sender resumes immediately after sending
• Blocking Receive: Receiver waits until a message is available
• Non-blocking Receive: Receiver retrieves message or null immediately

Addressing

• Direct: Sender and receiver explicitly name each other
• Indirect: Messages sent to shared structures (mailbox, port)

Mutual Exclusion

Token-based Mutual Exclusion

Message passing implements mutual exclusion using a shared mailbox as a token repository:

1. Initialise mailbox mutex with one “token” message
2. Process performs blocking receive on mutex to enter critical section
3. Process performs non-blocking send to return the token on exit

while (true) {
    receive(mutex, &msg);    // Acquire token
    // --- Critical Section ---
    send(mutex, msg);        // Release token
    // --- Remainder Section ---
}

Only the process holding the token can execute in its critical section, creating a distributed lock.