Chapter 3.2 Lock-in

ACompressed recap

Semaphore: wait (S--, block if S < 0), signal (S++, wake if S ≤ 0); −k = k waiters; final = initial − waits + signals. Mutex 1, ordering 0, k resources k. Bounded buffer: mutex 1, empty N, full 0, counting wait before mutex. Readers–writers (first): first reader waits rw, last signals; writers starve. Philosophers: all-left deadlock; ≤ 4 at table, asymmetry, both-at-once; max ⌊n/2⌋ eat. Monitor: one active inside; condition signal lost if no waiter. Method: shared/local, split, extremes, semaphores, four questions.

BMerged rule card

3.2.1 Semaphores: wait, signal, counting and binary semaphores

• wait/P: S--; if S < 0 block. signal/V: S++; if S ≤ 0 wake one. Atomic.
• Negative value −k = k processes waiting. Final value = initial − waits + signals.
• Binary (mutex, starts 1) vs counting (starts k). Ordering semaphore starts 0.
• Opposite orders of waits can deadlock; LIFO queues can starve.

3.2.2 Classic problems: bounded buffer, readers–writers, dining philosophers

• Bounded buffer: mutex = 1, empty = N, full = 0; counting wait before mutex wait; signals in any order.
• Readers–writers (reader priority): first reader waits on rw, last reader signals rw; writers may starve.
• Dining philosophers: all left-first → deadlock; fixes: ≤ 4 at table, asymmetry, both-at-once. Max ⌊n/2⌋ eat together.

3.2.3 Monitors, and reasoning about concurrent code

• 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.

CInterleaved GATE-style questions

Q1 · NAT · 1 mark(s) — Arithmetic

A semaphore starts at 7; 20 wait and 15 signal operations follow. Final value?

Numerical answer: ________

Q2 · NAT · 2 mark(s) — Outputs

s = 0, t = 0. P1: print "A"; signal(s); wait(t); print "C"; P2: wait(s); print "B"; signal(t); How many different outputs are possible?

Numerical answer: ________

Q3 · MCQ · 1 mark(s) — Deadlock

P1 does wait(S); wait(Q); and P2 does wait(Q); wait(S); (S = Q = 1). What can happen?

1. (A) Nothing can go wrong
2. (B) Mutual exclusion is violated
3. (C) Deadlock
4. (D) Both processes always finish

Q4 · MCQ · 1 mark(s) — Bounded buffer

In the bounded-buffer solution, which pair of lines can be swapped safely?

1. (A) None
2. (B) The consumer's wait(full) and wait(mutex)
3. (C) The producer's wait(empty) and wait(mutex)
4. (D) The producer's signal(mutex) and signal(full)

Q5 · NAT · 1 mark(s) — Initial values

Bounded buffer of size 5: sum of the initial values of empty, full and mutex?

Numerical answer: ________

Q6 · MCQ · 1 mark(s) — Readers–writers

In the first readers–writers solution, which reader releases the writers' semaphore?

1. (A) Every reader
2. (B) The writer itself
3. (C) The first reader
4. (D) The last reader to leave

Q7 · MCQ · 1 mark(s) — Monitor

A process calls x.wait() inside a monitor. Which is true?

1. (A) It terminates the process
2. (B) It returns immediately if no one signalled before
3. (C) It releases the monitor and sleeps on x
4. (D) It keeps the monitor locked while sleeping

Q8 · NAT · 2 mark(s) — Final values

x = 5. P1 runs wait(s); x = x + 1; signal(s); but P2 runs x = x − 1; without using s (s starts at 1). Statements are load/compute/store. How many different final values of x are possible?

Numerical answer: ________