25-Comp-A5 Operating Systems · May 2013

Question 2 of 7: Monitor for Bounded Concurrent Access

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

Notes on this paper

98-COMP A-5 Operating Systems — National Examinations, May 2013. 3 hours, closed book, 100 marks. Candidates were instructed to answer any five of the seven questions; all seven are answered below as a complete study resource.

Reference texts: Silberschatz, Galvin & Gagne, Operating System Concepts (10th ed.) — scheduling (ch. 5), process synchronization/monitors (ch. 6–7), deadlocks (ch. 8), memory management/paging (ch. 9–10), file systems and disk scheduling (ch. 11–12); Tanenbaum, Modern Operating Systems (5th ed.), corroborating chapters on scheduling and file systems.

Question 2: Monitor for Bounded Concurrent Access (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.

Given. N processes contend for a shared data record; up to K may access it concurrently (a generalization of mutual exclusion called K-exclusion, with ordinary mutual exclusion as the special case K=1); the monitor language construct provides automatic mutual exclusion on its own procedure bodies plus condition variables with wait()/signal().

Find. A correct monitor implementation of get_access/finish_access, and a justification against mutual exclusion, progress, and bounded waiting.

Approach. Keep a counter of processes currently inside the shared record; block an arriving process on a condition variable whenever the counter has reached K; wake exactly one waiter (in FIFO order) whenever a slot frees up.

monitor DataAccessControl {
    int count = 0;                 // number currently accessing the record
    condition ok;                  // processes blocked waiting for a free slot
                                    // (monitor's default condition queues are FIFO)

    procedure get_access() {
        while (count == K)         // re-check on wakeup (robust to Mesa-style
            ok.wait();             //   "signal-and-continue" monitor semantics)
        count = count + 1;
    }

    procedure finish_access() {
        count = count - 1;
        ok.signal();               // wake (at most) one blocked process, if any;
                                    // a no-op if the queue is empty
    }
}

// Process Pj:
do {
    // 1. compute
    DataAccessControl.get_access();
    // 3. operate on the shared data record
    DataAccessControl.finish_access();
} while (TRUE);

Using while (count == K) rather than if (count == K) costs nothing here (the condition can only become false one unit at a time via finish_access's single decrement) but makes the monitor robust if a future change lets more than one waiter be signalled per finish_access call, or if the underlying monitor uses Mesa-style "signal-and-continue" semantics, where a signalled process is not guaranteed to run immediately and must re-verify the condition before proceeding.

(ii) The three requirements for a solution to the critical-section problem (here generalized to K-way access rather than 1-way) are:

1. Mutual exclusion (generalized to K-exclusion): at any instant, no more than K processes may be inside the shared-data section simultaneously. The monitor enforces this directly — every call to get_access/finish_access executes under the monitor's own implicit mutual exclusion, so count is updated atomically, and a process is only allowed past the while guard when count < K, guaranteeing the invariant 0 ≤ count ≤ K holds at all times.
2. Progress: if the shared record is not at its K-process capacity and one or more processes wish to enter, the decision of who enters next cannot be postponed indefinitely by processes that are not themselves competing to enter (i.e., processes outside their remaining-code section). Here, the moment any accessing process calls finish_access, it immediately decrements count and signals, so a waiting process is admitted in the very next monitor entry — the decision is never deferred to unrelated processes.
3. Bounded waiting: there must be a bound on the number of times other processes are allowed to enter ahead of a process that is already waiting. Because the monitor's condition-variable queue for ok is served in FIFO order (as stated in the problem: "a blocked process is allowed to proceed when one of the processes exits the monitor", i.e., processes are unblocked one at a time as slots free up), a waiting process advances by exactly one queue position each time any of the K currently-active processes calls finish_access — so at most (number of processes ahead of it in the queue) entries can occur before it is admitted, which is a finite, bounded number.

Final Results — Q2

Requirement	How the monitor satisfies it
Mutual exclusion (K-exclusion)	Monitor lock + while(count==K) wait() guard keeps 0 ≤ count ≤ K
Progress	finish_access immediately decrements and signals; no unrelated process can delay admission
Bounded waiting	FIFO condition queue on ok — each finish_access advances the queue by one

---