CSR: Small: SHF: An Operating System and Programming Model for Deterministic Parallel Computation

确定性地运行程序的能力，使得重新执行总是产生相同的结果，对于许多目的是有用的：例如，重放调试、入侵分析、容错、拜占庭责任和定时通道控制。然而，传统上运行确定性并行程序是困难和昂贵的，特别是如果我们希望保证即使是任意错误或恶意软件的精确可重复性。Definator是一种新型操作系统，它对多线程和多进程计算执行确定性，并行化在一台机器的内核和集群中的所有节点上。内核只提供单线程的“无共享”地址空间，通过在所有用户级代码上强制执行确定性行为的同步原语进行交互。非确定性输入和可观测的时间概念--包括时钟、定时器、周期计数器和与时间相关的内部通信通道--只能通过受控I/O机制访问，使监控软件能够精确控制非确定性信息可能如何以及何时影响监控计算。在这个受限的内核API之上，一个不可信的运行时使用分布式计算技术来模拟熟悉的抽象概念，如Unix进程、文件系统和共享内存多线程。通过构建和评估这个实验性的OS体系结构，我们希望发现：(1)操作系统强制的确定性执行是否可以变得实用并且与传统OS环境的性能竞争，即使对于大规模并行应用程序也是如此；(2)如何模拟传统的非确定性API并以最少的修改确定性地运行遗留软件；以及(3)如何创建新的“自然确定的”并行编程API，为表达并行性提供强大但易于使用的抽象，同时保证独立于执行调度的可预测和精确可重复的结果。

The ability to run programs deterministically, so that re-execution always yields identical results, is useful for many purposes: e.g., replay debugging, intrusion analysis, fault tolerance, byzantine accountability, and timing channel control. Running parallel programs deterministically is traditionally difficult and costly, however, especially if we wish to guarantee precise repeatability even of arbitrarily buggy or malicious software.Determinator is a novel operating system that enforces determinism on multithreaded and multi-process computations, parallelized both across cores in one machine and across nodes in a cluster. The kernel provides only single-threaded, ``shared-nothing'' address spaces, interacting via synchronization primitives that enforce deterministic behavior on all user-level code. Nondeterministic inputs and observable notions of time - including clocks, timers, cycle counters, and timing-dependent internal communication channels - are accessible only via controlled I/O mechanisms, giving supervisory software precise control over how and when nondeterministic information may affect a supervised computation. Atop this constrained kernel API, an untrusted runtime uses distributed computing techniques to emulate familiar abstractions such as Unix processes, file systems, and shared memory multithreading.By building and evaluating this experimental OS architecture, we hope to discover: (1) whether OS-enforced deterministic execution can be made practical and performance-competitive with conventional OS environments, even for massively parallel applications; (2) how to emulate conventional nondeterministic APIs and run legacy software deterministically with few modifications; and (3) how to create new, "naturally determinisic" parallel programming APIs, offering powerful but easy-to-use abstractions for expressing parallelism, while guaranteeing predictable and precisely repeatable results that are independent of execution scheduling.