Part 5 - Monitors
In this series we’ve covered locks and semaphores as synchronization mechanism. Although these are essential in concurrent programs, they’re quite low-level synchronization mechanisms.
Semaphores for example have the problem that:
- They are global and unstructured, it can be quite difficult to understand what a certain semaphore does in a given piece of code.
- Often, we are prone to deadlocks or incorrect behavior,
it’s easy to forget a simple
up()ordown()call in your programs.
- They do not support well different conditions.
Monitors
Remember the synchronized keyword that can be used in Java for either blocks or whole methods?
Monitors are essentially a synchronized class. A more formal definition of a monitor would be.
Monitors provide a structured synchronization mechanism built on top of object-oriented constructs – especially the notions of classes, objects, and encapsulation.
In a monitor class:
- Attributes are private
- Methods execute in mutual exclusion
A monitor is an object instantiating a monitor class that encapsulates synchronization mechanisms:
- Attributes are shared variables, which all threads running on the monitor can see and modify
- Methods define critical sections, with the built-in guarantee that at most one thread is active on a monitor at any time
To gain access to these critical section methods, we have a so called entry-queue for these monitor objects. This is to ensure mutual access to the methods.
Let’s write a simple monitor class in pseudocode:
monitor class Counter {
// Attribute, implicitly private
(private) int count = 0;
// Methods, implicitly atomic
public void increment() {
count = count + 1;
}
public void decrement() {
count = count - 1;
}
}
What’s really powerful with monitors are conditions variables, sometimes we require more complex synchronization patterns.
We can define a condition using an interface:
interface Condition {
// Block until signal
void wait();
// Signal to unblock
void signal();
// Is no thread waiting on this condition?
boolean isEmpty(); }
Each condition variable also has a FIFO queue, blocked which stores all the blocked threads.
Which means:
c.wait()blocks the running thread, appends it to blocked, and releases the lock on the monitor
c.signal()removes one thread from blocked (if it’s not empty) and unblocks it
c.isEmpty()returns true if and only if, blocked is empty
Producer-Consumer problem
interface Buffer<T> {
// add item to buffer; block if full
void put(T item);
// remove item from buffer; block if empty
T get();
// number of items in buffer
int count();
}
Let’s solve this problem we have encountered earlier, using monitors now!
monitor class MonitorBuffer<T> implements Buffer<T> {
// Any collection (list, set, ...)
Collection storage = ...;
// Signal when not empty
Condition notEmpty = new Condition();
public void put(T item) {
// Store item
storage.add(item);
// Signal buffer not empty
notEmpty.signal();
}
public T get() {
if (storage.count() == 0) {
// Wait until buffer not empty
notEmpty.wait();
}
// Retrieve item
return storage.remove();
}
invariant {
# of storage.add == # notEmpty.signal
}
}
And the bounded buffer:
monitor class BoundedMonitorBuffer<T> extends MonitorBuffer<T> {
// Signal when not full
Condition notFull = new Condition();
public void put(T item) {
if (storage.count() == capacity) {
// Wait until buffer not full
notFull.wait();
}
super.put(item); // do as in MonitorBuffer.put(item)
}
public T get() {
// Do as in MonitorBuffer.get()
T item = super.get();
// Signal buffer not full
notFull.signal()
return item;
}
}
Signaling disciplines
When a thread, s, calls signal() it now signals to a thread that its being unblocked.
Say the thread, u, being unblocked by s. The signaling discipline determines what happens to a signaling thread, s, after it unblocks thread u.
There are two main choices for this:
- Signal and continue
- s continues executing; u is moved to the entry queue of the monitor.
- Signal and wait
- s is moved to the entry queue of the monitor; u resumes executing (it silently gets the monitor’s lock).
Under the signal and wait discipline, it is guaranteed that the signaled condition holds when the unblocked thread resumes execution, because it immediately follows the signal
In contrast, under the signal and continue discipline, the signaled condition may no longer hold when the unblocked thread, u, resumes execution - because the signaling thread, or other threads, may change the state while continuing
There is one problem though - the signal and continue discipline does not guarantee that a thread resuming
execution after a wait, will find that this condition has been met (true). The signal is like a hint.
Therefore, most monitor implementations use the signal and continue discipline. Often when using the signal and continue discipline you will have access to a method called:
// Unblock all threads blocked on this condition
void singalAll();
This is inefficient most of the time, but it just works for the given pattern.
There is also the signal and urgent wait discipline:
- Signal and urgent wait
- s is moved to the front of the entry queue, u resumes executing.
This means that urgent threads gets ahead of regular threads, but urgent threads still may need to queue amongst other urgent threads.
So let’s summarize:
- Signal and continue
- S > U = E
- Urgent Signal and continue
- S > U > E
- Signal and wait
- U > S = E
- Signal and urgent wait
- U > S > E
Where, S - signaling thread(s), U - unblocked thread(s), E - thread(s) in the entry queue.
Implementation
Let’s implement monitors now using semaphores!
class Counter {
// Strong/fair semaphore, initially 1
Semaphore entry = new Semaphore(1, true);
private int x = 0;
public void inc() {
entry.down();
x = x + 1;
entry.up();
}
}
Simple right!
Now let’s look at conditions variables:
abstract class WaitVariable implements Condition {
// Queue of blocked threads
Queue blocked = new Queue<Thread>();
// Block until signal
public void wait() {
// Release monitor lock
entry.up();
// Enqueue running thread
blocked.add(running);
// Set state as blocked
running.state = BLOCKED;
}
// Is no thread waiting?
public boolean isEmpty() {
return blocked.isEmpty();
}
}
Quite simple :)!
Now let’s try to implement two different disciplines:
class SCVariable extends WaitVariable {
// Signal to unblock
public void signal() {
if (!blocked.isEmpty()) {
// u is the unblocked thread
Thread u = blocked.remove();
// u gets moved to entry queue
entry.blocked.add(u);
// the running, signaling thread continues executing
}
}
}
And a signal wait:
class SWVariable extends WaitVariable {
// Signal to unblocked
public void signal() {
if(!blocked.isEmpty()) {
// Add the running, signaling thread, to the entry queue
entry.blocked.add(running);
// New unblocked thread, u
Thread u = blocked.remove();
// Set thread u to ready
u.state = READY;
// Block the old running thread
running.state = BLOCKED;
// the unblocked, signaled thread, u, continues executing
}
}
}
One fun little thing that one might have thought of is, can we implement semaphores from monitors?
The answer is yes! But it’s quite useless and impractical, but in theory one can!
Summary
Let’s try to write up all the pros and cons with monitors!
- Pros
- They provide a structured approach to concurrent programming
- They raise the level of abstraction compared to primitives like locks and semaphores.
- Monitors introduce separation of concerns:
- Mutual exclusion is implicit.
- Condition variables provide a clear vision of the synchronization
- Cons
- Monitors (generally) have a larger performance overhead than semaphores
- Note that, sometimes, performance must be traded against error proneness
- The different signaling disciplines can be confusing, which hurts the clarity of the monitor abstraction.
- For complex synchronization patterns, nested monitor calls will be complicated.
- Monitors (generally) have a larger performance overhead than semaphores