Futexes are Fun

Futexes are a synchronization primitive that is new to the 2.6 Linux kernel. If you're like me and had never heard of them before a few days ago, then I recommend reading Ulrich Drepper's article, Futexes are Tricky. To a Windows programmer like myself, futexes are a wonderful idea that would be lots of fun to play with. Essentially, they're the antithesis of Window's synchronization model.

Hmmm. I guess I'm showing how much I dislike Window's synchronization model...

Let's start there. In Windows, if you want to use a synchronization object, you go to the Micrsoft-approved zoo of Win32/.NET synchronization objects, and you find one that's close to what you need. You then modify your problem to fit this synchronization object.

Okay, the zoo of synchronization objects that Microsoft gives you isn't bad. There are some extremely useful ones in there. If you're using .NET, you even get to use a monitor, which was missing from Win32.

In fact, if you're doing relatively normal programming in Windows, you'll never even realize that you're missing futexes. However, if you're trying to build an application that has to have optimal performance, then you may want something unusual.

You may want to do a WaitForMultipleObjects on 65 mutexes. You may want to optimize a mutex implementation as much as possible, and you're willing to give up features like re-entrance. There are a lot of things you might need, and Microsoft deliberately doesn't give you all of them. Thomas Becker has tried to implement something that's not in Microsoft's zoo, and the difficulties that he ran into are instructive.

POSIX doesn't have a universal solution, either. However, it does have a monitor, and, assuming performance isn't an issue, you can solve any problem using this.

Futexes are all that and more. They let a programmer write their own synchronization object in user mode. They do this by avoiding doing anything that's unnecessary. A futex lets you have a thread join a wait list and sleep until it is woken. The user mode code decides when a thread will enter the wait list, and when threads in the wait list will get woken up. They're still a bit new, and they don't let you control which thread gets woken up with much precision. Even if it's missing some features, however, it's still an exciting idea. It allows user mode libraries almost complete control over the performance and features of a synchronization object.

That's pretty darn clever. My next goal is to find an application at PC-Doctor that needs a futex. It sounds like a lot of fun, but it won't work on Windows.

This originally appeared on PC-Doctor's blog.

Bonus Day at PC-Doctor: They Gave Me a Coffin!

This morning was PC-Doctor's 14^th anniversary! To celebrate, the management team at PC-Doctor put in overtime and bought a lot of goodies to give away to employees.

Wow. That's pretty cool.

Maybe I'll win a 50" TV or some Raiders tickets or the massage chair.

The management team picks names, ostensibly at random, and when someone's name comes up, they run over to a pile of stuff they choose and claim it. Sounds great! I don't own a TV, and they've got a bunch of them here. Maybe I can get one?

It's Andy's turn! I work a lot with Andy, but his kids were sick today, so I got to pick for him. He sounded pretty happy about his plasma TV on the phone.

There aren't many choices left, but there are still a few good options remaining.

When's it going to be my turn?

Okay, now it's really hard to find anything left. What's still around?

Uh, oh. It turns out that I'm the last person.

What's still there?

Woot! I get a Lady of Guadalupe Casket! Rob says that it'll get delivered next week.

While I'm not a coffin expert, it's at least got a long list of features. It's pretty long, too, so my legs would only be slightly bent!

I'd told my wife that I might win a TV. Somehow, I'd forgotten to mention that I might win a casket. In retrospect, this seems like poor planning on my part.

One question remains: Is there enough space in my cubical for my new coffin?

This originally appeared on PC-Doctor's blog.

RTL Languages and International Usability

When you localize a product into a right to left language such as Hebrew or Arabic, how much do you have to change the position of UI elements?

It's a pretty simple question, and I think the answer is also pretty simple. If you have to have your eye on the right side of the page to start reading a sentence, then your eye is going to start on the right side of the page.

As far as I can tell, that's the extent of the problem. What are the implications?

You can't assume that users will start in the upper left corner and scan down to the bottom right of a page. Important navigation tools should be on the right or the top. Tab order should go from the right to left.

Is that the whole story? As someone who knows absolutely nothing about the subject, it's tempting to say yes. Unfortunately, Saleh, a Persian blogger, knows better. I recommend reading his blog.

This originally appeared on PC-Doctor's blog.

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.