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.
Lee suggests that we design programming languages with threading in mind. That’s definitely the right approach. Threading needs to be treated in a first-class manner and integrated into the language design so the opportunities for threads to interact are limited. (It’s the 7000 times 7000 as opposed to 7000 plus 7000 that kills us. So if we limit the contact points between threads, we can make a huge difference in the manageability of the code.)
Do we need entirely new languages? Lee suggests a new category of languages that would be used just for coordination in conjunction with existing languages. But this approach will be difficult, given the difficulties of dealing with the semantics of languages not designed for concurrency.
In fact, there are programming languages that have been around for a while that address this issue. In particular, all three generations of Ada—Ada-83, Ada-95, and the just approved Ada-2005 standard—regard tasks (its word for threads) as first-class citizens. It’s no surprise that critical applications in air-traffic control, radar, and avionics make significant use of Ada. For example, iFACTs, the next-generation air-traffic control system for Great Britain, is being written entirely in Ada.
Before we go off and reinvent the wheel, we should check what we have on the shelf. Lee mentions Ada (and some other similar languages), but dismisses them on the grounds that they aren’t likely to become mainstream. Perhaps the widespread appearance of multicore processors should lead us to revise what should be in the mainstream.
Reference
1. Edward Lee, “The Problem With Threads,”
www.eecs.berkeley.edu/Pubs/TechRpts/2006/EECS-2006-1.pdf .
Dr. Robert Dewar is cofounder, president, and CEO of AdaCore. He also has had a distinguished career as Professor of Computer Science (emeritus) at the Courant Institute of New York University. He has been involved with the Ada programming language since its inception in the early 1980s and, as co-director of both the Ada-Ed and the GNAT projects, he led the NYU team that developed the first validated Ada compiler. Dr. Dewar was one of the authors of the requirements document for the Ada 95 revision, and he served as a distinguished reviewer for both Ada 83 and Ada 95. He has co-authored compilers for SPITBOL (SNOBOL), Realia COBOL for the PC (now marketed by Computer Associates), and Alsys Ada, and he is a principal architect of AdaCore’s GNAT Ada technology. He has also written several real-time operating systems for Honeywell Inc.