25-Comp-A5 Operating Systems · December 2015

Question 6 of 7: Monitor Design 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, December 2015. 3 hours, closed book (one approved pocket calculator only). 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.) — CPU scheduling (ch. 5), process synchronization/monitors (ch. 6–7), deadlocks (ch. 8), memory management/paging (ch. 9–10), mass-storage/file-system implementation and disk scheduling (ch. 11–12), real-time systems (ch. 19); Tanenbaum, Modern Operating Systems (5th ed.), corroborating chapters on scheduling, virtual memory and file systems.

Question 6: Monitor Design 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.

(a) Given. Up to $H$ processes may concurrently execute inside the monitor's protected region; a $(H{+}1)$-th requester must block until someone currently inside calls done_access. No semaphore variable is permitted — only ordinary variables and monitor condition variables. Find. Monitor pseudocode implementing get_access/done_access. Approach. Track a single integer counter of processes currently inside; a process requesting entry when the counter is already at $H$ waits on a condition variable; a process leaving decrements the counter and signals one waiter, since exactly one slot becomes free per done_access call.

monitor bounded_access
    integer count             // number of processes currently inside (0..H)
    condition not_full        // signalled whenever count drops below H

    procedure get_access() {
        while (count >= H)
            wait(not_full);    // blocks; releases the monitor lock while waiting
        count := count + 1;
    }

    procedure done_access() {
        count := count - 1;
        signal(not_full);      // wakes at most one waiting process, if any
    }

    initialization code {
        count := 0;
    }

Using a while loop (not if) around the wait makes the solution correct under both Hoare-style monitors (signal immediately transfers the CPU to the woken process) and Mesa-style monitors (signal is only a hint; the woken process must re-check the condition before proceeding, since another process could have raced back in first). Worked example check: with $H=2$, once $P_i$ and $P_j$ are both inside ($count=2$), a requesting $P_k$ finds $count\ge H$ and blocks on not_full; when $P_j$ calls done_access, $count$ drops to 1 and $P_k$ is signalled, re-checks $count(1)<H(2)$, and proceeds — exactly matching the behaviour described in the question.

(b) The three classical requirements for any critical-section solution are:

1. Mutual exclusion. No two processes may simultaneously execute inside a section that requires exclusive access to the same resource. Here, the monitor's own implicit lock guarantees mutual exclusion on the monitor's internal data (the count variable itself is never touched by two processes at once), while the shared data RECORD is allowed up to $H$ concurrent accessors by explicit design — this is bounded concurrency, not full mutual exclusion, and is exactly what the question asks for (H is a deliberate relaxation of strict 1-at-a-time mutual exclusion).
2. Progress. If no process is currently inside the protected region and one or more processes wish to enter, the decision of who enters next cannot be postponed indefinitely by processes that are NOT interested in entering. The monitor satisfies this because get_access only checks $count$ and the shared condition — a waiting process is only kept out by processes that are actually inside using up a slot, never by 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 has already requested entry and is waiting. The while-loop-plus-signal design here relies on the monitor's FIFO-ish wakeup discipline (most monitor implementations queue waiters and signal in FIFO or otherwise fair order); as written using plain signal/wait, bounded waiting is only guaranteed if the underlying condition-variable implementation queues waiters fairly — a common exam follow-up point is that a "signal-most-recent" or unfair implementation could, in principle, allow a waiter to be bypassed indefinitely, so a fully rigorous solution would use an explicit FIFO ticket (a queue of waiting IDs, each with its own condition variable) rather than relying on implementation-defined signal order.

---