Atop this kernel API, Determinator’s user-level runtime
emulates familiar shared-resource programming abstractions. The runtime employs file replication and versioning24
to offer applications a logically shared file system accessed
via the Unix file API, and adapts distributed shared memory
techniques1 to emulate shared memory for multithreaded
applications. Since this emulation is implemented in user
space, applications can freely customize it, and runtime bugs
cannot compromise the kernel’s guarantee of determinism.
Rather than emulating conventional parallel memory
models, Determinator explores a private workspace model.
In this model, each thread keeps a private virtual replica of
all shared memory and file system state; normal reads and
writes access and modify this working copy. Threads reconcile their changes only at program-defined synchronization
points, much as developers use version control systems.
This model eliminates read/write data races, because reads
see only causally prior writes in the explicit synchronization
graph, and write/write races become conflicts, which the
runtime reliably detects and reports independently of any
(real or synthetic) execution schedule.
Experiments with common parallel benchmarks suggest that Determinator can run coarse-grained parallel
applications deterministically with both performance and
scalability comparable to nondeterministic environments.
Determinism incurs a high cost on fine-grained parallel
applications, however, because of Determinator’s use of
virtual memory to isolate threads. For “embarrassingly parallel” applications requiring little inter-thread communication, Determinator can distribute the computation across
nodes in a cluster mostly transparently to the application,
maintaining usable performance and scalability. The prototype still has many limitations to be addressed in future
work, such as a restrictive space hierarchy, limited file
system size, no persistent storage, and inefficient cross-node communication.
2. A DeteRmiNistiC PRoGRAmmiNG moDeL
Determinator’s goal is to offer a programming model that
is naturally and pervasively deterministic. To be naturally
deterministic, the model’s basic abstractions should avoid
introducing data races or other nondeterministic behavior
in the first place, not merely provide ways to control, detect,
or reproduce races. To be pervasively deterministic, the
model should behave deterministically at all levels of abstraction: for example, for shared memory access, inter-thread
synchronization, file system access, interprocess communication, external device or network access, and thread/pro-cess scheduling.
Many intermediate design points may yield useful trade-offs: enforcing determinism only on synchronization
and not on memory accesses can improve efficiency, for
22 For now, however, we explore the feasibility of
a “purist” approach to pervasive determinism. To achieve
this goal, we found we had to address at least four sources
of nondeterminism in current systems: nondeterministic
inputs that applications may require for operation; shared
state such as memory and file systems; synchronization
APIs that threads and processes use to coordinate; and
namespaces through which applications use and manage
2. 1. explicit nondeterministic inputs
Many applications use nondeterministic inputs, such as
incoming messages for a Web server, timers for interactive
applications, and random numbers for cryptographic algorithms. We seek not to eliminate such nondeterministic
inputs but to make relevant inputs explicit and controllable.
Mechanisms for parallel debugging,
19 fault tolerance,
16 and intrusion analysis12 all rely on the
ability to replay a computation instruction-for-instruction,
in order to replicate, verify, or analyze a program’s execution history. Replay can be efficient when only I/O need be
logged, as for a uniprocessor virtual machine,
12 but becomes
much more costly if internal sources of nondeterminism
due to parallelism must also be replayed.
Determinator transforms useful sources of nondeterminism into explicit I/O, which applications access via
controllable channels, and eliminates only internal nondeterminism resulting from parallelism. If an application
calls gettime-ofday(), for example, a supervising process can intercept this I/O to log, replay, or synthesize these
2. 2. A race-free model for shared state
Conventional systems give threads concurrent access to
many forms of shared state, such as shared memory and file
systems, yielding data races and heisenbugs if the threads
are improperly synchronized.
20, 21 Replay debuggers19 and
deterministic schedulers8, 22 make data races reproducible
once they manifest, but do not change the inherently race-prone model in which developers write applications.
Determinator replaces the standard concurrent access
model with a private workspace model,
3 which avoids data
races in the first place. This model gives each thread a private
virtual replica of all logically shared states, including shared
memory and file system state. A thread’s normal reads and
writes affect only its private working state, and do not interact directly with other threads. Instead, Determinator accumulates each thread’s changes to the shared state, and then
reconciles these changes among threads only at program-defined synchronization points. This model is related to
early parallel Fortran systems,
6 replicated file systems,
24 distributed version control systems,
15 and snapshot isolation in
7 To our knowledge, however, Determinator is the
first OS to introduce such a model for pervasive thread- and
If one thread executes the assignment “x = y” while another
concurrently executes “y = x,” for example, these assignments
race in the conventional model, but are race-free under
Determinator and always swap x with y. Each thread’s read of
x or y always sees the “old” version of that variable, saved in
the thread’s private workspace at the last explicit synchronization point.
Figure 1 illustrates a more realistic example of a game or
simulator, which uses an array of “actors” (players, particles,
etc.) to represent some logical “universe,” and updates all
actors in parallel at each time step. To update the actors, the