We discussed on a previous page that a signal on a condition variable causes a waiting thread of that condition variable to resume its execution. Note that the released thread will have its monitor lock back. So, what happens to the lock owned by the signaling thread? The signaling thread must be running so that it can signal. Consequently, the signaling thread must own the monitor lock! Now, once the released thread runs, this thread and the signaling thread would both own the monitor lock and both be running in monitor! This violates the mutual exclusion requirement of monitors. Therefore, to make sure that mutual exclusion is guaranteed for monitors, either the released thread or the signaling thread can run, but not both. The choice of which thread should run creates at least two types of monitors: the Hoare type and the Mesa type.
In Hoare's original 1974 monitor definition, the signaler yields the monitor to the released thread. More specifically, if thread A signals a condition variable CV on which there are threads waiting, one of the waiting threads, say B, will be released immediately. Before B can run, A is suspended and its monitor lock is taken away by the monitor. Then, the monitor lock is given to the released thread B so that when it runs it is the only thread executing in the monitor. Sometime later, when the monitor becomes free, the signaling thread A will have a chance to run.
This type of monitor does have its merit. If thread B is waiting on condition variable CV when thread A signals, this means B entered the monitor earlier than A did, and A should yield the monitor to a "senior" thread who might have a more urgent task to perform.
Because the released thread runs immediately right after the signaler indicates the event has occurred, the released thread can run without worrying about the event has been changed between the time the condition variable is signaled and the time the released thread runs. This would simplify our programming effort somewhat.
Return to the resting-knocking monitor discussed on the previous page. If the resting thread is waiting on condition variable Event when a knocking thread, say K, calls method Event.Signal() to indicate a full count has reached, the lock owned originally by the knocking thread K is taken away from K and given to the resting thread. Then, the resting thread runs and "owns" the monitor. The knocking thread K waits until the monitor is empty, at which time, K may have a chance to run.
void MyMonitor::Rest(void)
{
MonitorBegin();
HasWaiting = 1; // I am waiting
Event.Wait();
HasWaiting = 0; // no one is waiting
MonitorEnd();
}
void MyMonitor::Knock(void)
{
MonitorBegin();
if (HasWaiting) {
counter++;
if (counter == Max_Count) {
Event.Signal();
counter = 0;
}
}
MonitorEnd();
}
Mesa is a programming language developed by a group of Xerox researchers in late 70s, and supports multithreaded programming. Mesa also implements monitors, but in a different style for efficiency purpose. With Mesa, the signaling thread continues and the released thread yields the monitor. More specifically, when thread A signals a condition variable CV and if there is no waiting thread, the signal is lost just like Hoare's type. If condition variable CV has waiting threads, one of them, say B, is released. However, B does not get his monitor lock back. Instead, B must wait until the monitor becomes empty to get a chance to run. The signaling thread A continues to run in the monitor.
What is the major difference between "signaler continues" and "signaler yields"? Consider the above code under Hoare's type. Suppose the resting thread is blocked on condition variable Event. If a knocking thread A calls monitor procedure Knock() and sees that it is a full count (after increasing counter by 1, of course), A signals the resting thread and continues until it exits the monitor. Meanwhile, because it is a Mesa monitor, the released thread is waiting until the monitor is cleared. However, when A exits, another knocking thread B calls Knock() before the resting thread could get a chance to execute its next statement (i.e., HasWaiting = 0). This B finds out that HasWaiting is 1, and adds 1 to counter. However, this increment step is done while there is no waiting thread, and does not fulfill the program specification. Consequently, Mesa monitors do make a difference.
So, what is the problem? The problem is that between the signaler executed Signal() and the released thread runs there is a time gap during which a new thread can take the monitor and change the event. Therefore, with Mesa monitor, an if is usually insufficient, and a while is more appropriate. We shall illustrate this point with a more realistic example in the next section.
Let us study a realistic example to learn more. Suppose we want to write a monitor MutexLock to simulate a mutex lock. Thus, this monitor must have two methods, Lock() and Unlock(). In the monitor, we need a variable to indicate if the lock is open or closed. This is the job of variable locked, whose initial value should be 0 (i.e., lock being open). If a thread calls method Lock() successfully, it makes the lock closed and variable locked should have value 1. On the other hand, if a thread calls method Unlock(), we should reset the value of locked to 0. However, a thread may not lock the lock successfully because the lock has already been locked by another thread. Should this happen, this thread must be blocked, and a condition variable Queue is needed for this thread to wait on. More precisely, a thread calls Lock() and sees the lock has already been locked, this thread blocks itself on condition variable Queue until it is signaled by another thread who releases the lock. This idea is illustrated below. Note that we assume the monitor is of Hoare type. Because it is a Hoare type monitor, when a thread is released from the condition variable Queue, it runs immediately and knows that the condition (i.e., the lock being open) is not altered between the time it was signaled and the time it runs. Consequently, a simple if statement is sufficient.
class MutexLock : public Monitor // Hoare type
{
public:
MutexLock(char *Name);
void Lock(void);
void Unlock(void);
private:
Condition Queue;
int locked;
};
void MutexLock::Lock(void)
{
MonitorBegin();
if (locked)
Queue.Wait();
locked = 1;
MonitorEnd();
}
void MutexLock::Unlock(void)
{
MonitorBegin();
locked = 0;
Queue.Signal();
MonitorEnd();
}
What if the monitor is of Mesa type? The above code does not work properly. Let me reiterate. Suppose thread A is blocked and waiting on condition variable Queue because the value of locked was 1 when it entered the monitor. Sometime later, another thread B calls method Unlock(). B resets the value of locked to 0 and signals condition variable Queue. If this is a Mesa type monitor, thread B continues and owns the monitor and thread A is released and waiting to enter. Right after thread B exits the monitor and before thread A can run, a third thread, say C, runs faster and is able to enter the monitor. Of course, thread C sees that the value of locked is 0, and, consequently, sets it to 1. This means that thread C essentially has acquired the lock successfully. After thread C exits, thread A enters the monitor and executes the next instruction following Queue.Wait(). Then, it also sets locked to 1, and now threads A and C both own the the same lock. This is certainly incorrect. The major reason is that when A has a chance to run, the situation has already been changed by thread C. To overcome this problem in a Mesa type monitor, a released thread must re-check the condition it has been waiting for as shown below:
class MutexLock : public Monitor // Mesa type
{
public:
MutexLock(char *Name);
void Lock(void);
void Unlock(void);
private:
Condition Queue;
int locked;
};
void MutexLock::Lock(void)
{
MonitorBegin();
while (locked) // changed to while!!!
Queue.Wait();
locked = 1;
MonitorEnd();
}
void MutexLock::Unlock(void)
{
MonitorBegin();
locked = 0;
Queue.Signal();
MonitorEnd();
}
It is the time to provide you with a complete picture of the states a thread may have in a monitor. A thread can be in one of the four states: entering, waiting, active, and inactive (or re-entering). A thread is in state entering if it calls a monitor procedure and is not able to enter. This is because the monitor is locked by another thread, and, as a result, it is forced to join the entry queue. See the diagram below. A thread is waiting for an event to occur on a condition variable (i.e., in the queue of a condition variable) is in the waiting state. A thread that is running in the monitor is in the active state. Finally, if a thread has entered the monitor and is temporarily removed, we will say it is in the inactive state. In a Hoare type monitor, the signaler of a condition variable yields and is put into the inactive state. Similarly, in a Mesa monitor, the released thread due to a signal is also in the inactive state. Note that those inactive threads had the lock previously; but, they are unable to re-acquire it. In the diagram below, we use a "waiting bench" to indicate the place where these inactive threads are waiting. All threads in the entering, waiting and inactive states do not have the lock of the monitor; only the active thread has the lock. When the monitor is empty because a thread exits or executes a Wait() on a condition variable, one thread from the entry queue or from the inactive thread pool will be selected to enter. We should not assume which thread will be selected.
After the discussion of the two monitor types, it is the time to talk about how to write a monitor constructor. The base monitor class Monitor has two variables to be set by a constructor. The first one is the name of a monitor Name, and the second can have two possible values, HOARE for a Hoare monitor and MESA for a Mesa monitor. If we prefer to use a Hoare monitor to implement monitor MutexLock, its constructor should be similar to the one shown below. Note that we assume that the constructor will be supplied with a name when it is created. The second argument to the constructor of class Monitor is HOARE, and, hence this is a Hoare monitor. Replacing HOARE with MESA changes the monitor to a Mesa monitor.
MutexLock::MutexLock(char *Name)
: Monitor(Name, HOARE)
{
locked = 0;
}
|
|
|