4

From Operating System Concepts by Abraham Silberschatz, Peter B. Galvin, Greg Gagne

5.8.3 Implementing a Monitor Using Semaphores

We now consider a possible implementation of the monitor mechanism using semaphores. For each monitor, a semaphore mutex (initialized to 1) is provided. A process must execute wait(mutex) before entering the monitor and must execute signal(mutex) after leaving the monitor.

Since a signaling process must wait until the resumed process either leaves or waits, an additional semaphore, next, is introduced, initialized to 0. The signaling processes can use next to suspend themselves. An integer variable next count is also provided to count the number of processes suspended on next. Thus, each external function F is replaced by

wait(mutex);
...
body of F
...
if (next count > 0)
    signal(next);
else
    signal(mutex);

Mutual exclusion within a monitor is ensured.

  1. Since the semaphore mutex is initialized to 1, is it used for limiting at most one process can be inside the monitor?

  2. The semaphore next means the number of processes suspended on next. Are these processes suspended on next all inside a monitor?

  3. If the answers to the above two questions are yes, do they contradict each other?

    If no, how does a monitor work actually?

Thanks.

2
  1. Since the semaphore mutex is initialized to 1, is it used for limiting at most one process can be inside the monitor?

Yes.

  1. The semaphore next means the number of processes suspended on next. Are these processes suspended on next all inside a monitor?

Yes, some are suspended on next, some on mutex. Those suspended on next are "in" the monitor, in the sense that have passed the wait on mutex, and have used that mutual exclusion in order to perform a test of condition(s) within the safety (atomicity) of the lock that the monitor provides, yet have chosen to yield until a later time, and are thus suspended on the next queue instead of on the mutex queue.

This is an optional feature. If no client ever yields due to conditions, then there will only be clients waiting on the mutex. If a client does yield due to conditions, then it gets priority over clients that haven't yet passed the original wait for the mutex. (As a thread yields due to conditions, it effectively releases the monitor during its sleeping, and reacquires it on waking; however, it doesn't loose its priority, e.g. it is in the next queue now, not the mutex queue.)

  1. If the answers to the above two questions are yes, do they contradict each other?

No, because the next queue has a different purpose and is optionally used when a thread that has obtained the lock chooses to yield instead of simply releasing the lock.


Another text states this somewhat clearer:

5.8.3 Implementing a Monitor Using Semaphores

• One possible implementation of a monitor uses a semaphore "mutex" to control mutual exclusionary access to the monitor, and a counting semaphore "next" on which processes can suspend themselves after they are already "inside" the monitor ( in conjunction with condition variables, see below. ) The integer next_count keeps track of how many processes are waiting in the next queue. Externally accessible monitor processes are then implemented as:

• Condition variables can be implemented using semaphores as well. For a condition x, a semaphore "x_sem" and an integer "x_count" are introduced, both initialized to zero. The wait and signal methods are then implemented as follows. ( This approach to the condition implements the signal-and-wait option described above for ensuring that only one process at a time is active inside the monitor. )

  • Thanks. what is the relation betw the next queue and the queue for each condition variable? Especially I don't understand why we need to call next.signal and next.wait in the implementations of x_sem.wait and x_sem.signal respectively. – Tim Oct 28 '16 at 12:58
  • Must the processes in the queue of x_sem also appear in the queue of next? How about vice versa? – Tim Oct 28 '16 at 13:31
  • (a) Each differentiated condition, x, y, z, requires its own semaphore/queue so that just those threads can be signaled individually. However parties interested in specific condition(s) must still fully coordinate with the main monitor: (1) so they run under mutual exclusion protection with respect to all interested parties, not just the ones interested in a single condition, say x, and (2) so that they continue the execution of other interested parties (on other conditions and without conditions) upon their completion. – Erik Eidt Oct 28 '16 at 14:32
  • (b) For threads interested in condition variables, yes -- but not concurrently. The threads transition from "executing", i.e. having control of the monitor (and being de-queued of all queues) to being in one queue, then back to having control of the monitor, then to being in another queue. – Erik Eidt Oct 28 '16 at 14:40
  • Effectively, only one thread of each condition variable queue is in the next queue. Condition-Wait transitions the thread from controlling the main monitor to the condition variable queue first, then on condition wait completion, back to having control of the main monitor once again (and not being in queue). Condition-Signal gives one of the other waiters on the same condition variable control of the monitor while transferring itself to the next queue (so that it can later safely decrement the next counter). – Erik Eidt Oct 28 '16 at 14:42

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.