25-Comp-A5 Operating Systems · December 2013
Nivaar worked solution (AI-drafted; not reviewed by a licensed engineer)
Question text not reproduced: the examination questions are © Engineers and Geoscientists BC. Open the official past paper (linked at the top of this page) to read the question, then follow the worked solution below.
Given. Two processes share boolean flags want_access[0] (A's flag) and want_access[1] (B's flag), both initially false. Each process's loop body: set its own flag true; check the OTHER process's flag ONCE; if set, clear its own flag, spin-wait until the other's flag clears, then set its own flag true again and fall straight into the critical section (no re-check); execute the critical section; clear its own flag; repeat.
Find. Every distinct design defect in this algorithm, including ones that do not always cause an incorrect result.
Approach. Trace concrete interleavings (assuming each read/write of a shared flag is an atomic, individually-scheduled step, which is the standard assumption for this class of problem) to show a defect actually manifests, rather than asserting it abstractly.
Process A Process B
repeat repeat
want_access[0] = true; want_access[1] = true;
if want_access[1] { if want_access[0] {
want_access[0] = false; want_access[1] = false;
while want_access[1] no-op; while want_access[0] no-op;
want_access[0] = true; want_access[1] = true;
}; };
<Critical Section> <Critical Section>
want_access[0] = false; want_access[1] = false;
until false; until false;
true again and falls straight into the critical section WITHOUT re-checking the other's flag. A concrete interleaving that puts both processes in the critical section together:
want_access[0]=true. (2) B: want_access[1]=true. (3) A reads want_access[1]=true $\to$ backs off: want_access[0]=false; A now spins on while want_access[1]. (4) B reads want_access[0]=false (A already cleared it in step 3) $\to$ B's if is false, B skips the back-off entirely and enters its critical section directly. (5) B finishes and executes want_access[1]=false, then immediately loops back and executes want_access[1]=true for its NEXT iteration. (6) A's spin loop happens to sample want_access[1] in the brief instant between B's clear and B's next set — A sees false, exits the loop, sets want_access[0]=true, and (per the algorithm) proceeds STRAIGHT into its critical section without checking want_access[1] again. (7) Meanwhile B, now back at the top of its own loop, reads want_access[0] — if this read happens before step 6's write completes, B sees false, skips its own back-off, and also enters its critical section. Both A and B are now inside the critical section simultaneously — mutual exclusion is broken. This is possible specifically because the single un-looped if-check is not re-verified after the flag is reasserted.no-op polling loop, burning CPU cycles the whole time a process is blocked rather than yielding the CPU (as a semaphore-based blocking wait or a monitor's condition variable would). This never produces a wrong RESULT, but it is a real design flaw the question explicitly asks to include: on a single-CPU system it can even slow down the very process whose flag is being awaited, since the spinning process consumes cycles that could otherwise let the flag-holder finish sooner.| # | Defect | Severity |
|---|---|---|
| 1 | Mutual exclusion can be violated (single un-looped re-check after back-off) | Correctness — critical |
| 2 | Livelock / no guaranteed progress under symmetric back-off | Correctness — critical |
| 3 | No bounded waiting (no fairness/turn mechanism) | Correctness — important |
| 4 | Busy waiting (spin loop wastes CPU cycles) | Design/efficiency, not correctness |
(b) A correct solution to the critical section problem must satisfy three requirements, illustrated against the algorithm above precisely because it fails (or only accidentally satisfies) each one. Mutual exclusion: at most one process may execute in its critical section at any time — violated here as shown in Defect 1 (both A and B can be inside simultaneously after a back-off/re-entry race). Progress: if no process is in the critical section and one or more wish to enter, the decision as to which enters next cannot be postponed indefinitely by processes not competing to enter (e.g. by processes outside their remaining code) — here the decision is left ENTIRELY to scheduler timing with no arbitration logic, so although progress isn't blocked by an unrelated third party, the algorithm's own logic provides no positive guarantee that a requesting process is ever admitted (Defect 2). Bounded waiting: there must be a bound on the number of times other processes are allowed to enter after a process has requested entry and before that request is granted — violated here because nothing counts or limits how many times the "other" process may win the race (Defect 3). A correct algorithm (e.g. Peterson's, which adds an explicit shared turn variable checked inside a LOOPED condition while (flag[other] && turn==other)) satisfies all three simultaneously specifically by re-checking the entry condition every time rather than once, and by using turn to guarantee that whichever process was NOT given priority this round is guaranteed to get it if it asks again.
(c) A semaphore is an integer variable accessed only through two atomic operations, wait() (a.k.a. P, decrement, blocking if the result would go negative) and signal() (a.k.a. V, increment, waking a blocked process if any is waiting) — critically, both operations are guaranteed atomic by the underlying OS/hardware, which is exactly the property the flag-based algorithm above lacks. A binary semaphore initialized to 1 solves the two-process (or N-process) critical section problem directly: wait(mutex) immediately before the critical section, signal(mutex) immediately after. Mutual exclusion follows because the atomic decrement in wait() can only let ONE process see the semaphore drop from 1 to 0 and proceed; every other simultaneous caller is blocked by the same atomic operation (this is precisely the atomicity the flag algorithm's if-then-set sequence lacks, which is what created Defect 1). Progress and (with a FIFO-ordered block queue) bounded waiting follow because signal() unblocks a waiting process rather than requiring processes to poll and race each other, removing the busy-waiting inefficiency (Defect 4) as well. As an example beyond mutual exclusion, a counting semaphore initialized to $N$ generalizes this to $N$-way concurrent access (e.g. a pool of $N$ identical resources), with wait()/signal() pairs around each acquire/release exactly as in Q2's monitor-style problems.