change the state. These mechanisms
allow for reasonable scalability if used
˲ Locking mutexes opens a whole
new can of worms, though. Using a
single program-wide mutex would in
most cases dramatically hurt program
performance by decreasing the portion of the program that can run in
parallel (P in the formula). Using more
mutexes increases not only P but also
the overhead associated with locking
and unlocking the mutexes. This is
especially problematic if, as it should
be, the critical regions are only lightly
contended. Dealing with multiple mutexes also means there is the potential for deadlocks. Deadlocks happen
if overlapping mutexes are locked by
multiple threads in a different order.
This is a mistake that happens only
too easily. Often the use of mutexes
is hidden in library functions and not
immediately visible, complicating the
the Programmer’s Dilemma
The programmer is caught between
˲ Increasing the part of the program
that can be executed in parallel (P).
˲ Increasing the complexity of the
program code and therefore the potential for problems.
An incorrectly functioning program
can run as fast as you can make it run,
but it will still be useless. Therefore,
the parallelization must go only so far
as not to introduce problems of the
second kind. How much parallelism
this is depends on the experience and
knowledge of the programmer. Over
the years many projects have been developed that try to automatically catch
problems related to locking. None is
succeeding in solving the problem for
programs of sizes as they appear in the
real world. Static analysis is costly and
complex. Dynamic analysis has to depend on heuristics and on the quality
of the test cases.
illUstration by oli larUelle
For complex projects it is not possible to convert the whole project at
once to allow for more parallelism.
Instead, programmers iteratively add
ever more fine-grained locking. This
can be a long process, and if the testing of the intermediate steps isn’t
thorough enough, problems that are
not caused by the most recently added
set of changes might pop up. Also, as
experience has shown, it is sometimes
very difficult to get rid of the big locks.
For an example, look at the BKL (big
kernel lock) discussions on the Linux
kernel mailing list. The BKL was introduced when Linux first gained SMP
(symmetric multiprocessing) support
in the mid-1990s, and we still haven’t
gotten rid of it in 2008.
People have come to the conclusion
that locking is the wrong approach to
solving the consistency issue. This is
especially true for programmers who
are not intimately familiar with all the
problems of parallel programming
(which means almost everybody).
The problem of consistency is nothing
new in the world of computers. In fact,
it has been central to the entire solution in one particular area: databases.
A database, consisting of many tables
with associated indexes, has to be
updated atomically for the reason already stated: consistency of the data.
It must not happen that one part of
the update is performed while the rest
is not. It also must not happen that
two updates are interleaved so that in
the end only parts of each modification are visible.
The solution in the database world
is transactions. Database programmers explicitly declare which database operations belong to a transaction. The operations performed in the
transaction can be done in an arbitrary
order and do not actually take effect
until the transaction is committed. If
there are conflicts in the transaction
(that is, there are concurrently other
operations modifying the same data
sets), the transaction is rolled back
and has to be restarted.
The concept of the transaction is
something that falls out of most programming tasks quite naturally. If
all changes that are made as part of a
transaction are made available atomically all at once, the order in which the
changes are added to the transaction
does not matter. The lack of a requirement to perform the operations in a
particular order helps tremendously.
All that is needed is to remember to
modify the data sets always as part of
a transaction and not in a quick-and-dirty, direct way.
feBRuaRY 2009 | vol. 52 | No. 2 | CommunICatIons of the aCm