Re: MT Design Question
On Aug 29, 11:37 am, Joshua Maurice <joshuamaur...@gmail.com> wrote:
On Aug 29, 10:47 am, "Chris M. Thomasson" <cris...@charter.net> wrote:
"Balog Pal" <p...@lib.hu> wrote in message
news:i5d2jb$1ob3$1@news.ett.com.ua...
"Joshua Maurice" <joshuamaur...@gmail.com>
[...]
Implementing the equivalent of
pthread_cond_wait with the windows XP and earlier API is surprisingly
difficult, and generally results in much less efficient code than if
they had properly implemented kernel and scheduler to directly
understand pthread_cond_wait or equivalent.
Implementing the perfect equivalent maybe. But covering the same
high-level
use case is not. The use of attached an auto-locking mutex in sig=
naling
looks convenient, but is not needed more often than it is. And the=
rest
of
the cases can be probably covered better too, using
WaitFormultipleObjects.
(Btw if you just use the latter to wait on Event and a mutex with ALL
option, isn't the effect the same as you are after? )
FWIW, here are some of the issues:
http://www.cs.wustl.edu/~schmidt/win32-cv-1.html
Well, actually, it's not all _that_ hard to get a correct condvar impl =
on
Windows. Here is a sketch for a simple broadcast only condvar for Windo=
ws.
Keep in mind that POSIX allows for broadcast only impls as
`pthread_cond_signal()' is allowed to wake more than one thread.
<pseudo-code sketch>
_______________________________________________________
struct condvar
{
struct waitset
{
HANDLE m_event; // = manual reset event; set to false
LONG m_refs; // = 0
};
waitset* m_waitset; // = NULL
LONG m_refs; // = 0
CRITICAL_SECTION m_mutex;
void wait(LPCRITICAL_SECTION umutex)
{
// grab a reference to the current waitset
EnterCriticalSection(&m_mutex);
waitset* w = m_waitset;
if (! w) w = m_waitset = new waitset();
++m_refs;
LeaveCriticalSection(&m_mutex);
// unlock user mutex and wait on the waitset we obtaine=
d
LeaveCriticalSection(umutex);
WaitForSingleObject(w->m_waitset, INFINITE);
// decrement the waitsets refcount
if (! InterlockedDecrement(&w->m_refs))
{
delete w;
}
EnterCriticalSection(umutex);
// that's all folks! ;^)
}
void broadcast()
{
// swap a reference to the current/new waitset with NUL=
L
EnterCriticalSection(&m_mutex);
waitset* w = m_waitset;
LONG refs = m_refs;
m_waitset = NULL;
m_refs = 0;
LeaveCriticalSection(&m_mutex);
if (w)
{
// signal all waiters
SetEvent(w->m_event);
// transfer the swapped reference count to the =
waitset reference
count
if (InterlockedExchangeAdd(&w->m_refs, refs) =
== -refs)
{
delete w;
}
}
}
void signal()
{
broadcast();
}};
_______________________________________________________
Barring any damn typos, the algorithm works perfectly fine. BTW, there =
are
several enhancements that can be made to it... Perhaps a waitset cache?
;^)
Second, don't we have a race condition in wait? Luckily, I see it just
with instruction interleaving (as opposed to something more complex
like 2 writes becoming visible to different cores in different
orders).
thread X enters wait,
thread X creates a waitset,
thread X assigns it to m_waitset,
thread X calls WaitForSingleObject(w->m_waitset, INFINITE),
thread X returns from it,
thread X uses an atomic decrement and sees 0.
thread Y enters wait,
thread Y assigns m_waitset to the local w,
thread Y runs if (! w) and sees w is non-zero,
thread X calls "delete w;"
thread Y then calls WaitForSingleObject(w->m_waitset, INFINITE), which
waits on an object which was just deleted.
We could move "EnterCriticalSection(umutex);" up above the code:
// decrement the waitsets refcount
if (! InterlockedDecrement(&w->m_refs))
{
delete w;
}
That might remove that race, I think. Alternatively, we can use
m_mutex to guard the decrement and delete if 0 part, and I think that
also removes the race condition.
Do the windows wait functions have spurious wakeups? At the very
least, I know INFINITE is just a macro for a very large number, so all
waits are just timed waits right? Without spurious wakeups (or timed
waits ala INFINITE), I think your code works. Anyway, I think you
implicitly assumed this.