Monitors, and reasoning about concurrent code

0 · Recall Warm-up

Answer from memory first. Answers are in the Answer Vault at the bottom.

1. Initial value of full in a bounded buffer? from Lesson 3.2.2
2. How many processes can be inside a CS guarded by a semaphore that starts at 1? from Lesson 3.2.1
3. Does Peterson's solution guarantee bounded waiting? from Lesson 3.1.2

1 · The Hook

Semaphores are like raw wires: powerful, but one wire in the wrong place causes a fire. A monitor is like a switchboard: the dangerous wiring is done for you. After monitors, this lesson gives a five-step method for the GATE questions that show a few lines of concurrent code and ask what can happen.

3 · Core Concept

Predict First — the answer

Semaphore: no, the earlier signal was remembered (value went up). Condition variable: yes, a signal with no waiter is simply lost.

In plain words

A monitor is a box containing shared data and the only functions allowed to touch it. The language makes sure only one process is running inside the box at a time, so you can't forget the lock. If a process inside must wait for something, it waits on a condition variable, which also lets others into the box meanwhile.

1. Monitors

monitor Account {
    int balance;
    condition enough;
    void withdraw(int a) { while (balance < a) enough.wait(); balance -= a; }
    void deposit(int a)  { balance += a; enough.signal(); }
}

• At most one process active inside the monitor at a time (mutual exclusion is automatic).
• x.wait(): the caller sleeps on x and releases the monitor.
• x.signal(): wakes one process sleeping on x; if none is sleeping, nothing happens (unlike a semaphore's signal, which is remembered).
• After a signal, who runs first? Signal-and-wait: the woken process runs at once. Signal-and-continue: the signaller continues; the woken one runs later, so it must re-check its condition (that is why the example uses while, not if).

2. A five-step method for "analyse this code" questions

1. Mark shared vs local variables (locals and registers are private to each thread).
2. Split statements into load / compute / store if the question says statements are not atomic; otherwise treat each line as one step.
3. Try the extremes: run the threads one after the other, and try "everyone reads before anyone writes".
4. Track semaphore values: a wait can pass only when the value is above 0; a counting semaphore of k lets k threads overlap.
5. Ask four questions: Is mutual exclusion kept? Can all threads block for ever (deadlock)? Can a free CS be refused (progress)? Can one thread wait for ever (starvation)?

3. Worked GATE-style example

x = 0. Processes W and X each do x = x + 1; Y and Z each do x = x − 2. Each process does wait(S) before reading x and signal(S) after storing it, and S starts at 2. What is the largest possible final x?

• S = 2 lets two processes be between wait and signal together, so two can still race.
• To make x large, lose the decrements. W and Y enter; both read 0; Y stores −2 and leaves; W stores 1 (Y's −2 is lost) and leaves.
• X and Z enter; both read 1; Z stores −1 and leaves; X stores 2 (Z's −2 is lost).
• Largest value 2. Losing the increments instead gives the smallest value, −4.

4 · Visual

A process that calls x.wait() sleeps in x's queue and lets the next process into the monitor.

5 · Worked Examples

Example 1 Easy

In a monitor, process A calls x.signal() and no process is waiting on x. Later B calls x.wait(). Does B sleep?

Solution

Yes. A's signal had no effect, so nothing is remembered.

Example 2 Medium

B = 3. P1 runs C = B − 1; B = 2 * C; and P2 runs D = 2 * B; B = D − 1;. Each line is atomic; C and D are local. How many different final values can B have?

Solution

P1 then P2: B = 4, then 7. P2 then P1: B = 5, then 8. Interleaved: C = 2, D = 6, then the two stores of B in either order give 5 or 4. Values {4, 5, 7, 8} → 4 different values.

Example 3 GATE

In the W, X, Y, Z example above, what if S starts at 1?

Solution

Then only one process at a time touches x, so there is no race: x = 0 + 1 + 1 − 2 − 2 = −2, always.

6 · GATE Traps

• A condition variable's signal is lost if no one waits; a semaphore's signal is remembered.
• x.wait() releases the monitor while sleeping.
• A counting semaphore larger than 1 used as a "lock" lets several processes in, so races are still possible.
• Read carefully whether each line is atomic or must be split into load/compute/store.

7 · Memory Hook

"Monitor: one inside, wait releases, signal can be lost. For code questions: shared, split, extremes, semaphores, four questions."

8 · Connect the Dots

Phase 3 is complete. We met deadlock several times (flags, semaphores in the wrong order, philosophers). Phase 4 studies deadlock itself: exactly when it can happen and how an OS prevents, avoids, detects or recovers from it.

9 · Self-Test

GATE format. Try every question before opening the vault.

Q1 · MCQ · 1 mark(s) — Condition variables

In a monitor, x.signal() is called when no process is waiting on x. What happens?

1. (A) Nothing happens
2. (B) The caller blocks
3. (C) The signal is saved for the next x.wait()
4. (D) An error is raised

Q2 · NAT · 1 mark(s) — Monitor

At most how many processes can be active inside a monitor at the same time?

Numerical answer: ________

Q3 · NAT · 2 mark(s) — Race with S = 2

x = 0. W and X each do x = x + 1; Y and Z each do x = x − 2; each brackets its read-modify-write with wait(S) … signal(S), and S starts at 2. Largest possible final value of x?

Numerical answer: ________

Q4 · NAT · 2 mark(s) — Race with S = 2

Same setup (S starts at 2). Smallest possible final value of x?

Numerical answer: ________

Q5 · NAT · 2 mark(s) — Distinct values

B = 3. P1: C = B − 1; B = 2 * C; P2: D = 2 * B; B = D − 1; (each line atomic, C and D local). How many different final values of B are possible?

Numerical answer: ________

10 · Rule Card

• Monitor: shared data + functions; one process active inside; condition variables wait/signal.
• x.wait releases the monitor; x.signal wakes one, or does nothing if none waits.
• Signal-and-wait vs signal-and-continue (re-check with while).
• Code analysis: shared/local → split → extremes → semaphore values → ME, deadlock, progress, starvation.

11 · Concept Ledger

Unlocked in this lesson. From here on, these terms may be used.

monitorcondition variablewait and signal on conditionslost signal vs remembered Vsignal-and-waitsignal-and-continuemethod for analysing concurrent code