25-Comp-A5 Operating Systems · December 2014
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.
(a) Given. The two-process algorithm above, each using only its own boolean flag (get_entry[i]) and the other's flag — there is no shared turn/priority variable. Find. Every distinct design flaw, with a concrete triggering scenario for each. Approach. Trace specific interleavings of the two do-while bodies against the shared flags to see which of mutual exclusion, progress, and bounded waiting can actually be broken, then separately note any non-correctness design weaknesses (the question explicitly asks for those too).
while get_entry[1] loop observes the other flag is false and exits" and "set my own flag back to true and enter CS" is not re-checked, so a process can act on stale information. Concrete interleaving (both flags start false):
| Step | Action | get_entry[0] | get_entry[1] | Proc1 in CS? | Proc2 in CS? |
|---|---|---|---|---|---|
| 1 | Proc1: get_entry[0]=true | T | F | no | no |
| 2 | Proc2: get_entry[1]=true | T | T | no | no |
| 3 | Proc1 sees get_entry[1]=true ⇒ enters if-block, sets get_entry[0]=false | F | T | no | no |
| 4 | Proc2 sees get_entry[0]=false ⇒ skips its if-block, proceeds straight to CS | F | T | no | yes |
| 5 | Proc2 leaves CS: get_entry[1]=false | F | F | no | no |
| 6 | Proc1's while get_entry[1] now sees false ⇒ exits loop (but has not yet re-set its own flag or re-entered CS) | F | F | no | no |
| 7 | Proc2 begins a NEW iteration: get_entry[1]=true | F | T | no | no |
| 8 | Proc2 sees get_entry[0]=false (still) ⇒ skips if-block, enters CS again | F | T | no | yes |
| 9 | Proc1 (resuming step 6) now sets get_entry[0]=true and, per the algorithm, proceeds straight to CS without re-checking get_entry[1] | T | T | yes | yes |
while get_entry[1] no-op; loop spins the CPU rather than blocking, wasting cycles on a uniprocessor (the waiting process cannot even yield the CPU to the very process it is waiting on without an explicit scheduler call) and wasting power/cache bandwidth on a multiprocessor. This is the design flaw the question flags as "not necessarily incorrect results but a design flaw" — a monitor or semaphore-based solution (parts (b)/(c)) blocks the waiting process instead.| Flaw | Category | Trigger |
|---|---|---|
| 1. Mutual exclusion violation | Correctness | Stale "loop exited" state acted on without re-checking the other flag (trace above, step 9) |
| 2. No bounded waiting | Correctness | No turn/queue mechanism; one process can always win the race |
| 3. Possible livelock | Correctness/liveness | Symmetric simultaneous raise/back-off with no progress |
| 4. Busy-waiting | Design/efficiency only | CPU spins in the no-op loop instead of blocking |
(b) A monitor bundles shared data together with the only procedures allowed to touch it, and the language runtime automatically ensures at most one process executes inside any of the monitor's procedures at a time — this alone gives mutual exclusion "for free," with no explicit flags or locks written by the programmer. Synchronization beyond simple exclusion is provided by condition variables, each supporting wait() (block the calling process and release the monitor lock) and signal() (wake one waiting process). Example — a bounded buffer of capacity $N$ shared between a producer and a consumer:
monitor BoundedBuffer {
item buf[N]; int count = 0, in = 0, out = 0;
condition notFull, notEmpty;
procedure insert(item x) {
while (count == N) notFull.wait(); // buffer full: block, don't spin
buf[in] = x; in = (in+1) % N; count++;
notEmpty.signal(); // wake a consumer if one is waiting
}
procedure remove() returns item {
while (count == 0) notEmpty.wait(); // buffer empty: block
item x = buf[out]; out = (out+1) % N; count--;
notFull.signal(); // wake a producer if one is waiting
return x;
}
}
Mutual exclusion (only one of insert/remove runs at a time) is automatic; synchronization (a producer must wait when full, a consumer when empty) is explicit via the two condition variables, and each side signals the condition the other side is plausibly waiting on exactly when that condition becomes true.
(c) A counting or binary semaphore guarding a critical section prevents starvation when its internal blocked-process queue is served in FIFO order: every process that calls wait() (P) while the semaphore is unavailable is appended to the end of the queue, and every signal() (V) wakes the process at the front of that queue, not an arbitrary or newest one. Example: three processes P1, P2, P3 all call wait(mutex) in that order while P0 holds the critical section; they queue as [P1, P2, P3]. Each time P0 (or whichever process currently holds the section) calls signal(mutex), the process at the front of the queue — P1 first, then P2, then P3 — is admitted next, regardless of how many *new* processes arrive and call wait() afterward (any newcomer is appended to the back of the queue, behind P1–P3). This guarantees a process waits at most (queue length at the time it joined) turns before entering, which is a hard bound — exactly what rules out starvation. (A "weak" semaphore implementation that wakes an arbitrary blocked process instead of the front of a FIFO queue does not give this guarantee and can starve a process indefinitely.)