How to wait correctly

In this short tutorial I'll describe how to wait for conditions and how to get notified about changes. A quite common way, most programmers are used to, is to use boolean flags. In a serial program, a check using a function like "isConditionXYZ()" will return true or false. And you will know that this flag will not change as long you are in your function, since they do not run in parallel. But if you have a function, which requires a flag to be true, a flag which can change at any time since some other thread may change it, you'll probably need to wait for it. At a first glance most programmer would use something like:

while ( !isConditionXYZ ) {};

A loop, waiting for a condition to become true. Do never use something like that. This consumes a lot of CPU cycles. Most operating system (and yes, we assume Windows to be an operating system too) can help us here. And thanks to Boost, we can utilize the operating system facilities quite easily.

Conditions

First we need to understand what conditions are and what kind of conditions are available in OpenWalnut. Basically, conditions in Boost are implemented using mutex. One thread can go to sleep, by waiting for a condition. In the meanwhile, another thread updates some classes and can now notify others to awake. This sleeping state is very CPU sparing. I think the idea behind condition variables is now clear. To have a more complete overview, you may look at http://www.boost.org/doc/libs/1\_35\_0/doc/html/thread/synchronization.html. Now, lets take a look at OpenWalnut's implementation of several condition types.

WCondition

This is basically a wrapper around boost::condition_variable_any. With it, a thread can wait for the owner of the condition to call notify(). Simple isn't it? Lets have a look at some code:

class MyList
{
public:
   ...

    void add( std::string s )
    {
        list.push_back( s );
        c.notify();
        c.wait();
    }

    WCondition* getAddCondition() { return &c; };

private:
    WCondition c;
}

class MyListWorker
{
public:
    MyListWorker( MyList& list ) { l = list };

    // the worker thread which should awake everytime a new item has been added
    void thread()
    {
        while ( running )
        {
            // wait until list thread adds something
            l.getAddCondition()->wait()

            // the list thread added an item
            doSomething( l );

            // awake list thread            
            l.getAddCondition()->notify();
        }
    }

    const WCondition& getAddCondition() { return c; };

private:
    MyList& l;
}

This is a simple (and not really good) example for the Worker Thread Pattern. The MyList adds an item and signals everybody to wake up and handle the new item. While they do, the MyList Thread sleeps. The worker can now do its work and notify the MyList thread when ready.

Note: The example has one weakness. If no worker thread is present to wake up the MyList thread again, it will sleep forever. You have to take such situations into account when using WCondition.

WConditionOneShot

If we have WCondition, why do we need WConditionOneShot? Assume the following situation. You have two parallel threads T1 and T2. One thread's object (T1) offers a WCondition member, lets name it T1::c. Furthermore assume, that the condition c will only fire once! A typical example would be initialization flags. So, if T2 starts, grabs the condition and waits, everything will be fine. T1 will later (after T2 got asleep) fire the condition and T2 will wake up. But if T2 gets delayed and uses T1's condition c.wait() after T1 notified it, it will sleep forever. This will be no problem if the condition fires repeatedly, as in our above example. But since T1 just fires it once, to notify everybody that T1 is not initialized, every Thread which came to late is stuck. One trivial solution would be to check a boolean flag variable before going asleep if the condition already came true. This would work if it is ensured that, while checking it with an IF statement, the flag will not change in the meanwile. That's where WConditionOneShot comes into play.

WConditionOneShot will prevent c.wait() to wait endlessly if the condition got fired in the past. Therefore it does not use a boolean flag. It uses shared mutex, since locking operations on them are atomic. So, you can use wait() in such cases without headaches.

Note: Since WConditionOneShot is derived from WCondition, the class offering a condition has to take care whether it is a condition or one shot condition. That's not the job of the class using the condition.

WFlag

Although the conditions are very useable, they miss the possibility to conjunct them with a variable/value. That is what is commonly called "flag" or "state". If you wait for a condition you will not know which state/flag changed when the condition got fired. WFlag's goal is to have a condition associated with a variable. In the simplest case: a bool.

class A
{
    a(){ m_isInitialized = new WFlag< bool >( new WConditionOneShot, false ); };

    // initialize
    void init()
    {
       doInitStuff();
       m_isInitialized( true );
    };

    const WFlag< bool >& isInitialized() { return m_isInitialized; };

private:
    WFlag< bool > m_isInitialized;
}

...

void someThread( A* a )
{
   // to simply get the value of the flag use the () operator
   // NOTE: you have to dereference it using *
   cout << "Initialized?: " << ( *a->isInitialized() )() << endl;

   // to wait until initialized
   ( *a->isInitialized() )->wait();

   // now the A instance is definitively initialized by some other thread
   doStuff( a );
}

The good news is: you can specify what kind of condition a flag should use. In this example a one shot condition to avoid endless waiting of "someThread". You can access the associated variable using get() or the () operator. To wait for it use wait() as with the conditions. Which condition type to use also has to be decided by the owning class, since it knows best what is needed.

Note: Please note, that for convenience reasons, a class WBoolFlag is available (which simply is a WFlag< bool > shortcut).

Note: The getter for WFlag instances should always return const references or const pointer.

WConditionSet

A great disadvantage of conditions is? Exactly! You can only wait on one condition at once. To wait for multiple conditions the WConditionSet is optimal. It allows several conditions to be added to a set. The WConditionSet itself is a WCondition and can therefore be used for other WConditionSet. The condition set will notify its waiting threads once one of the conditions in the set fires. The usage is simple:

boost::shared_ptr< WCondition > c1 = new boost::shared_ptr< WCondition >( new WCondition() );
boost::shared_ptr< WCondition > c2 = new boost::shared_ptr< WCondition >( new WCondition() );
s.add( c1 );
s.add( c2 );
s.wait(); // wait until myCondition1 or myCondition2 fires

Although condition sets are very practical, one has to be clear about several logical implications.

Assume the following situation: You have two conditions c1 and c2, both inside a condition set s. c1 fires, so s fires and a pending wait() call returns. Your algorithm does a lot of calculations. While those calculations are running, c2 fires and, therefore, s. But since your thread is busy, it will never be noticed about it. The next wait() call will wait until the next condition fires and will NOT return even though c2 fired in the past. To resolve this problem, one can use the "resetable" feature of WConditionSet. Using s.setResetable() allows the condition set to "remember" the last notification. Now lets use our above example again. The condition c1 fires while a thread waits for s. It will awake and do some tasks. In the meanstime, c2 fires. The resetable condition set s will now remember it. After the thread has finished its tasks, it will call s.wait() again. Now, wait() instantly returns, since it knows about the condition c2, which fired in the past. The call also resets the "memory" of s. A consequent call to wait() will wait again until the next condition fires. These resetable condition sets are especially useful for module threads waiting for conditions denoting changes in the input connectors, or waiting for changes in some properties. This usecase can be seen in HowtoWriteModules.

FAQ

Why should WCondition* and WFlag instances be returned as const?

Because this prevents everybody from changing the value of the flag.

Why per reference/pointer?

That's because the used mutex and condition variables have a private copy constructor and are, therefore, non-copyable.