Foundational Concepts: Interprocess Communication (IPC) Models

Before we dive into synchronization, we must understand the two fundamental ways processes can communicate. This is core to the module title — Inter-process Communication — and is directly tested in exams [2024 Q1b].

The Two IPC Paradigms

Direct vs Indirect Communication [2024 Q1b — 2 marks]

Under Direct Communication, each process that wants to communicate must explicitly name the recipient or sender of the communication.

1// Direct Communication Primitives:
2send(P, message);      // Send a message to process P
3receive(Q, message);   // Receive a message from process Q

• Property: A link is automatically established between every pair of processes that want to communicate.
• Disadvantage: The sender must know the exact identity of the receiver. If a process's identifier changes, all communicating processes must be updated.

Under Indirect Communication, processes communicate through mailboxes (also called ports). A process sends a message into a mailbox, and another process receives from that same mailbox.

1// Indirect Communication Primitives:
2send(A, message);      // Send a message to mailbox A
3receive(A, message);   // Receive a message from mailbox A

• Property: Multiple processes can share the same mailbox.
• Advantage: Sender and receiver do not need to know each other's identity — they only need to know the shared mailbox name. This provides loose coupling and location transparency.

Synchronous vs Asynchronous Communication

Buffering — How Messages are Queued

Why Do Processes Need to Cooperate?

In a modern multiprogramming OS, processes do not live in isolation. Cooperating processes share data — a counter, a buffer, a file record — to accomplish a common goal. This cooperation is powerful, but it introduces a subtle and catastrophic danger: what happens when two processes touch the same data at the same time?

The answer, without proper synchronization, is data corruption — and the worst kind: corruption that is silent, non-deterministic, and almost impossible to reproduce in a debugger.

The Setup: A Shared Counter

Consider the simplest possible scenario. Two processes, a Producer and a Consumer, share a variable called counter that tracks how many items are in a buffer. Both processes update it:

• The Producer executes counter++ when it adds an item.
• The Consumer executes counter-- when it removes one.

Individually, each line looks perfectly safe. But here is the critical insight that every OS engineer must internalize:

counter++ is NOT a single atomic operation. It compiles to THREE separate machine instructions.

1// What the programmer writes:
2counter++;
3
4// What the CPU actually executes (x86 assembly):
5MOV  EAX, [counter]   // (1) LOAD:  Read the value of counter from RAM into register EAX
6ADD  EAX, 1           // (2) ADD:   Increment the value in the register
7MOV  [counter], EAX   // (3) STORE: Write the new value from EAX back to RAM

The same 3-instruction breakdown applies to counter--, except the ADD becomes SUB. The OS can interrupt a process between any two of these instructions and switch to another process. This is the root of the problem.

---

The Race Condition: A Silent Disaster

A Race Condition occurs when the final result of a computation depends on the precise, unpredictable interleaving of instructions from two or more concurrent processes. The system "races" to update shared data, and whoever finishes last "wins" — overwriting the other's work.

Let's prove this with exact numbers. Assume counter = 5.

Expected Result: Producer runs counter++, Consumer runs counter--. The net result should always be counter = 5.

What can actually happen:

Final value: counter = 6 — which is wrong. The Consumer's decrement was completely lost. The Producer's stale register value (loaded at T1 before the Consumer ran) was written back, overwriting the Consumer's valid result.

This is a race condition. The same code can also produce counter = 4 depending on the order of the interrupt. The final value is undefined and non-deterministic.

The Critical Section: Giving the Problem a Name

To build a general solution, we need a precise vocabulary. Operating System theory formalizes this around the concept of a Critical Section.

Definition

A Critical Section (CS) is the segment of code within a process where it accesses and potentially modifies shared resources — shared variables, tables, files, or buffers. The fundamental rule is:

When one process is executing inside its Critical Section, no other process is permitted to execute inside its own Critical Section for the same shared resource.

The Four-Part Structure of a Process

Any process that uses a critical section can be divided into exactly four logical parts:

The Critical Section Problem

The Critical Section Problem is the formal challenge of designing an Entry Section and Exit Section protocol such that the execution of all processes is correctly serialized when they access shared data. This protocol must work for any number of processes and any interleaving of instructions.

The Three Requirements: What a Correct Solution Must Guarantee

Any proposed solution to the Critical Section Problem — whether software or hardware — is only valid if it satisfies all three of the following conditions simultaneously. These are not optional guidelines; they are formal mathematical requirements.

---

Requirement 1: Mutual Exclusion

If process $P_i$ is executing in its critical section, then no other process can be executing in its critical section (for the same shared resource).

This is the most fundamental requirement — the bare minimum. It directly prevents the race condition. If two processes can be inside the critical section at the same time, you have no protection.

Analogy: A bathroom with a lock. When occupied, the door is locked. No one else can enter.

---

Requirement 2: Progress

If no process is currently executing in its critical section, and some processes wish to enter it, then the selection of which process enters next cannot be postponed indefinitely. Only processes that are NOT in their Remainder Section may participate in the decision. This decision must be made in a finite amount of time.

This requirement prevents a scenario where the "gatekeeper" logic is so broken that even when the critical section is free, no process can enter it. This would cause the system to freeze even without a race condition.

Why it's subtle: "Only processes NOT in the Remainder Section can vote." This means a process that doesn't want to enter cannot accidentally block one that does.

Analogy: If everyone leaves the bathroom, the next person in line must be allowed to enter immediately. You can't have a broken door that stays locked even when nobody is inside.

---

Requirement 3: Bounded Waiting

There must exist a bound (a finite limit) on the number of times that other processes are allowed to enter their critical sections after a process has made a request to enter and before that request is granted.

This requirement prevents starvation. A process cannot be made to wait forever while others repeatedly jump ahead of it. There must be a formal guarantee of fairness.

Analogy: A ticket system at a deli counter. You take a number when you arrive. You are guaranteed to be served in a finite number of turns, even if many people arrive after you.

---

The Requirements at a Glance: A Comparison

Exam Trap — Progress vs. Bounded Waiting: These two are frequently confused.

• Progress asks: "Can someone enter when the CS is free?" (liveness of the system)
• Bounded Waiting asks: "Will a specific waiting process eventually get in?" (fairness for individuals) A solution can satisfy Progress while violating Bounded Waiting if it always lets the same process in first.