In a recent article, U.C. Berkeley Professor Edward Lee sounds the alarms on the challenge of multithreaded programming.1 Though multithreading isn’t new, it’s suddenly receiving a lot of attention with the widespread distribution of multicore processors. For the first time, average users are sitting at the keyboards of multiprocessing machines. And software folks are worrying about how to exploit this new, potentially very interesting technology, which promises to multiply available computing power by a very large factor. For example, Intel recently demonstrated an 80-core processor.
So why is threading such a problem? It’s not hard to understand. Suppose we have a 10,000-line program that’s single-threaded. Roughly speaking, the program can be in any one of 10,000 situations, depending on where it is currently executing. To help make such a program reliable, we need to consider all these 10,000 situations and make sure there are no problems. This is a large but manageable number, and we can use coverage testing to make sure we have tests that cover all the cases.
Now take the same 10,000-line program and assume it has two threads. Let’s assume that each of the two threads can execute 7000 lines of the program. Furthermore, the two threads can be at arbitrary points within these 7000 lines. This creates 49 million combinations of situations to consider. That’s a huge number, and there’s no simple analog of coverage testing that can make sure tests cover every possibility.
To make things worse, as the program gets bigger and the number of threads increases, the problem explodes exponentially. A million-line program with a hundred threads has an unimaginable number of possible states.
So what are we to do? Are we facing an impossible problem? The answer is a definite no. In fact, we have techniques for building large, completely reliable multithreaded programs. (If you don’t believe this, then maybe you should avoid flying since air-traffic control systems typically fall into this category.) As a starting point, we need to be using the right languages and tools. Let’s list the features in C and C++ for handling multithreading.
An editing error? No! These two languages have nothing whatever to say about threading. C was designed before this was a factor, and C++ took the lead from C. Yes, one can glue on thread libraries. But that’s an unsatisfactory approach for many reasons, including significant portability problems.
Java does have some capabilities for threading, but they’re low-level capabilities, and it’s generally recognized that Java must be augmented to be suitable for real-time programming. Indeed, more than one such effort is under way, but it is a challenge to add major new features to an existing language.