Message Passing & Monitors

DSA, Database System & Operating System — Operating System and Process Management, NEC licence examination syllabus (Nepal Engineering Council).

Message Passing and Monitors

Two higher-level answers to synchronisation: don't share memory at all, or let the compiler enforce the locking.

🌍 Where this lives: the two ideas here won in different places, and both won decisively. Message passing became the default for distributed systems — every microservice architecture, every Kafka topic, every HTTP API is message passing, chosen because shared memory across machines is impossible. Monitors became the default inside a single program: Java's synchronized methods, C#'s lock, and Python's with lock: are all monitors. The reason both replaced raw semaphores is the same — semaphores require the programmer to remember every signal(), and people forget. Search "why Java chose monitors over semaphores".

Message passing

Processes communicate by exchanging MESSAGES rather than sharing memory. Two primitives: send(destination, message) receive(source, message) Synchronisation comes for free: a receive cannot complete before the matching send, so ordering is automatic. There is no shared variable, so there is no race condition to protect against. DESIGN CHOICES — each is an examinable dimension: 1. NAMING DIRECT send(P, msg) — name the process explicitly · simple, but the sender must know the receiver · changing a process name breaks every sender INDIRECT send(mailbox, msg) — via a named mailbox/port · senders and receivers are decoupled · a mailbox may have many senders and receivers · this is what message queues and Kafka topics are 2. SYNCHRONISATION BLOCKING SEND the sender waits until the message is received ("synchronous", rendezvous) NON-BLOCKING SEND the sender continues immediately ("asynchronous") BLOCKING RECEIVE the receiver waits until a message arrives — the common case NON-BLOCKING RECEIVE returns immediately, with a message or nothing (a poll) RENDEZVOUS = blocking send + blocking receive. Both wait for each other, so no buffer is needed at all. This is what Go's unbuffered channels do, and Ada's accept. 3. BUFFERING ZERO CAPACITY no buffer; the sender must block until the receiver takes it (rendezvous) BOUNDED CAPACITY n messages may be queued; the sender blocks only when the queue is full UNBOUNDED CAPACITY the sender never blocks · convenient and DANGEROUS: a fast producer with a slow consumer consumes all memory. Real systems always bound the queue, precisely to create backpressure. THE PRODUCER-CONSUMER PROBLEM WITH MESSAGES — note how much simpler it is than the semaphore version: producer: consumer: while (true) { while (true) { produce(item); receive(mailbox, item); send(mailbox, item); consume(item); } } No mutex. No `empty` or `full` semaphore. No index arithmetic. A BOUNDED mailbox provides the blocking behaviour that `empty` and `full` provided manually — and the deadlock from the previous topic (mutex before semaphore) cannot be written, because there is no mutex. That simplification is the whole argument for message passing.

Monitors

A MONITOR is a language construct that bundles shared data with the procedures that operate on it, and GUARANTEES that only one process executes inside the monitor at a time. monitor SharedCounter { int count = 0; /* private data */ procedure increment() { /* automatically count = count + 1; mutually exclusive */ } procedure get() returns int { return count; } } THE KEY PROPERTY: mutual exclusion is provided by the CONSTRUCT, not by the programmer. There is no wait() to forget and no signal() to omit on an error path. The compiler or runtime inserts the locking. CONDITION VARIABLES — monitors need a way to wait for a condition, not just for the lock: condition x; x.wait() the calling process is SUSPENDED and RELEASES the monitor, so another process can enter x.signal() resumes exactly ONE process waiting on x; if none is waiting, it has NO EFFECT THE CRUCIAL DIFFERENCE FROM A SEMAPHORE: semaphore signal() increments a counter — it is REMEMBERED even if nobody is waiting condition signal() is FORGOTTEN if nobody is waiting That distinction causes real bugs. A signal sent before the other thread waits is lost, and the waiter blocks forever. Hence the RULE: always use a condition variable with a PREDICATE in a LOOP, never a bare wait: while (!condition_is_true) /* while, not if */ x.wait(); WHY A LOOP AND NOT AN IF: 1. SPURIOUS WAKEUPS — POSIX explicitly permits wait() to return without any signal 2. another thread may have consumed the condition between the signal and this thread actually running Both are real; the loop handles both. SIGNAL SEMANTICS — two schools, and exams ask which: HOARE (signal-and-wait) the signaller immediately yields to the signalled process · the condition is guaranteed still true when the waiter resumes · needs an extra context switch MESA (signal-and-continue) the signaller keeps running; the signalled process becomes ready · cheaper, but the condition may be falsified before the waiter runs · THEREFORE the while loop is mandatory Every real implementation — Java, C, POSIX, C# — uses MESA semantics. That is precisely why "always wait in a loop" is the universal advice.

Bounded buffer with a monitor

monitor_buffer.txt

monitor BoundedBuffer {
    int  buffer[N];
    int  count = 0, in = 0, out = 0;
    condition notFull, notEmpty;

    procedure insert(item x) {
        while (count == N)          /* WHILE, not IF */
            notFull.wait();
        buffer[in] = x;
        in = (in + 1) % N;
        count = count + 1;
        notEmpty.signal();
    }

    procedure remove() returns item {
        while (count == 0)
            notEmpty.wait();
        item x = buffer[out];
        out = (out + 1) % N;
        count = count - 1;
        notFull.signal();
        return x;
    }
}

/* COMPARE with the semaphore version from the previous topic:

   SEMAPHORE VERSION needs
     · three semaphores (empty, full, mutex)
     · wait(empty) BEFORE lock(mutex) — get the order wrong and
       it deadlocks (verified on this machine)
     · a matching signal() on every path, including errors

   MONITOR VERSION needs
     · no explicit mutex at all — the monitor provides it
     · two condition variables, each used in a while loop
     · no ordering rule to remember

   The monitor cannot express the deadlock, because there is no
   separate mutex to acquire in the wrong order. That is the
   point of the abstraction: it removes a class of error rather
   than documenting it. */

/* THE SAME THING IN JAVA — monitors are built into the
   language, which is why this is idiomatic rather than exotic: */
class BoundedBuffer<T> {
    private final Object[] buf; private int count, in, out;
    BoundedBuffer(int n) { buf = new Object[n]; }

    public synchronized void insert(T x)
            throws InterruptedException {
        while (count == buf.length) wait();   // while!
        buf[in] = x; in = (in + 1) % buf.length; count++;
        notifyAll();
    }
    @SuppressWarnings("unchecked")
    public synchronized T remove() throws InterruptedException {
        while (count == 0) wait();
        T x = (T) buf[out]; out = (out + 1) % buf.length; count--;
        notifyAll();
        return x;
    }
}
// `synchronized` IS the monitor lock. wait()/notify() are the
// condition variable. Java uses ONE implicit condition per
// object, which is why notifyAll() is safer than notify():
// with a single condition you cannot know whether the thread
// you woke is waiting for the right thing.

WHY notifyAll() RATHER THAN notify() IN JAVA — a real subtlety worth knowing: Java gives each object ONE condition variable, shared by both "not full" and "not empty" waiters. With notify(), the runtime picks an arbitrary waiter — possibly a producer when you needed to wake a consumer. That producer re-checks its while condition, finds the buffer still full, and waits again — and the consumer that should have woken never does. The result is a LOST WAKEUP and a deadlock. notifyAll() wakes everyone; each re-tests its own predicate and only the appropriate ones proceed. It costs a thundering herd of wakeups but cannot lose one. Languages with MULTIPLE condition variables per lock (POSIX pthread_cond_t, java.util.concurrent.locks.Condition) let you signal precisely, so notify-one is safe there. MONITOR vs SEMAPHORE, summarised: SEMAPHORE MONITOR mutual exclusion manual AUTOMATIC provided by OS / library the LANGUAGE signal if no waiter remembered FORGOTTEN error-prone yes much less flexibility higher lower wait in a loop n/a MANDATORY (Mesa)

The "signal is remembered versus forgotten" difference is the single most important line in this topic. A semaphore's signal() increments a count that persists; a condition variable's signal() vanishes if nobody is waiting. Code translated from one to the other without accounting for that will deadlock, and it is the most common bug when people move from semaphores to monitors.

🌍 Go further: Go made a deliberate bet on message passing with goroutines and channels — "share memory by communicating" — and then discovered that both are needed: the standard library ships sync.Mutex alongside channels, and the official advice is to use whichever fits ("use channels for passing ownership, mutexes for protecting state"). Erlang went further and removed shared memory entirely, which is how it achieves nine-nines reliability in telecom switches. The modern synthesis is the actor model: each actor owns its state and communicates only by messages — Akka, Orleans, and Erlang/Elixir. Search "Go proverbs share memory by communicating" and "actor model Erlang".

💡 Exam angle: give the message-passing design dimensions — direct vs indirect naming, blocking vs non-blocking, and the three buffering capacities (zero = rendezvous, bounded, unbounded). Define a monitor as a construct providing automatic mutual exclusion, and know condition variables with wait() and signal(). Two high-value details: a condition-variable signal() is lost if nobody is waiting (unlike a semaphore), and you must always wait in a while loop because real systems use Mesa (signal-and-continue) semantics. Be able to write the bounded buffer both ways and say why the monitor version cannot deadlock on lock ordering.

Syllabus points

Message passing
Monitors

Create a free account to tick topics off, take notes as you read, watch the video lessons and get a day-by-day study plan built around your exam date.