[Notes] Mutex, Semaphore, Monitor

Parent/Index article

· Monitor [Busy Wait → wait(), signal()]
∘ Condition Variables
∘ Why the while Loop
· Java’s Monitor & Hoare vs Mesa Monitors
∘ Java’s Monitor
∘ Hoare vs Mesa Monitors
· Mutex vs Semaphore
· Monitor Vs Semaphore
· Missed Signals

Monitor [Busy Wait → wait(), signal()]

Monitor is made up of a mutex and one or more condition variables.

In Java each object is a monitor and implicitly has a lock and is a condition variable too. You can think of a monitor as a mutex with a wait set. Monitors allow threads to exercise mutual exclusion as well as cooperation by allowing them to wait and signal on conditions.

Theoretically, Another way to think about a monitor is to consider it as an entity having two queues or sets where threads can be placed. One is the entry set and the other is the wait set.
When a thread A enters a monitor it is placed into the entry set. If no other thread owns the monitor, which is equivalent of saying no thread is actively executing within the monitor section, then thread A will acquire the monitor and is said to own it too. Thread A will continue to execute within the monitor section till it exits the monitor or calls wait() on an associated condition variable and be placed into the wait set. While thread A owns the monitor no other thread will be able to execute any of the critical sections protected by the monitor. New threads requesting ownership of the monitor get placed into the entry set.

say another thread B comes along and gets placed in the entry set, while thread A sits in the wait set. Since no other thread owns the monitor, thread B successfully acquires the monitor and continues execution. If thread B exits the monitor section without calling notify() on the condition variable, then thread A will remain waiting in the wait set. Thread B can also invoke wait() and be placed in the wait set along with thread A. This then would require a third thread to come along and call notify() on the condition variable on which both threads A and B are waiting. Note that only a single thread will be able to own the monitor at any given point in time and will have exclusive access to data structures or critical sections protected by the monitor.

Condition Variables

Mutex provides mutual exclusion, however, at times mutual exclusion is not enough. We want to test for a predicate with a mutually exclusive lock so that no other thread can change the predicate when we test for it but if we find the predicate to be false, we’d want to wait on a condition variable till the predicate’s value is changed. This thus is the solution to spin waiting.

• Conceptually, each condition variable exposes two methods wait() and signal().
• The wait() method when called on the condition variable will cause the associated mutex to be atomically released, and the calling thread would be placed in a wait queue. There could already be other threads in the wait queue that previously invoked wait() on the condition variable.
• Since the mutex is now released, it gives other threads a chance to change the predicate that will eventually let the thread that was just placed in the wait queue to make progress.
• As an example, say we have a consumer thread that checks for the size of the buffer, finds it empty and invokes wait() on a condition variable. The predicate in this example would be the size of the buffer.
• Now imagine a producer places an item in the buffer. The predicate, the size of the buffer, just changed and the producer wants to let the consumer threads know that there is an item to be consumed.
• This producer thread would then invoke signal() on the condition variable. The signal() method when called on a condition variable causes one of the threads that has been placed in the wait queue to get ready for execution.
• Note we didn't say the woken up thread starts executing, it just gets ready - and that could mean being placed in the ready queue.
• It is only after the producer thread which calls the signal() method has released the associated mutex that the thread in the ready queue starts executing. The thread in the ready queue must wait to acquire the mutex associated with the condition variable before it can start executing.

void efficientWaitingFunction() {
mutex.acquire()
while (predicate == false) {
condVar.wait()
}
// Do something useful
mutex.release()
}

void changePredicate() {
mutex.acquire()
set predicate = true
condVar.signal()
mutex.release()
}

• Let’s dry run the above code. Say thread A executes efficientWaitingFunction() first and finds the loop predicate is false and enters the loop.
• Next thread A executes the statement condVar.wait() and is be placed in a wait queue. At the same time thread A gives up the mutex.
• Now thread B comes along and executes changePredicate() method. Since the mutex was given up by thread A, thread B is be able to acquire it and set the predicate to true.
• Next it signals the condition variable condVar.signal(). This step places thread A into the ready queue but thread A doesn't start executing until thread B has released the mutex.
• Note that the order of signaling the condition variable and releasing the mutex can be interchanged, but generally, the preference is to signal first and then release the mutex. However, the ordering might have ramifications on thread scheduling depending on the threading implementation.

Why the while Loop

Have noticed us using a while loop to test for the predicate. After all, the pseudocode could have been written as follows

void efficientWaitingFunction() {
mutex.acquire()
if (predicate == false) {
condVar.wait()
}
// Do something useful
mutex.release()
}

• If the snippet is re-written in the above manner using an if clause instead of a while then, we need a guarantee that once the variable condVar is signaled, the predicate can't be changed by any other thread and that the signaled thread becomes the owner of the monitor. This may not be true.
• For one, a different thread could get scheduled and change the predicate back to false before the signaled thread gets a chance to execute, therefore the signaled thread must check the predicate again, once it acquires the monitor.
• Secondly, use of the loop is necessitated by design choices of monitors that we'll explore in the next section. Last but not the least, on POSIX systems, spurious or fake wakeups are possible (also discussed in later chapters) even though the condition variable has not been signaled and the predicate hasn't changed. The idiomatic and correct usage of a monitor dictates that the predicate always be tested for in a while loop.

Java’s Monitor & Hoare vs Mesa Monitors

Java’s Monitor

In Java every object is a condition variable and has an associated lock that is hidden from the developer. Each java object exposes wait() and notify() methods.

• Before we execute wait() on a java object we need to lock its hidden mutex. That is done implicitly through the synchronized keyword. If you attempt to call wait() or notify() outside of a synchronized block, an IllegalMonitorStateException would occur. It's Java reminding the developer that the mutex wasn't acquired before wait on the condition variable was invoked.
• wait() and notify() can only be called on an object once the calling thread becomes the owner of the monitor. The ownership of the monitor can be achieved in the following ways:
  → the method the thread is executing has synchronized in its signature
  → the thread is executing a block that is synchronized on the object on which wait or notify will be called
  → in case of a class, the thread is executing a static method which is synchronized.

Hoare vs Mesa Monitors

So far we have determined that the idiomatic usage of a monitor requires using a while loop as follows. Let’s see how the design of monitors affects this recommendation.

while( condition == false ) {
condVar.wait();
}

Once the asleep thread is signaled and wakes up, you may ask why does it need to check for the condition being false again, the signaling thread must have just set the condition to true?

In Mesa monitors — Mesa being a language developed by Xerox researchers in the 1970s — it is possible that the time gap between thread B calls notify() and releases its mutex and the instant at which the asleep thread A, wakes up and reacquires the mutex, the predicate is changed back to false by another thread different than the signaler and the awoken threads! The woken up thread competes with other threads to acquire the mutex once the signaling thread B empties the monitor. On signaling, thread B doesn't give up the monitor just yet; rather it continues to own the monitor until it exits the monitor section.

In contrast, Hoare monitors — Hoare being one of the original inventor of monitors — the signaling thread B yields the monitor to the woken up thread A and thread A enters the monitor, while thread B sits out. This guarantees that the predicate will not have changed and instead of checking for the predicate in a while loop an if-clause would suffice. The woken-up/released thread A immediately starts execution when the signaling thread B signals that the predicate has changed. No other thread gets a chance to change the predicate since no other thread gets to enter the monitor.

Java, in particular, subscribes to Mesa monitor semantics and the developer is always expected to check for condition/predicate in a while loop. Mesa monitors are more efficient than Hoare monitors.

Mutex vs Semaphore

1. Mutex implies mutual exclusion and is used to serialize access to critical sections whereas semaphore can potentially be used as a mutex but it can also be used for cooperation and signaling amongst threads. Semaphore also solves the issue of missed signals.
2. Mutex is owned by a thread, whereas a semaphore has no concept of ownership.
3. Mutex if locked, must necessarily be unlocked by the same thread. A semaphore can be acted upon by different threads. This is true even if the semaphore has a permit of one
4. Analogy:

• Think of semaphore analogous to a car rental service such as Hertz. Each outlet has a certain number of cars, it can rent out to customers. It can rent several cars to several customers at the same time but if all the cars are rented out then any new customers need to be put on a waitlist till one of the rented cars is returned.
• In contrast, think of a mutex like a lone runway on a remote airport. Only a single jet can land or take-off from the runway at a given point in time. No other jet can use the runway simultaneously with the first aircraft.

Monitor Vs Semaphore

1. A monitor and a semaphore are interchangeable and theoretically, one can be constructed out of the other or one can be reduced to the other. However, monitors take care of atomically acquiring the necessary locks whereas, with semaphores, the onus of appropriately acquiring and releasing locks is on the developer, which can be error-prone.
2. Semaphores are lightweight when compared to monitors, which are bloated. However, the tendency to misuse semaphores is far greater than monitors. When using a semaphore and mutex pair as an alternative to a monitor, it is easy to lock the wrong mutex or just forget to lock altogether. Even though both constructs can be used to solve the same problem, monitors provide a pre-packaged solution with less dependency on a developer’s skill to get the locking right.
3. Java monitors enforce correct locking by throwing the IllegalMonitorState exception object when methods on a condition variable are invoked without first acquiring the associated lock. The exception is in a way saying that either the object's lock/mutex was not acquired at all or that an incorrect lock was acquired.
4. A semaphore can allow several threads access to a given resource or critical section, however, only a single thread at any point in time can own the monitor and access associated resource.
5. Semaphores can be used to address the issue of missed signals, however with monitors additional state, called the predicate, needs to be maintained apart from the condition variable and the mutex which make up the monitor, to solve the issue of missed signals.

Missed Signals

A missed signal happens when a signal is sent by a thread before the other thread starts waiting on a condition.