Death of the Thread Model
You haven’t really had the fear of Turing struck into you until you’ve tried concurrent programming. Any lofty visions you’ve had of a normal, happy life as a programmer won’t survive your first pthread or Thread.run() call.
My most recent non-trivial attempt at threads was way back when in college. The course was “TCP/IP Programming.” It was the kind of course that didn’t interest me just from its title and description. Really, I signed up for it because the best professor in the entire school was delivering it, Dan Duchamp, and this was my last semester. In the end, it actually wound up being an informative course, because networking is not my strong point.
We were warned that the assignments would be in C and would be back-breakers. This almost turned out to be true. I had Duchamp in three other courses, and sometimes he would overstate the scope of a project.
- a DNS resolver that sent UDP to DNS and relayed the result via TCP back to whomever requested it
- a simulation of ICMP and IP; this is one of the courses that I look back on and think “I can’t believe I pulled that off”
- a link-state and distance vector routing simulation
- a simulation of TCP
- port the first assignment to the TCP simulation
Somehow, someway, I had no problem with the first three. Then I read the description of the TCP simulation, and I shuddered when I saw that three threads were required.
I pretty much knew right then that it was over.
In fact, after getting extra help from Duchamp, it became apparent that I needed to use pthread_cond_wait, pthread_cond_timedwait, pthread_mutex_t, and pthread_cond_signal to name a few. These were system calls and types that I had never used before.
Duchamp, bless his heart, claimed that he covered them in the OS course, which I also took with him. While he covered mutexes and locking, we did not make use of condition variables in assignments. So on top of the intellectual burden of dealing with my half-finished attempt at multi-threading, which was already based on a bad thread design (and it was too late to start over), I had to learn and use new system calls correctly.
My point is my last semester of senior year could’ve been much less stressful if programming with threads wasn’t a death trap. At work, I asked our technical lead if they made use of multi-threading in the code, and the answer was a resounding “No, it becomes too ugly too quickly.”
So something can’t be right. It can’t be such a nightmare to do something like three threads, one for each layer boundary, plus another to do the real work, but so effortlessly achieve concurrent data access and processing. Why do I have to suffer through concurrency if it is not DB-related?
Larry O’Brien: Oh, absolutely, but even if you get it and even if you think it’s fun, there’s a thing about that thread and process model that we have in the CLR today, which I would argue makes it fundamentally broken for business programming. So, check out this scenario. You have a library and it has some publicly available method by which it acquires a lock, right?
Carl Franklin: Yeah.
Larry O’Brien: And holds that lock and returns to you and you go about and do your other thing. If you have another method that calls that library on which that library performs a callback and by a callback I mean all sorts of important things. I’m talking about virtual method calls in a world of object orientation. I’m talking about delegates and events central to graphics programming and I’m talking about lambda expressions, which are coming out in C# 3.0 and they’re very important for LINQ. You can never safely have a library that simultaneously has a publicly triggerable lock that executes a callback to client code because it’s perfectly legal for the client code to start up a new thread…
Carl Franklin: Yeah.
Larry O’Brien: And within that new thread, call that method attempts to get the lock which is already held by the previous thread and the end result of that is deadlock.
I’d take this even a step further: the thread-and-lock model of concurrency is broken because it is too low-level. Why, in this age of garbage collection, managed code, and workflow engines, hasn’t the abstraction level been raised on concurrency as well?
The itching issue that needs scratching is that it has been for quite some time, but only in the niche of databases. Memory management used to be a pest; now there is platform support for garbage collection. We need similar support for concurrency. It was just then that the guys on the show discuss Software Transactional Memory:
Larry O’Brien: Okay. Software Transactional Memory is essentially optimistic locking for memory.
Carl Franklin: Yeah.
Larry O’Brien: You wrap a call or a block in what’s essentially a transaction. You say “Atomic, start block” and then you finish the block and it runs at full speed and then you have a follow-along processor that goes through it and it looks for that one in a thousand, one in a million memory collision. If a memory collision has occurred, it retries it.
Carl Franklin: Yeah.
Larry O’Brien: Yeah. It’s not at all a bad model.
This would be a giant step forward. It does have its problems, namely that it still requires the programmer to be aware and predict what blocks of code are critical sections in order to mark them off as transactions.
To take it a step higher, using Futures, this sort of demarcation can be delegated to the compiler and/or runtime environment entirely:
Larry O’Brien: Instead of trying to second guess the creation of thread, what you do is you say, “Well, I want this value” you know this value being returned from a function, “but I can either have the value or I can have” what Sutter calls “a Future.”
A Future is basically an IOU. Okay, so you have this reference to a Future and when you need it, when you say, “Okay, I want to cash in this IOU” at that point, the system will block and guarantee that the value becomes concrete. So, just by sort of flipping things around from “Okay, let’s create processes and kind of second guess how many cores I have” and those sorts of approaches.
This approach says, okay by simply having a whole bunch of IOUs floating around then it becomes possible for the compiler on the runtime to do a lot of really clever reasoning about “Oh hey, look. Here’s this IOU, but I know that this IOU won’t be required for several hundred milliseconds and so, therefore, I have enough information to distribute that to another core.”
The only drawback here is again another programmer-dependent pitfall. Functions that return Futures work best, if at all, when they are pure functions with no side effects. This is a throwback to functional programming, and my personal least-favorite Scheme.
I still favor these methods to the rather Draconian no-shared-mutable-state edict of Erlang:
Carl Franklin: There’s no shared memory, right?
Larry O’Brien: Oh, that’s huge.
Carl Franklin: Between processes?
Larry O’Brien: That’s a huge thing. Really to make Concurrency work at the language level, the number one thing that you want to get rid of is shared mutable state.
Carl Franklin: Yup.
Larry O’Brien: Erlang is single assignment to variables…
This is why I think Polyphonic C# is a nice try but gives me some of the same headaches I felt at the start of this post.
It is ultimately a trade-off between shared mutable state (and thus performance) a la Futures and functional programming, and clarity (and thus less performance) a la STM. I think this trade-off is a familiar one to most people in this field. Moreover, I’ll say that this trade-off is as innate to our field as Brooks’ Law.
I maintain that abstractions like STM and Futures are going to be very important for us software developers in the coming decade if we are to make affordable full use of the next wave of hardware.