Does the set operation on an Auto-Reset event make a waiter ready? (was: Producer at DPC,Consumer at

OSR_Community_User · December 16, 2010, 12:34pm

> -----Original Message-----

From: xxxxx@lists.osr.com [mailto:bounce-434607-
xxxxx@lists.osr.com] On Behalf Of Prokash Sinha
Sent: Thursday, December 16, 2010 9:06 AM
To: Windows System Software Devs Interest List
Subject: Re: [ntdev] Producer at DPC,Consumer at helper thread,puzzled

>
> What makes it different from Max’s approach is that there are no idle
invocations - if thread gets released it can be 100% sure that it will
find at least one item to process (although it may contend for a
spinlock). In Max’s implementation, N threads wake up and contend for a
spinlock…and N-1 of them may go back to sleep without having done
anything useful. This is particularly true if the load is low. This is
what I would call
> “thundering herd”. However, I don’t think this term applies to a
situation when few workers may have to contend for a spinlock once in a
while…

Yes, Max’s code has thundering herd problem

In your implementation, try to find the region of preemptions — There
are two I noticed.

I’ve 128 processor machine, with 128 Nic ports ( 64 cards ). Each
10Gbits… Observed capacity is around 7 to 8 Gbits/port. So 1GByte/s
per port. So roughly 128 GBytes/sec or actual payload.

Traffic is essentially random, I will take a burst that would occupy
128 processors at higher level than the worker threads.

Calculate the worst case, what is the maximum I can put in in a Work
item to indicate up.

The synchronized event would be hammered then there is a pause in the
traffic pattern, 128 worker threads will be scheduled back from
preemption. One will win the race and break out of wait. Start
processing - No one else will wake up…

Now essentially I’ve a one processor machine to serve traffic.

As far as I’ve been able to follow this thread, Anton believes that setting
an Auto-Reset event actually makes a thread ready as part of the Set()
operation, and Max and Pro believe it does not.

First, if that’s not really the difference of opinion, someone please set me
straight.
Second, if that really is the issue, could someone who *knows* please chime
in and confirm one or the other of the premises?

Once I figured out the difference of opinion, it became a useful discussion.
Took me a while to figure out who was saying what, though. And I’m not sure
I’ve got the differences really figured out.

Thanks,

Phil

Philip D. Barila (303) 776-1264

anton_bassov · December 16, 2010, 1:48pm

Phil,

The only thing I can tell you is that if Max and Prokash are correct, then the entire concept of synch event is fundamentally flawed exactly the same way the one of PulseEvent() API is - you may miss a call to SetEvent(), i.e. for example, 3 calls are made but only 2 of 5 waiting threads are released…

Anton Bassov

Ken_Johnson · December 16, 2010, 2:15pm

No, SynchronizationEvents are not flawed in the same way that PulseEvent is (although you can certainly misuse SynchronizationEvents and shoot yourself in the foot with them as a result of doing so – just as you could with nearly anything else).

PulseEvent is flawed because it provides no guarantee that anyone will ever be awoken (as a (or all) user mode thread(s) waiting on the event could be temporarily pulled out of a wait state to process an APC (or the like) at the moment when someone calls PulseEvent, and thus never receive the notification).

A SynchronizationEvent, once set, guarantees that it will not automagically reset until it has actually woken exactly one waiting thread. This contrasts with PulseEvent, which wakes zero or more threads and provides no guarantee of forward progress as threads may unpredictably fail to receive their notifications. (The design intention of PulseEvent, FWIW, was clearly to wake zero or more threads up, and not exactly one.)

Note that SynchronizationEvents aren’t ideal for every purpose – exactly one thread woken up means exactly one thread, for instance, so it is an inappropriate mechanism to use to wake N threads at once. This doesn’t mean the concept is flawed, just that it’s probably not the concept you’re looking for in such a case.

(Calling SetEvent multiple times in rapid succession on a SynchronizationEvent with intent to wake multiple waiter threads is misusing the SynchronizationEvent, to make that clear – the bug would be in the program that is trying to abuse the SynchronizationEvent to wake N threads in this way (which won’t work reliably). The bug would not be that SynchronizationEvents are fundamentally flawed, because they are designed to suit a different purpose.)

S

-----Original Message-----
From: xxxxx@lists.osr.com [mailto:xxxxx@lists.osr.com] On Behalf Of xxxxx@hotmail.com
Sent: Thursday, December 16, 2010 10:49 AM
To: Windows System Software Devs Interest List
Subject: RE:[ntdev] Does the set operation on an Auto-Reset event make a waiter ready? (was: Producer at DPC,Consumer at helper thread,puzzled)

Phil,

The only thing I can tell you is that if Max and Prokash are correct, then the entire concept of synch event is fundamentally flawed exactly the same way the one of PulseEvent() API is - you may miss a call to SetEvent(), i.e. for example, 3 calls are made but only 2 of 5 waiting threads are released…

Anton Bassov

NTDEV is sponsored by OSR

For our schedule of WDF, WDM, debugging and other seminars visit:
http://www.osr.com/seminars

To unsubscribe, visit the List Server section of OSR Online at http://www.osronline.com/page.cfm?name=ListServer

OSR_Community_User · December 16, 2010, 2:29pm

Per this specific fork:

KeSetEvent and companions satisfy as many waiting threads as possible before they return. So if there are N threads waiting on a synch event and (because there is a WFMO and maximization is the goal) that synch event being set will ready any of them, one and only one of them will be readied before it returns.

That said, I haven’t paid close attention to this dispute, so I’m not vouching for anything beyond that specific request.

Ken_Johnson · December 16, 2010, 2:52pm

To expand on these remarks –

The behavior of KeSetEvent depends on the flavor of event (NotificationEvent versus SynchronizationEvent).

Invoking KeSetEvent on a NotificationEvent will cause any number of threads that attempt to wait on it to continually be released from their waits until someone manually calls KeClearEvent/KeResetEvent on the event object. (Hence why these are called ‘manual reset events’ in Win32.)
Invoking KeSetEvent of a SynchronizationEvent sets up the event so that it will remain signaled until it has successfully woken exactly one thread from a wait state, at which point the event will automagically be reset (hence the name ‘auto reset event’ in Win32). An event is not a semaphore, so setting the event multiple times before it has awoken anyone will cause nothing special to happen – there is no ‘stacking up’ of KeSetEvent requests that will cause N threads to be awoken.

Now, it’s perfectly okay to set the same SynchronizationEvent multiple times before someone gets around to wait on it, if you are using the SynchronizationEvent properly – for example, consider a single producer thread and single consumer thread model, where the producer may produce two items to make available to the consumer thread, with each item causing a SynchronizationEvent to be set, before the consumer gets around to waiting on the event to process the new available items. Note that this model (involving the use of SynchronizationEvents) is not generally appropriate or ideal for multiple consumer threads.

Another example of where SynchronizationEvents are useful is for the construction of high level synchronization primitives. For example, the Win32 critical section package uses a SynchronizationEvent[1] to block waiters on the critical section if there is contention on the critical section. In this case, once the critical section finally becomes available, the SynchronizationEvent is set by the person releasing the critical section, conveniently waking (at most) a single waiter to attempt to acquire the critical section. (Note that the critical section package still has to guard against new waiters spinning on the critical section which haven’t gotten around to waiting on the SynchronizationEvent yet. Waking every waiter to try and take the lock wouldn’t be intrinsically beneficial, however, as the critical section is a single owner lock so only one thread will succeed in taking ownership anyway.)

[1] This is how they used to work; things are more complicated now due to additional optimizations. This is additionally an implementation detail and is subject to change (and in fact, has changed since some releases back).

S (Msft)

-----Original Message-----
From: xxxxx@lists.osr.com [mailto:xxxxx@lists.osr.com] On Behalf Of Bob Kjelgaard
Sent: Thursday, December 16, 2010 11:28 AM
To: Windows System Software Devs Interest List
Subject: RE: [ntdev] Does the set operation on an Auto-Reset event make a waiter ready? (was: Producer at DPC,Consumer at helper thread,puzzled)

Per this specific fork:

KeSetEvent and companions satisfy as many waiting threads as possible before they return. So if there are N threads waiting on a synch event and (because there is a WFMO and maximization is the goal) that synch event being set will ready any of them, one and only one of them will be readied before it returns.

That said, I haven’t paid close attention to this dispute, so I’m not vouching for anything beyond that specific request.

NTDEV is sponsored by OSR

For our schedule of WDF, WDM, debugging and other seminars visit:
http://www.osr.com/seminars

To unsubscribe, visit the List Server section of OSR Online at http://www.osronline.com/page.cfm?name=ListServer

Mark_Roddy · December 16, 2010, 3:28pm

On Thu, Dec 16, 2010 at 2:51 PM, Skywing wrote:
> An event is not a semaphore, so setting the event multiple times before it has awoken anyone will cause nothing special to happen

We all agree that a sync event is not a semaphore.

The dispute is over the exact semantics of the auto-reset property of
a sync event. If in fact exactly one thread is set to the wake state
by kesetevent before it returns, with the event now in the
non-signaled reset state, the theory is that ‘anton’s algorithm’ for
waking up consumer threads per item insertion could work.

The problem however with anton’s algorithm is that clearly kesetevent
returns with the event still set when no threads are waiting, without
waking up any threads. At that point any number of additional
kesetevent operations can occur, and anton’s clueless consumer threads
are now in trouble. Unless anton can guarantee that there will always
be a waiting thread, or handles as a special case the period of time
when no threads are waiting, I think his approach is broken.

Ken_Johnson · December 16, 2010, 3:33pm

There is no API contract around whether any thread(s) will be awoken by KeSetEvent before it returns. It would, IMO, be best to avoid assuming such things without an explicit guarantee that any such behavior is part of the functional contract provided by KeSetEvent.

S

-----Original Message-----
From: xxxxx@lists.osr.com [mailto:xxxxx@lists.osr.com] On Behalf Of Mark Roddy
Sent: Thursday, December 16, 2010 12:28 PM
To: Windows System Software Devs Interest List
Subject: Re: [ntdev] Does the set operation on an Auto-Reset event make a waiter ready? (was: Producer at DPC,Consumer at helper thread,puzzled)

On Thu, Dec 16, 2010 at 2:51 PM, Skywing wrote:
> An event is not a semaphore, so setting the event multiple times
> before it has awoken anyone will cause nothing special to happen

We all agree that a sync event is not a semaphore.

The dispute is over the exact semantics of the auto-reset property of a sync event. If in fact exactly one thread is set to the wake state by kesetevent before it returns, with the event now in the non-signaled reset state, the theory is that ‘anton’s algorithm’ for waking up consumer threads per item insertion could work.

The problem however with anton’s algorithm is that clearly kesetevent returns with the event still set when no threads are waiting, without waking up any threads. At that point any number of additional kesetevent operations can occur, and anton’s clueless consumer threads are now in trouble. Unless anton can guarantee that there will always be a waiting thread, or handles as a special case the period of time when no threads are waiting, I think his approach is broken.

—
NTDEV is sponsored by OSR

For our schedule of WDF, WDM, debugging and other seminars visit:
http://www.osr.com/seminars

To unsubscribe, visit the List Server section of OSR Online at http://www.osronline.com/page.cfm?name=ListServer

OSR_Community_User · December 16, 2010, 3:39pm

“As many as possible” could be 0. And 0 does not mean nobody is waiting on a specific event- any thread could be in WFMO requiring ALL items to be signaled and other waitable items in that collection are not signalled.

OSR_Community_User · December 16, 2010, 3:48pm

And I should add that if the event in this particular case is a synch event, it will still be in the signaled state, even if such a thread was waiting. It is cleared only when a thread is readied because of its being signaled (in doc parlance “When a wait is satisfied”). If that weren’t true, it would be useless.

>
“As many as possible” could be 0. And 0 does not mean nobody is waiting on a specific event- any thread could be in WFMO requiring ALL items to be signaled and other waitable items in that collection are not signalled.

anton_bassov · December 16, 2010, 4:19pm

>Unless anton can guarantee that there will always be a waiting thread, or handles as a special

case the period of time when no threads are waiting, I think his approach is broken.

If no threads are waiting KeSetEvent() does not get invoked by the producer because in such case count>=NumberOfItms - there is no problem here whatsoever. The problem with my approach is somewhat different. As James pointed out, there is a possibility of context switch between worker releases a lock (after having decremented count) and the moment it actually gets blocked, i.e.“somewhere on the way”. In such case, a thread is not yet waiting as far as dispatcher is concerned, but as far as producer that judges things upon ‘count’ variable is concerned, it already is. Let’s call it a “funny state”. If during some period of time X threads enter this “funny state” and producer calls KeSetEvent() Y times (Y>X)while no one is waiting as far as dispatcher is concerned , then Y-X items will be left outstanding for a while…

The funniest thing is that originally I used a counting semaphore (because the whole thing was meant to demonstrate that counting semaphore may be quite useful thing), but then, for reason a unknown even to myself, decided that synch event will suffice and changed the code. If I left a counting semaphore the problem James pointed out would not exist. DUH!!!

Anton Bassov

anton_bassov · December 16, 2010, 4:42pm

> No, SynchronizationEvents are not flawed in the same way that PulseEvent is

Yes, as it follows from Bob’s post, they are not - they work the way I thought they do…

(Calling SetEvent multiple times in rapid succession on a SynchronizationEvent with intent to wake
multiple waiter threads is misusing the SynchronizationEvent, to make that clear – the bug would
be in the program that is trying to abuse the SynchronizationEvent to wake N threads in this way
(which won’t work reliably). The bug would not be that SynchronizationEvents are fundamentally
flawed, because they are designed to suit a different purpose.)

Ironically, as it follows from Bob’s post there is no bug whatsoever - as long as X threads are known to be waiting and Y calls to SetEvent() are made (X>=Y), all Y threads will be released. However, if less than Y thread could be released under these circumstances I would say the synch event is fundamentally flawed.
I would agree with you in a situation when not all threads are released because wait and set calls may potentially race with one another - in such case there is, indeed, a bug in the code written this way…

Anton Bassov