International Symposium on Computer Architecture (ISCA), June 2009.
Shared-memory multi-threaded programming is inherently more difficult
than single-threaded programming. The main source of complexity is
that, the threads of an application can interleave in so many
different ways. To ensure correctness, a programmer has to test all
possible thread interleavings, which, however, is impractical.
Many rare thread interleavings remain untested in production
systems, and they are the root cause for a majority of concurrency
bugs. We propose a shared-memory multi-processor design that avoids
untested interleavings to improve the correctness of a
multi-threaded program. Since untested interleavings tend to occur
infrequently at runtime, the performance cost of avoiding them is not
high.
We propose to encode the set of tested correct interleavings in a
program's binary executable using Predecessor Set (PSet) constraints.
These constraints are efficiently enforced at runtime using processor
support, which ensures that the runtime follows a tested interleaving.
We analyze several bugs in open source applications such as MySQL,
Apache, Mozilla, etc., and show that, by enforcing PSet constraints,
we can avoid not only data races and atomicity violations, but also
other forms of concurrency bugs.