25-Comp-A5 Operating Systems · May 2014

Question 5 of 7: Monitor for a Priority-Scheduled Shared Plotter

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

Notes on this paper

98-COMP A-5 Operating Systems — National Examinations, May 2014. 3 hours, closed book (approved calculator only). 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 5: Monitor for a Priority-Scheduled Shared Plotter (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. A single plotter shared by n processes; each request is tagged red ('R') or black ('B'); on release, if ≥1 process waits, the plotter goes to a red waiter when $\text{redWaiting} \ge 3\times\text{blackWaiting}$ and $\text{redWaiting}>0$, otherwise to a black waiter (whenever one is waiting).

Find. Correct monitor pseudocode for get_plotter(colour) / release_plotter(colour), using only ordinary monitor-local variables and condition variables (no semaphores).

Approach. Keep a busy flag and two waiter counters (redWaiting, blackWaiting), one condition variable per colour. A caller blocks on its own colour's condition variable only if the plotter is currently busy; release_plotter applies the 3× rule to decide which single condition variable to signal (a direct hand-off, so the woken process resumes already holding the plotter and busy never needs to be cleared and re-set).

monitor PlotterControl {
    boolean busy = false;       // true while some process is using the plotter
    int redWaiting = 0;         // processes currently blocked wanting 'R'
    int blackWaiting = 0;       // processes currently blocked wanting 'B'
    condition redQ;             // FIFO queue of blocked red-waiting processes
    condition blackQ;           // FIFO queue of blocked black-waiting processes

    procedure get_plotter(char colour) {
        if (busy) {
            if (colour == 'R') {
                redWaiting = redWaiting + 1;
                redQ.wait();          // blocks here; resumes already holding
                redWaiting = redWaiting - 1;   //   the plotter once signalled
            } else { // colour == 'B'
                blackWaiting = blackWaiting + 1;
                blackQ.wait();
                blackWaiting = blackWaiting - 1;
            }
        }
        busy = true;   // reached directly (plotter was free) or on wakeup
    }

    procedure release_plotter(char colour) {
        // colour is accepted per the interface but is not needed to decide
        // who goes next -- the 3x rule depends only on the waiter counts.
        if (redWaiting > 0 && redWaiting >= 3 * blackWaiting) {
            redQ.signal();     // hands the plotter directly to a red waiter
        } else if (blackWaiting > 0) {
            blackQ.signal();   // hands the plotter directly to a black waiter
        } else {
            busy = false;      // nobody waiting; plotter goes idle
        }
    }
}

// Process Pi:
do {
    // 1. compute
    PlotterControl.get_plotter(colour);
    // 3. use the plotter
    PlotterControl.release_plotter(colour);
} while (TRUE);

Documentation / correctness. busy is true exactly while some process holds the plotter, and is only ever set on the two paths that grant it (falling straight through in get_plotter when the plotter was free, or being resumed by a signal from release_plotter) — it is never set to false except in release_plotter's final else, when both counters are zero, so no two processes can ever believe they hold the plotter simultaneously. The 3× test in release_plotter is written as redWaiting > 0 && redWaiting >= 3*blackWaiting rather than just redWaiting >= 3*blackWaiting: with blackWaiting = 0 the bare inequality is always true (any redWaiting ≥ 0 satisfies "≥ 0"), which would be correct anyway since red is the only colour waiting, but the explicit redWaiting > 0 guard makes the branch's intent self-documenting and avoids relying on the degenerate case. Because release_plotter hands the plotter directly to the process it signals (rather than merely making it "runnable to compete again"), the design relies on Hoare-style immediate-transfer monitor semantics; on a Mesa-style ("signal-and-continue") monitor, each waiter would instead re-check busy in a while loop after waking, which is the more portable but slightly more defensive variant.

Final Results — Q5

Requirement	How the monitor satisfies it
Mutual exclusion on the plotter	busy flag, set/cleared only inside monitor procedures
Priority rule (3× red-to-black)	release_plotter tests redWaiting >= 3*blackWaiting before signalling
No starvation of a solo waiting colour	the else if (blackWaiting > 0) branch always serves black when no red qualifies
No semaphore variables	only boolean, int, and monitor condition variables declared

---