If I signal an auto-reset event and there is a thread waiting on it, is it guaranteed that the event will be reset and the waiting thread released before SetEvent returns?


Let's go straight to the question:

I have two programs that take turns doing something. Right now, I manage the hand-off with two auto-reset events. In Thread A, after it finishes doing some work, it signals Event B and then immediately waits on Event A. Thread B does the converse: When its wait on Event B completes, it does some work, then signals Event A and then immediately waits on Event B.

This works great, but I'm wondering if I can save myself an event and use the same event to hand control back and forth. Is it guaranteed that when Thread A signals Event B, that this will release Thread B and reset the event (since it is auto-reset) before the call to Set­Event returns? If so, then I can just have one event and use it to bounce control back and forth.

Let's try it!

#include <windows.h>
#include <stdio.h>

HANDLE h;
DWORD CALLBACK ThreadProc(void *msg)
{
 for (;;) {
  SetEvent(h);
  // The theory is that the above SetEvent does not return
  // until the other thread has positively completed its wait,
  // so this upcoming wait will not complete until the other
  // thread calls SetEvent.
  WaitForSingleObject(h, INFINITE);
  puts((LPSTR)msg);
 }
}

int __cdecl main(int, char**)
{
 DWORD id;
 h = CreateEvent(0, FALSE, TRUE, 0);
 CloseHandle(CreateThread(0, 0, ThreadProc, "T1", 0, &id));
 CloseHandle(CreateThread(0, 0, ThreadProc, "T2", 0, &id));
 Sleep(INFINITE);
 return 0;
}

If you run this program, you'll see that the two threads come nowhere near taking turns. Instead, you see stretches where thread T1 gets to run a whole bunch of iterations in a row, and stretches where thread T2 gets to run a whole bunch of iterations in a row.

Okay, so we have demonstrated by experiment that this technique does not work. (You can use experimentation to show that something doesn't always work, but you can't use it to show that something always will work. For that you need to read some contracts and put on your thinking cap.) But why doesn't it work?

The lawyerly explanation for why it doesn't work is that there is nothing in the contract that says that it does work. Perfectly correct, but not particularly insightful.

Signaling an event makes all waiting threads eligible to run, but that doesn't mean that they actually will run. One of the waiting threads is woken to say "Hey, now's your chance." But that thread might be groggy and slow to wake, and in the meantime, another thread can swoop in and steal the event signal. And then that groggy thread shuffles downstairs to the breakfast table to find that somebody ate his pancake. (Actually, in principle, the kernel could just make it a total free-for-all and wake all the waiting threads, but I suspect it just picks one.)

We saw earlier that the thread that you would expect to run next might be temporarily unavailable and miss its chance to claim what it thinks is rightfully his. And more recent versions of Windows have exacerbated the problem by abandoning fairness in order to improve throughput and avoid lock convoys. Now, in principle, the kernel could have reset the event when it woke the waiting thread, thereby assigning the wake to the thread at signal time, but that would have reintroduced the problem that unfairness was trying to solve.

The irony here is that what you're doing here is intentionally trying to create a convoy, and you're running into the scheduler's convoy-resistance.

Just use the two-event pattern. That makes it explicit what you want.

Comments (13)
  1. TripShock says:

    The two event approach is the right way to go, and just in case they don't know already, they should be using SignalObjectAndWait, instead of SetEvent followed by WaitForSingleObject, which could be inefficient.

  2. alegr1 says:

    I'm afraid Joe Duffy's article is (un)intentionally vague on the matter for what locks the convoy problem was solved, so it doesn't actually mean what you think it means.

    The description matches the problem of simple kernel spinlocks. All contenders were simply busy-waiting on a pointer-sized variable, while on DISPATCH_LEVEL, which makes them ineligible for thread switch (interrupts could still happen). When the owner released the lock, a random contender would grab it and become the owner. No fairness whatsoever. Also, that would cause a lot of inter-socket cache coherency traffic, because InterlockedCompareExchange is implemented using cache coherency protocol. This is the main cost of such a spinlock, especially in systems with large number of processors.

    Enter InStackQueued spinlocks, which Mr Duffy describes. Each contender busy-waits on its own local variable. The owner simply passes ownership to the next contender in the chain, in FIFO order, this guaranteeing fairness, and reducing cache coherency traffic.

    The article confuses things by talking about threads. On DISPATCH_LEVEL and higher, there is no thread scheduling. Spinlocks are owned by processors, not threads, because the spinlock owner or contender on DISPATCH is guaranteed to continue running without preemption (other than by ISRs) on the same processor until it drops to at APC_LEVEL or PASSIVE_LEVEL.

    Waiting on kernel objects has been fair – all waiter threads are linked to a FIFO list. Mr Duffy's article refers to the old Raymond's article about CRITICAL_SECTIONS. Well, since contenders wait on an auto-reset event, the least recent one will be awaken. There is a scenario when a new contender will come and grab it before the fairly selected one will have a chance, but such is life.

  3. Rob says:

    I love all the insight you give us, but the windows shell irritates me by not just getting on with the job. Why can't explorer give us a file listing straight away, before it has figured out all the icons in a big listing. I feel long-time bloat in the shell even if is being very smart in ways I don't care about.

    I do love your stories, and the things you tell me that make my life easier as a developer.

    Sometimes I feel like I'm fighting with bad design decisions. Maybe some of the were yours too – I don't know how much influence you have there. Trading cool for getting the job done.

    Simpler means less bugs.

    Rob. (With respect, but lots of fighting with the odd shell and other APIs that were just broken over the years).

    [That's such a great idea, we did it 17 years ago. That's why you see the blank icons briefly. -Raymond]
  4. Rob says:

    And we are encouraged to talk to the shee rather than the core file APIs, right?

  5. alegr1 says:

    Rob,

    Windows UI coding goes by spec. Some commitee comes with a spec, and then some clueless offshore programmers write code. Nobody makes sure the code actually does what the users want, other than running some benchmarks in the ivory tower. Need to refresh desktop icons cache? Redraw them all blank, and then rebuild the icon cache one by one and redraw them one by one. This makes SOO MUCH SENSE. Need to implement "go back" list in the Explorer? Keep ephemeral IDs in it, so if your network drives get reconnected, you cannot go back there. Opening a folder? enumerate into the child folders, who cares if it takes long, especially on network.

    [Wait, you don't like the blank icons? You prefer that they be loaded synchronously with the content enumerator? Can you get in a room with Rob and decide once and for all whether icons should be loaded synchronously with the file listing or not? -Raymond]
  6. Gabe says:

    One nice thing about File Manager was that even back in 1995 it could show a directory of tens of thousands of files nearly instantly. I often find myself wishing Explorer had a mode where it was as fast as FileMan by not opening files to look for icons or metadata.

  7. Joshua says:

    @Gabe: Grab an NT4 CD. winfile.exe is there and it still works. I used it to have a UAC-incompatible file manager back in the day.

  8. alegr1 says:

    [Wait, you don't like the blank icons? You prefer that they be loaded synchronously with the content enumerator?]

    Raymond, have you ever booted your Windows computer or installed any programs? (tricky question). When the desktop first shows up after login, it triggers icon cache refresh. It also happens if any program (mostly an installe3r) broadcasts WM_WININICHANGE.

    Icon cache refresh is done the most retarded way possible, to cause the most visual disruption. They all are redrawn blank, and then redrawn with (99.9%) the same unchanged images.

    Folder load is slow, partially because the programmers didn't think about how do it most efficient (it also affects how it shows total selected size). They seem to use only file names from WIN32_FIND_DATA. If Explorer wants to pull the localized folder names, it could use cached values, display all the child folders promptly, and then lazily confirm or update the cached values. That will make opening of remote folders VERY fast, unlike it's now.

    [My icons don't refresh. I would suspect some program you installed. Some developers are lazy and force icon cache rebuilds in order to "fix" icon problems. (Going for the global solution to a local problem.) They are initially drawn blank because when the icon cache is destroyed and a new one created, the only icon initially available in the new icon cache is the blank icon. Or are you saying there should be an "icon cache cache"? -Raymond]
  9. Joshua says:

    [Or are you saying there should be an "icon cache cache"? -Raymond]

    What alegr1 is saying is the in-use entries should have been rebuilt in place. I've dealt with caches with this property before. Blanking the cache doesn't remove them but sets an invalid bit that causes it to be reloaded on the next pass.

    As for the rest of alegrl1's stuff, if you want a fast file manager these days, you're going to have to build one. Explorer is too heavyweight.

    [The purpose of rebuilding the icon cache is not to refresh the icons. It's to throw everything away and start over, for example, because the icon cache is too big and needs to be pruned. Leaving everything in place doesn't accomplish pruning. -Raymond]
  10. Anonymous Coward says:

    Clearly the answer is to have another checkbox in the configuration. Then both people can pick the way they want their blank icons (or lack thereof) to work, and the two of them can gang up on the guy complaining that the configuration has just expanded to 83 tab pages and is a little bloated.

    Trying to please everyone is fun.

  11. icabod says:

    Nice article, and thanks to TripShock for the pointer to SignalObjectAndWait – I'd been taking the two-step approach when asking a thread to die, simply as I hadn't spotted that call, and the two-step approach always worked for me.  I guess that's one of the problems of programming – spotting _other_ ways of doing what you're already doing inefficiently.

    As an aside – I didn't realise auto-reset events were quite so related to file explorer and the icon cache.

  12. Marc K says:

    icabod, It looks like SignalObjectAndWait was not available in Win9x.  So, that may be why you missed it.  Old school programmers had no choice but the two step approach.

  13. alegr1 says:

    @icabod:

    SignalObjectAndWait is just marginally faster than separate calls, because it only saves one SYSENTER roundtrip, while having a bit of overhead to switch to different kernel calls to signal the object, depending on its type. Not enough to go and replace the existing calls in the legacy code.

    There used to be a saving on not having to release and acquire the dispatcher lock, but it doesn't matter anymore in Vista+.

Comments are closed.