technical Perspective
An experiment in Determinism
By Steven Hand

THe ADVeNT of multicore processors means that complex software is becoming more complex: developers must turn to the use of multiple threads to exploit hardware parallelism, yet it is widely held that parallel programming is far more difficult and error prone than writing sequential code. In particular, the myriad allowable interleavings of thread execution mean that different runs of a program can produce different behaviors, including different outputs or—worse—bugs!

To address this concern, the recent past has seen considerable interest in deterministic parallelism: techniques to ensure that multiple executions of a program observe the same interleavings, regardless of variations in the hardware, the vagaries of the scheduler, the use of synchronization primitives, or the presence or absence of external workloads. The hope is that deterministic parallelism will make it easier to have confidence in testing software quality: for example, if a bug can manifest due to a particular ordering of read and writes to objects in memory, then deterministic parallelism will ensure that this either always happens—thus making it easier to debug—or ensure it never happens, avoiding the bug altogether.

Some previous work has investigated providing deterministic parallelism in the language (Deterministic Parallel Java), at the level of the compiler and/ or runtime system (Kendo, CoreDet, dThreads), or within the hardware (DMP, RCDC). Most of these schemes do little to make parallel programming inherently simpler, and most are limited to multithreaded (rather than multiprocess) systems. In the following paper, however, Aviram et al. explore the idea of building an operating system that inherently enforces deterministic parallelism both within and across all hosted programs.

Most traditional operating systems
provide interfaces that are nondeter-
ministic; for example, creating a new
process with fork() or opening a file
with open() result in handles that de-
pend on the set of prior operations per-
formed, either systemwide or within
the current process; similar behavior
can be seen with memory allocations.
The values can directly or indirectly af-
fect control flow and general computa-
tion, thus leading to different behav-
iors even if there are no explicit ‘race
conditions.’ And, of course, explicit
nondeterminism is often exposed via
operations such as wait()on a process
or condition variable, or invoking se-
lect() on a set of file descriptors.

Determinator also controls other aspects of nondeterminism. For example, identifiers returned by the kernel are thread-private rather than global, and all synchronization operations are deterministic, rather than first-come-first-served (like many mutual exclusion locks). This leads to a system that has a quite different “feel” to traditional operating systems, yet the authors demonstrate it is possible to run a number of parallel benchmark programs without any ill effect. They also describe an emulation layer that provides some familiar Unix APIs, albeit with occasionally different semantics. One good example is in the implementation of process synchronization; while waitpid() can be easily supported, the nondeterminism of wait() cannot be. Instead wait() turns into “wait for the child process with the lowest (thread-local) process id” that, in many cases, suffices.

Determinator is an interesting and thought-provoking piece of research. However, it is unclear whether or not future operating systems will be built this way. There are a number of challenges in terms of how to support I/O operations, particularly those that interact with users or remote systems; and in terms of how to support inherently nondeterministic computation, such as generating cryptographic keys.

This is not just a limitation of Determinator, but rather of most work in the field. Although deterministic parallelism has the potential to reduce the number of allowable behaviors a program (or system) can express, which should increase the efficacy of testing, it does not help with the fact that most useful programs behave differently given different inputs. Relying on extensive testing to validate the correctness of programs is intellectually unsatisfactory, particularly given the woefully inadequate coverage obtained, and the general lack of any specification. Nonetheless, it is possible that deterministic parallelism will make it all a smidge easier—and that can’t be a bad thing, can it?

 

Steven hand ( [e-mail]) is a reader in computer systems in the computer laboratory at the University of cambridge, U.k.