Patterns for POSIX Condition Variables on Win32

Douglas C. Schmidt and Irfan Pyarali
Department of Computer Science
Washington University, St. Louis, Missouri


1. Introduction

This section is under construction


2. The Wrapper Facade Pattern

Intent

This pattern simplifies the OS system programming interface by combining multiple related OS system calls like the socket API or POSIX Pthreads into cohesive OO abstractions. This pattern avoids tedious, non-portable, and non-type-safe programming of low-level, OS-specific system calls.

Context

One benefit of OO techniques is to shield application-specific servants from the details of low-level systems programming. For instance, middleware developers, rather than application developers, are responsible for tedious, low-level tasks like synchronization and threading.

Problem

It is difficult for developers to wrestle with low-level system APIs written in languages like C, which often causes the following problems:

Solution

An effective way to avoid accessing system mechanisms directly is to use the Wrapper Facade pattern. In general, the Wrapper Facade pattern should be applied when existing system-level APIs are non-portable and non-type-safe.


3. Applying the Wrapper Facade Pattern to Condition Variables and Mutexes

This section is under construction

class Mutex
{
public:
  int acquire (void);
  int release (void);
  // ...

private:
  pthread_mutex_t mutex_;
};

class Condition
{
public:
  Condition (Mutex &m);
  ~Condition (void);
  int wait (Mutex &m);
  int wait (void);
  int signal (void);
  int broadcast (void);

private:
  Mutex &mutex_;
  pthread_cond_t cond_;
};

4. Win32 Condition Variable Implementations Revised

4.1. Modifying the SignalObjectAndWait Solution for Windows '95 and Windows NT 3.51

We'll start by changing the pthread_mutex_t typedef from a HANDLE back to a CRITICAL_SECTION:
typedef CRITICAL_SECTION pthread_mutex_t;
Then, we'll revise the implementation of our pthread_cond_wait function, as follows:
int
pthread_cond_wait (pthread_cond_t *cv, 
                   pthread_mutex_t *external_mutex)
{
  // Acquire lock to avoid race conditions.
  EnterCriticalSection (&cv->waiters_count_lock_);
  cv->waiters_count_++;
  LeaveCriticalSection (&cv->waiters_count_lock_);

  // The following two function calls are used in place of
  // <SignalObjectAndWait> for versions of Win32 that lack this
  // function.

  // Keep the lock held just long enough to increment the count of
  // waiters by one.  We can't keep it held across the call to
  // <WaitForSingleObject> since that will deadlock other calls to
  // <pthread_cond_signal> and <pthread_cond_broadcast>.
  ExitCriticalSection (external_mutex);  

  // Wait to be awakened by a <pthread_cond_signal> or
  // <pthread_cond_broadcast>. 
  WaitForSingleObject (cv->sema_, INFINITE);

  // Reacquire lock to avoid race conditions.
  EnterCriticalSection (&cv->waiters_count_lock_);

  // We're no longer waiting...
  cv->waiters_count_--;

  // Check to see if we're the last waiter after a
  // <pthread_cond_broadcast> call. 
  int last_waiter = 
    cv->was_broadcast_ && cv->waiters_count_ == 0;

  LeaveCriticalSection (&cv->waiters_count_lock_);

  // If we're the last waiter thread during this particular broadcast
  // then let all the other threads proceed.
  if (last_waiter)
    SetEvent (cv->waiters_done_);

  // Always regain the external mutex since that's the guarantee that
  // we give to our callers.
  EnterCriticalSection (external_mutex);
}

Evaluating the Modified Solution

Unfortunately, there's a very subtle problem with the implementation shown above. Note how the pthread_cond_broadcast implementation waits on the waiters_done_ manual-reset event until all waiters are finished. However, the last waiter thread, which signals this event, may not get the chance to wait on the external_mutex before another waiter gets it, performs some processing, and then releases and immediately reacquires the external_mutex. To implement a portable ``fair'' condition variable without using SignalObjectAndWait requires yet another approach, which is described next.

4.2. The Specific Notification Solution

This section is under construction

This approach uses the Specific Notification pattern [Cargill].

typedef struct
{
  std::deque waiters_count_;
  // FIFO queue of threads waiting on the condition variable.

  CRITICAL_SECTION waiters_count_lock_;
  // Protect the <waiters_count_> state.
} pthread_cond_t;
The pthread_cond_init initializes this implementation:

int
pthread_cond_init (pthread_cond_t *cv, 
                   const pthread_condattr_t *)
{
  broadcast_ = CreateSemaphore (NULL,  // no security
                                0,     // initially 0
                                0x7fffffff, // max
                                NULL); // unnamed
  mutex_ = CreateMutex (NULL,  // no security
                        FALSE, // unsignaled initially
                        NULL);  // unnamed
}

int
pthread_cond_destroy (pthread_cond_t *cv)
{
}

int 
pthread_cond_wait (pthread_cond_t *cv,
                   pthread_mutex_t *external_mutex)
{
}

int 
pthread_cond_signal (pthread_cond_t *cv)
{
}

int 
pthread_cond_broadcast (pthread_cond_t *cv)

{
}
pthread_cond_broadcast wakes up all threads currently blocked on the cv so they can recheck the condition expression before any other thread can successfully complete the wait.

Evaluating the Specific Notification Solution

This solution may be less efficient than Windows NT 4.x approach shown earlier since it creates and destroys events for every pthread_cond_wait. However, it is portable to all versions of Win32.

5. Implementing Events on non-Win32 Platforms

This section illustrates how to implement events on non-Win32 platforms. The following are the five primary operations defined on a Win32 event object:

Implementation

The following structure is used to keep track of the state of an event:
struct event_t
{
  mutex_t lock_;
  // Protect critical section.

  cond_t condition_;
  // Keeps track of waiters.

  int manual_reset_;
  // Specifies if this is an auto- or manual-reset event.

  int is_signaled_;
  // "True" if signaled.

  u_long waiting_threads_;
  // Number of waiting threads.
};
event_init is used to initialize an event structure:
void
event_init (event_t *event,
            int manual_reset,
            int initial_state,
            int type,
            char *name,
            void *arg)
{
  event->manual_reset_ = manual_reset;
  event->is_signaled_ = initial_state;
  event->waiting_threads_ = 0;
  
  cond_init (&event->condition_,
             type,
             name,
             arg);
  
  mutex_init (&event->lock_,
              type,
              name,
              arg);
}
event_destroy is used to destroy an event:
void
event_destroy (event_t *event)
{
  mutex_destroy (&event->lock_);
  cond_destroy (&event->condition_);
}
event_wait is used to wait on an event:
void
event_wait (event_t *event)
{
  // grab the lock first
  mutex_lock (&event->lock_);

  if (event->is_signaled_ == 1)
    // Event is currently signaled.
    {
      if (event->manual_reset_ == 0)
        // AUTO: reset state
        event->is_signaled_ = 0;
    }
  else
    // event is currently not signaled
    {
      event->waiting_threads_++;

      cond_wait (&event->condition_,
                 &event->lock_);

      event->waiting_threads_--;
    }

  // Now we can let go of the lock.
  mutex_unlock (&event->lock_);
}
event_signal is used to signal an event:
void
event_signal (event_t *event)
{
  // grab the lock first
  mutex_lock (&event->lock_);

  // Manual-reset event.
  if (event->manual_reset_ == 1)
    {
      // signal event
      event->is_signaled_ = 1;

      // wakeup all
      cond_broadcast (&event->condition_);
    }
  // Auto-reset event
  else
    {
      if (event->waiting_threads_ == 0)
        // No waiters: signal event.
        event->is_signaled_ = 1;
      else 
        // Waiters: wakeup one waiter.
        cond_signal (&event->condition_);
    }
  
  // Now we can let go of the lock.
  mutex_unlock (&event->lock_);
}
event_pulse is used to pulse an event:
void
event_pulse (event_t *event)
{
  // grab the lock first
  mutex_lock (&event->lock_);

  // Manual-reset event.
  if (event->manual_reset_ == 1)
    {
      // Wakeup all waiters.
      cond_broadcast (&event->condition_);
    }

  // Auto-reset event: wakeup one waiter.
  else 
    {
      cond_signal (&event->condition_);

      // Reset event.
      event->is_signaled_ = 0;
    }

  // Now we can let go of the lock.
  mutex_unlock (&event->lock_);
}
event_reset resets an event:
void
event_reset (event_t *event)
{
  // Grab the lock first.
  mutex_lock (&event->lock_);

  // Reset event.
  event->is_signaled_ = 0;
      
  // Now we can let go of the lock.
  mutex_unlock (&event->lock_);
}


6. Concluding Remarks


Acknowledgements

Thanks to David Holmes <dholmes@mri.mq.edu.au>, Bil Lewis <Bil@LambdaCS.com>, Alan Conway <aconway@iona.ie>, Kenneth Chiu <chiuk@cs.indiana.edu>, Jason Rosenberg <jason@erdas.com>, James Mansion <james@wgold.demon.co.uk>, Saroj Mahapatra <saroj@bear.com>, and Patrick Taylor <patrick.taylor@template.com> for many suggestions and constructive comments that helped to improve this paper.


References

[Cargill] ``Specific Notification for Java Thread Synchronization,'' Proceedings of the Pattern Languages of Programming Conference, Allerton Park, Illinois, August, 1996.

[GoF] Erich Gamma, Richard Helm, Ralph Johnson, and John Vlissides, Design Patterns: Elements of Reusable Software Architecture, Addison-Wesley, 1995.

[Pthreads] ``Threads Extension for Portable Operating Systems,'' IEEE P1003.4a, February, 1996.

[Richter] Jeffrey Richter, Advanced Windows, 1997, Microsoft Press, Redmond, WA.