Internal Scheduling

Internal Scheduling

Most of the scheduling occurs inside the monitor instead of from the entry queue (the entry queue must still exist).

Requires additional queues inside the monitor on which tasks can block and subsequently be unblocked by other tasks.

Very similar scheduling to the synchronization capabilities provided by synchronization locks.

• Notice declaration of two uCondition variable at top of the bounded buffer.
• Both insert and remove begin by checking the buffer state to determine if progress can be made, like the accept version.
• Very similar to semaphore version, except the Monitor/Monitor (Synchronization) version has an explicit counter, count, because a condition variable has no counter.
• If progress cannot be made, i.e., the buffer is full or empty, the task in the monitor explicitly executes a wait to block its execution at this time (like a P), which implicitly unlocks the monitor so another task can enter and change the monitor state.
  • a wait always blocks the task executing it. The blocked task relies on cooperation to unblock it at some appropriate time
• If a task can make progress, an element is add ed or removed from the buffer, respectively.
• Cooperation occurs as a task exits either mutex member insert or remove
• Both routines attempt to wake up a task that is waiting for a specific event to occur. For example, if a producer task has blocked itself on condition empty waiting for an empty buffer slot, cooperation suggests the next consumer task wake a waiting producer because it has created an empty slot in the buffer. The reverse situation exists when the buffer is empty and a consumer task is waiting for a full buffer slot; the next producer should wake a waiting consumer because it has created a full slot in the buffer.
• Restarting a blocked task is done with a signal on the specified condition variable, which restarts one (and only one) waiting task (like a V), and both insert and remove end by unconditionally signalling the appropriate condition variable.
• The signals can be unconditional because of the lack of an implicit counter for condition variables; hence, if the condition has no waiting tasks, the signal does nothing. If the speed of the producer and consumer tasks are reasonably balanced, the buffer is seldom full or empty, and hence, the signals do nothing because tasks are not blocked. (The ideal scenario.)

Condition Variable

Is an external synchronization lock protected by the implicit monitor mutex-lock.

Common to associate with each condition variable an assertion about the state of the mutex object.

For example, in the bounded buffer, a condition variable might be associated with the assertion “waiting for an empty buffer slot”. Blocking on that condition variable corresponds to blocking until the condition is satisfied, that is, until an empty buffer slot appears.

Naming falls into these categories:

1. The condition name identifies a precise event that must be true to fulfill the cooperation of a waiter, e.g.:
   • uCondition empty;
   • So empty.wait() means “wait for an empty buffer slot” and empty.signal() means “there is now an empty buffer slot”
2. Alternatively, the condition name identifies a property of the shared resource that must be true before waiters can continue execution, e.g.:
   • uCondition nonFull;
   • so nonFull.wait() means “wait until the buffer is not full” and nonFull.signal() means “the buffer is not full”

• Snapshot of a monitor with tasks waiting.
• Finally, the active task in the monitor has signalled one of the tasks from a condition queue.
• The semantics of the $\text{micro}$C++ signal is that the signalled task waits until the signalling task exits the monitor or waits.
  • Opposite of _Accept which blocks the acceptor until the accepted task exits the monitor or waits.
  • waits vs. blocked
  • However, an _Accept is more than than a signal, it is a combination of a wait and signal. The wait component of an accept occurs implicitly and blocks the acceptor on the top of the acceptor stack. The signal component of an accept is performed implicitly when the accepted task finishes a mutex member or waits, i.e., there is an implicit signal of the acceptor task from the top of the acceptor stack. The effect is that the acceptor task waits until the accepted task exits the monitor or waits.
• As a result of the signal semantics, the signalled task is removed from the condition queue and must be temporarily stored (like an acceptor) until the signalling task exits or waits, which is accomplished by moving the signalled task to an implicit queue associated with the monitor, called the signalled queue
• When the signalling task exits or waits, the task at the front of the signalled queue becomes the active task in the monitor (i.e., the baton is passed from the signaller to the signalled task)
• If the signalling task does multiple signals, multiple tasks are moved to the signalled queue, and when the signaller exits or waits, the front signalled task becomes the active monitor task, and when it exits or waits, the next signalled task becomes the active monitor task, and so on.
• When there are no tasks on the signalled queue, a task at the front of the entry queue is selected if one is present.
• Processing the signalled queue before the entry queue ensures an external task cannot barge ahead of an internal task, which has already waited its turn in the monitor.

Note

Signalled queue serves a similar purpose to the acceptor stack

to facilitate the implicit management of tasks in the monitor.

Internal Scheduling vs. Semaphores

Simpler than semaphores because the monitor implicitly handles all the baton passing necessary when a task waits or exits the monitor to implicitly schedule the next task to enter the monitor.

Finally, there is no legitimate circumstance where a mutex, synchronization, or semaphore lock should be used in a monitor.

Only condition variables should be used in a monitor for synchronization because blocking on a condition variable implicitly releases the monitor lock.