Hello.

Is this implementation of thread-safe queue correct? Does it have any
problem (correctness and performance)?

Note: hEvent is auto release event.

Push:
EnterCriticalSection(&cs);
queue.push(item);
SetEvent(hEvent);
LeaveCriticalSection(&cs);

Pop:
EnterCriticalSection(&cs);
WaitForSingleObject(hEvent, INFINITE);
item = queue.pop();
if (!queue.isEmpty())
    SetEvent(hEvent);
LeaveCriticalSection(&cs);
return item;

Thank you.
Roman Perepelitsa.

Roman.Perepelitsa@gmail.com schrieb:
> Is this implementation of thread-safe queue correct? Does it have any
> problem (correctness and performance)?

> EnterCriticalSection(&cs);
> WaitForSingleObject(hEvent, INFINITE);

It's obviously wrong. This will cause a deadlock.


Marcel

On May 4, 5:52 pm, Marcel M=FCller <news.5.ma...@spamgourmet.com> wrote:
> Roman.Perepeli...@gmail.com schrieb:
>
> > Is this implementation of thread-safe queue correct? Does it have any
> > problem (correctness and performance)?
> > EnterCriticalSection(&cs);
> > WaitForSingleObject(hEvent, INFINITE);
>
> It's obviously wrong. This will cause a deadlock.
>
> Marcel

My bad. Should be:

Pop:
WaitForSingleObject(hEvent, INFINITE);
EnterCriticalSection(&cs);
item =3D queue.pop();
if (!queue.isEmpty())
    SetEvent(hEvent);
LeaveCriticalSection(&cs);
return item;

On May 4, 7:51 am, Roman Perepelitsa <Roman.Perepeli...@gmail.com>
wrote:

> My bad. Should be:
>
> Pop:
> WaitForSingleObject(hEvent, INFINITE);
> EnterCriticalSection(&cs);
> item = queue.pop();
> if (!queue.isEmpty())
>     SetEvent(hEvent);
> LeaveCriticalSection(&cs);
> return item;

Suppose a thread calls 'WaitForSingleObject', finishes waiting, but
then before it can call 'pop', another thread grabs the entry from the
queue. This could result in your 'pop' method returning NULL.

It's also very inefficient. Here are a few things to think about:

1) Why wait for the event if the queue isn't empty? The wait is pure
waste.

2) Why set the event every time even if it was already set? The set is
pure waste.

Something to remember: EnterCriticalSection and LeaveCriticalSection
are fairly cheap. SetEvent and WaitForSingleObject are fairly
expensive.

DS

Roman.Perepelitsa@gmail.com wrote:
> Hello.
> 
> Is this implementation of thread-safe queue correct? Does it have any
> problem (correctness and performance)?
> 
[...]

By way of a discussion on how to use win32 events.
http://groups.google.com/group/comp.programming.threads/msg/bdccc96487ee6cba?hl=en&


-- 
Joe Seigh

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

Hi,

> Suppose a thread calls 'WaitForSingleObject', finishes waiting, but
> then before it can call 'pop', another thread grabs the entry from the
> queue. This could result in your 'pop' method returning NULL.

It's a of the Windows autoreset event that exactly one thread awakes on 
one SetEvent. Unfortunately it has no set count to let more than one 
thread pass following calls to WaitForSingleObject. I think the 
implementation correctly compensates for this.


> It's also very inefficient. Here are a few things to think about:
> 
> 1) Why wait for the event if the queue isn't empty? The wait is pure
> waste.

See above.

> 2) Why set the event every time even if it was already set? The set is
> pure waste.

That's true. The SetEvent is not required unless the queue was empty 
before queue.push.

> Something to remember: EnterCriticalSection and LeaveCriticalSection
> are fairly cheap. SetEvent and WaitForSingleObject are fairly
> expensive.

Of course, the performance could be better with a double check 
implementation of pop.


Marcel

Thank you everyone for your answers. Finally I came up with this
implementation:

Push:
EnterCriticalSection(&cs);
bool wasEmpty = queue.isEmpty();
queue.push(item);
if (wasEmpty)
    SetEvent(hEvent);
LeaveCriticalSection(&cs);

Pop:
EnterCriticalSection(&cs);
while (queue.isEmpty())
{
    LeaveCriticalSection(&cs);
    WaitForSingleObject(hEvent, INFINITE);
    EnterCriticalSection(&cs);
}
item = queue.pop();
if (!queue.isEmpty())
    SetEvent(hEvent);
LeaveCriticalSection(&cs);
return item;

As far as I understand it's both correct and efficient in case of any
number of consumer and producer threads. I see only one possible
problem: This implementation is not "fair" (threads waiting for queue
to become nonempty can be awaken in any order), but I don't care about
it in my application.

Roman Perepelitsa.

Roman Perepelitsa wrote:
> Thank you everyone for your answers. Finally I came up with this
> implementation:
> 
> Push:
> EnterCriticalSection(&cs);
> bool wasEmpty = queue.isEmpty();
> queue.push(item);
> if (wasEmpty)
>     SetEvent(hEvent);
> LeaveCriticalSection(&cs);
> 
> Pop:
> EnterCriticalSection(&cs);
> while (queue.isEmpty())
> {
>     LeaveCriticalSection(&cs);
>     WaitForSingleObject(hEvent, INFINITE);
>     EnterCriticalSection(&cs);
> }
> item = queue.pop();
> if (!queue.isEmpty())
>     SetEvent(hEvent);

You want
   if (queue.isEmpty())
     ResetEvent(hEvent);



> LeaveCriticalSection(&cs);
> return item;
> 
> As far as I understand it's both correct and efficient in case of any
> number of consumer and producer threads. I see only one possible
> problem: This implementation is not "fair" (threads waiting for queue
> to become nonempty can be awaken in any order), but I don't care about
> it in my application.
> 
> Roman Perepelitsa.
> 

You should look at semaphore based solutions also.  The logic is even simpler.
Semaphore is initialized to number of items on queue, zero for new empty queue.

pop:
   WaitForSingleObject(hSemaphore);
   EnterCriticalSection(&cs);
   item =  queue.pop();
   LeaveCriticalSection(&cs);
   return item;

push:
   EnterCriticalSection(&cs);
   queue.push(item);
   LeaveCriticalSection(&cs);
   ReleaseSemaphore(hSemaphore, 1, null);



-- 
Joe Seigh

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

On May 7, 1:14 am, Marcel M=FCller <news.5.ma...@spamgourmet.com> wrote:

> That's true. The SetEvent is not required unless the queue was empty
> before queue.push.

Well, maybe not, depending on your implementation.

Suppose two threads are both blocked waiting for a message on the
queue. If two other threads each put a message on the queue, it's
important that both waiting threads be woken, even though one of the
two threads putting messages on the queue will not be putting a
message on an empty queue.

I have seen real-world implementations that had this problem. You can
wind up with the entire pool of threads save one blocked on rapidly-
filling queue, and only one thread is running because only one message
was put on an empty queue. Sadly, no new threads will be woken until
the one thread that is running finishes what it's doing -- which could
be a l-o-n-g time.

The sequence goes like this:

1) The queue is empty.

2) The whole pool of service threads is blocked on the queue.

3) Two threads put messages on the queue at roughly the same time (and
before any woken threads can run), only one puts a message on an empty
queue. Only one wakeup is commanded. The queue has two messages on it.

4) One thread is woken, pulls the first message, which is for a long
and complex task. The queue is still not empty, having one message
left.

5) No new threads will be woken because the queue is not empty and
will not empty because all threads from the pool (save the busy one)
are blocked. The whole pool and the queue are stalled until the only
long, complex task can be finished. (And if that task relies on
subtasks that involve this queue, you are permanently deadlocked. Yes,
I have actually seen this happen in real-world programs!)

There are several ways to fix this. One is to wake all threads instead
of one. Another is to wake a thread any time you put a message on a
queue. Yet another is to wake a thread if the count of waiting threads
is non-zero. And still another way is to wake a thread if you put a
message on a queue with fewer messages than servicing threads.

There are also queue architectures that are invulnerable to this race
condition for structural reasons or because they are built on top of
primitives that already work around it.

DS

David Schwartz schrieb:
>> That's true. The SetEvent is not required unless the queue was empty
>> before queue.push.
> 
> Well, maybe not, depending on your implementation.
> 
> Suppose two threads are both blocked waiting for a message on the
> queue. If two other threads each put a message on the queue, it's
> important that both waiting threads be woken, even though one of the
> two threads putting messages on the queue will not be putting a
> message on an empty queue.

It will not take longer to awake the second thread, since every thread 
reading a message posts the event again unless the queue is empty. And 
this is done /before/ the processing of the message.

> There are several ways to fix this. One is to wake all threads instead
> of one. Another is to wake a thread any time you put a message on a
> queue.

The latter will not be sufficient with Win32 events, since they have no 
post count.

Posting the event if the queue was empty before push and if it is not 
empty after pop requires exactly one call to SetEvent per queue item.
Doing a double check at pop can reduce this further.


Marcel

> You want
>    if (queue.isEmpty())
>      ResetEvent(hEvent);

I use auto-reset events. I don't think I need to call ResetEvent at
all.

Roman Perepelitsa.

Roman Perepelitsa wrote:
>>You want
>>   if (queue.isEmpty())
>>     ResetEvent(hEvent);
> 
> 
> I use auto-reset events. I don't think I need to call ResetEvent at
> all.
> 



> Pop:
> EnterCriticalSection(&cs);
> while (queue.isEmpty())
> {
>     LeaveCriticalSection(&cs);

You have a race condition here.  The Event can
be auto reset before you even get a chance to
wait on it.


>     WaitForSingleObject(hEvent, INFINITE);
>     EnterCriticalSection(&cs);
> }
> item = queue.pop();
> if (!queue.isEmpty())
>     SetEvent(hEvent);
> LeaveCriticalSection(&cs);
> return item;

You can disagree but you need to prove that within that
window another thread cannot queue something on the
queue and auto reset the event before the about to wait
thread gets a chance to be Event's waitset.

-- 
Joe Seigh

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

> > Pop:
> > EnterCriticalSection(&cs);
> > while (queue.isEmpty())
> > {
> >     LeaveCriticalSection(&cs);
>
> You have a race condition here.  The Event can
> be auto reset before you even get a chance to
> wait on it.
>
> >     WaitForSingleObject(hEvent, INFINITE);
> >     EnterCriticalSection(&cs);
> > }
> > item = queue.pop();
> > if (!queue.isEmpty())
> >     SetEvent(hEvent);
> > LeaveCriticalSection(&cs);
> > return item;
>
> You can disagree but you need to prove that within that
> window another thread cannot queue something on the
> queue and auto reset the event before the about to wait
> thread gets a chance to be Event's waitset.

Auto-reset events work another way. If you signal event and no threads
wait on event then it won't reset. It will be kept in signalling
state. Event resets automatically after some thread succesfully waits
for this event.

What you are saying is correct for PulseEvent. But I use SetEvent
here.

Roman Perepelitsa.

"Roman Perepelitsa" <Roman.Perepelitsa@gmail.com> wrote in message 
news:1178871034.835801.98930@u30g2000hsc.googlegroups.com...
>> > Pop:
>> > EnterCriticalSection(&cs);
>> > while (queue.isEmpty())
>> > {
>> >     LeaveCriticalSection(&cs);
>>
>> You have a race condition here.

[...]


> Auto-reset events work another way. If you signal event and no threads
> wait on event then it won't reset. It will be kept in signalling
> state. Event resets automatically after some thread succesfully waits
> for this event.

Your waiters seem to have to go through an "undefined period" so to speak... 
They take no reference count, no eventcount, no specific waitset 
"identification card", no "nothing in particular", before they unlock 
themselves. If your thread can issue a signal that is suppose to make some 
other thread set some predicate that must be true in order for the issuer 
thread to make any sort of forward progresss well, you should learn about 
ping-pong signaling and the ability to use a single condition variable and 
the broadcast function to handle multiple predicate combinations. Joe knows 
99.9876% of the potential problems that may or may not be attributed to this 
sort of usage pattern..


..... And, well, what if the issuer (e.g., thread) makes the signal, and 
immediately and subsequently waits on the waitset to be an explicit state 
which means that some other group of thread(s) modifies the predicate in a 
specific and explicit fashion.?... POSIX condition variable rules clearly 
and explicitly state that a signal/broadcast MUST apply for the CURRENT 
waitset... PLEASE NOTE!, this does not include any soft of  SUBSEQUENT 
waitset indeed!! In order words a thread A which signals to a waiting thread 
pool of Threads B && c

:^)

Roman Perepelitsa wrote:
>>>Pop:
>>>EnterCriticalSection(&cs);
>>>while (queue.isEmpty())
>>>{
>>>    LeaveCriticalSection(&cs);
>>
>>You have a race condition here.  The Event can
>>be auto reset before you even get a chance to
>>wait on it.
>>
>>
>>>    WaitForSingleObject(hEvent, INFINITE);
>>>    EnterCriticalSection(&cs);
>>>}
>>>item = queue.pop();
>>>if (!queue.isEmpty())
>>>    SetEvent(hEvent);
>>>LeaveCriticalSection(&cs);
>>>return item;
>>
>>You can disagree but you need to prove that within that
>>window another thread cannot queue something on the
>>queue and auto reset the event before the about to wait
>>thread gets a chance to be Event's waitset.
> 
> 
> Auto-reset events work another way. If you signal event and no threads
> wait on event then it won't reset. It will be kept in signalling
> state. Event resets automatically after some thread succesfully waits
> for this event.
> 
> What you are saying is correct for PulseEvent. But I use SetEvent
> here.
> 

You still have a race condition when there are mulitple threads
about to wait.  Only one will get signaled.



-- 
Joe Seigh

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

[...]

> .... And, well, what if the issuer (e.g., thread) makes the signal, and 
> immediately and subsequently waits on the waitset to be an explicit state 
> which means that some other group of thread(s) modifies the predicate in a 
> specific and explicit fashion.?... POSIX condition variable rules clearly 
> and explicitly state that a signal/broadcast MUST apply for the CURRENT 
> waitset... PLEASE NOTE!, this does not include any soft of  SUBSEQUENT
                                                                             
             ^^^^^^^^^^^^^

Not 'soft'!

I mean 'sort'!

:^0

> You still have a race condition when there are mulitple threads
> about to wait.  Only one will get signaled.

Notice this code:

item = queue.pop();
if (!queue.isEmpty())
    SetEvent(hEvent);
LeaveCriticalSection(&cs);

The first thread who awakes signals to other threads if there are more
elements in queue. No race condition.

Roman Perepelitsa.

On 11 ���, 12:50, "Chris Thomasson" <cris...@comcast.net> wrote:
> "Roman Perepelitsa" <Roman.Perepeli...@gmail.com> wrote in message
>
> news:1178871034.835801.98930@u30g2000hsc.googlegroups.com...
>
> >> > Pop:
> >> > EnterCriticalSection(&cs);
> >> > while (queue.isEmpty())
> >> > {
> >> >     LeaveCriticalSection(&cs);
>
> >> You have a race condition here.
>
> [...]
>
> > Auto-reset events work another way. If you signal event and no threads
> > wait on event then it won't reset. It will be kept in signalling
> > state. Event resets automatically after some thread succesfully waits
> > for this event.
>
> Your waiters seem to have to go through an "undefined period" so to speak...
> They take no reference count, no eventcount, no specific waitset
> "identification card", no "nothing in particular", before they unlock
> themselves. If your thread can issue a signal that is suppose to make some
> other thread set some predicate that must be true in order for the issuer
> thread to make any sort of forward progresss well, you should learn about
> ping-pong signaling and the ability to use a single condition variable and
> the broadcast function to handle multiple predicate combinations. Joe knows
> 99.9876% of the potential problems that may or may not be attributed to this
> sort of usage pattern..

I didn't understand your answer? Do you think my implementation is
incorrect? In which case?

> .... And, well, what if the issuer (e.g., thread) makes the signal, and
> immediately and subsequently waits on the waitset to be an explicit state
> which means that some other group of thread(s) modifies the predicate in a
> specific and explicit fashion.?... POSIX condition variable rules clearly
> and explicitly state that a signal/broadcast MUST apply for the CURRENT
> waitset... PLEASE NOTE!, this does not include any soft of  SUBSEQUENT
> waitset indeed!! In order words a thread A which signals to a waiting thread
> pool of Threads B && c

This use case is too generic for me to understand it. Could you
provide simple scenario for my queue in which it fails?

Roman Perepelitsa.

On May 11, 11:45 pm, Roman Perepelitsa <Roman.Perepeli...@gmail.com>
wrote:

> Notice this code:
>
> item = queue.pop();
> if (!queue.isEmpty())
>     SetEvent(hEvent);
> LeaveCriticalSection(&cs);
>
> The first thread who awakes signals to other threads if there are more
> elements in queue. No race condition.

That solves the problem, but is horrendously inefficient. You are
using one of the most expensive operations (SetEvent) in a situation
where it does nothing when you're under load. (Or, to put it another
way, you are writing code that becomes less efficient when under load,
which is very bad.)

DS