25-Comp-A5 Operating Systems · May 2017

Question 3 of 7: Critical Section Problem

Nivaar worked solution (AI-drafted; not reviewed by a licensed engineer)

Question 3: Critical Section Problem (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) Given. The flag-based algorithm above (no shared "turn" variable — only each process's own need[i] flag is used to arbitrate entry). Find. Every distinct design flaw, with a concrete triggering interleaving for each. Approach. Because the "set my flag / check the other's flag / maybe back off" sequence is NOT atomic, construct an explicit fine-grained interleaving of individual statements from both processes and track the shared flags step by step — this is the only way to expose a race that a hand-wave ("there might be a race") would miss.

1. Defect 1 — mutual exclusion CAN be violated (not just a livelock). Trace the following interleaving of individual statements, starting from need[0]=need[1]=false:

   Fine-grained interleaving that puts BOTH processes in the critical section at once

   Step	Process : statement	need[0]	need[1]
   1	P0: need[0] = true;	true	false
   2	P1: need[1] = true;	true	true
   3	P0: evaluates if(need[1]) → true (reads need[1]=true, takes the branch)	true	true
   4	P1: evaluates if(need[0]) → true (reads need[0]=true, takes the branch)	true	true
   5	P0: executes need[0] = false;	false	true
   6	P1: executes need[1] = false;	false	false
   7	P0: evaluates while(need[1]) → reads false (P1 just cleared it in step 6) → loop exits immediately, no spin	false	false
   8	P1: evaluates while(need[0]) → reads false (P0 cleared it in step 5, still false) → loop exits immediately, no spin	false	false
   9	P1: executes need[1] = true; and falls straight through to Code for CS	false	true
   10	P0: executes need[0] = true; and falls straight through to Code for CS	true	true

   After step 10, both P0 and P1 are simultaneously executing "Code for CS" — there is no further check between re-asserting need[i]=true and entering the critical section, so once both busy-wait loops exit "at the same moment" (steps 7–8, each reading the other's flag as momentarily false), nothing stops both from proceeding. $$\boxed{\text{Defect 1: the algorithm does NOT guarantee mutual exclusion}}$$
2. Defect 2 — busy-waiting is itself a design flaw, independent of correctness. The statement while need[1] no-op; (and its P1 mirror) spins the CPU in a tight loop instead of blocking, burning CPU cycles that could run other ready processes; on a single-CPU system this can also cause priority-inversion-like starvation if the waiting process has higher scheduling priority than the process it is waiting on (it never yields the CPU to let that process make progress). The question's own wording — "may not give incorrect results but indicates a design flaw" — is a direct pointer at exactly this class of defect.
3. Defect 3 — the algorithm cannot guarantee bounded waiting. As illustrated by a variant of the step 6–9 timing above, a process can be repeatedly "overtaken": every time P0's busy-wait loop happens to sample need[1] during the brief instant it is false, P1 can already be looping back around its own do-loop and re-claiming the critical section before P0's own re-entry completes, with no counter or turn-token limiting how many times this can repeat in P1's favour. No explicit bound is enforced on how many times one process can enter the CS while the other keeps waiting.

(b) The bounded waiting requirement states that there must exist a fixed, finite bound on the number of times OTHER processes are allowed to enter their critical sections after a given process has signalled its intent to enter (e.g. by requesting entry) and before that process's own request is granted. Example: with 3 processes P0, P1, P2 sharing one critical section, a correct bounded-waiting solution might guarantee that once P0 requests entry, at most one more entry each by P1 and P2 (i.e. at most 2 intervening entries total) can occur before P0 is admitted — a design that let P1 and P2 alternate admission indefinitely while P0's request sits unserved would violate bounded waiting even though mutual exclusion and progress both still hold.

(c) Whether bounded waiting holds under a monitor depends on the queuing discipline used for processes blocked trying to ENTER the monitor (the entry queue), which the monitor construct itself does not specify. A monitor guarantees mutual exclusion (only one process executes inside it at a time) by construction, but the language/runtime is free to choose ANY policy — including an unfair one — for which waiting process is admitted next when the monitor becomes free. If the underlying implementation serves the entry queue (and any condition-variable wait queues) in strict FIFO order, then bounded waiting IS satisfied, since a waiting process can be overtaken by at most the number of processes already ahead of it in that FIFO queue — a fixed bound. But if the implementation makes no such guarantee (e.g. picks an arbitrary or priority-based next process), a process could in principle be repeatedly bypassed and wait unboundedly, so bounded waiting is not an inherent property of monitors — it holds only when the entry/condition queues are explicitly implemented as FIFO.