Interprocess Communication and Synchronization Basics

Two fundamental IPC models. Shared Memory: processes share a region of memory; fast (after setup) since no kernel involvement per access, but requires explicit synchronization to avoid race conditions. Message Passing: processes exchange messages via send/receive; easier for distributed systems, no shared variables, but slower due to kernel involvement and copying. Message passing can be blocking (synchronous) or non-blocking (asynchronous), with direct or indirect (mailbox/port) addressing. Memory aid: 'Shared memory = fast but you synchronize; Message passing = safe but slow'. Pipes, sockets, and message queues are common implementations; named pipes (FIFOs) persist and work between unrelated processes.

A race condition occurs when the outcome depends on the non-deterministic ordering of concurrent accesses to shared data. The critical section (CS) is the code segment accessing shared resources. Any correct CS solution must satisfy THREE requirements: (1) Mutual Exclusion - at most one process in the CS at a time; (2) Progress - if no process is in the CS, selection of the next entrant cannot be postponed indefinitely and only contenders decide; (3) Bounded Waiting - a bound exists on how many times others enter before a waiting process is granted entry. Memory aid: 'ME, Progress, Bounded Wait' = 'MPB'. Note: assumptions about relative process speeds or number of CPUs must NOT be made.

Peterson's algorithm is one of the most elegant ideas in concurrent programming and one of the most-loved testbeds in GATE Computer Science. It solves the critical section problem for two processes using nothing but ordinary memory reads and writes — no special hardware instructions like Test-and-Set or atomic Compare-and-Swap. That minimalism is exactly what makes it teachable and examable.

Definition: The critical section problem asks: given multiple processes that share a resource, how do we ensure that at most one process at a time accesses the shared data, while still guaranteeing progress and fairness?

Definition: A correct solution to the critical section problem must satisfy three properties — mutual exclusion (only one in the critical section), progress (if no one is inside, those wanting to enter must eventually be allowed in), and bounded waiting (no process is starved indefinitely).

Definition: Peterson's solution is a software-only algorithm by Gary Peterson (1981) that uses two shared variables — a boolean array flag[2] and an integer turn — to satisfy all three properties for exactly two processes.

The Algorithm in One Block

shared:
    boolean flag[2] = {false, false};   // intent to enter
    int     turn;                       // whose turn it is

process i (i = 0 or 1; let j = 1 - i):
    // ENTRY SECTION
    flag[i] = true;                 // (1) I want in
    turn    = j;                    // (2) but you go first
    while (flag[j] && turn == j)    // (3) wait only if peer also wants in AND it's their turn
        ;                           //     busy-wait

    // CRITICAL SECTION
    // ... access shared data ...

    // EXIT SECTION
    flag[i] = false;                // (4) I'm done; release

That is the whole algorithm. Three writes and a busy-wait. The cleverness is hidden in the order of lines (1) and (2) and the conjunction in line (3).

Why the Three Properties Hold

Mutual exclusion. Suppose both P0 and P1 are inside the critical section at the same time. Then both must have read flag[other] && turn == other as false. Each of them set flag[i] = true before the check, so flag[other] could not have been false at the moment of the check. Therefore turn == other must have been false for both — but turn is a single variable, so it cannot equal both 0 and 1 simultaneously. Contradiction. Hence at most one process is inside the critical section at a time.

Progress. Suppose P0 is waiting in its while-loop. That means flag[1] && turn == 1. If P1 does not want to enter, it would have set flag[1] = false, so P0 would proceed. If P1 does want to enter, then after P1 wrote turn = 0 in its own entry section, P0's condition turn == 1 becomes false, so P0 proceeds. Either way, someone makes progress — neither process is blocked unless the other is actively in or trying.

Bounded waiting. Once P0 exits and re-enters, it again sets turn = 1 in line (2). So if P1 was waiting, P1 enters next. P0 cannot starve P1 for more than one critical-section worth of waiting. Bound = 1 turn.

The Polite-Friends Intuition

The mental model that sticks for GATE is two friends at a single doorway.

• Each friend first raises a hand to signal intent (line 1).
• Then each friend says "You go first" by setting turn to the other person's name (line 2).
• The friend who said "you go first" last ends up waiting — because turn now holds the other name.

So whichever friend most recently deferred ends up being the one who waits. The peer enters, finishes, lowers their flag, and the waiting friend then proceeds. The asymmetry created by the last write to turn is what breaks the tie.

Why the Order of Lines (1) and (2) Matters

If we swap lines (1) and (2) — i.e., set turn = j before raising our flag — then both processes can pass the while-check before either flag is high. Two processes would enter the critical section together. Mutual exclusion breaks. So the flag-then-turn ordering is structurally essential, not stylistic.

Similarly, the while-condition is a conjunction (&&), not a disjunction (||). Using || would deadlock both processes when both raise their flags. The conjunction lets one of them break free precisely because turn can hold only one value.

Why it matters

Peterson's solution is the cleanest illustration of three GATE-favourite ideas at once:

1. Software-only synchronisation is possible — you do not always need atomic hardware instructions.
2. All three correctness properties must be checked; satisfying mutual exclusion alone is not enough.
3. Memory consistency assumptions matter — and on modern hardware, naive Peterson without memory barriers can fail.

GATE setters love this last point because it bridges OS, computer architecture and compilers.

Real-world example

Imagine two Bangalore-based microservices, each running on a separate core, both writing to a shared in-memory cache entry. A pre-2010 textbook would suggest Peterson-style software locks. In modern practice, the engineers would reach for the OS's atomic primitives (std::atomic in C++, synchronized in Java, Mutex in Rust) — but understanding Peterson explains why those higher-level primitives must use memory fences internally.

Common misconception

Many students believe Peterson's algorithm works perfectly on any modern multi-core CPU. It does not. Out-of-order execution and store buffers in x86, ARM and POWER architectures can reorder the writes to flag[i] and turn. If process i's flag[i] = true becomes visible to other cores after turn = j, then process j may pass the while-check and both processes enter the critical section. The fix is to insert a memory barrier (mfence on x86) between lines (1) and (2). On the textbook model assumed by GATE — sequentially consistent memory with atomic loads and stores — this concern disappears.

A second misconception: students think Peterson can extend trivially to n processes. It cannot. The two-variable structure is specifically tied to two processes. The n-process generalisation is Lamport's Bakery Algorithm, not a Peterson extension. (A nested Peterson tournament can simulate n-process exclusion but is impractical.)

A third trap: students confuse Peterson with strict alternation (using only turn). Strict alternation guarantees mutual exclusion but violates progress — if one process never wants to enter, the other can never enter either. Likewise, using only flag[] without turn (Dekker's earlier attempt) can deadlock when both flags go up together. Peterson's two-variable design is the minimal fix.

Question: A student writes Peterson's algorithm but swaps the order of the first two entry-section statements (sets turn = j first, then flag[i] = true). Does the algorithm still guarantee mutual exclusion?

Solution:
Step 1: Suppose both processes execute turn = j first. Now both flags are still false.
Step 2: Both then set flag[i] = true. Now both flags are true.
Step 3: P0 checks flag[1] && turn == 1. If turn is currently 0 (overwritten by P1's turn = 0), P0 enters.
Step 4: P1 checks flag[0] && turn == 0. With turn == 0, P1 must wait. But the timing window between steps 1 and 2 can let both pass.
Conclusion: Mutual exclusion can fail with swapped order. Order matters.

Cover the answer, recall, then check. 11 cards on IPC and synchronization basics for GATE OS.

Q1. Two fundamental IPC models?
A1. Shared memory (processes share a memory region; fast, user-space after setup) and message passing (send/receive via the kernel; easier in distributed systems, slower per message).

Q2. Shared memory vs message passing — speed and effort trade-off?
A2. Shared memory is faster (no kernel copy per access) but needs the programmer to handle synchronization. Message passing is slower (system calls, copying) but the kernel mediates, so it's simpler and works across machines.

Q3. Blocking (synchronous) vs non-blocking (asynchronous) send/receive?
A3. Blocking send waits until the message is received; blocking receive waits until a message arrives. Non-blocking versions return immediately (send continues; receive returns a message or null).

Q4. Direct vs indirect communication in message passing?
A4. Direct: sender names the receiver explicitly (send(P, msg)). Indirect: messages go through a mailbox/port shared by processes (send(mailbox, msg)).

Q5. Bounded vs unbounded buffer in message passing?
A5. Zero-capacity: sender blocks until receiver takes it (rendezvous). Bounded: sender blocks only when the buffer is full. Unbounded: sender never blocks.

Q6. What is a pipe, and difference between ordinary and named pipes?
A6. A pipe is a unidirectional byte-stream IPC. An ordinary (anonymous) pipe exists only between related processes (parent-child); a named pipe (FIFO) has a name in the filesystem and works between unrelated processes.

Q7. Why is synchronization needed with shared-memory IPC?
A7. Concurrent readers/writers on the shared region can race; producer-consumer coordination (buffer full/empty) requires semaphores or condition variables to stay correct.

Q8. State the producer-consumer (bounded buffer) problem.
A8. A producer adds items to a fixed buffer, a consumer removes them. Constraints: producer must wait when full, consumer must wait when empty, and mutual exclusion on the buffer. Solved with semaphores full, empty, mutex.

Q9. Which three semaphores solve the bounded-buffer problem and their initial values?
A9. mutex = 1 (mutual exclusion), empty = N (empty slots), full = 0 (filled slots). Producer: wait(empty), wait(mutex), … signal(mutex), signal(full). Consumer mirrors it.

Q10. Why must wait(mutex) come AFTER wait(empty)/wait(full), not before?
A10. If a process does wait(mutex) first and then blocks on wait(empty)/wait(full), it holds mutex while blocked — the other party can't proceed → deadlock. Order the counting semaphore first.

Q11. What is a socket in the IPC context?
A11. An endpoint for communication (IP + port) enabling message passing between processes on the same or different machines — the general mechanism underlying networked IPC.