Monitor (Synchronization)

C. A. R. Hoare and Per Brinch Hansen who did the initial work on the development of the monitor.

Hence, the basic monitor is an abstract data type combining shared data with serialization of its modification through the operations on it.

In $\text{micro}$C++, a monitor is an object with mutual exclusion defined by a monitor type that has all the properties of a class. The general form of the monitor type is the following:

In addition, it has an implicit mutual-exclusion property, like a critical region, i.e., only one task at a time can be executing a monitor operation on the shared data. The monitor shared data is normally private so the abstraction and mutual- exclusion property ensure serial access to it.

A consequence of the mutual-exclusion property is that only one member routine can be active at a time because that member can read and write the shared data. Therefore, a call to a member of a monitor may block the calling task if there is already a task executing a member of the monitor. Only after the task in the monitor returns from the member routine can the next call occur. $\text{micro}$C++ defines a member with this implicit mutual-exclusion property as a mutex member (short for mutual-exclusion member), and the public members of a monitor are normally mutex members (exceptions are discussed shortly)

Similar to Coroutine

A monitor is either inactive or active! Depending on whether or not a task is executing a mutex member (versus a task executing a coroutine main)

The monitor mutual exclusion is enforced by locking the monitor when execution of a mutex member begins and unlocking it when the active task voluntarily gives up control of the monitor.

As for a critical region, each monitor has a lock, which is basically Ped on entry to a mutex member and Ved on exit, as in:

Because a monitor is like a shared variable, each monitor must have an implicit entry queue on which calling tasks block if the monitor is active (busy waiting is unacceptable).

In C++, arriving tasks wait to enter the monitor on the entry queue, and this queue is maintained in order of arrival of tasks to the monitor (see top of Fig. 9.3).

When a task exits a mutex member, the next task waiting on the entry queue is made ready so tasks are serviced in FIFO order, and the monitor mutual exclusion is implicitly passed to this task (i.e., the baton is passed) so when it restarts no further checking is necessary.

HAS CONDITIONAL BLOCKING CAPABIILITIES

Mutex Calling Mutex

Here, mutex member mem2 is calling mutex member mem1 and then performing some additional work. To prevent a deadlock, the code for mem1 is factored into a no-mutex routine, mem3, and mem3 is called from mutex members mem1 and mem2.

This restructuring ensures that only one attempt is made to acquire the monitor lock.

$\text{micro}$C++ does allow the active task in a monitor to call among mutex members without deadlocking. once a task acquires the monitor lock it can acquire it again, like the owner lock.

Can acquire it again

This capability allows a task to call into the mutex member of one monitor, and from that mutex member call into the mutex member of another monitor, and then call back to a mutex member of the first monitor, i.e., form a cycle of calls among mutex members of different monitors. Therefore, in C++, once a task acquires a monitor, there is no restriction on the use of the monitor’s functionality.

Scheduling

Notice, scheduling in this context does not imply that tasks are made running; it means a task waits on a queue until it can continue execution and then is made ready.

Two basic techniques for performing scheduling are introduced and discussed in detail: external and internal scheduling.

External scheduling schedules tasks outside the monitor and is accomplished with the accept statement.

Internal scheduling schedules tasks inside the monitor and is accomplished using wait and signal. A system can exist with only one of the two scheduling schemes, but it will be shown there is only a weak equivalence between the schemes.

Monitor Details

_Mutex qualifier placed on a class definition:

• All public member routines have the mutual-exclusion property,
• unless overridden on specific member routines with the _Nomutex qualifier.

_Nomutex qualifier placed on a class definition:

• all public member routines have the no-mutual-exclusion property, which is the same as a class,
• unless overridden on specific member routines with the _Mutex qualifier
• The default qualifier for a class, i.e., if no qualifier is specified, is _Nomutex because the mutual-exclusion property for public members is not needed.

$\to$ a class creates a monitor if and only if it has at least one _Mutex member routine, and that _Mutex member routine can have any visibility (private, protected, or public)

Destructor of a monitor is always mutex. $\to$ because same as a task (the storage for the monitor cannot be deallocated if the monitor is active).

Monitor with minimum number of mutex members:

class M{
	public:
		_Mutex ~M(){}
};

Following examples illustrate most of the different possible combinations for implicit and explicit creation of mutex members of a mutex object:

In fact, the name _Monitor used so far is just a preprocessor macro for “_Mutex class” defined in include file uC++.h.

Monitor Creation and Destruction

When a monitor is created, the appropriate monitor constructor and any base-class constructors are executed in the normal order by the creating thread. Because a monitor is a mutex object, the execution of its destructor waits until it can gain access to the monitor, just like the other mutex members of the monitor, which can delay the termination of the block containing a monitor or the deletion of a dynamically allocated monitor.

Accept Statement

A _Accept statement dynamically chooses the mutex member(s) that executes next, which indirectly controls the next accepted caller, that is, the next caller to the accepted mutex member. The simplest form of the _Accept statement is:

_Accept(mutex-member-name);

with the restriction that constructors, new, delete, and _Nomutex members are excluded from being accepted.

When a _Accept statement is executed, the acceptor is blocked and pushed on the top of the implicit acceptor/signalled stack and a task is scheduled from the mutex queue for the specified mutex member. If there is no outstanding call to that mutex member, the acceptor is accept-blocked until a call is made. The accepted member is then executed like a member routine of a conventional class by the caller’s thread.

If the caller is expecting a return value, this value is returned using the return statement in the member routine.

Notice

An accept statement accepts only one call, regardless of the number of mutex members listed in the statement.

When the caller’s thread exits the mutex member or waits, further implicit scheduling occurs. First, a task is unblocked from the acceptor/signalled stack if present, and then from the entry queue. Therefore, in the case of nested accept calls, the execution order between acceptor and caller is stack order, as for a traditional routine call. If there are no waiting tasks present on either data structure, the next call to any mutex member is implicitly accepted.

_Accept(mutex-member-name-list)
	statement                 // optional statement
or _Accept(mutex-member-name)
	statement                 // optional statement
...

A list of mutex members in an _Accept clause:

_Accept(insert, remove);
 
// equivalent to
 
_Accept(insert) or _Accept(remove);

the order of the _Accepts indicates their relative priority for selection if several accept clauses can execute.

Once the accepted call has completed or the caller waits, the statement after the accepting _Accept clause is executed and the accept statement is complete. If there are no outstanding calls to these members, the task is accept-blocked until a call to one of these members is made.

If vs. _Accept clause

The if statement only executes one of S1, S2, S3; it does not execute them all. The reason is that the first conditional to evaluate to true executes its corresponding “then” clause (S1, S2, or S3), and the if statement terminates. Similarly, the accept statement accepts the first call to one of mutex members M1, M2, or M3, then executes the corresponding “then” clause (S1, S2, or S3) and the _Accept statement terminates. The analogue also holds when there is a list of mutex member names in an accept clause, as in:

$\to$ Since for the _Accept case, control blocks until a call to one of the accepted member occurs and then the corresponding “then” clause is executed. Hence, an accept statement accepts only one call

$\to$ Condition Variable

Monitor Errors

Nested Monitor Call

When a task blocks in a monitor, either through _Accept or wait, other tasks can enter the monitor so that progress can be made. However, when a task, T1, calls from one monitor, M1, to another monitor, M2, and blocks in M2, M2 can continue to process requests but not M1. The reason M1 cannot process requests is that task T1 still has M1 locked and blocking in M2 only releases M2’s monitor lock.

Therefore, acquiring one monitor and blocking in another monitor results in a hold and wait situation, which may reduce concurrency in most cases and may result in a synchronization deadlock in others.

Can lead to Deadlock

Coroutine-Monitor

A coroutine-monitor type has a combination of the properties of a coroutine and a monitor, and can be used where a combination of these properties are needed, such as a finite automata that is used by multiple tasks.

Has all properties of a Coroutine and a Mutex class:

A _Coroutine creates a coroutine-monitor if and only if it has at least one _Mutex member routine, and that _Mutex member routine can have any visibility, i.e., private, protected or public

Creation & Destruction:

• A coroutine-monitor is the same as a monitor with respect to creation and destruction.