Fairness in Win32 Lock Objects

Windows Vista has given up fairness in their synchronization objects. In fact, Windows XP isn't guaranteed to be fair, but Vista goes quite a bit further.

The issue and the solution is explained pretty well by Joe Duffy over here. At first glance, it looks as though this could cause some really bad thread starvation in some circumstances.

The change to unfair locks clearly has the risk of leading to starvation. But, statistically speaking, timing in concurrent systems tends to be so volatile that each thread will eventually get its turn to run, probabilistically speaking. Many more programs would suffer from the convoy problems resulting from fair locks than would notice starvation happening in production systems as a result of unfair locks.

The problem they're trying to solve and the problem that I'm worried about are pretty similar, so it's worth explaining it carefully. If you have a mutex that protects a small chunk of code, and you have a large number of threads trying to get that mutex, then you have the potential to have a lock convoy. You can get this easily if you wake up a large number of threads with the same priority and have them all immediately try to get another lock.

Here's what happens. A bunch of threads are waiting for a mutex. A thread releases the mutex. Under Windows XP, the next thread in line to get the mutex now owns the mutex and gets a temporary priority boost. Windows does a context switch to the new thread, and it performs a short operation and releases the mutex. (Note that this will also boost the priority of the next thread in line, but that thread will have the same priority, so no context switch is performed.)

These context switches are expensive. Joe Duffy claims that it's about 1000 cycles. Avoiding these switches would be a good thing, so Vista changes the way mutexes work. When a thread releases a mutex under Vista, the mutex does not become owned by the next thread in the queue. Instead, it becomes unowned. This allows a third thread that's already in the running state to grab the mutex and keep going without any context switches at all. That's much cheaper, much less fair, and has the potential to starve the waiting threads.

One problem with this is that you're giving priority to running threads over waiting threads. As the number of cores in your CPU goes up, then the number of running threads gets higher. Eventually, isn't there going to be some starvation of the waiting threads?

I tried for a while to construct an artificial scenario where a thread could be starved for a long period of time. I've got to admit that I couldn't do it. The reason is that there is always some randomness in the scheduling. In order to make it so that there is a problem, I had to increase the fraction of time that a thread holds the synchronization object. Once you do that, you're going to limit the number of threads that can run without having to run into problems with a lack of fairness. It feels as though that might be true of all problems where this change becomes bad, but I couldn't prove it.

In short, Vista gives up the pretense of fairness in synchronization objects, and it does so without guaranteeing that it doesn't starve a thread. However, it looks to me as though thread starvation will never be a huge issue.

This originally appeared on PC-Doctor's blog.

ActiveX is still around!

ActiveX has been around a while. When Microsoft was battling Netscape, they needed a way to put custom, active content on web pages. Java was being used by Netscape, and people thought it was great. Microsoft needed something they could develop quickly that would let programmers put new types of content on the web browser. ActiveX was born.

The basic idea behind ActiveX is really simple. A programmer creates a DLL that can be accessed by anyone. Some introspection is added, and now a web browser can call native code! Once you're in native code, you can do whatever the heck you want, so Microsoft's work was done. Of course, Microsoft added a bunch of ways to make it complicated, but the basic architecture is extremely simple.

That was back when Bill Gates thought that no one would pay money for security. The security model Microsoft used was also extremely simple: All ActiveX DLLs are signed. If someone hijacks thousands of computers using your DLL, then Microsoft will know who's responsible!

Of course, Microsoft signed some DLLs that had some big holes in them. In fact, lots of legitimate companies did. For the next decade and a half, a whole team of Microsoft employees dealt with the consequences of these design decisions.

ActiveX is still here, though.

Even in Vista, ActiveX is still available. It's still possible to run whatever code you want in Internet Explorer under Windows Vista. If you don't believe me, go over to your Vista machine and head over to this URL: Microsoft Windows Update. This page can replace your drivers and reboot your computer!

So, what has Microsoft changed? Is it still business as usual in the land of ActiveX? No, it's not. A lot has changed.

First of all, enough warnings pop up around an ActiveX control that both programmers and users avoid them like the plague. Back in the early days, programmers were supposed to put UI widgets on the browser window because Microsoft said it was easier to do it that way than by using HTML. (This conveniently prevented the page from loading under Netscape, so no one actually took this advice.) Now, almost no one makes ActiveX controls. Once you've got some video players, Flash, and a few others, you're done. No one else has to write them anymore! Certainly no one has to write one that requires administrative access to the computer. Once Windows Update was finished, the designers probably concluded that that was all you needed.

There's very close to no documentation on the subject, but it's still possible to have your ActiveX control run as an administrator. The strange part is that now, instead of being a mainstream programmer, you have to put on your dark sunglasses and visit some very murky areas. Microsoft won't tell you exactly what to do, but they do put clues in a variety of blog postings and tech notes. Bugs will haunt you as you make your way toward what you need, and you'll never really know if you're exploiting the OS or doing it correctly.

It's amazing what's changed. It's even more amazing how little has changed.

This originally appeared on PC-Doctor's blog.