Threads without locks

by xtacy • 16 years ago

27 14 16 years ago

I hate the slideshow format they used. It took me 5 minutes to arrive at the point of the presentation, and if I had actually known what their solution was, I wouldn't have needed to read any of it, since it's a fairly simple and moderately well-known idea.

For anyone wondering, Bell's proposal is each state has its own local variables (limited to the scope of the thread function itself, but I like thread local storage too), and _no_ variables are shared between more than one thread. Any data that needs to be passed between the threads is done via message passing (their so-called "events").

All this would be OK if they had a good reason for it all. Their only excuse is that event loops are inefficient (which I totally agree), and that writing thread-safe code is hard (which I completely disagree with). Using their message-passing system to solve thread concurrency is really not an efficient idea, and it's wholly unnecessary. Wrapper functions, judicious use of your CPUs "Interlocked*" functions to atomically modify or swap variables, and possibly using (yet-to-catch-on) lock-free data structures is the way to go.

maximilianburke• 16 years ago

Writing shared-state thread safe code is very hard to get right especially in the context of large systems. When you move beyond safely coordinating mutation of shared resources there are many other headaches that can pop up, like priority inversion issues, lock ordering problems, etc.

Atomic operations are not a panacea either. Lock free data structures are very difficult to write correctly and the performance benefits associated with using atomics can start to evaporate when there is contention between multiple threads. There are also numerous subtle problems that can arise, from data visibility problems when modifying an unaligned address on multi-socket x86 platforms to ABA problems.

The easiest to write, and safest, multithreaded code is that which shares no state. Saying that atomic operations are the way to go is like saying NoSQL is the way to go, they are useful for a subset of problems but in general they are the wrong level at which to be thinking when approaching concurrency.

Aegean• 16 years ago

I think that's not their point. What they advocate is based on Tony Hoare's CSP model. When you introduce locks and share data, your program suddenly becomes extremely complex to validate. Yes if you are skilled enough, you can lock things and it works (most operating systems would only rarely crash due to locking) but what this brings is true determinism.

The programs become provably stable and deterministic. Furthermore, the determinism can scale. E.g. If you achieve a safely validated program with 10 threads, you can consider that as a single block and replicate and connect it to thousands more, and yet your system remains safe from concurrency bugs.

The downside is that its overkill to separate the program into multiple threads just to make sure you don't have shared data.

But it has its merits, imagine you are developing a mission critical system. Its a powerful thing to claim you have a fully deterministic concurrent system with hundreds of communicating threads in it. Also note that cpus will multiply soon to 64, 128 ... cores, so might as well use some of them for something like this.

sjs• 16 years ago

> I hate the slideshow format they used.

Disable JavaScript and you'll see the slides layed out one after the other, vertically. It was pretty easy to read and skim that way.

(I've been using NoScript and NotScripts for the last month or two and wouldn't go back. Not only is it safe but the web is far less annoying in general. e.g. not hunting around for links to disable IntelliTxt and every other similar "service".)

NickM• 16 years ago

Sounds like they're essentially advocating an Erlang-style model of concurrency, which generally seems to be recognized as a good way of doing things.

That said, they're not really eliminating all the pitfalls of threaded programming. It's still possible to have deadlocks and timing-dependent bugs when using a message-passing model of concurrency.

To take it one step further, they could implement something like the Erlang OTP behaviors to abstract out the concurrency primitives. (Not that this would totally eliminate the drawbacks I mentioned, but it's another incremental step above the approach they've presented, IMHO.)

konad• 16 years ago

Erlang came later

mseebach• 16 years ago

Later than what? The presentation is from 2007, Erlang is from 1986, and open sourced in 1998.

masklinn2• 16 years ago

Than Hoare's CSP? Yeah. Than this proposal? Absolutely not. This presentation is from 2007 (and so is Go), Plan9 was released in 1992, Erlang dates back to 1986.

albertzeyer• 16 years ago

I'm just curious: For the channel implementation itself, of course you need locking, don't you? Or how is it possible to implement such a message queue without synchronisation?

cma• 16 years ago

Condition variables (although somewhere underneath, locks are probably used).

masklinn2• 16 years ago

If it can block, there's probably a lock.

It's also multiple-producer multiple-consumer, I'm not sure there are lockless implementations even for non-blocking versions of that.

papaf• 16 years ago

I've not done it myself, but once when I thought I'd need such a queue I found this pseudo code and references:

http://www.cs.rochester.edu/research/synchronization/pseudoc...

brettmjohnson• 16 years ago

I, too was annoyed at the obtuse presentation of message passing. I've been writing software for Mach/NeXTstep/MacOSX since 1988, and even before that, message queues between threads were in common use. I can't believe it took 5 or 6 slides to realize what they were presenting. I read the whole presentation and it definitely wasn't worth it.

Threads without locks

Related Stories