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. 3 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 example. 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 system resources.

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, 11 accountability, 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. 13

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 time “inputs.”

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 databases. 7 To our knowledge, however, Determinator is the first OS to introduce such a model for pervasive thread- and process-level determinism.

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