Since our current focus is on emulating familiar abstractions and not on developing storage systems, Determinator’s
file system currently provides no persistence: it effectively
serves only as a temporary file system.
Our runtime mimics a weakly consistent, replicated file
24 by maintaining a complete file system replica in
each process’s address space, as shown in Figure 5. When a
process creates a child via fork(), the child inherits a copy
of the parent’s file system in addition to the parent’s open file
descriptors. Individual open/close/read/write operations in a process use only that process’s file system replica,
so different processes’ replicas may diverge as they modify
files concurrently. When a child terminates and its parent
collects its state via wait(), the parent’s runtime uses file
versioning to propagate the child’s changes into the parent.
If a parallel make forks several compiler processes, for
example, each child writes its output .o file to its own file
system replica. The parent’s runtime merges these .o files
into the parent’s file system as the parent wait()s on each
child. This copying and reconciliation is not as inefficient as
it may appear, due to the kernel’s copy-on-write optimizations. Replicating a file system image among many spaces
copies no physical pages until user-level code modifies them,
so all copies of identical files consume only one set of pages.
As in any weakly consistent file system, processes that
perform unsynchronized, concurrent writes to the same file
may cause conflicts. When our runtime detects a conflict, it
simply discards one copy and sets a conflict flag on the file;
subsequent attempts to open() the file result in errors.
This behavior is intended for batch compute applications
for which conflicts indicate a bug, whose solution is to fix
the bug and rerun the job. Interactive use would demand a
policy that avoids losing data. The user-level runtime could
implement stronger consistency and avoid unsynchronized
concurrent writes, at higher synchronization costs.
4. 3. input/output and logging
Since unprivileged spaces can access external I/O devices
only indirectly via parent/child interaction within the space
hierarchy, our user-level runtime treats I/O as a special case
of file system synchronization. In addition to regular files, a
process’s file system contains special I/O files, such as console input and output files. Unlike Unix device special files,
figure 5. each process maintains a private replica of the shared file
system, using file versioning to reconcile replicas at synchronization
Job Outputs Job Inputs
Determinator’s I/O files actually hold data in the process’
file system image: for example, the console input file accumulates all characters that the process has received from
the console, and the console output file holds all characters
written to the console. In the current prototype, console
or log files can eventually “fill up” and become unusable,
though a suitable garbage-collection mechanism could
address this flaw.
When a process does a console read(), the C library first
returns unread data already in the process’s local console
input file. When no more data is available, instead of returning an end-of-file condition, the process calls Ret to synchronize with its parent and wait for more console input (or in
principle any other form of new input) to become available.
When the parent does a wait() or otherwise synchronizes
with the child, it propagates any new input to the child.
When the parent has no new input for any waiting children,
it forwards all their input requests to its parent, and ultimately to the kernel via the root process.
When a process does a console write(), the runtime
appends the new data to its internal console output file as
it would append to a regular file. The next time the process
synchronizes with its parent, file system reconciliation
propagates these writes toward the root process, which
forwards them to the kernel’s I/O devices. A process can
request immediate output propagation by explicitly calling fsync().
Reconciliation handles “append-only” writes differently
from other writes, enabling concurrent writes to console
or log files without conflict. During reconciliation, if both
the parent and child have made append-only writes to the
same file, reconciliation appends the child’s latest writes to
the parent’s copy of the file, and vice versa. Each process’s
replica thus accumulates all processes’ concurrent writes,
though different processes may observe these writes in a different order. Unlike Unix, rerunning a parallel computation
from the same inputs with and without output redirection
yields byte-for-byte identical console and log file output.
4. 4. shared memory multithreading
Shared memory multithreading is popular despite its nondeterminism, in part because parallel code need not pack
and unpack messages: threads simply compute “in-place”
on shared variables and structures. Since Determinator
gives user spaces no physically shared memory other than
read-only sharing via copy-on-write, emulating shared memory involves distributed shared memory (DSM) techniques.
Adapting the private workspace model of Section 2. 2 to
thread-level shared memory reuses ideas from early parallel Fortran machines6 and release-consistent DSM systems,
although these prior designs did not offer determinism.
Our runtime uses the kernel’s Snap and Merge operations (Section 3. 2) to emulate shared memory in the private workspace model, using fork/join synchronization.
To fork a child, the parent thread calls Put with the Copy,
Snap, Regs, and Start options to copy the shared part of its
memory into a child space, save a snapshot of that memory
state in the child, and start the child running, as illustrated
in Figure 6. The master thread may fork multiple children