If an event is signaled more than once, are they delivered in the order in which they were signaled?


A customer asked the following question:

Is it guaranteed that the events when signaled multiple times on an event object are delivered in the order in which they were signaled?

For example, a thread is waiting on the event handle and performs some operation each time it is signaled. The ordering of those operations should be in the same order in which the event is signaled. Do events provide this guarantee? In case it matters, we're using an auto-reset event. We're finding issues when the system is under heavy load.

This question is confusing because events don't "remember" who signaled them. When an event is signaled, then a waiting thread is released. The waiting thread doesn't know "who" did it; there is no context associated with an event. So the answer is, "Sure, whatever, it comes in the order they were signaled, if that's how you want to think about it. If you want to think about it in reverse order, then sure, they come in reverse order. They come in whatever order you want since there's no way you can detect what order they arrived in, since they are identical."

You and your friend enter the museum at the same time. The museum attendance person clicks the number counter twice. "Was that first click for me or for my friend?" Who cares? All that got recorded is two clicks. There's nothing in the clicks that associates each one with you or your friend.

When asked for clarification, the customer explained:

We have a producer process that signals the waiting thread when certain 'events' occur. The service maintains a single list of context structures for each of these 'events' and then signals the waiting thread to tell it to wake up and take some action based on the associated context. When the client wakes up, it calls back into the producer process to retrieve the details of the event that woke it up. We want to know whether the thread, when it wakes up, will receive those events in the same order they were generated.

This explanation makes clear that the issue is not the event at all. The issue is the order in which the context structures are added to the list. We have this:

Thread A:
Add context to list in some manner
Signal event
Thread B:
Add context to list in some manner
Signal event
Waiting thread:
Wait for event
Retrieve context from list in some manner
Do something with context
Repeat

The question boils down to "If thread A adds its context and then signals the event, and simultaneously thread B adds its context and signals the event, then when the waiting thread wakes up, is it guaranteed that the waiting thread will retrieve thread A's context first?"

The answer is "Well, it depends on how you added the context to the list and how you retrieved it." If the race between thread A's "Add context to list in some manner" and thread B's "Add context to list in some manner" is won by thread A, and the waiting thread retrieves the context FIFO, then it will get thread A's context. But the event has nothing to do with it. The race condition took place before the event was signaled.

The answer to the question is of no real value, however, because this design pattern is flawed from the start. Events are not counted. They have only two states: Signaled and not signaled. Consider the situation where three events are raised in rapid succession.

Thread A:
Add context to list in some manner
Signal event
Waiting thread:
Wait for event completes; event returns to unsignaled
Retrieve context
Thread A:
Add context to list in some manner
Signal event
Add context to list in some manner
Signal event (has no effect since event is already signaled)
Waiting thread:
Do something with first context
Wait for event (completes immediately since event is already signaled)
Event returns to unsignaled
Retrieve context (gets second context)
Do something with second context
Wait for event (waits since event is not signaled)

Congratulations, you just lost an event signal because setting an event that is already set is a no-op.

If you need the number of wakes to equal the number of signals, then use a semaphore. That's what it's for.

In response to this explanation, the customer simply wrote back, "Semaphores worked. Thanks."

Comments (18)
  1. Tom says:

    I’m sure glad you were able to figure out what the customer was complaining about.  That’s an impressive display of detective work.  All that talk about "events in the right order" certainly distracted me from the real problem.

    Of course, another way to solve the problem would have been the traditional producer/consumer pattern where the consumer gets a signal and processes the list until there are no entries left, then goes back to waiting on the event.  Given the limited context provided, I think this pattern would have solved the problem without requiring a semaphore.

  2. Koro says:

    I bet they used a semaphore, but in the end, didn’t really understand why.

  3. Anonymous says:

    I think that part of the confusion comes from the fact that events can be auto-reset or manual-reset.  With manual-reset, it’s pretty clear that two simultaneous signals will be equivalent to one.  With something like auto-reset, it’s reasonable for someone to expect that signal + reset happens atomically, and that signalling means "dequeue exactly one waiter", hence two simultaneous calls would dequeue (up to) two waiting contexts.

    Of course even with the above semantics you still won’t detect multiple signals while there are no waiters.  So there is still brokenness in the algorithm above.  But, even so, I think the semantics of auto-reset is still an interesting detail.

  4. nathan_works says:

    perhaps people should be required to pass a test before writing any multi-threaded code.. I wonder if their list/queue (whatever structure they used..) was even correctly locked for multi-threaded reader/writer access..

  5. porter says:

    > perhaps people should be required to pass a test before writing any multi-threaded code..

    Difficult in this day and age given that both C# and Java are threaded by default ( unless on a Java smart card ).

  6. Alexandre Grigoriev says:

    One thing people should remember: there is no ordering between multiple threads and events. Unless you explicitly make it so.

  7. kbiel says:

    Anon,

    Even with auto-reset events, two simultaneous signals will appear as one. There is no guarantee that the processing thread will receive CPU time right after the first signal.

    I am not sure what the person was trying to accomplish, but usually we just have the processing thread work the queue until empty. In that way, you don’t need a semaphore and you don’t lose "events".

  8. David says:

    What an unbelievably complex and pompous response to a simple question… And a response that doesn’t even answer the question.

    If I throw two tomatoes at you, can I assume they will splash on your face in the order I threw them?

  9. mikeb says:

    How can a question that makes no sense be a simple question?

  10. GrumpyYoungMan says:

    @David

    Boy, did you ever miss the point.  The answer is trivial to find for anybody who’s halfway competent.  There’s no need to post it.

  11. Ray Trent says:

    The real flaw in Raymond’s answer is that it violates one of Dilbert’s Law’s: "Never [engage in a long discussion] with time-wasting morons".

    The correct answer is "No".

    Raymond wasted a bunch of words answering a question that was unrelated to the user’s actual problem.

    But it should have been obvious to him that this was probably the case, because the question so mind-numbingly demonstrates a complete lack of understanding of what events are. Sometimes there really are stupid questions.

  12. Bruno Martinez says:

    I just thought a related question:  If thread A signals two events that thread B is waiting for both with WaitForMultipleObjects, is B guaranteed to wake on the first signaled event?

  13. zzz says:

    looking at various definitions of "event"s it’s rather obvious the windows "event" is not an even at all and is a very poor choice of word for what the mechanism described here is meant for.

  14. John says:

    Ray Trent, your post displays a complete lack of understanding of the way people learn.

  15. Bob says:

    I’m willing to bet that part of Raymond’s job description is something like "people pay you to answer their questions, don’t be an ass about it."

    I’ld also say that Raymond is good at his job, while many commenters here feel free to be insulting because they’re not going to be held accountable for their own desperate need to make themselves feel better by being jerks.

    And while it’s true that there are stupid questions, refusal to ask the question is much worse – I’ld rather answer a thousand stupid questions than deal with the consequences of a thousand people not bothering to find out that they didn’t know as much as they thought they knew.

    Also, I have nothing but respect for people who can work tech support, where the only time people contact them is when they don’t know something – which means you get nothing but questions that you already know the answer to, and hence can easily start to consider to be "stupid questions".

  16. steveg says:

    interesting post.

    It was nice the customer wrote back to say thanks, so many people don’t.

  17. Mike Dimmick says:

    Bruno, I believe the documented answer is ‘no’, and that is the only answer you should rely on.

    In practice, Windows initiates a reschedule when signalling an object, if there are threads waiting on that object – at least checking whether to make a thread runnable, though not necessarily pre-empting the current thread. (The thread[s] made runnable may be a lower priority, even after priority boosting, or may have affinity on a different processor core, or perhaps another core is free.) That would mean that the waiting thread would already be released and marked runnable after the first SetEvent call, before the second was processed.

    However, we also know that the kernel may borrow threads (e.g. to deliver I/O completions for asynchronous I/O that the thread started) and when this happens, the thread isn’t actually waiting. See http://blogs.msdn.com/oldnewthing/archive/2005/01/05/346888.aspx for details. In this case the thread will check the state of objects when it goes back to waiting, and it may then happen to check object B before object A.

  18. Golden hammer says:

    Repeat after me:

    1. Threads are Hard

    2. Threads are not magic bullets

    3. Threads introduce WHOLE NEW CLASSES of bugs

Comments are closed.