Monitors and Wait Conditions in Qt (Part 1)

Материал из Wiki.crossplatform.ru

Qt Quarterly | Выпуск 21 | Документация

by Jasmin Blanchette

This article assumes that you have some experience with multithreadedprogramming and have familiar with concepts such as mutual exclusionand atomic operations. If this is a new topic to you, I recommendthat you start by readingThread Support in Qtand consult a book on the topic, such as Multithreaded, Parallel, andDistributed Programming by Gregory R. Andrews (2000).

[править] What is a Monitor?

The following pseudo-code presents a very simple monitor thatmodels 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 callswill always be serialized, no matter how many threads try to accessthe same monitor instance at the same time. For instance, ifthread A tries to call deposit() while thread B is executingwithdraw(), A will have to wait until B is done before executing.

In Java, the above monitor would be implemented using thesynchronized 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 amember 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 constructorcalls lock() on the mutex and its destructor calls unlock().

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

[править] Wait Conditions

The above monitor isn't very realistic, because it lets us performwithdrawals even if that leaves the account in the red. This is wherewait conditions come into play. Here's a new version of theBankAccount monitor that will simply block if there is not enoughmoney 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. Waitconditions support the following three operations:

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

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

To make all of this a bit clearer, let's consider the example of anEducation Loan Authority thread and a Student thread. The LoanAuthority deposits 500 dollars each month. The Student takes outmoney in a more erratic fashion. One possible scenario is presentedbelow:

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

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

When March arrives, the Authority deposits 500 dollars as usual andtries to wake up the Student by signaling the moreMoneycondition, but the Student realizes that 1000 dollars still aren'tsufficient (at least not for two weeks in the Bahamas), so he orshe goes back to sleep.

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

The revised version of the BankAccount monitor has the followingnoteworthy characteristics:

• The balance can never be negative. If a thread tries totake out money that isn't in the account, the thread is put tosleep.
• 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 sumof all withdrawals. In short, there are no race conditions.
• The solution scales to more than two threads. Forexample, 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++, usingQt'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. Themutex is automatically unlocked immediately before the thread goesto sleep, and locked again when the thread is woken up. Unlockingthe mutex is necessary to let other threads access the bank accountwhile the thread is sleeping. (In our pseudo-code syntax, this wasall implicit.)

Also, the signal() and signalAll() functions from thepseudo-code are called wakeOne() and wakeAll() in Qt, to avoidconfusion 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 theirlectures, a two-month sleep at the bank seems undesirable at best.Fortunately, it turns out that this is fairly easy to fix, by addinga 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 itreturns true, instead of hibernating through the winter andwaking up a few weeks before the final exams.

[править] Example: Bounded Buffers

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

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 itcomputes. The Consumer thread calls get() to obtain the bytes asthey are generated by the Producer. If the Producer is significantlyfaster than the Consumer, it will end up filling the buffer, at whichpoint it must wait for the Consumer to retrieve at least one byte.Likewise, if the Consumer is faster than the Producer, it will haveto wait so as to avoid reading garbage.

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

To synchronize the two threads, we use two waitconditions: bufferIsNotFull and bufferIsNotEmpty. If theProducer calls put() when the buffer is already full, theProducer 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 waitconditions to synchronize threads, through the BankAccount andBoundedBuffer examples. We have also seen how to implement monitorsin Qt. In the next issue, we will look at a few fundamentaltechniques for developing more powerful monitors than those presentedhere: covering conditions, "passing the condition", priority wait,and invariants. We will also compare monitors with semaphores, alower-level synchronization primitive, and show how they can beimplemented in terms of each other.