The problem with threads

With Intel and AMD introducing Quad core systems and Sun pushing the envelope even further with its first hexadeca-core CPU named Rock the question that software industry has to ask itself is: are we ready to make all these threads of execution do useful work for us? My strong opinion is that we are not ready. A new paradigm is yet to be invented and we don't really know what it should look like. We do, however, seem to know what it should NOT look like. It definitely should not look like POSIX threads.
What's wrong with POSIX threads you ask? Well, lots and if you want to get a really good treatment of the subject matter delve into an excellent article by Prof. Edward A. Lee where he rightfully postulates that:
Threads discard the most essential and appealing properties of sequential computation: understandability, predictability, and determinism.
Of course, the key word here is determinism. What POSIX shared memory threading model does is it turns a fundamentally determimistic von Neumann architecture on its head by wreaking havoc on how memory gets used during computation to store intermediate results. What you get with POSIX threads is that even the code as simple as:
a = a\*2;
might be broken by a different thread accessing the same memory locations. And with modern languages like C++ knowing when memory gets accessed could be a very complex proposition. After all, those 'a' variables could have very well been objects of a class with an 'operator\*' overloaded, couldn't they? And the more you think about it the deeper the rabbit hole goes. Until you find yourself under a total paranoia spell: all of a sudden you don't trust anybody with your shared data and you start putting locks everywhere. Which, in turn, usually makes performance of your code plummet.
The problem is that we have chosen concurrent abstractions that do not even vaguely resemble the concurrency of the physical world. [...] Nondeterminism should be explicitly added to programs, and only where needed, as it is in sequential programming. Threads take the opposite approach. They make programs absurdly nondeterministic, and rely on programming style to constrain that nondeterminism to achieve deterministic aims.
True words, indeed. Especially when you start considering how much do we struggle with, what Prof. Lee calls 'constraining nondeterminism' even at a very basic syntactic level. You see, even though syntactic constructs such as 'synchronized' keyword from Java help a bit, they don't really solve a fundamental problem of expressing transactional properties. Take a look at this code:
if (buffer_size < my_chunk)
    wait_for_data_to_arrive();
buffer_size -= my_chunk;
process_my_chunk_of_data(my_chunk);
If we want to make it thread-safe \*and\* efficient we have to make sure that the above sequence is, at the same time atomic (perhaps all the way till the process_my_chunk_of_data() call happens) and interruptible (after all, it'll be pointless to go wait_for_data_to_arrive() if nobody can modify the buffer while we sleep). The closest we can get in expressing that very predicate is the following code, which is as ugly as it is suboptimal:
synchronized(buffer) {
   while (buffer_size < my_chunk)
          wait(); 
   buffer_size -= my_chunk;
}
process_my_chunk_of_data(my_chunk);
Look how we had to change an easy to follow if-logic into a totally insane while cycle. To quote Prof. Lee once again:
To offer a third analogy, a folk definition of insanity is to do the same thing over and over again and to expect the results to be different. By this definition, we in fact require that programmers of multithreaded systems be insane. Were they sane, they could not understand their programs.
That's right. Paranoid and insane. And also wasteful. Why? Well, at least in Java when you do notify() to wake that thread doing the wait() call -- you don't release your lock immediately. You have to exit the synchronized() block for that to happen. You have to remember all those nuisances in order to avoid tons of potential mistakes such as deadlocks, race conditions, spurious wakeups and quite a few more. And that makes a successful design of a properly synchronized systems based on POSIX threads more of an exception, than a rule. Here's a scary, yet so cassandranesque passage from the article:
I conjecture that most multithreaded general-purpose applications are, in fact, so full of concurrency bugs that as multi-core architectures become commonplace, these bugs will begin to show up as systems failures. This scenario is bleak for computer vendors: their next generation of machines will become widely known as the ones on which many programs crash. These same computer vendors are advocating more multi-threaded programming, so that there is concurrency that can exploit the parallelism they would like to sell us. Intel, for example, has embarked on an active campaign to get leading computer science academic programs to put more emphasis on multi-threaded programming. If they are successful, and the next generation of pro- grammers makes more intensive use of multithreading, then the next generation of computers will become nearly unusable.
Scary, huh? Well, it scares me allright. And even thought, I don't really agree with the solution proposed in the article, I must say that its key conclusion is worths to be memorized and repeated like a mantra:
If we expect concurrent programming to be mainstream, and if we demand reliability and pre- dictability from programs, then we must discard threads as a programming model. Concurrent programming models can be constructed that are much more predictable and understandable than threads. They are based on a very simple principle: deterministic ends should be accomplished with deterministic means. Nondeterminism should be judiciously and carefully introduced where needed, and should be explicit in programs. This principle seems obvious, yet it is not accomplished by threads. Threads must be relegated to the engine room of computing, to be suffered only by expert technology providers.

P.S. For somebody who is still not convinced that being paranoid and insane isn't all that fun, I highly recommend jumping right into chapter 4: "How Bad is it In Practice?". Follow the examples given there. Once you're done go to your bookshelf and dust off that old copy of "Design Patterns". Open it up in a random place and apply multithreaded thinking. Repeat until you achieve enlightenment.
Comments:

I've had trouble understanding just how competent developers would have problems developing correctly multithreaded programs, and how "we" have a problem. But then, you pretty conveniently branded me insane.

Posted by Mikael Gueck on July 30, 2007 at 07:59 AM PDT #

To: Mikael Gueck

I'm just a messenger, who happens to be as insane as you are. ;-)

Posted by Roman Shaposhnik on July 30, 2007 at 08:06 AM PDT #

Sometimes, functional programming helps :-)

Posted by Sohail on July 30, 2007 at 08:10 AM PDT #

There are alternate solutions to this, the most known is message-based concurrency, used in languages like Erlang and Oz. I remember the first time I used concurrency in Erlang.. and finally reached enlightenment :)

Posted by Rodrigo Barrientos on July 30, 2007 at 08:44 AM PDT #

To: Sohail

It sure does! Stay tuned for the follow up article ;-)

Posted by Roman Shaposhnik on July 30, 2007 at 10:49 AM PDT #

To: Rodrigo Barrientos

Agreed 100%. I guess the message-based concurrency model dates all the way back to CSP and it is quite amazing to realize how well that works in terms of "judiciously introducing nondeterminism where it is needed" while still having your program mostly deterministic. My personal favorite incarnation of the message-based concurrency, however, can be found in Inferno's Limbo.

Posted by Roman Shaposhnik on July 30, 2007 at 10:54 AM PDT #

Thanks for the link to Limbo!

Posted by Sohail on July 30, 2007 at 11:36 AM PDT #

Yep. Very interesting.. using a channel to pass channels.. I love those kind of features!

Posted by Rodrigo Barrientos on July 30, 2007 at 12:37 PM PDT #

Very interesting article. I haven't worked with multithreaded apps in a while, but I used to do a lot of low-level Unix Network Programming where I used POSIX threads all the time. I agree that pthreads have a lot of problems -- programmers are generally smart, and good programmers can work with POSIX threads, but humans make mistakes. When you're tired, bored, unmotivated, etc. it's extremely easy to screw things up royally with POSIX threads. I'd certainly welcome a more straightforward abstraction. On the other hand, I have to argue a bit with you re: the claim that our current abstractions do not model the real world. The real world is ridiculously random and nondeterministic. How does the current abstraction not mesh with that reality? For example, if I tell you that the last request to my web server was received 3 seconds ago, it'd be essentially impossible for you to guess when the next request would arrive. If I gave you my server logs for the past year, it'd be equally difficult.

Posted by Mike Malone on July 31, 2007 at 08:35 AM PDT #

As other posters commented, multi-threaded is not the only way to use a multi-core system. How about multi-process? There are any number of interprocess communication techniques to go with that. Ivan Novick

Posted by Ivan Novick on July 31, 2007 at 03:39 PM PDT #

I have to fix a bug in a multithreaded application and agree fully with Prof. Lee. You can do a multithreaded application with pthreads, but any change inside or outside the code may result in a disaster. There is no practical way to have a tool check for the constructs, which are likely to have produced the bug. There are so much things which may be the source of the problem, that you have to understand the spplication in full, which is not the case with most other bugs.

Posted by Knut Grunwald on August 01, 2007 at 12:29 AM PDT #

To: Mike Malone

I guess you would have to argue with Prof. Lee as well, but since he's not available at the moment let me try to explain how I would read his statement about concurrency of the world around us. ;-) True the real world is mindbogglingly concurrent and it is also (at least in my opinion) infinite. Both are thing that we, as human beings, can not fully understand yet we have to reason about them. I'm going to be real cheesy now and state that in order to tame the infinity we've invented calculus. And that was a useful abstraction for us to deal with the very notion of infinite. Does it mean that we've fully comprehended it? I would say no, but it definitely gave us a very useful tool to assess properties of infinite objects without going crazy. The same thing has to happen for concurrency as well. And the model that we build has to reflect the way we are wired. POSIX threads is definitely not reflective of that.

Posted by Roman Shaposhnik on August 01, 2007 at 09:23 AM PDT #

To: Ivan Novick

Agreed. But fundamentally for data parallel tasks you might as well bite the bullet and agree on the shared memory model being a must. That is not to say that you have to settle for a shared memory programming paradigm, though. Which kind of, was the whole point of the article to begin with -- its ok for POSIX threads to "be relegated to the engine room of computing" as long as we don't have to visit that room very often.

Posted by Roman Shaposhnik on August 01, 2007 at 09:29 AM PDT #

I don't know if you follow Apple news, but if so: what do you think of the new NSOperation and NSOperationQueue they've introduced into Cocoa?

To quote their site (as not a lot of printed information is given):

By using NSOperation, a breakthrough new API that optimizes applications for the world of multicore processing. Independent chunks of computation (operations) are added to an NSOperationQueue, which dynamically determines how many operations to run in parallel based on the current architectures. So there’s no need to hand-code the complexities of threading and locking. You simply describe the operations in a program along with their dependencies.

There was a freely available keynote where they described the idea.. If you're interested, I can find it..

Posted by Aviad Ben Dov on August 05, 2007 at 06:00 PM PDT #

How about STM ? Is that a bad proposition ? Can't that be abstracted to be the engine room of multithreaded computing ?

Posted by Gangadhar on August 06, 2007 at 12:37 AM PDT #

The whole concurrency issue is overflogged. - Desktop users will take advantage of multiprocessor chips by running more desktop applications concurrently. - Server users will continue develop with the well-debugged multithreaded and multiprocess apps they have been using all along on SMP systems (apache, for instance). - Where extra cores are not needed, more features such as RAM and graphics will be squeezed into the processor to reduce the total cost of computing. Any questions? :)

Posted by Seun Osewa on August 06, 2007 at 01:54 AM PDT #

To: Aviad Ben Dov

I would very much appreciate if you could send me more info on NSOperation. It does look interesting, indeed. At this point all I can say is -- the way Apple describes it makes it sound very similar to Intel's Thread Building Blocks.

Posted by Roman Shaposhnik on August 06, 2007 at 04:09 AM PDT #

To: Gangadhar

If by STM you mean Software transactional memory and not Scanning tunneling microscope, then I have two comments. First of all, it'll be much easier to evaluate STM when hardware support for transactional memory makes its debut (Rock from Sun is coming real soon now). And second of all, I'm yet to see a reasonable language support for it that would take into account things like IO.

Posted by Roman Shaposhnik on August 06, 2007 at 04:14 AM PDT #

To: Seun Osewa

I have one word for you: uptime. See how many process are trying to run concurrently on your desktop. As for servers, perhaps you're right. But you can't Xen everything.

Posted by Roman Shaposhnik on August 06, 2007 at 04:17 AM PDT #

in .NET there is the Concurrency and Coordination Runtime (CCR): http://channel9.msdn.com/ShowPost.aspx?PostID=143582

Posted by Lars on August 06, 2007 at 08:59 AM PDT #

Interesting thing to look at is how the recently merged completely-fair-scheduler in the linux kernel has affected applications. Simply changing how a single core is scheduled has exposed race conditions in existing code that was thought to be relatively bug free.

Posted by Carey Underwood on August 06, 2007 at 12:37 PM PDT #

Okay, I've found it. It's one of the free ADC's movies shown when Leopard was first introduced. You just log in to your DC account (http://developers.apple.com/ ) and get the movie - It is called "Session 000 - Mac OS X State of the Union" - It's quite long and not all of it is thread related, but they get to the multi-core and multi-threading as the first issue.

Posted by Aviad Ben Dov on August 08, 2007 at 04:09 AM PDT #

Seun:

||| Server users will continue develop with the
||| well-debugged multithreaded and multiprocess apps
||| they have been using all along on SMP systems
||| (apache, for instance).

Unfortunately, consider that corporate development of server-side applications outnumber infrastructure apps like Apache by many orders of magnitude. For instance, once you start stuffing objects into web sessions, you start having concurrency issues. Chances are you won't even know how it'll behave until the system loads up.

Posted by Chui Tey on August 08, 2007 at 04:11 AM PDT #

To: Lars

Thanks a lot for posting a link to CCR! I've just finished their article "An Asynchronous Messaging Library for C#" and I must say that I was intrigued by their approach. I do not necessarily agree with
the syntax outlined there, but the semantics of something like:

activate (!p.with(MyIntHandler)
|
!p.with(MyStringHandler)
|
!pShutdown(Shutdown)
);

made me a believer.

In fact, it looks to me as though they are on the verge of redefining the very notion of the control flow in a programming language. Which kind of explains why C# gets in the way so much and also makes you wonder what kind of tools would go well with such an environment. To some extent that might be a solution to the problem postulated in Prof. Lee paper -- you get a bunch of deterministic "thunks" connected together in a network. Thus purging all nondeterminism to the messaging layer. Now, I must admit that it is definitely not a panacea but a solution intriguing enough to think about it in details. All in all, thanks again for providing the link.

Posted by Roman Shaposhnik on August 09, 2007 at 01:23 PM PDT #

Some comments on this blog have been disabled pending author identification.

Posted by Roman Shaposhnik on August 14, 2007 at 06:27 AM PDT #

Post a Comment:
  • HTML Syntax: NOT allowed
About

rvs

Search

Top Tags
Archives
« April 2014
SunMonTueWedThuFriSat
  
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
   
       
Today