Prerequisite – Process Synchronization, Monitors, Readers-Writers Problem
Considering a shared Database our objectives are:
- Readers can access database only when there are no writers.
- Writers can access database only when there are no readers or writers.
- Only one thread can manipulate the state variables at a time.
Basic structure of a solution –
Reader() Wait until no writers Access database Check out – wake up a waiting writer Writer() Wait until no active readers or writers Access database Check out – wake up waiting readers or writer
–Now let’s suppose that a writer is active and a mixture of readers and writers now show up.
Who should get in next?
–Or suppose that a writer is waiting and an endless of stream of readers keep showing up.
Would it be fair for them to become active?
So we’ll implement a kind of back-and-forth form of fairness:
- Once a reader is waiting, readers will get in next.
- If a writer is waiting, one writer will get in next.
Implementation of the solution using monitors:-
- The methods should be executed with mutual exclusion i.e. At each point in time, at most one thread may be executing any of its methods.
- Monitors also provide a mechanism for threads to temporarily give up exclusive access, in order to wait for some condition to be met, before regaining exclusive access and resuming their task.
- Monitors also have a mechanism for signaling other threads that such conditions have been met.
- So in this implementation only mutual exclusion is not enough. Threads attempting an operation may need to wait until some assertion P holds true.
- While a thread is waiting upon a condition variable, that thread is not considered to occupy the monitor, and so other threads may enter the monitor to change the monitor’s state.
Code –
// STATE VARIABLES // Number of active readers; initially = 0 int NReaders = 0; // Number of waiting readers; initially = 0 int WaitingReaders = 0; // Number of active writers; initially = 0 int NWriters = 0; // Number of waiting writers; initially = 0 int WaitingWriters = 0; Condition canRead = NULL; Condition canWrite = NULL; Void BeginWrite() { // A writer can enter if there are no other // active writers and no readers are waiting if (NWriters == 1 || NReaders > 0) { ++WaitingWriters; wait(CanWrite); --WaitingWriters; } NWriters = 1; } Void EndWrite() { NWriters = 0; // Checks to see if any readers are waiting if (WaitingReaders) Signal(CanRead); else Signal(CanWrite); } Void BeginRead() { // A reader can enter if there are no writers // active or waiting, so we can have // many readers active all at once if (NWriters == 1 || WaitingWriters > 0) { ++WaitingReaders; // Otherwise, a reader waits (maybe many do) Wait(CanRead); --WaitingReaders; } ++NReaders; Signal(CanRead); } Void EndRead() { // When a reader finishes, if it was the last reader, // it lets a writer in (if any is there). if (--NReaders == 0) Signal(CanWrite); } |
Understanding the solution:-
- It wants to be fair.
- If a writer is waiting, readers queue up.
- If a reader (or another writer) is active or waiting, writers queue up.
- This is mostly fair, although once it lets a reader in, it lets ALL waiting readers in all at once, even if some showed up “after” other waiting writers.
- The code is “simplified” because we know there can only be one writer at a time.
- It also takes advantage of the fact that signal is a no-op if nobody is waiting.
- In the “EndWrite” code (it signals CanWrite without checking for waiting writers)
- In the EndRead code (same thing)
- In StartRead (signals CanRead at the end)
With Semaphores we never did have a “fair” solution of this sort. In fact it can be done but the code is quite tricky. Here the straightforward solution works in the desired way! Monitors are less error-prone and also easier to understand.
leave a comment
0 Comments