Simple condvar implementation for Win32

[Sergey P. Derevyago]

I've implemented a condvar on Win32 using the following code:

class win_cond_var {
mutex& m;
HANDLE evs[2];
int gen;

public:
static const long infinite=-1;

win_cond_var(mutex& mtx);
~win_cond_var();

void wait(long timeout);
void notify();
void notify_all();
};

win_cond_var::win_cond_var(mutex& mtx) : m(mtx), gen(0)
{
evs[0]=CreateEvent(0, FALSE, FALSE, 0);
assert(evs[0]!=0);

evs[1]=CreateEvent(0, TRUE, FALSE, 0);
assert(evs[1]!=0);
}

win_cond_var::~win_cond_var()
{
CloseHandle(evs[0]);
CloseHandle(evs[1]);
}

void win_cond_var::wait(long timeout)
{
int currGen=gen;
m.unlock();

DWORD rcd=WaitForMultipleObjects(2, evs, FALSE, (timeout==infinite) ?
timeout : INFINITE);
assert(rcd>=WAIT_OBJECT_0 && rcd<WAIT_OBJECT_0+2 || rcd==WAIT_TIMEOUT);

m.lock();
if (currGen==gen+1) {
BOOL rcb=ResetEvent(evs[1]);
assert(rcb!=0);
}
}

void win_cond_var::notify()
{
BOOL rc=SetEvent(evs[0]);
assert(rc!=0);
}

void win_cond_var::notify_all()
{
gen++;

BOOL rc=SetEvent(evs[1]);
assert(rc!=0);
}

Do you see any problems?

The constraints are:
1. The code must run on Win98 too.
2. No lost wakeups are allowed. Spurios wakeups allowed, though.
3. Simple and clear implementation.

The hot answers:
1. Yes, I've successfully run several tests.
2. Yes, I've read http://www.cs.wustl.edu/~schmidt/win32-cv-1.html
3. Yes, I know about http://sourceware.org/pthreads-win32/
4. Yes, I've read "Windows System Programming Third Edition" by Johnson M.
Hart.
5. Yes, I've read "Programming with POSIX Threads" by David R. Butenhof.

So please be precise and specific. Thank you.
--
With all respect, Sergey. http://ders.stml.net/
mailto : ders at skeptik.net

[Joe Seigh]

Sergey P. Derevyago wrote:
> I've implemented a condvar on Win32 using the following code:

[...]
>

> void win_cond_var::wait(long timeout)
> {
> int currGen=gen;
> m.unlock();

There's a race condition here for some threads waiting on a broadcast.
The broadcast event could get signaled and some other thread waiting
on that generation of the broadcast resets the event before all threads
waiting on that generation gets a chance to wait.

>
> DWORD rcd=WaitForMultipleObjects(2, evs, FALSE, (timeout==infinite) ?
> timeout : INFINITE);
> assert(rcd>=WAIT_OBJECT_0 && rcd<WAIT_OBJECT_0+2 || rcd==WAIT_TIMEOUT);
>
> m.lock();
> if (currGen==gen+1) {
> BOOL rcb=ResetEvent(evs[1]);
> assert(rcb!=0);
> }
> }
>
> void win_cond_var::notify()
> {
> BOOL rc=SetEvent(evs[0]);
> assert(rc!=0);
> }
>
> void win_cond_var::notify_all()
> {
> gen++;

Unsynchronized updating of gen. There seems to be an implicit
assumption that the lock will be held.

>
> BOOL rc=SetEvent(evs[1]);
> assert(rc!=0);
> }
>
> Do you see any problems?
>
> The constraints are:
> 1. The code must run on Win98 too.
> 2. No lost wakeups are allowed. Spurios wakeups allowed, though.
> 3. Simple and clear implementation.
>

--
Joe Seigh

When you get lemons, you make lemonade.
When you get hardware, you make software.

[Sergey P. Derevyago]

Joe Seigh wrote:
> > void win_cond_var::wait(long timeout)
> > {
> > int currGen=gen;
> > m.unlock();
>
> There's a race condition here for some threads waiting on a broadcast.
> The broadcast event could get signaled and some other thread waiting
> on that generation of the broadcast resets the event before all threads
> waiting on that generation gets a chance to wait.
>

> > void win_cond_var::notify()
> > {
> > BOOL rc=SetEvent(evs[0]);
> > assert(rc!=0);
> > }
> >
> > void win_cond_var::notify_all()
> > {
> > gen++;
>
> Unsynchronized updating of gen. There seems to be an implicit
> assumption that the lock will be held.
>

Sure, notifyXXX calls must always be synchronized using the mutex.
In particular, it prevents from the RC you're talking above.

[Joe Seigh]

It doesn't prevent the race condition. A thread can arbitrarily pause
in execution at any time and you have to logic that prevents resetting
an event before all waiters have had a chance to actually wait on the
event. It's a race condition that SignalAndWait was seemingly designed
to fix except you can only wait on a single event object.

[Sergey P. Derevyago]

Joe Seigh wrote:
> > void win_cond_var::wait(long timeout)
> > {
> > int currGen=gen;
> > m.unlock();
>
> There's a race condition here for some threads waiting on a broadcast.
> The broadcast event could get signaled and some other thread waiting
> on that generation of the broadcast resets the event before all threads
> waiting on that generation gets a chance to wait.
>

Yes, this is a RC. You're right.
Sorry, I didn't get it at the first reading.

[Markus Elfring]

> Sorry, I didn't get it at the first reading.

Did you look at any previous discussions about this programming topic to reuse
any well-known experiences? How useful are the descriptions in your case?

Regards,
Markus

[Sergey P. Derevyago]

Markus Elfring wrote:
> Did you look at any previous discussions about this programming topic to reuse
> any well-known experiences? How useful are the descriptions in your case?
>

I look for a _simple_ implementation.
Unfortunately, my tests didn't check for lost wakeups correctly.

[Joe Seigh]

Sergey P. Derevyago wrote:
> Markus Elfring wrote:
>
>>Did you look at any previous discussions about this programming topic to reuse
>>any well-known experiences? How useful are the descriptions in your case?
>>
>
> I look for a _simple_ implementation.
> Unfortunately, my tests didn't check for lost wakeups correctly.

Well, we've all been there. How do you think we spotted the race condition
so quickly? :)

[Markus Elfring]

> I look for a _simple_ implementation.

1. You are looking for a correct one, aren't you?
I suggest to be careful with the wording.

2. If an error-free approach will look simple, may be a topic for interpretation
and open discussion.

Regards,
Markus

[Phil Frisbie, Jr.]

Sergey P. Derevyago wrote:

> Markus Elfring wrote:
>
>>Did you look at any previous discussions about this programming topic to reuse
>>any well-known experiences? How useful are the descriptions in your case?
>>
>
> I look for a _simple_ implementation.
> Unfortunately, my tests didn't check for lost wakeups correctly.

Pthreads and Windows threads are too different to have a simple
emulation either way. I used the pthread for WIN32 for a few years, and
it works well at emulating pthreads on Windows, but it has a high overhead.

So, I choose to create my own API that is 'in between' pthreads and
Windows threads for my own portable projects. The API is closer to
Windows than pthreads, but it is easy to use with much less overhead
than some other wrappers. More details at my site below if you are
interested.

--
Phil Frisbie, Jr.
Hawk Software
http://www.hawksoft.com

[Sergey P. Derevyago]

"Phil Frisbie, Jr." wrote:
> Pthreads and Windows threads are too different to have a simple
> emulation either way.
>

Yes, that's the problem.

> I used the pthread for WIN32 for a few years, and
> it works well at emulating pthreads on Windows, but it has a high overhead.
>

Except for the overhead, I don't like the messages like "The Borland Builder
5.5 version of the library produces memory read exceptions in some tests." My
goal is to build something simple and robust (in particular, I don't need the
cancellation).

> So, I choose to create my own API that is 'in between' pthreads and
> Windows threads for my own portable projects. The API is closer to
> Windows than pthreads, but it is easy to use with much less overhead
> than some other wrappers. More details at my site below if you are
> interested.
>

I'll take a look, thank you.

[rfis...@gmail.com]

Phil Frisbie, Jr. wrote:
> Sergey P. Derevyago wrote:

> So, I choose to create my own API that is 'in between' pthreads and
> Windows threads for my own portable projects. The API is closer to
> Windows than pthreads, but it is easy to use with much less overhead
> than some other wrappers.

Quick question: did you make the pthread mutexes recursive? Or did
you leave recursive behaviour undefined? I won't pretend to be
impartial: I hate recursive mutexes, they feel "mushy". When a
piece of code written by an author that seems to have heard of
threads and not mutexes falls into my lap I like to slowly sure
things up with some well placed mutexes, backing off when deadlocks
occur (to later remove because the code is almost always gratuitously
threaded). For me deadlock can be a handy debugging tool, so it drives
me up the wall when clanlib, win32 and inhouse-thread-wrapper-N go to
great lengths to not implement the simplest solution (non recursive).
Occam would be turning in his grave.

[Sergey P. Derevyago]

"Phil Frisbie, Jr." wrote:
> So, I choose to create my own API that is 'in between' pthreads and
> Windows threads for my own portable projects.
>

Your implementation uses PulseEvent() so it's obviously buggy.

[Joe Seigh]

Sergey P. Derevyago wrote:
> "Phil Frisbie, Jr." wrote:
>
>>So, I choose to create my own API that is 'in between' pthreads and
>>Windows threads for my own portable projects.
>>
>
> Your implementation uses PulseEvent() so it's obviously buggy.
> --

Depending on your event handling logic, SetEvent/ResetEvent has
the same problem. It just has a much larger window so the race
condition is rarely observed. I think we discussed this before
on c.p.t.

[Sergey P. Derevyago]

Joe Seigh wrote:
> Depending on your event handling logic, SetEvent/ResetEvent has
> the same problem.
>

I've already agreed that my implementation has a RC. No point to discuss it
farther.

BTW could you please suggest some good test cases for the lost wakeups? I'm
currently testing the second version and I don't want to present yet another
buggy attempt.

[Joe Seigh]

Sergey P. Derevyago wrote:
> Joe Seigh wrote:
>
>>Depending on your event handling logic, SetEvent/ResetEvent has
>>the same problem.
>>
>
> I've already agreed that my implementation has a RC. No point to discuss it
> farther.

This is a totally different issue that was discussed much further back on
c.p.t. It has to do with a thread waiting on an event, being removed
from the event waitset for a kernel APC, and a SetEvent/ResetEvent occurring
before the thread returned from the kernel APC and was added back into the
event waitset. The point is that it's not just PulseEvent that has this
kind of problem. So if you did a broadcast only condvar with SignalAndWait
to avoid the race condition in your original code, there would still be a
kernel APC issue which wasn't discussed earlier w.r.t. your earlier code.
This is a side discussion but probably one that's important in whatever
condvar implementation you ultimately come up with. Most of the solutions that
work use some form of explicit waitset management.

>
> BTW could you please suggest some good test cases for the lost wakeups? I'm
> currently testing the second version and I don't want to present yet another
> buggy attempt.

This would mostly be a code and logic review issue. You could put Sleeps in certain
code sections to exaggerate timings but you'd have to recognize which sections were
important.

[rfis...@gmail.com]

Sergey P. Derevyago wrote:
> Joe Seigh wrote:
> > Depending on your event handling logic, SetEvent/ResetEvent has
> > the same problem.
> >
> I've already agreed that my implementation has a RC. No point to discuss it
> farther.

I don't know... it was a pretty buggy, racey condition. I'm sure we
could get a
few more good yuks out of it.

> BTW could you please suggest some good test cases for the lost wakeups? I'm
> currently testing the second version and I don't want to present yet another
> buggy attempt.

Boh, I don't know, you could write some interesting condvar code and
compare
the results using yours and pthread-win32... Sorry for the content-free
response.

[rfis...@gmail.com]

Sergey P. Derevyago wrote:
> Joe Seigh wrote:
> > Depending on your event handling logic, SetEvent/ResetEvent has
> > the same problem.
> >
> I've already agreed that my implementation has a RC. No point to discuss it
> farther.

I don't know... it was a pretty buggy, racey condition. I'm sure we

could get a
few more good yuks out of it.

> BTW could you please suggest some good test cases for the lost wakeups? I'm

> currently testing the second version and I don't want to present yet another
> buggy attempt.

Boh, I don't know, you could write some interesting condvar code and

[Markus Elfring]

> So, I choose to create my own API that is 'in between' pthreads and
> Windows threads for my own portable projects.

Which are the relevant design decisions for your choice?

> The API is closer to Windows than pthreads, but it is easy to use with
> much less overhead than some other wrappers.

Would you like to explain the specific differences?

I have got doubts about coding correctness if I see instructions like the
following in your source file "htcondition.c":
(void)pthread_mutex_lock((pthread_mutex_t *)&cv->mutex);

Why do you (intentionally) ignore the return value from this function call?
Would you like to add any checking for error codes?
How do you think that an implementation with correct error handling would look
like in your approach?

Which of the solutions from the description "Strategies for Implementing POSIX
Condition Variables on Win32" by Douglas C. Schmidt and Irfan Pyarali did you
try to implement?
http://www.cs.wustl.edu/~schmidt/win32-cv-1.html

Regards,
Markus

[Phil Frisbie, Jr.]

rfis...@gmail.com wrote:
> Quick question: did you make the pthread mutexes recursive? Or did
> you leave recursive behaviour undefined?

They are non-recursive.

[Chris Thomasson]

Here is how to create highly efficient signaling mechanism for windows:

http://groups.google.com/group/comp.programming.threads/browse_frm/thread/de83c4ebcdcc07e5

The waitset cannot be used as a condvar. Joe pointed out why. However, you
can "wrap" the waitset with a heavily fast-pathed eventcount algorithm. I
invented the algorithm presented above. It outperforms all of the
synchronization mechanism on Vista!

Blows them out of the fuck$ing water.!!!!!

Really.

[Sergey P. Derevyago]

Chris Thomasson wrote:
> Here is how to create highly efficient signaling mechanism for windows:
> http://groups.google.com/group/comp.programming.threads/browse_frm/thread/de83c4ebcdcc07e5
>

I skimmed over this topic and it seems like there were some problems with
your approach.
Nevertheless, the synchronization primitives must not be the bottleneck of a
good MT code (if you pay so much to transfer some work from one thread to
another, why don't you do this work in the current thread?).

Finally, I've come to the following simple and straightforward implementation
and it seems like it serves well to my needs. The essence is:

class win_cond_var {
mutex& m;
event_cache evc;
vector<HANDLE> wts;

public:
static const long infinite=-1;

win_cond_var(mutex& mtx);
~win_cond_var();

void wait(long timeout);
void notify();
void notify_all();
};

void win_cond_var::wait(long timeout)
{
HANDLE ev=evc.getEvent();
wts.push_back(ev);
m.unlock();

DWORD rcd=WaitForSingleObject(ev, (timeout==infinite) ? timeout : INFINITE);
assert(rcd==WAIT_OBJECT_0 || rcd==WAIT_TIMEOUT);

m.lock();
evc.returnEvent(ev);
}

void win_cond_var::notify()
{
if (wts.size()==0) return;

HANDLE ev=wts.back();
wts.pop_back();

BOOL rc=SetEvent(ev);
assert(rc!=0);
}

void win_cond_var::notify_all()
{
if (wts.size()==0) return;

for (int i=0, end=wts.size(); i<end; i++) {
BOOL rc=SetEvent(wts[i]);
assert(rc!=0);
}

wts.clear();
}

Any comments are welcome :)

[Alexander Terekhov]

You're reinventing the wheel (albeit with standard puch_back() and
pop_back() goodies added), ders. Try google.

regards,
alexander.

[Chris Thomasson]

"Sergey P. Derevyago" <non-ex...@iobox.com> wrote in message
news:45827525...@iobox.com...

> Chris Thomasson wrote:
>> Here is how to create highly efficient signaling mechanism for windows:
>> http://groups.google.com/group/comp.programming.threads/browse_frm/thread/de83c4ebcdcc07e5
>>
> I skimmed over this topic and it seems like there were some problems with
> your approach.

Like what?

> Finally, I've come to the following simple and straightforward
> implementation
> and it seems like it serves well to my needs. The essence is:

That works. I posted code in this thread:

http://groups.google.com/group/comp.programming.threads/browse_frm/thread/237a65dbc2269e/acccad585f244493?lnk=gst&q=condvar+win32+chris&rnum=3&hl=en#acccad585f244493

That uses per-thread bin-semas..

One problem... Your bound to SCHED_OTHER. My eventcount algorithm is not
bound to sched_other.

[Sergey P. Derevyago]

Alexander Terekhov wrote:
> You're reinventing the wheel (albeit with standard puch_back() and
> pop_back() goodies added), ders. Try google.
>

I.e. it works. Thank you ;)

[Sergey P. Derevyago]

Chris Thomasson wrote:
> > I skimmed over this topic and it seems like there were some problems with
> > your approach.
>
> Like what?
>

I only skimmed over this thread, so it's just an opinion. Quick and dirty.

[Anthony Williams]

Your notify functions require that the associated mutex is locked whilst they
are called, else the calls on wts are subject to race conditions.

Anthony
--
Anthony Williams
Software Developer
Just Software Solutions Ltd
http://www.justsoftwaresolutions.co.uk

[Alexander Terekhov]

"Sergey P. Derevyago" wrote:
>
> Alexander Terekhov wrote:
> > You're reinventing the wheel (albeit with standard puch_back() and
> > pop_back() goodies added), ders. Try google.
> >
> I.e. it works. Thank you ;)

It doesn't mean that. Timeouts are surely busted, but you're quite
welcome. ;-)

regards,
alexander.

[Sergey P. Derevyago]

Anthony Williams wrote:
> Your notify functions require that the associated mutex is locked whilst they
> are called,
>

Sure they are. I don't need to implement all properties of phtreads.
BTW it was noted in the following reply from the very beginning:
http://groups.google.com/group/comp.programming.threads/msg/348991943942c918

[Sergey P. Derevyago]

Alexander Terekhov wrote:
> It doesn't mean that. Timeouts are surely busted,
>

Does it mean that WaitForSingleObject() incorrectly processes the timeout
argument?

[Alexander Terekhov]

"Sergey P. Derevyago" wrote:
>
> Alexander Terekhov wrote:
> > It doesn't mean that. Timeouts are surely busted,
> >
> Does it mean that WaitForSingleObject() incorrectly processes the timeout
> argument?

Suppose that it does it correctly. What happens next with your wts
queue in the case of timeout?

regards,
alexander.

[Sergey P. Derevyago]

Alexander Terekhov wrote:
> Suppose that it does it correctly. What happens next with your wts
> queue in the case of timeout?
>

Oops! It's an error, thank you.

[Sergey P. Derevyago]

Alexander Terekhov wrote:
> Suppose that it does it correctly. What happens next with your wts
> queue in the case of timeout?
>

OK, what about the following quick and obvious patch?

void win_cond_var::wait(long timeout)
{
HANDLE ev=evc.getEvent();
wts.push_back(ev);
m.unlock();

DWORD rcd=WaitForSingleObject(ev, (timeout==infinite) ? timeout : INFINITE);
assert(rcd==WAIT_OBJECT_0 || rcd==WAIT_TIMEOUT);

m.lock();

if (rcd==WAIT_TIMEOUT) {
vec_type::iterator it=find(wts.begin(), wts.end(), ev);
if (it==wts.end()) {
BOOL rc=ResetEvent(ev);
assert(rc!=0);
}
else wts.erase(it);
}

evc.returnEvent(ev);

[Alexander Terekhov]

"Sergey P. Derevyago" wrote:
>
> Alexander Terekhov wrote:
> > Suppose that it does it correctly. What happens next with your wts
> > queue in the case of timeout?
> >
> OK, what about the following quick and obvious patch?
>
> void win_cond_var::wait(long timeout)
> {
> HANDLE ev=evc.getEvent();
> wts.push_back(ev);
> m.unlock();
>
> DWORD rcd=WaitForSingleObject(ev, (timeout==infinite) ? timeout : INFINITE);
> assert(rcd==WAIT_OBJECT_0 || rcd==WAIT_TIMEOUT);
>
> m.lock();
>
> if (rcd==WAIT_TIMEOUT) {
> vec_type::iterator it=find(wts.begin(), wts.end(), ev);
> if (it==wts.end()) {
> BOOL rc=ResetEvent(ev);
> assert(rc!=0);
> }
> else wts.erase(it);
> }
>
> evc.returnEvent(ev);
> }

Depends on whether your feature list includes POSIX like destruction
safety.

regards,
alexander.

[Chris Thomasson]

"Alexander Terekhov" <tere...@web.de> wrote in message
news:4586FFC1...@web.de...

> Depends on whether your feature list includes POSIX like destruction
> safety.

Yup...

http://groups.google.com/group/comp.programming.threads/browse_frm/th...

http://groups.google.com/group/comp.programming.threads/browse_frm/th...

Most implementations' simply do not take this stuff into account...

;^(...

[Sergey P. Derevyago]

Alexander Terekhov wrote:
> Depends on whether your feature list includes POSIX like destruction
> safety.
>

Could you elaborate?

[Alexander Terekhov]

"Sergey P. Derevyago" wrote:
>
> Alexander Terekhov wrote:
> > Depends on whether your feature list includes POSIX like destruction
> > safety.
> >
> Could you elaborate?

http://opengroup.org/onlinepubs/009695399/functions/pthread_cond_destroy.html

See EXAMPLES section.

regards,
alexander.

[Sergey P. Derevyago]

Alexander Terekhov wrote:
> http://opengroup.org/onlinepubs/009695399/functions/pthread_cond_destroy.html
> See EXAMPLES section.
>

OK, got it. The "POSIX like destruction safety" is irrelevant in this case.

Just look at class win_cond_var from C++ POV: there is no
win_cond_var::cond_destroy() member. So there is no any RC issue here:
~win_cond_var() dtor must not get called while the win_cond_var object is
still being used in other threads. And an unfinished win_cond_var::wait() call
means that the object is still in use.

[Alexander Terekhov]

"Sergey P. Derevyago" wrote:
>
> Alexander Terekhov wrote:
> > http://opengroup.org/onlinepubs/009695399/functions/pthread_cond_destroy.html
> > See EXAMPLES section.
> >
> OK, got it. The "POSIX like destruction safety" is irrelevant in this case.
>
> Just look at class win_cond_var from C++ POV: there is no
> win_cond_var::cond_destroy() member. So there is no any RC issue here:
> ~win_cond_var() dtor must not get called while the win_cond_var object is
> still being used in other threads. And an unfinished win_cond_var::wait() call
> means that the object is still in use.

Sez who? After all, it's no big deal to have a valid C++ program with
"delete this" in an "unfinished" call, no?

regards,
alexander.

[Sergey P. Derevyago]

Alexander Terekhov wrote:
> Sez who? After all, it's no big deal to have a valid C++ program with
> "delete this" in an "unfinished" call, no?
>

"Delete this" topic (of ST C++ world) is quite irrelevant in this context.

I feel I should provide some information to be understood. I'm writing a C++
tutorial on multithreading where I explain some fundamental properties of good
C++ MT design and show several basic patterns in action. It's supposed to
explain these issues just like present "Interfaces and Messages" tutorial[1]
explains fundamental C++ OO principles and patterns.
That's why I need some abstract condition variables with an acceptable Win32
implementation. One possible implementation is being discussed in this thread
right now. And it's not supposed that concurrent destruction of cond_var
objects is allowed. It's clearly a logic error in this context so the
application will just be aborted.

[1] http://ders.stml.net/cpp/intmsg/intmsg.html

[Phil Frisbie, Jr.]

Markus Elfring wrote:
>> So, I choose to create my own API that is 'in between' pthreads and
>> Windows threads for my own portable projects.
>
> Which are the relevant design decisions for your choice?

First, the API should require the minimal amount of code for Windows and
POSIX threads.

Second, I prefer the simplicity of Windows conditions, so I emulate them
on POSIX.

Third, I believe mutexes should NOT allow recursion, so the code for
both disallow recursion.

>> The API is closer to Windows than pthreads, but it is easy to use with
>> much less overhead than some other wrappers.
>
> Would you like to explain the specific differences?

In addition to what I said above, the mutex, thread, and thread local
storage APIs are most like POSIX, but the conditions and thread
priorities are most like Windows.

> I have got doubts about coding correctness if I see instructions like
> the following in your source file "htcondition.c":
> (void)pthread_mutex_lock((pthread_mutex_t *)&cv->mutex);
>
> Why do you (intentionally) ignore the return value from this function call?

That particular case is due to the fact that the mutex is hidden and
ignored in order to emulate Windows type conditions.

> Would you like to add any checking for error codes?

Not in that case, but I see others cases in my code that I am
correcting. It seems I have some hold-over code from when the API was
part of my networking library and used its own error code system.

> How do you think that an implementation with correct error handling
> would look like in your approach?

This is moot due to the reasons above. But for other cases you can see
my code when I release it.

> Which of the solutions from the description "Strategies for Implementing
> POSIX Condition Variables on Win32" by Douglas C. Schmidt and Irfan
> Pyarali did you try to implement?
> http://www.cs.wustl.edu/~schmidt/win32-cv-1.html

None! I do not emulate POSIX conditions, I emulate Windows conditions.

[Alexander Terekhov]

"Sergey P. Derevyago" wrote:
>
> Alexander Terekhov wrote:
> > Sez who? After all, it's no big deal to have a valid C++ program with
> > "delete this" in an "unfinished" call, no?
> >
> "Delete this" topic (of ST C++ world) is quite irrelevant in this context.
>
> I feel I should provide some information to be understood. I'm writing a C++
> tutorial on multithreading where I explain some fundamental properties of good
> C++ MT design and show several basic patterns in action. It's supposed to
> explain these issues just like present "Interfaces and Messages" tutorial[1]
> explains fundamental C++ OO principles and patterns.
> That's why I need some abstract condition variables with an acceptable Win32
> implementation. One possible implementation is being discussed in this thread
> right now. And it's not supposed that concurrent destruction of cond_var
> objects is allowed. It's clearly a logic error in this context so the
> application will just be aborted.

POSIX safety for sync objects destruction is no more "concurrent
destruction" than standard C++ "delete this". It's your logic error
if you don't get it.

regards,
alexander.

[Joe Seigh]

Posix condition variables are an exception to this convention as you
like to repeatedly point out every chance you get. Unless someone
is implementing Posix, there's no requirement for this behavior.

--
Joe Seigh

When you get lemons, you make lemonade.
When you get hardware, you make software.

[Marcin 'Qrczak' Kowalczyk]

"Phil Frisbie, Jr." <ph...@hawksoft.com> writes:

> Second, I prefer the simplicity of Windows conditions, so I emulate
> them on POSIX.

I'm not familiar with "Windows conditions", but the pthread-implemented
variant of the source code of your conditions doesn't make much sense
for me.

How would you use it to implement a queue, such that taking an element
from an empty queue waits until some other thread puts an element?
With pthreads it goes like this (pseudocode):

type queue {
mutex_t mutex;
node_t first;
node_t last;
condition_t not_empty;
}

put(queue, elem) {
mutex_lock(queue.mutex);
raw_put(queue, elem);
cond_signal(queue.not_empty);
mutex_unlock(queue.mutex);
}

take(queue) {
mutex_lock(queue.mutex);
while (queue.first == null)
cond_wait(queue.not_empty, queue.mutex);
elem = raw_take(queue);
mutex_unlock(queue.mutex);
return elem;
}

--
__("< Marcin Kowalczyk
\__/ qrc...@knm.org.pl
^^ http://qrnik.knm.org.pl/~qrczak/

[Markus Elfring]

> Second, I prefer the simplicity of Windows conditions, so I emulate them
> on POSIX.

Which details seem to be simpler in this case?

> Not in that case, but I see others cases in my code that I am
> correcting. It seems I have some hold-over code from when the API was
> part of my networking library and used its own error code system.

I imagine that you have got two options.
1. If you would like to adhere to the programming contract that is defined by
the standard API, the checking for error codes will be required for true
thread-safety.
http://opengroup.org/onlinepubs/009695399/functions/pthread_mutex_lock.html

2. Your locking function might implement a different approach because of your
design decisions. => It should be renamed and should get the return type "void",
shouldn't it?

> This is moot due to the reasons above. But for other cases you can see
> my code when I release it.

How much do you care for coding correctness?
Which time frame have you got in mind for your updated library?

> None! I do not emulate POSIX conditions, I emulate Windows conditions.

How do you distinguish your kind of condition object between both styles?
What do you really want to achieve?

Regards,
Markus

[Alexander Terekhov]

Joe Seigh wrote:
[...]

> Posix condition variables are an exception to this convention as you
> like to repeatedly point out every chance you get.

What convention and what exception are you talking about? How would
you solve the problem of CV reuse without that "exception"? Code
example,
please.

regards,
alexander.

[Joe Seigh]

Same as you solve the problem of reuse of anything.

[Alexander Terekhov]

Joe Seigh wrote:
[...]

> Same as you solve the problem of reuse of anything.

Well, not sure that I follow, but whatever, reuse means that dtor's
invocation in question is supported. Care to post a fix to ders' CV?

regards,
alexander.

[Joe Seigh]

We're talking about whether condition variable implementation have to
have Posix condvar semantics even if they're not Posix condition
variables. Correct?

[Alexander Terekhov]

Joe Seigh wrote:
[...]

> We're talking about whether condition variable implementation have to
> have Posix condvar semantics even if they're not Posix condition
> variables. Correct?

We are talking about EXAMPLES section of

http://opengroup.org/onlinepubs/009695399/functions/pthread_cond_destroy.html

regards,
alexander.

[Joe Seigh]

That relies on semantics that are unique to Posix condition variables. It's
not intuitive behavior. If they didn't mention that in the documentation, it
probably wouldn't occur to most people to do anything like that.

Even the bit with destroying a Posix mutex that has been unlocked is sort of
Posix specific. You don't have to have mutexes that protect themselves as
a resource.

[Alexander Terekhov]

Joe Seigh wrote:
[...]

> > http://opengroup.org/onlinepubs/009695399/functions/pthread_cond_destroy.html
> >
>
> That relies on semantics that are unique to Posix condition variables. It's

> not intuitive behavior. ...

I disagree. It is intuitive behavior to me.

regards,
alexander.

[Joe Seigh]

It doesn't follow that it's intuitive for everyone else. How common
is that particular usage, destroying a condvar like that, in real
life? A more intuitive solution is reference or usage counts, or
some other from of PDR which works with almost anything.

[Alexander Terekhov]

Joe Seigh wrote:
[...]

> It doesn't follow that it's intuitive for everyone else. How common
> is that particular usage, destroying a condvar like that, in real
> life?

Quite common, in my life.

> A more intuitive solution is reference or usage counts, or
> some other from of PDR which works with almost anything.

That's your life. ;-)

regards,
alexander.

[Phil Frisbie, Jr.]

Marcin 'Qrczak' Kowalczyk wrote:
> "Phil Frisbie, Jr." <ph...@hawksoft.com> writes:
>
>
>>Second, I prefer the simplicity of Windows conditions, so I emulate
>>them on POSIX.
>
> I'm not familiar with "Windows conditions", but the pthread-implemented
> variant of the source code of your conditions doesn't make much sense
> for me.

I am sure it does not make sense. My primary target for this code is
Windows, with POSIX (Linux, MacOS, etc.) second. I started out using
POSIX all the way with the pthread for WIN32 on Windows, but the
overhead of full POSIX compliance is very high for conditions. Windows
threads are just too much different than POSIX for simple wrappers to
work well.

So, for a simple explanation, Windows conditions are not tied to, or do
they require, a mutex. It is this tied mutex in POSIX conditions that is
hard to code properly on Windows. That is why I chose to code for
Windows like conditions. I felt that made sense, because what if you
have some high performance code and are using a lock free queue? On
Windows you just signal the condition and no need to worry about locking
a mutex that is not needed.

Anyway, when I am working on projects that are for POSIX first and
Windows second I directly use POSIX threads.

> How would you use it to implement a queue, such that taking an element
> from an empty queue waits until some other thread puts an element?
> With pthreads it goes like this (pseudocode):

You simply move the mutex lock/unlock as appropriate:

> type queue {
> mutex_t mutex;
> node_t first;
> node_t last;
> condition_t not_empty;
> }
>
> put(queue, elem) {
> mutex_lock(queue.mutex);
> raw_put(queue, elem);

mutex_unlock(queue.mutex);
> cond_signal(queue.not_empty);
> }
>
> take(queue) {

> while (queue.first == null)
> cond_wait(queue.not_empty, queue.mutex);

mutex_lock(queue.mutex);

> elem = raw_take(queue);
> mutex_unlock(queue.mutex);
> return elem;
> }

Disclaimer: HawkThreads started out as an integral part of HawkNL
(Originally OpenNL). I had so many requests by HawkNL users to export
the thread API that I did. I later rewrote it as a stand alone library.
It is a work in progress. It was NOT designed to replace POSIX threads,
but as a porting tool for Windows apps that may need to be compiled on
POSIX systems.

[Phil Frisbie, Jr.]

Markus Elfring wrote:

>> Second, I prefer the simplicity of Windows conditions, so I emulate
>> them on POSIX.
>
> Which details seem to be simpler in this case?

If you are using a lock free messaging or do not NEED a mutex then you
do not need to create one.

>> Not in that case, but I see others cases in my code that I am
>> correcting. It seems I have some hold-over code from when the API was
>> part of my networking library and used its own error code system.
>
>
> I imagine that you have got two options.
> 1. If you would like to adhere to the programming contract that is
> defined by the standard API, the checking for error codes will be
> required for true thread-safety.
> http://opengroup.org/onlinepubs/009695399/functions/pthread_mutex_lock.html

Good point. After rereading the definitions for pthread_cond_* I see
that even though I am hiding the mutex that failure to lock it could
result in undefined behavior.

> 2. Your locking function might implement a different approach because of
> your design decisions. => It should be renamed and should get the return
> type "void", shouldn't it?

No, it will be fixed properly.

>> This is moot due to the reasons above. But for other cases you can see
>> my code when I release it.
>
>
> How much do you care for coding correctness?

As I said above, I do care. I cannot remember the coding decisions I
made three+ years ago that got us into this conversation, but I welcome
the input and it will be fixed.

> Which time frame have you got in mind for your updated library?

In a few weeks. The Christmas and New Years time is busy for me and my
family.

>> None! I do not emulate POSIX conditions, I emulate Windows conditions.
>
> How do you distinguish your kind of condition object between both styles?

I do not understand the question. If you look at the code you will see
that my conditions are a simple wrapper around the Windows API, so they
are used the same way.

> What do you really want to achieve?

This is cut and past form my reply to Marcin:

... My primary target for this code is Windows, with POSIX (Linux,

MacOS, etc.) second. I started out using POSIX all the way with the
pthread for WIN32 on Windows, but the overhead of full POSIX compliance
is very high for conditions. Windows threads are just too much different
than POSIX for simple wrappers to work well.

So, for a simple explanation, Windows conditions are not tied to, or do
they require, a mutex. It is this tied mutex in POSIX conditions that is
hard to code properly on Windows. That is why I chose to code for
Windows like conditions. I felt that made sense, because what if you
have some high performance code and are using a lock free queue? On
Windows you just signal the condition and no need to worry about locking
a mutex that is not needed.

Anyway, when I am working on projects that are for POSIX first and
Windows second I directly use POSIX threads.

--

[Chris Thomasson]

"Alexander Terekhov" <tere...@web.de> wrote in message

news:4589E515...@web.de...

Well, PDR simply works. It solves the race-conditions that come along with
adhering to POSIX's rules:

[Chris Thomasson]

ACK! forgot the link... Sorry

"Alexander Terekhov" <tere...@web.de> wrote in message
news:4589E515...@web.de...
>

Well, PDR simply works. It solves the all of the various race-condition(s)
that "come along with" a strict adherence to POSIX's rules:

http://groups.google.com/group/comp.programming.threads/browse_frm/thread/8b855eab7dc55ad9

http://groups.google.com/group/comp.programming.threads/browse_frm/thread/38d68d1289352a53

http://groups.google.com/group/comp.programming.threads/msg/667fa209809b41db

What say you? Agreed?

;^)

[Marcin 'Qrczak' Kowalczyk]

"Phil Frisbie, Jr." <ph...@hawksoft.com> writes:

> You simply move the mutex lock/unlock as appropriate:

This doesn't work.

>> take(queue) {
>> while (queue.first == null)

If another thread inserts an element to an empty queue at this point,
this thread will be waiting forever (nobody will wake up the wait).

>> cond_wait(queue.not_empty, queue.mutex);

If another thread makes the queue empty at this point, taking an
element below will fail.

If pthread_cond_wait returns because of a spurious wakeup, taking an
element below will fail

> mutex_lock(queue.mutex);
>> elem = raw_take(queue);
>> mutex_unlock(queue.mutex);
>> return elem;

I wonder whether the Windows part has the same problems.

The design of POSIX condition variables has a reason.

[Marcin 'Qrczak' Kowalczyk]

"Phil Frisbie, Jr." <ph...@hawksoft.com> writes:

> You simply move the mutex lock/unlock as appropriate:

This doesn't work.

>> take(queue) {
>> while (queue.first == null)

If another thread inserts an element to an empty queue at this point,

this thread will be waiting forever (nobody will wake up the wait).

>> cond_wait(queue.not_empty, queue.mutex);

If another thread makes the queue empty at this point, taking an
element below will fail.

> mutex_lock(queue.mutex);

>> elem = raw_take(queue);
>> mutex_unlock(queue.mutex);
>> return elem;

I wonder whether the Windows part has the same problems.

The design of POSIX condition variables has a reason.

--

[Joe Seigh]

Phil Frisbie, Jr. wrote:
>
> I am sure it does not make sense. My primary target for this code is
> Windows, with POSIX (Linux, MacOS, etc.) second. I started out using
> POSIX all the way with the pthread for WIN32 on Windows, but the
> overhead of full POSIX compliance is very high for conditions. Windows
> threads are just too much different than POSIX for simple wrappers to
> work well.
>
> So, for a simple explanation, Windows conditions are not tied to, or do
> they require, a mutex. It is this tied mutex in POSIX conditions that is
> hard to code properly on Windows. That is why I chose to code for
> Windows like conditions. I felt that made sense, because what if you
> have some high performance code and are using a lock free queue? On
> Windows you just signal the condition and no need to worry about locking
> a mutex that is not needed.
>

Events are not strictly equivalent to condition variables so you can't
use the the same way. If you had eventcounts the usage patterns would
be more similar but you don't.

http://groups.google.com/group/comp.programming.threads/msg/bdccc96487ee6cba?hl=en&

[Sergey P. Derevyago]

Alexander Terekhov wrote:
> Care to post a fix to ders' CV?
>

AFAICS you propose to improve class XXX to make it ready for YYY usage. But:
1. Class XXX will get slower for the common set of operations.
2. YYY usage isn't required by XXX class design and therefore will never be
used.

So what's the point?

[Markus Elfring]

> If you are using a lock free messaging or do not NEED a mutex then you
> do not need to create one.

I do not recognise the relationship that you have got in mind here.

> No, it will be fixed properly.

It is likely that you will need to delegate the error handling to trigger an
abnormal program termination, isn't it?
http://opengroup.org/onlinepubs/009695399/functions/abort.html

> I do not understand the question. If you look at the code you will see
> that my conditions are a simple wrapper around the Windows API, so they
> are used the same way.

Are you sure that your wrapping approach is correct for condition variables?

Regards,
Markus

[Markus Elfring]

> I started out using POSIX all the way with the pthread for WIN32
> on Windows, but the overhead of full POSIX compliance is very high
> for conditions.

May we expect standard conpliance from your variants of Pthread functions?
Would you like to try an interesting programming competition with Alexander
Terekhov and Louis Thomas to lower the unpleasant overhead?
Is the performance of their library implementation good enough today so that its
reuse is better than the effort to develop an alternative?

> Windows threads are just too much different than POSIX for simple wrappers
> to work well.

The wrapper should be correctly implemented. Which approach would fit to your
expectation for simplicity if all relevant rules will be considered?

> So, for a simple explanation, Windows conditions are not tied to, or do
> they require, a mutex. It is this tied mutex in POSIX conditions that is
> hard to code properly on Windows. That is why I chose to code for
> Windows like conditions.

Windows versions before Vista did not offer a condition variable API.

> I felt that made sense, because what if you have some high performance code
> and are using a lock free queue?

Where is lock-free programming involved in the discussed context?

> On Windows you just signal the condition and no need to worry about locking
> a mutex that is not needed.

I would prefer a clarification here to avoid misinterpretation.

> It is a work in progress. It was NOT designed to replace POSIX threads,
> but as a porting tool for Windows apps that may need to be compiled on
> POSIX systems.

If own Pthread functions are used, they might be seen as an useable replacement
for other purposes.

Regards,
Markus

[Chris Thomasson]

"Sergey P. Derevyago" <non-ex...@iobox.com> wrote in message
news:458668F5...@iobox.com...
> Chris Thomasson wrote:
>> > I skimmed over this topic and it seems like there were some problems
>> > with
>> > your approach.
>>
>> Like what?
>>
> I only skimmed over this thread, so it's just an opinion. Quick and dirty.

Well, the posted eventcount algorithm actually works... BTW, its essentially
the exact same algorithm as my older one which should be easier to read:

http://groups.google.com/group/comp.programming.threads/browse_frm/thread/aa8c62ad06dbb380

The algorithm works... It also boasts atomic operation free fast-paths for
signals/broadcasts.

This beats current NPTL sync primitives... You can use the algorithm to wrap
a NPTL condition variable with an eventcount which in turn only hits the NTL
condvar on the slow-paths. Current NPTL sync primitive implementation is
suboptimal. So, for time being, my algorithm consistently outperforms NPTL
by only calling into it on the slow-paths... Oh well...

[Chris Thomasson]

"Alexander Terekhov" <tere...@web.de> wrote in message
news:4589E515...@web.de...
>

Here ya go Alex!

http://appcore.home.comcast.net/vzoom/pthread/

Nice!

[Chris Thomasson]

"Chris Thomasson" <cri...@comcast.net> wrote in message
news:UvednYavJuK4GgDY...@comcast.com...

Should I release the initial experimental code for this library?