Search This Blog

Saturday, June 11, 2005

Conditions - Windows Implementation

The Windows version of the condition is fairly straightforward (and I don't know about you, but I'm getting a bit bored with all these almost-alike-but-not-quite fast synchronization objects), and more than a bit resembles the fast mutex. Here, we have a slow semaphore that waiting threads wait on, and a counter of how many waiting threads there are. The use of atomic functions to access the waiting threads counter allows us to signal from either inside or outside the mutex paired with the condition. Really, the only major difference between the condition and the mutex implementation is that with the condition, a paired mutex must be exited before waiting, and reentered after waiting.

In doing so, it's essential that the counter be incremented before leaving the mutex to wait (despite the fact that the counter is accessed atomically). Were this not the case, we'd create a race between the data (which is protected by the mutex) and the counter (which is accessed atomically) and possibly set a thread to sleep for some indefinite period of time. This is a problem that does not work the other way: we can safely access the counter outside the mutex if we're decrementing it (that is, we're waking waiting threads).

The code:

class CCondition // Win32 version of CCondition (fast)
{
private:

CMutex &m_pairedMutex; // The paired mutex
CSemaphore m_sem; // Semaphore waiters will wait on

// Atomically accessed, so that Signal may be called outside the mutex
int32 m_nWaiters; // Number of threads waiting on the semaphore

public:
// Associates a mutex with the condition. From this point on, no other mutex may be used to access the condition. However, multiple conditions may be associated with the same mutex.
inline CCondition(CMutex &mutex) : m_pairedMutex(mutex), m_sem(0)
{
m_nWaiters = 0;
}

inline ~CCondition()
{
if (m_nWaiters)
m_sem.Post(m_nWaiters);
}

// Signal that the condition is true and signal threads waiting; has no effect if no threads are waiting. Can either release one thread or all threads. May be called inside the mutex or outside.
inline void Signal(bool bSignalAll = false)
{
int32 nWaiters, nReleaseThreads;

do
{
nWaiters = m_nWaiters;
assert(nWaiters >= 0);

if (!nWaiters)
return; // Do nothing if no threads are waiting

nReleaseThreads = (bSignalAll ? nWaiters : 1);
} while (AtomicCompareExchange(&m_nWaiters, nWaiters - nReleaseThreads, nWaiters) != nWaiters);

m_sem.Post(nReleaseThreads); // Set them loose
}

// Waits for the condition to become true. Must be called from inside the mutex, and the thread will be back inside the mutex at return. HOWEVER, return does not GUARENTEE that the condition is true. You must verify that condition has indeed become true upon return.
inline void Wait()
{
// Absolutely essential that this get done before we leave the mutex or we create a race condition
AtomicIncrement(&m_nWaiters); // One more waiter

m_pairedMutex.Leave(); // Leave mutex
m_sem.Wait(); // Wait for signal
m_pairedMutex.Enter(); // Reenter mutex after signal
}
};

No comments: