by Jasmin Blanchette

This article assumes that you have some experience with multithreaded programming and have familiar with concepts such as mutual exclusion and atomic operations. If this is a new topic to you, I recommend that you start by reading Thread Support in Qt and consult a book on the topic, such as Multithreaded, Parallel, and Distributed Programming by Gregory R. Andrews (2000).

What is a Monitor?

Monitors are a construct found in a few programming languages, such as Concurrent Pascal and Mesa. Java and C# are sometimes credited with supporting monitors, but neither of them really incorporates them as first-class citizens. ^[1] Conceptually, a monitor is a class whose data members are private and whose member functions are implicitly executed with mutual exclusion. In addition, monitors may define wait conditions that can be used inside the monitor to synchronize the member functions.

The following pseudo-code presents a very simple monitor that models a bank account:

monitor BankAccount
{
public:
    BankAccount() { balance = 0; }
 
    void withdraw(int amount) {
        balance -= amount;
    }
    void deposit(int amount) {
        balance += amount;
    }
 
private:
    int balance;
};

In our pseudo-code universe, declaring BankAccount as a monitor (as opposed to a plain class) implies that member function calls will always be serialized, no matter how many threads try to access the same monitor instance at the same time. For instance, if thread A tries to call deposit() while thread B is executing withdraw(), A will have to wait until B is done before executing.

In Java, the above monitor would be implemented using the synchronized keyword:

public class BankAccount
{
    public synchronized void withdraw(int amount) {
        balance -= amount;
    }
    public synchronized void deposit(int amount) {
        balance += amount;
    }
 
    private int balance = 0;
}

Using C++ and Qt, the monitor would be implemented by adding a QMutex to the class, and by keeping the mutex locked whenever a member function executes:

class BankAccount
{
public:
    BankAccount() { balance = 0; }
 
    void withdraw(int amount) {
        QMutexLocker locker(&mutex);
        balance -= amount;
    }
    void deposit(int amount) {
        QMutexLocker locker(&mutex);
        balance += amount;
    }
 
private:
    QMutex mutex;
    int balance;
};

For locking and unlocking the mutex, we use QMutexLocker. Its constructor calls lock() on the mutex and its destructor calls unlock().

Thanks to the QMutex, the methods are mutually exclusive: When executing withdraw(), no other thread can change balance's value, which would result in a race condition. In Java, this was achieved using the synchronized keyword, and in the pseudo-code, mutual exclusion was implicit because we used the pseudo-keyword monitor.

Wait Conditions

The above monitor isn't very realistic, because it lets us perform withdrawals even if that leaves the account in the red. This is where wait conditions come into play. Here's a new version of the BankAccount monitor that will simply block if there is not enough money to perform a withdrawal:

monitor BankAccount
{
public:
    BankAccount() { balance = 0; }
 
    void withdraw(uint amount) {
        while (amount > balance)
            wait(moreMoney);
        balance -= amount;
    }
    void deposit(uint amount) {
        balance += amount;
        signalAll(moreMoney);
    }
 
private:
    cond moreMoney;
    uint balance;
};

The cond keyword is used to declare a wait condition. Wait conditions support the following three operations:

• wait(c) puts the calling thread to sleep, until another thread calls signal(c).
• signal(c) wakes one thread that is currently waiting on the wait condition c. If there are no threads waiting, signal() does nothing.
• signalAll(c) wakes all threads that are waiting on c.

In the BankAccount example, we declared one wait condition, called moreMoney. It is signaled whenever fresh money is poured into the account. Any thread that is waiting for fresh money to proceed will then wake up, check if there is enough money, and either go ahead with the withdrawal or go to sleep on moreMoney.

To make all of this a bit clearer, let's consider the example of an Education Loan Authority thread and a Student thread. The Loan Authority deposits 500 dollars each month. The Student takes out money in a more erratic fashion. One possible scenario is presented below:

The Loan Authority starts by depositing 500 dollars for January. When the Student tries to withdraw 500 dollars, the operation succeeds and leaves the account empty.

One month later, the Loan Authority deposits a new 500 dollars, but this time, the Student tries to take out 1200 dollars (which happens to be the cost of a two-week trip to the Bahamas). Because there isn't enough money in the account, the Student goes to sleep.

When March arrives, the Authority deposits 500 dollars as usual and tries to wake up the Student by signaling the moreMoney condition, but the Student realizes that 1000 dollars still aren't sufficient (at least not for two weeks in the Bahamas), so he or she goes back to sleep.

Finally, in April, the Authority deposits 500 dollars for the last time, and this time the Student can wake up and take out 1200 dollars.

The revised version of the BankAccount monitor has the following noteworthy characteristics:

• The balance can never be negative. If a thread tries to take out money that isn't in the account, the thread is put to sleep.
• The bank account doesn't create or lose money. At any time, the balance is the sum of all deposits performed so far minus the sum of all withdrawals. In short, there are no race conditions.
• The solution scales to more than two threads. For example, there could be several threads depositing money (Mom, Dad, Grandma), and several taking out money (Spouse, Ex, ...).

Let's try to implement the BankAccount monitor in C++, using Qt's QWaitCondition class to represent wait conditions:

class BankAccount
{
public:
    BankAccount() { balance = 0; }
 
    void withdraw(uint amount) {
        QMutexLocker locker(&mutex);
        while (amount > balance)
            moreMoney.wait(&mutex);
        balance -= amount;
    }
 
    void deposit(uint amount) {
        QMutexLocker locker(&mutex);
        balance += amount;
        moreMoney.wakeAll();
    }
 
private:
    QMutex mutex;
    QWaitCondition moreMoney;
    uint balance;
};

Notice that the wait() method takes a QMutex as argument. The mutex is automatically unlocked immediately before the thread goes to sleep, and locked again when the thread is woken up. Unlocking the mutex is necessary to let other threads access the bank account while the thread is sleeping. (In our pseudo-code syntax, this was all implicit.)

Also, the signal() and signalAll() functions from the pseudo-code are called wakeOne() and wakeAll() in Qt, to avoid confusion with Qt's existing concept of signals and slots.

There is, however, one significant flaw in what we have done so far. While students have been occasionally observed sleeping during their lectures, a two-month sleep at the bank seems undesirable at best. Fortunately, it turns out that this is fairly easy to fix, by adding a tryWithdraw() function to the monitor:

monitor BankAccount
{
    ...
    bool tryWithdraw(uint amount) {
        if (amount <= balance) {
            balance -= amount;
            return true;
        } else {
            return false;
        }
    }
    ...
};

This allows our student to repeatedly call tryWithdraw() until it returns true, instead of hibernating through the winter and waking up a few weeks before the final exams.

Example: Bounded Buffers

Consider the following monitor, which implements a bounded buffer (or circular buffer) used for transferring data between a producer and a consumer:

monitor BoundedBuffer
{
public:
    BoundedBuffer() { head = 0; tail = 0; }
 
    void put(char ch) {
        while (tail == head + N)
            wait(bufferIsNotFull);
        buffer[tail++ % N] = ch;
        signal(bufferIsNotEmpty);
    }
    char get() {
        while (head == tail)
            wait(bufferIsNotEmpty);
        char ch = buffer[head++ % N];
        signal(bufferIsNotFull);
        return ch;
    }
 
private:
    cond bufferIsNotFull;
    cond bufferIsNotEmpty;
    int head, tail;
    char buffer[N];
};

The Producer thread calls put() repeatedly with bytes that it computes. The Consumer thread calls get() to obtain the bytes as they are generated by the Producer. If the Producer is significantly faster than the Consumer, it will end up filling the buffer, at which point it must wait for the Consumer to retrieve at least one byte. Likewise, if the Consumer is faster than the Producer, it will have to wait so as to avoid reading garbage.

The diagram below depicts the situation that arises when the Producer has generated 8 bytes and the Consumer has read 3 of them, assuming a buffer of size N = 16:

To synchronize the two threads, we use two wait conditions: bufferIsNotFull and bufferIsNotEmpty. If the Producer calls put() when the buffer is already full, the Producer goes to sleep on the bufferIsNotFull condition; likewise, if the Consumer calls get() when the buffer is empty, it waits on the bufferIsNotEmpty condition.

Here's an implementation of the BoundedBuffer class in C++:

class BoundedBuffer
{
public:
    BoundedBuffer() { head = 0; tail = 0; }
 
    void put(char ch) {
        QMutexLocker locker(&mutex);
        while (tail == head + N)
            bufferIsNotFull.wait(&mutex);
        buffer[tail++ % N] = ch;
        bufferIsNotEmpty.wakeOne();
    }
    char get() {
        QMutexLocker locker(&mutex);
        while (head == tail)
            bufferIsNotEmpty.wait(&mutex);
        char ch = buffer[head++ % N];
        bufferIsNotFull.wakeOne();
        return ch;
    }
 
private:
    QMutex mutex;
    QWaitCondition bufferIsNotFull;
    QWaitCondition bufferIsNotEmpty;
    int head, tail;
    char buffer[N];
};

Conclusion

We have seen how monitors work in theory, including the use of wait conditions to synchronize threads, through the BankAccount and BoundedBuffer examples. We have also seen how to implement monitors in Qt. In the next issue, we will look at a few fundamental techniques for developing more powerful monitors than those presented here: covering conditions, "passing the condition", priority wait, and invariants. We will also compare monitors with semaphores, a lower-level synchronization primitive, and show how they can be implemented in terms of each other.

^[1] See for example Per Brinch Hansen's paper "Java's Insecure Parallelism" (ACM SIGPLAN Notices Vol. 34, Issue 4, April 1999).