Question 2 of 7

Question 2 (20 marks)

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.

(a) The algorithm has one genuinely incorrect (mutual-exclusion-violating) defect plus design flaws (busy waiting, no bounded waiting) that do not by themselves corrupt a result; each occurs symmetrically in P0 and P1 and is explained once.

Defect 1 (correctness — mutual exclusion can actually fail). The retreat-and-re-raise pattern (check0=false; while(check1); check0=true;) contains no re-check of check1 immediately before the unconditional re-raise, and no shared "whose turn is it" tie-breaker (unlike Peterson's algorithm, which adds exactly such a turn variable to this same flag skeleton). If both processes retreat in lockstep — each sees the other's flag raised, both lower their own flag and spin, and both then observe the other's flag drop to false during the same interval — both re-raise unconditionally and both fall through into the critical section simultaneously. A concrete interleaving that forces this:

At step 10 both processes are inside their critical sections simultaneously — mutual exclusion is violated. This is not a rare corner case invented for the exam; it is exactly the failure Peterson's algorithm's turn variable exists to rule out (whichever process set turn to the other's id last is forced to wait, breaking the lockstep symmetry above).

Defect 2 (design flaw — busy waiting). Each retreating process waits in while(check1){no-op}; (P0) / while(check0){no-op}; (P1), a spin loop that consumes its whole CPU quantum repeatedly testing a flag that cannot change until the other process is scheduled. On a uniprocessor this is pure waste (the flag it is waiting on can only change when it is descheduled), and the results are still correct — exactly the question's “may not give rise to incorrect results but indicates a flaw in design” category. A blocking primitive (semaphore/condition variable) should be used instead. The same flaw occurs symmetrically in P1.

Defect 3 (no bounded waiting — a retreating process can starve). While P0 spins it has lowered check0, so P1 can repeatedly run check1=true → test check0 (false) → enter its CS directly, then set check1=false, run its RS and raise check1 again. P0 escapes the spin only if it happens to be scheduled during the short window in which check1 is false; an unlucky (but legal) schedule can keep missing that window forever, so there is no bound on how many times P1 enters its CS ahead of P0 (and symmetrically for P1). Note what does not happen: the algorithm cannot deadlock or livelock, because the retreat happens only once per attempt and, if both processes are spinning at the same time, both flags are necessarily false so both leave the spin — the price of that “progress” is precisely the unconditional entry that causes Defect 1. A fourth, related point: the if-test and the re-raise are separate non-atomic steps, so every check-then-act on the shared flags is itself a race window; this is the root cause of Defect 1 in both processes.

(b) Monitors and the three critical-section requirements. A monitor is a language-level construct that automatically wraps every one of its procedure bodies in an implicit lock, so only one process can be executing any monitor procedure at a time.

• Mutual exclusion — satisfied by construction. The compiler/runtime, not the programmer, enforces that only one thread is active inside the monitor at once; there is no way to write a monitor procedure that violates it (unlike the hand-rolled flag algorithm in part (a)).
• Progress — satisfied provided the monitor is used correctly. When a thread blocks on a condition variable (cwait) it releases the monitor lock, so some other thread can enter and eventually csignal it; progress can only be lost by a programming error (e.g. an infinite loop inside the monitor, or forgetting to signal a condition another thread is permanently blocked on), not by the monitor mechanism itself.
• Bounded waiting — NOT guaranteed by the monitor construct itself. The standard monitor specification says nothing about the order in which multiple threads blocked on the entry queue or on the same condition variable are woken; an implementation with an unfair (e.g. LIFO or arbitrary) wake-up policy can let one thread wait indefinitely while others are repeatedly serviced. Bounded waiting is only obtained if the underlying implementation additionally guarantees FIFO ordering on the entry queue and on each condition variable's wait queue.

(c) Starvation. Starvation (indefinite postponement) is the situation where a process that is ready to run and would eventually be scheduled under a fair policy instead waits for an unbounded, in principle infinite, amount of time because the scheduler's rule keeps preferring other processes. Under strict (non-aged) priority-based CPU scheduling, a low-priority process starves whenever a steady stream of higher-priority processes keeps arriving: each time the low-priority process is about to reach the head of the ready queue, a new higher-priority arrival preempts it (if preemptive) or is simply dispatched ahead of it (if non-preemptive), so it never actually receives the CPU. Example: on a system running a continuous stream of high-priority interactive/real-time tasks (e.g. keyboard/network interrupts serviced as priority-1 work) alongside one priority-10 batch job, the batch job can wait indefinitely if the priority-1 workload never lets up, even though the CPU is technically being fully utilised the whole time. The standard remedy is aging: gradually increase a waiting process's priority the longer it waits, so it eventually becomes the highest-priority ready process and is guaranteed to run.