25-Comp-A5 Operating Systems · May 2015
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 monitor is a programming-language construct that bundles shared data with the only procedures allowed to touch it, and the compiler/runtime automatically inserts mutual exclusion around every procedure body — at most one process is ever "inside" the monitor executing one of its procedures at a time. This directly satisfies mutual exclusion: two processes can never simultaneously execute code that touches the shared data, because entry to any monitor procedure is itself serialized by the monitor's implicit lock. Progress is satisfied because the moment the active process either exits the monitor or blocks itself on a condition variable (wait()), the monitor's lock becomes available and the runtime immediately admits the next waiting process (chosen by the monitor's own scheduler) — the decision of who enters next is made entirely by monitor/OS machinery, never deferred to processes that are not themselves trying to enter. Bounded waiting depends on how the monitor's entry queue and any condition-variable queues are served: if they are served fairly (e.g. FIFO, or at least with no indefinite favouritism), a process's wait is bounded by the finite number of other processes that can overtake it, each overtake corresponding to one finite monitor entry by someone else. The strength of the monitor here is that all three properties reduce to a single, centrally-enforced locking discipline rather than requiring each programmer to hand-code correct entry/exit protocols, which is exactly why monitors are considered less error-prone than raw semaphores for this problem.
The Readers-Writers problem models a shared resource (e.g. a database record or a shared file) accessed by two classes of processes: readers, who only inspect the data and may safely do so concurrently with any number of other readers, and writers, who modify the data and must have completely exclusive access — no reader or other writer may be touching the data while a writer is active. The synchronization challenge is to allow many simultaneous readers for good throughput while still guaranteeing a writer's mutual exclusion, and to do so without starving either class (a naive "readers always win if any are active" policy can starve writers indefinitely if readers keep arriving).
monitor ReaderWriter {
int active_readers = 0; // readers currently inside
boolean writing = false; // a writer is currently inside
int waiting_writers = 0; // writers blocked, waiting their turn
condition okToRead, okToWrite;
procedure start_read() {
// a new reader waits if a writer is active OR a writer is
// already waiting (this is what prevents writer starvation --
// readers do not keep cutting in front of a waiting writer)
while (writing || waiting_writers > 0)
okToRead.wait();
active_readers = active_readers + 1;
okToRead.signal(); // cascade-wake the next waiting reader, if any
}
procedure end_read() {
active_readers = active_readers - 1;
if (active_readers == 0)
okToWrite.signal(); // last reader out wakes a waiting writer
}
procedure start_write() {
waiting_writers = waiting_writers + 1;
while (active_readers > 0 || writing)
okToWrite.wait();
waiting_writers = waiting_writers - 1;
writing = true;
}
procedure end_write() {
writing = false;
if (waiting_writers > 0)
okToWrite.signal(); // prefer a waiting writer next
else
okToRead.signal(); // otherwise release the readers
}
}
Readers call start_read()/end_read() around their access, writers call start_write()/end_write() around theirs. Mutual exclusion for writers holds because start_write() only proceeds when both active_readers==0 and writing==false. Concurrent reading is allowed because start_read() only checks for an active or waiting writer, never for other readers. Writer starvation is prevented because a newly arriving reader is blocked the instant any writer is waiting (not just active) — so a steady stream of readers cannot indefinitely postpone a writer that has already announced intent by incrementing waiting_writers.
Deadlock is a state in which a set of processes are each waiting for an event (typically, release of a resource) that can only be caused by another process in that same set — none of them can ever proceed, and the condition persists forever without external intervention. Starvation (indefinite postponement) is different: a process remains perpetually unable to make progress even though the system as a whole continues to run and other processes continue to complete — the starved process is simply always passed over by whatever selection policy decides who goes next. Deadlock is a global standstill; starvation can coexist with a perfectly "live" system for everyone except the unlucky process.
Can starvation occur under a semaphore-guarded critical section? Yes. The semaphore primitive itself only guarantees that at most one process is in the critical section at a time (mutual exclusion) and, in most textbook treatments, that some blocked process is woken on every signal() — but it does not, by definition, guarantee which blocked process is woken. If the semaphore's internal waiting-process list is not served in FIFO order (e.g. it is implemented as a LIFO stack, or the OS scheduler simply picks whichever waiting process is scheduled next with no queue-position guarantee), a particular process can in principle be repeatedly bypassed by other processes that arrive later but are chosen first, waiting indefinitely even though the semaphore itself is being signalled regularly. Guaranteeing bounded waiting (and thus ruling out this kind of starvation) requires the semaphore's implementation to additionally commit to FIFO (or some other fairness-bounding) service of its waiting queue.