Software acquire the lock for that data,perform its computation, and then release the lock so other operations on the data and the can proceed.Unfortunately,although locks work,they pose serious problems for modern software development. Concurrency A fundamental problem with locks is that they are not composable.You can't take two correct lock-based Revolution pieces of code,combine them,and know that the result is still correct.Modern software development relies on the ability to compose libraries into larger programs,and so it is a serious difficulty that we cannot build on lock-based code behind the operations can be analyzed to determine components without examining their implementations. how to execute them concurrently and what data they The composability issue arises primarily from the share.This advantage is sometimes hypothetical,since possibility of deadlock.In its simplest form,deadlock program analysis is an imprecise discipline,and suffi- happens when two locks might be acquired by two tasks ciently complex programs are impossible for compilers to in opposite order:task T1 takes lock L1,task T2 takes lock understand and restructure. L2,and then T1 tries to take L2 while T2 tries to take L1. At the other end of the granularity axis,computa- Both block forever.Because this can happen any time tions on a Web site are typically independent except for two locks can be taken in opposite order,calling into accesses to a common database.The computations run code you don't control while holding a lock is a recipe for in parallel without a significant amount of coordination deadlock. beyond the database transactions.This ensures that con- That is exactly what extensible frameworks do,how- current access to the same data is consistently resolved. ever,as they call virtual functions while holding a lock. Today's best-of-breed commercial application frameworks UNSTRUCTURED PARALLELISM all do this,including the .NET Frameworks and the Java The most general,and least disciplined,form of parallel- standard libraries.We have gotten away with it because ism is when the concurrent computations differ,so that developers aren't yet writing lots of heavily concur- their data accesses are not predictable and need to be rent programs that do frequent locking.Many complex coordinated through explicit synchronization.This is the models attempt to deal with the deadlock problem-with form of parallelism most common in programs written backoff-and-retry protocols,for example-but they using threads and explicit synchronization,in which require strict discipline by programmers,and some intro- each thread has a distinct role in the program.In general, duce their own problems(e.g.,livelock). it is difficult to say anything specific about this form of Techniques for avoiding deadlock by guarantee- parallelism,except that conflicting data accesses in two ing locks will always be acquired in a safe order do not threads need explicit synchronization;otherwise,the compose,either.For example,lock leveling and lock program will be nondeterministic. hierarchies prevent programs from acquiring locks in con- flicting order by requiring that all locks at a given level be THE PROBLEM OF SHARED STATE AND acquired at once in a predetermined order,and that while WHY LOCKS ARENT THE ANSWER holding locks at one level,you can acquire additional Another challenging aspect of unstructured parallelism is locks only at higher levels.Such techniques work inside sharing unstructured state.A client application typically a module or framework maintained by a team(although manipulates shared memory organized as unpredictably they're underused in practice),but they assume control interconnected graphs of objects. of an entire code base.That severely restricts their use in When two tasks try to access the same object,and one extensible frameworks,add-in systems,and other situa- could modify its state,if we do nothing to coordinate tions that bring together code written by different parties. the tasks,we have a data race.Races are bad,because the A more basic problem with locks is that they rely on concurrent tasks can read and write inconsistent or cor- programmers to strictly follow conventions.The rela- rupted values. tionship between a lock and the data that it protects is There are a rich variety of synchronization devices implicit,and it is preserved only through programmer that can prevent races.The simplest of these is a lock. discipline.A programmer must always remember to take Each task that wants to access a piece of shared data must the right lock at the right point before touching shared 58 September 2005 QUEUE rants:feedback@acmqueue.com58 September 2005 QUEUE rants: feedback@acmqueue.com code behind the operations can be analyzed to determine how to execute them concurrently and what data they share. This advantage is sometimes hypothetical, since program analysis is an imprecise discipline, and suffi- ciently complex programs are impossible for compilers to understand and restructure. At the other end of the granularity axis, computa￾tions on a Web site are typically independent except for accesses to a common database. The computations run in parallel without a significant amount of coordination beyond the database transactions. This ensures that con￾current access to the same data is consistently resolved. UNSTRUCTURED PARALLELISM The most general, and least disciplined, form of parallel￾ism is when the concurrent computations differ, so that their data accesses are not predictable and need to be coordinated through explicit synchronization. This is the form of parallelism most common in programs written using threads and explicit synchronization, in which each thread has a distinct role in the program. In general, it is difficult to say anything specific about this form of parallelism, except that conflicting data accesses in two threads need explicit synchronization; otherwise, the program will be nondeterministic. THE PROBLEM OF SHARED STATE, AND WHY LOCKS AREN’T THE ANSWER Another challenging aspect of unstructured parallelism is sharing unstructured state. A client application typically manipulates shared memory organized as unpredictably interconnected graphs of objects. When two tasks try to access the same object, and one could modify its state, if we do nothing to coordinate the tasks, we have a data race. Races are bad, because the concurrent tasks can read and write inconsistent or cor￾rupted values. There are a rich variety of synchronization devices that can prevent races. The simplest of these is a lock. Each task that wants to access a piece of shared data must acquire the lock for that data, perform its computation, and then release the lock so other operations on the data can proceed. Unfortunately, although locks work, they pose serious problems for modern software development. A fundamental problem with locks is that they are not composable. You can’t take two correct lock-based pieces of code, combine them, and know that the result is still correct. Modern software development relies on the ability to compose libraries into larger programs, and so it is a serious difficulty that we cannot build on lock-based components without examining their implementations. The composability issue arises primarily from the possibility of deadlock. In its simplest form, deadlock happens when two locks might be acquired by two tasks in opposite order: task T1 takes lock L1, task T2 takes lock L2, and then T1 tries to take L2 while T2 tries to take L1. Both block forever. Because this can happen any time two locks can be taken in opposite order, calling into code you don’t control while holding a lock is a recipe for deadlock. That is exactly what extensible frameworks do, how￾ever, as they call virtual functions while holding a lock. Today’s best-of-breed commercial application frameworks all do this, including the .NET Frameworks and the Java standard libraries. We have gotten away with it because developers aren’t yet writing lots of heavily concur￾rent programs that do frequent locking. Many complex models attempt to deal with the deadlock problem—with backoff-and-retry protocols, for example—but they require strict discipline by programmers, and some intro￾duce their own problems (e.g., livelock). Techniques for avoiding deadlock by guarantee￾ing locks will always be acquired in a safe order do not compose, either. For example, lock leveling and lock hierarchies prevent programs from acquiring locks in con- flicting order by requiring that all locks at a given level be acquired at once in a predetermined order, and that while holding locks at one level, you can acquire additional locks only at higher levels. Such techniques work inside a module or framework maintained by a team (although they’re underused in practice), but they assume control of an entire code base. That severely restricts their use in extensible frameworks, add-in systems, and other situa￾tions that bring together code written by different parties. A more basic problem with locks is that they rely on programmers to strictly follow conventions. The rela￾tionship between a lock and the data that it protects is implicit, and it is preserved only through programmer discipline. A programmer must always remember to take the right lock at the right point before touching shared Software and the Concurrency Revolution