Condvar Algorithm 6b by Terekhov & Thomas
Michael B Allen
I need a simple condition variable implementation and the below code
which has been discussed here before looks like what I want. However
I'm having trouble understanding some of the details and I was hoping
this list could help me.
gate - semaphore
queue - semaphore
counters - CS or mutex
ex_mutex - CS or mutex
nWaiters - int
nSignaled - int
nGone - int
wait(timeout) {
sem_wait gate // pass gate
nWaiters++
sem_post gate
unlock ex_mutex
_bTimedOut=sem_wait(queue, timeout)
lock counters
if (_bTimedOut ?? (0==nSignaled || 0!=nWaiters-nGone)) {
nGone++ // retract our waiter status (ignore overflow)
} else {
if (_bTimedOut) {
sem_wait queue // better now than spurious later
_bTimedout=false
}
nSignaled--
if (0==nSignaled) {
sem_post gate // open gate
}
}
unlock counters
lock ex_mutex
return _bTimedOut?ETIMEDOUT:0
}
signal(bAll) {
_nSig=0
lock counters
// this is safe because nWaiting can only be decremented by a thread that
// owns counters and nGone can only be changed by a thread that owns counters.
if (nWaiting?nGone) {
if (0==nSignaled) {
sema_wait gate // close gate if not already closed
}
if (nGone?0) {
nWaiting-=nGone
nGone=0
}
_nSig=bAll?nWaiting:1
nSignaled+=_nSig
nWaiting-=_nSig
}
unlock counters
if (0!=_nSig) {
sema_post queue, _nSig
}
}
Regarding the line:
if (_bTimedOut ?? (0==nSignaled || 0!=nWaiters-nGone)) {
What is the "??" operator? In C this should this look like the following?
if (_bTimedOut && (0 == nSignaled || 0 != (nWaiters - nGone))) {
Similarly regarding:
if (nWaiting?nGone) {
if (nGone?0) {
What is the "?" operator mean? Are these charset bloopers?
Regarding the line:
sem_wait queue // better now than spurious later
I assume this call is guaranteed to return without waiting?
Regarding the comment under the counters lock, can I use a single
"counters" lock between all condition variables? I want to try to minimize
the number of semaphores needed for each condvar (from 3n to 2n+1).
In general, is anyone familar with this algorithm and is it still
considered to be correct? Is there an updated version?
Mike
Alexander Terekhov
Michael B Allen wrote:
[...]
> What is the "?" operator mean? Are these charset bloopers?
Yup.
http://google.com/groups?as_umsgid=3A9D1CA8...@web.de
>
> Regarding the line:
>
> sem_wait queue // better now than spurious later
>
> I assume this call is guaranteed to return without waiting?
Yes, if semaphore is not busted regarding timeouts. It can deadlock
otherwise. I've already mentioned in the other thread that pthread-win32
has to remove that logic because there was a deadlock on some version of
windows (meaning that it had busted semaphores regarding timeouts). So
you better stick to the same solution as pthread-win32.
regards,
alexander.
Michael B Allen
Alexander Terekhov <tere...@web.de> wrote:
>
> Michael B Allen wrote:
> [...]
> > What is the "?" operator mean? Are these charset bloopers?
>
> Yup.
>
> http://google.com/groups?as_umsgid=3A9D1CA8...@web.de
Yeah, I found and implemented your 6b.2 algorithm. It worked like a champ
in the steady state but for some reason when I shutdown my app it would
unconditionally deadlock with the "gate" closed. I ended up using the
"Generation Count Solution" algo from the Apache reference in the other
recent thread about this. That seems to be working fine so far so I
think I'll stick with it.
Thanks,
Mike
Chris Thomasson
"Michael B Allen" <mia...@ioplex.com> wrote in message
news:20080711221642....@ioplex.com...
> Hi,
>
> I need a simple condition variable implementation and the below code
> which has been discussed here before looks like what I want. However
> I'm having trouble understanding some of the details and I was hoping
> this list could help me.
> In general, is anyone familar with this algorithm and is it still
> considered to be correct? Is there an updated version?
There is an updated version; algorithm 8a: