Subj : Re: Win32 condition variables redux
To   : comp.programming.threads
From : Charles Bryant
Date : Wed Aug 03 2005 11:02 pm

In article <1123053927.358976.266600@g44g2000cwa.googlegroups.com>,
d|dq <digital_don_quijote@yahoo.com> wrote:
>So, I would settle for a redux version of condition variables...
>
>For instance, if one assumes the following requirements:
>
>- Thread cancellation is not supported.
>- The external mutex is held by any thread executing a wait, timed
>wait, signal or broascast operation.
>- The solution does not need to support versions of Windows prior to
>Windows 2000.
>
>- The solution should be based on the Windows API without making any
>assumption beyond its documentation.
>- The solution should not make assumptions about the underlying
>hardware.
>
>So what would such an implementation look like?

The folowing works, subject to one major restriction:

A condition variable is a manual reset event.

A mutex is anything you like (critical section, event, mutex, etc).

cv_wait(cv, mx) looks like this:
	ResetEvent(cv);
	unlock(mx);
	WaitForSingleObject(cv);
	lock(mx);

cv_signal(cv) and cv_broadcast(cv) both look like this:
	SetEvent(cv);

Here's how it works. Suppose you have a predicate P used with a condition
variable. P might be 'the queue is empty'. The use of a condition
variable will be like this:

somewhere:
	lock(mx);
	while (P) {
		cv_wait(cv, mx);
	}
	do something which requires !P
	unlock(mx)

somewhere else:
	lock(mx);
	do something which makes P false
	unlock(mx);
	cv_signal(cv);

Given some reasonable assumptions, we can prove that the cv_wait will
always wake up soon after P becomes false. These assumptions are:
	* if P is true at the point of any lock(mx), then at the
	  corresponding unlock(mx) either P is true or a cv_signal(cv)
	  will soon be executed
	* no code can change the value of P unless it holds the lock

From this it follows that we can guarantee that if no thread holds the
lock then either P is false (which means threads can safely sleep) or
some thread is about to perform SetEvent(), or the event is aleady
signalled.

In fact, you may even be able to convince yourself that this approach
can be proven correct.

Unfortunately, there is one important assumption it makes: that there
is only one predicate used with a given condition variable. For
example, a queue object might use a single condition variable to
signal both "queue is not full" and "queue is not empty". With proper
condition variables, this is quite reasonable, since you can't have
one thread waiting for the queue to be non-empty while another waits
for it to have space. However the implementation outlined above can
fail in this way:

	Thread A attempts to dequeue an item, finds the queue is
	empty, and calls cv_wait(), which resets the event, and
	unlocks the mutex. At this point thread A gets pre-empted.

	Thread B starts up and quickly fills the queue. It then
	attempts to put another item in the queue, finds it full, and
	calls cv_wait(), which resets the event, unlocks the mutex,
	and blocks thread B in the WaitForSingleObject().

	Thread A now resumes, gets into WaitForSingleObject() and goes
	to sleep on the event.

Both threads end up asleep on an event which will never be signalled.

.