A resource allocation graph contains a cycle. Which conclusion is correct?

The system is deadlocked only if every resource type in the cycle has a single instance

The system is deadlocked only if the cycle has even length

In the bounded-buffer producer–consumer solution, the producer executes `P(mutex)` before `P(empty)` instead of after. What is the consequence?

Deadlock, when the producer sleeps on a full buffer while holding the mutex

Nothing changes; both semaphores are acquired either way

Deadlock, when the producer sleeps on a full buffer while holding the mutex

The buffer can overflow past n items

Compared with message passing, shared-memory IPC is faster because:

After the region is mapped, the kernel is not involved in each access

The kernel copies the data more efficiently

After the region is mapped, the kernel is not involved in each access

It works across a network as well

IPC, Synchronisation and Deadlock

These three sub-items are one argument rather than three topics, and reading them that way makes most of the questions fall into place. Inter-process communication is how separate processes exchange information, and there are exactly two families: shared memory, where the kernel maps one region into two address spaces and then gets out of the way, and message passing, where every exchange goes through the kernel. The trade is stated once and asked repeatedly — shared memory is fast because the kernel is not involved per access, and for that same reason it makes synchronisation the programmer’s problem; message passing is slower because every message is a system call, and for that same reason it needs no locks. Which brings the second item: synchronisation exists because shared state read and written by concurrent flows produces results that depend on interleaving, and a race condition is exactly that dependence. The instrument is the semaphore: an integer with two atomic operations, P (wait, decrement) and V (signal, increment), and the single most useful thing to know is that a counting semaphore initialised to k admits exactly k processes into the critical section, so a mutex is the k = 1 case. Then deadlock, which is what synchronisation buys you if you are careless: four conditions must hold simultaneously — mutual exclusion, hold and wait, no preemption, circular wait — and every prevention strategy is an attack on exactly one of them. Detection and avoidance are different questions, and the Banker’s algorithm answers avoidance: not is there a deadlock but could granting this request ever lead to one.

Two Ways to Share, and the Trade Between Them

Shared memory against message passing
Aspect	Shared memory	Message passing
Kernel involvement	Once, to set the region up	Every message — each is a system call
Speed	Faster, at memory speed	Slower, at system-call speed
Synchronisation	The programmer’s problem — needs locks	Handled by the kernel’s queue
Across a network	No — one physical memory	Yes, which is why distributed systems use it

ℹ️ The producer–consumer semaphores, and where the counts come from

A bounded buffer of n slots shared by a producer and a consumer needs exactly three semaphores, and each initial value is derivable rather than arbitrary. mutex = 1 protects the buffer structure itself — one writer at a time, so the k = 1 case. empty = n, because at the start there are n slots a producer may fill. full = 0, because at the start there is nothing a consumer may take. The producer does P(empty); P(mutex); …; V(mutex); V(full) and the consumer the mirror image with full and empty swapped. Two things are examined about this. The order of the first two waits matters: acquire the mutex before checking for space and a full buffer leaves the producer holding the lock while it sleeps, so the consumer can never drain it — a deadlock built out of correct pieces in the wrong order. And empty + full is not invariant during an operation, only between them, which is why a question asking for the value at an arbitrary instant has to be answered from the interleaving and not from the sum.

Semaphores, and the Arithmetic They Obey

A counting semaphore is an integer plus a queue, with two atomic operations. P(S) decrements S; if the result is negative the caller is put on the queue and blocks. V(S) increments S; if the result is still ≤ 0 someone was waiting, so one process is released. Under that convention the value carries two pieces of information at once: when S is positive it is the number of further processes that may proceed without blocking, and when S is negative |S| is the number of processes currently blocked on it. The arithmetic then needs no case analysis at all. A semaphore initialised to s after p wait operations and v signal operations has value s − p + v, whatever order they happened in, because each operation contributes ±1 unconditionally. So a semaphore initialised to 7 after 20 P and 15 V operations sits at 7 − 20 + 15 = 2.

⚠️ Mutual exclusion is the easy requirement; progress is the one solutions fail

A correct critical-section solution must satisfy three requirements, and questions almost always attack the second. Mutual exclusion: at most one process inside. Progress: if no process is inside and some want in, one of them gets in — a solution may not stall when nobody is holding anything. Bounded waiting: there is a limit on how many times others may enter ahead of you, so nobody starves. Now the standard failing example. A single shared turn variable, where each process waits until turn names it, gives mutual exclusion perfectly and fails progress: it enforces strict alternation, so if P0 finishes and does not want in again, P1 can never re-enter even with the critical section empty. Peterson’s solution repairs exactly this by adding a flag array to the turn variable — the flags say who wants in and the turn breaks the tie — and it satisfies all three. When a question offers a two-process solution, test progress first: construct the case where one process simply stops asking.

Deadlock: Four Conditions, and the Banker’s Question

The four necessary conditions, and what attacking each costs
Condition	How prevention attacks it	What that costs
Mutual exclusion	Make the resource sharable	Usually impossible — a printer is not sharable
Hold and wait	Request everything at once, or release before requesting	Low utilisation, and possible starvation
No preemption	Take resources back from a waiting process	Only works where state can be saved and restored
Circular wait	Total ordering — request resources in increasing order only	The practical one, and the one real systems use

⚠️ A cycle proves deadlock only when there is one instance per resource type

In a resource allocation graph, a cycle is necessary for deadlock but not always sufficient, and the dividing line is the number of instances. With exactly one instance of every resource type, a cycle is a deadlock: each process in the cycle waits for the single copy held by the next, and none can move. With multiple instances, a cycle may resolve on its own, because a process outside the cycle can release an instance of a contested type and let one of the waiters proceed. So the correct statements are: no cycle ⟹ no deadlock, always; cycle ⟹ deadlock, only in the single-instance case. Questions exploit this in both directions — offering a multi-instance graph with a cycle and asking whether it is deadlocked (answer: not necessarily, examine the instances), and offering “a cycle always means deadlock” as a plausible option.

The Banker’s algorithm answers avoidance. Take three resource types with totals (10, 5, 7) and five processes whose Allocation and Max are given below. Allocated across all five is (7, 2, 5), so Available = (3, 3, 2), and Need = Max − Allocation. A state is safe if some order exists in which every process can finish, each one releasing its allocation to help the next. Run the check: only P1 (need 1,2,2) and P3 (need 0,1,1) fit inside (3, 3, 2) at all, so one of those must go first; take P1, and Available becomes (5, 3, 2); then P3 releases, giving (7, 4, 3); and from there P0, P2 and P4 all fit in some order. The state is safe.

Totals (10, 5, 7); Available = (3, 3, 2); Need = Max − Allocation
Process	Allocation	Max	Need	Fits in (3,3,2)?
P0	(0, 1, 0)	(7, 5, 3)	(7, 4, 3)	No
P1	(2, 0, 0)	(3, 2, 2)	(1, 2, 2)	Yes
P2	(3, 0, 2)	(9, 0, 2)	(6, 0, 0)	No
P3	(2, 1, 1)	(2, 2, 2)	(0, 1, 1)	Yes
P4	(0, 0, 2)	(4, 3, 3)	(4, 3, 1)	No

🎯 There is no such thing as “the” safe sequence — this state has 16

Walking all 120 orderings of these five processes finds exactly 16 safe sequences, among them P1→P3→P0→P2→P4, P1→P3→P4→P0→P2 and P3→P4→P1→P0→P2. So a question asking for the safe sequence is badly posed on this state, and a question asking whether the state is safe has a clean answer, because safety means at least one such order exists. What is genuinely determined here is the start: every one of the 16 begins with P1 or P3, and the reason is visible in the last column — no other process has a Need that fits inside (3, 3, 2). That is the shape to look for in an exam. “Which process can be granted first?” is well posed and has answer {P1, P3}; “what is the safe sequence?” needs the question to have pinned down a tie-breaking rule, and if it has not, look for the option that is a safe sequence rather than for the one you happened to derive.

🧠 The single-resource formula: m ≥ n(k − 1) + 1

One resource type, n processes, each of which may eventually need up to k units. The system is guaranteed deadlock-free exactly when m ≥ n(k − 1) + 1, and the derivation is worth doing once because it makes the formula unforgettable. The worst case is every process holding k − 1 units and asking for one more; that state has n(k − 1) units committed and everyone stuck. One extra unit breaks it: give it to any process, that process reaches k, finishes, and releases all k for the others. So the boundary is exactly one above the total worst-case hold. Two directions get asked. Forward: 4 processes each needing at most 3 units are safe with m ≥ 4(2) + 1 = 9. Backward: with m = 12 units and k = 4 each, solve n(3) + 1 ≤ 12 to get n ≤ 3.67, so at most 3 processes — and note the floor, because 4 processes would need 13.

Key takeaways

Shared memory is fast and needs locks; message passing is slower and needs none — the same fact twice.
A counting semaphore initialised to k lets exactly k processes in; a mutex is the k = 1 case.
After p waits and v signals a semaphore initialised to s holds s − p + v, in any order.
When S is negative, |S| is the number of processes blocked on it.
Producer–consumer: mutex = 1, empty = n, full = 0 — and P(empty) must come before P(mutex).
Test a critical-section solution against progress first: make one process stop asking to enter.
All four deadlock conditions must hold at once; prevention attacks exactly one, usually circular wait.
A cycle means deadlock only with one instance per type; safety means at least one safe sequence exists.

Practice questions (8)

Attempt each one before opening the answer. Every explanation names the tempting wrong option as well as the right one, because that is where marks are lost.

A counting semaphore is initialised to 7. Then 20 P (wait) operations and 15 V (signal) operations are executed on it in some interleaved order. The final value of the semaphore is ______
Numerical answer — type the value.
Show answer
Answer: 2
2. Each P contributes −1 and each V contributes +1 unconditionally, so the final value is 7 − 20 + 15 = 2, and the interleaving cannot change it — that is why the question can say “in some interleaved order” without under-specifying anything. The blocking is what depends on order, not the arithmetic: a P that drives the value negative blocks its caller, and a later V releases one, but both still moved the integer by one. Worth noticing what the final value tells you here: 2 is positive, so no process is left blocked, and two more processes could pass without waiting. Had the answer come out negative, its magnitude would have been the number of processes still queued.
Three resource types have totals (10, 5, 7). Allocations are P0 (0,1,0), P1 (2,0,0), P2 (3,0,2), P3 (2,1,1), P4 (0,0,2), and maximum demands are P0 (7,5,3), P1 (3,2,2), P2 (9,0,2), P3 (2,2,2), P4 (4,3,3). Which processes could be the first to complete in a safe sequence?
1. P1
2. P2
3. P3
4. P0
Show answer
Answer: A — P1; C — P3
P1 and P3. Total allocated is (7, 2, 5), so Available = (10,5,7) − (7,2,5) = (3, 3, 2), and Need = Max − Allocation gives P0 (7,4,3), P1 (1,2,2), P2 (6,0,0), P3 (0,1,1), P4 (4,3,1). A process can complete first only if its entire Need fits inside the current Available, and testing each component: P1 (1,2,2) ≤ (3,3,2) ✓ and P3 (0,1,1) ≤ (3,3,2) ✓, while P0 fails on the first component (7 > 3), P2 also fails on the first (6 > 3) despite needing nothing of B or C, and P4 fails on the first too (4 > 3). Exhaustively walking all 120 orderings confirms it: there are 16 safe sequences and every one of them starts with P1 or P3. Note that P2 is the instructive wrong answer — needing zero units of two resource types looks like being nearly satisfied, but a vector comparison is componentwise and one failing component is enough.
A single resource type has m identical units, shared by n processes each of which may need up to k units. The system is guaranteed to be deadlock-free when:
1. m ≥ nk
2. m ≥ n(k − 1) + 1
3. m ≥ n + k
4. m ≥ nk − 1
Show answer
Answer: B — m ≥ n(k − 1) + 1
m ≥ n(k − 1) + 1, and the worst case shows why. Suppose every process holds k − 1 units and needs one more; that commits n(k − 1) units with nobody able to move. Add a single unit and the deadlock is impossible: hand it to any process, which then reaches its maximum k, completes, and releases all k units for the rest. So the boundary sits exactly one above the total worst-case hold. Option A is sufficient but far from necessary — giving every process its full maximum simultaneously wastes n − 1 units’ worth of capacity, and a question asking for the guarantee condition wants the tight bound. Option D is off by exactly the unit that does all the work, which makes it the deadlock state rather than the safe one. Option C has the wrong shape entirely: the bound must scale with the product, since doubling both n and k roughly quadruples the requirement.
A resource allocation graph contains a cycle. Which conclusion is correct?
1. The system is deadlocked
2. The system is deadlocked only if every resource type in the cycle has a single instance
3. The system is not deadlocked
4. The system is deadlocked only if the cycle has even length
Show answer
Answer: B — The system is deadlocked only if every resource type in the cycle has a single instance
A cycle is necessary but not sufficient in general, and the number of instances is what decides. With one instance of each type in the cycle, each process waits on the single copy held by the next and nothing can move — a genuine deadlock. With multiple instances, the cycle can dissolve on its own: a process outside the cycle may release an instance of a contested type, which satisfies one waiter and breaks the chain. Option A is the single-instance answer stated unconditionally, which is the commonest error here. Option C inverts the reliable half of the rule — the direction that always holds is no cycle ⟹ no deadlock, so a cycle is exactly the wrong evidence for concluding safety. Option D invents a parity condition; cycle length never enters the argument.
In the bounded-buffer producer–consumer solution, the producer executes P(mutex) before P(empty) instead of after. What is the consequence?
1. Nothing changes; both semaphores are acquired either way
2. Mutual exclusion is violated
3. Deadlock, when the producer sleeps on a full buffer while holding the mutex
4. The buffer can overflow past n items
Show answer
Answer: C — Deadlock, when the producer sleeps on a full buffer while holding the mutex
Deadlock. With the order reversed, a producer facing a full buffer takes the mutex first and then blocks on empty, so it goes to sleep still holding the lock. The consumer now needs that mutex to remove an item, cannot get it, and therefore can never signal empty — the one event that would wake the producer. Each waits for something only the other can provide, out of two operations that are individually correct. Option A is the intuition being tested and it is wrong precisely because a blocked process does not release what it holds. Option B is not the failure mode: mutual exclusion is preserved here, which is what makes the bug so easy to miss in review. Option D would need empty to be skipped, not merely reordered; the count is still checked, just too late. The general rule this illustrates: never block while holding a lock.
A two-process critical-section solution uses a single shared variable turn, each process waiting until turn names it. Which requirement does this fail?
1. Mutual exclusion
2. Progress
3. Bounded waiting
4. It fails none of the three
Show answer
Answer: B — Progress
Progress. A single turn variable enforces strict alternation, and that is stronger than the problem requires. Mutual exclusion holds perfectly — turn has one value, so only one process is ever admitted — which is why the solution looks correct. But suppose P0 leaves its critical section, sets turn to 1, and then never wants to enter again. P1 enters, sets turn back to 0, and is now permanently locked out: the critical section is empty, P1 wants in, and no process is inside, yet P1 cannot proceed. That is exactly the progress violation. Bounded waiting (option C) is actually satisfied — strict alternation bounds the overtaking at one, which is the irony of this solution. Peterson’s algorithm fixes progress by adding a flag array, so a process announces that it wants in and turn is consulted only to break a genuine tie.
Compared with message passing, shared-memory IPC is faster because:
1. The kernel copies the data more efficiently
2. After the region is mapped, the kernel is not involved in each access
3. It needs no synchronisation
4. It works across a network as well
Show answer
Answer: B — After the region is mapped, the kernel is not involved in each access
The kernel sets up the mapping once and then steps out; after that a read or write to the shared region is an ordinary memory access at memory speed, with no mode switch. Message passing puts a system call on every exchange, and that per-message crossing is the whole of the cost difference. Option A misdescribes the mechanism — the point is that no copying through the kernel happens at all, not that it happens faster. Option C states the exact opposite of the consequence: because the kernel is not mediating, ordering and mutual exclusion become the programmer’s responsibility, so shared memory needs more synchronisation, not less. Option D belongs to message passing, which is precisely why distributed systems are built on it: shared memory presumes one physical memory.
Requiring every process to request resources only in increasing order of a global numbering attacks which deadlock condition?
1. Hold and wait
2. Mutual exclusion
3. Circular wait
4. No preemption
Show answer
Answer: C — Circular wait
Circular wait, and the argument is a one-liner: in a cycle of waiting processes, following the edges around returns you to where you started, so the resource numbers would have to increase all the way around and come back to a smaller value, which is impossible under a total order. Removing the possibility of a cycle removes deadlock, because all four conditions are needed simultaneously. This is also the prevention strategy real systems actually adopt — lock ordering — because the other three attacks are impractical or expensive: mutual exclusion usually cannot be given up (option B: a printer is not sharable), no preemption only works where a resource’s state can be saved and restored (option D), and breaking hold and wait means requesting everything up front (option A), which wastes capacity and can starve a process that needs a popular resource.