25-Comp-A5 Operating Systems · May 2018
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 P0, P1 share boolean flags guard0, guard1 (both initially false). Each process raises its own flag, checks the other's flag, and — only if it finds the other's flag raised — retreats (lowers its own flag, busy-waits for the other's flag to clear, then re-raises its own) before proceeding into the critical section (CS).
Find. Every distinct design flaw, each with a concrete triggering interleaving.
Approach. Model each process as a small state machine of atomic actions (set/check guard0/guard1, enter/exit CS) and exhaustively search every possible interleaving — a model-checking approach — for (i) reachable states in which both processes are inside the CS simultaneously, and (ii) the design smell the question itself calls out (harm even without incorrect results).
| # | Event | guard0 | guard1 |
|---|---|---|---|
| 0 | Initial state | F | F |
| 1 | P0 sets guard0 = true | T | F |
| 2 | P1 sets guard1 = true | T | T |
| 3 | P0 checks guard1 (true) → takes the retreat branch | T | T |
| 4 | P1 checks guard0 (true) → takes the retreat branch | T | T |
| 5 | P0 retreats: guard0 = false | F | T |
| 6 | P1 retreats: guard1 = false | F | F |
| 7 | P0's busy-wait sees guard1 = false → exits wait | F | F |
| 8 | P1's busy-wait sees guard0 = false (P0 hasn't re-raised it yet) → exits wait | F | F |
| 9 | P0 re-raises guard0 = true and enters CS unconditionally | T | F |
| 10 | P1 re-raises guard1 = true and enters CS unconditionally | T | T |
while (guard1) ; and P1's while (guard0) ; — but is the same underlying design defect in both, so it is explained once: a process that finds the CS occupied spins on the CPU consuming cycles instead of blocking and yielding the processor to other ready work. On a uniprocessor this can waste an entire time slice with no useful progress, and under priority scheduling a low-priority waiter spinning while a high-priority holder is delayed elsewhere is the classic setup for priority inversion.turn variable for this reason). Nothing in the design bounds how many times, in a row, one process's retreat/re-raise can happen to win the race over the other's whenever both attempt entry at nearly the same time; a scheduler could repeatedly resolve the race the same way, so bounded waiting is not established by this algorithm even on the runs where mutual exclusion happens to hold.| Flaw | Class | Evidence |
|---|---|---|
| Mutual exclusion violated | Correctness | 10-step interleaving, both processes reach CS simultaneously (model-checked) |
| Busy-waiting (2 occurrences: P0 and P1) | Design flaw, not incorrect results | while (guardX) ; in each process |
| No bounded-waiting guarantee | Design flaw / fairness | No turn/tie-break variable, unlike Peterson's solution |
(b) The three critical-section requirements under a monitor. A monitor is a language-level construct that bundles shared data with the only procedures allowed to touch it, and the runtime guarantees that at most one thread is active inside the monitor at any time.
wait() on a condition variable, which atomically releases the monitor lock while blocking, so the monitor is never held by an idle waiter and some other thread can always enter and make progress. This is not entirely "free," however: an incorrectly designed signalling discipline (e.g. a lost wakeup, or "signal-and-continue" semantics where the signalled thread's condition is re-invalidated before it runs) can still stall progress, so progress depends on correct monitor design, not just the construct's existence.(c) Real-time systems. A real-time system is one whose correctness depends not only on the logical result of a computation but on the time by which that result is produced — a logically correct answer delivered after its deadline is treated as a failure. Hard real-time systems have deadlines that must never be missed: a missed deadline is a system failure with potentially catastrophic consequences (e.g. an anti-lock braking controller that must compute a new brake-pressure command within a few milliseconds of a wheel-speed sample, or a pacemaker's pacing-pulse timer). Soft real-time systems have deadlines whose occasional miss degrades quality of service but is not catastrophic: a missed deadline just makes the result less useful, not useless (e.g. a video-conferencing frame decoder that occasionally drops or delays a frame under load, or an online game's physics tick running a little late under heavy load) — the system still functions, just with visibly degraded, statistically bounded quality.