Amittai Aviram
Bryan Ford
Abstract
Deterministic execution offers many benefits for debugging, fault tolerance, and security. Current methods of executing parallel programs deterministically, however, often incur high costs, allow misbehaved software to defeat repeatability, and transform time-dependent races into input-or path-dependent races without eliminating them. We introduce a new parallel programming model addressing these issues, and use Determinator, a proof-of-concept OS, to demonstrate the model's practicality. Determinator's microkernel application programming interface (API) provides only "shared-nothing" address spaces and deterministic interprocess communication primitives to make execution of all unprivileged code---well-behaved or not---precisely repeatable. Atop this microkernel, Determinator's user-level runtime offers a private workspace model for both thread-level and process-level parallel programming. This model avoids the introduction of read/write data races, and converts write/write races into reliably detected conflicts. Coarse-grained parallel benchmarks perform and scale comparably to non-deterministic systems, both on multicore PCs and across nodes in a distributed cluster.
- Amza, C. et al. TreadMarks: Shared memory computing on networks of workstations. IEEE Computer 29, 2 (Feb. 1996), 18--28. Google Scholar
Digital Library
- Artho, C., Havelund, K., Biere, A. High-Level data races. in Workshop on Verification and Validation of Enterprise Information Systems (VVEIS) (Apr. 2003), 82--93.Google ScholarCross Ref
- Aviram, A., Ford, B., Zhang, Y. Workspace consistency: A programming model for shared memory parallelism. In 2nd Workshop on Determinism and Correctness in Parallel Programming (WoDet) (Mar. 2011).Google Scholar
- Aviram, A., Hu, S., Ford, B., Gummadi, R. Determinating timing channels in compute clouds. In ACM Cloud Computing Security Workshop (CCSW) (Oct. 2010). Google ScholarDigital Library
- Bellard, F. QEMU, a fast and Portable Dynamic Translator, In USENIX Annual Technical Conference, Anaheim, CA, April 10--15, 2005. Google ScholarDigital Library
- Beltrametti, M., Bobey, K., Zorbas, J.R. The control mechanism for the Myrias parallel computer system. Comput. Architect. News 16, 4 (Sept. 1988), 21--30. Google ScholarDigital Library
- Berenson, H. et al. A critique of ANSI SQL isolation levels. In SIGMOD (June 1995). Google ScholarDigital Library
- Bergan, T. et al. CoreDet: A compiler and runtime system for deterministic multithreaded execution. In 15th International Conference on Architectural Support for Programming Languages and Operating Systems (ASPLOS) (Mar. 2010). Google ScholarDigital Library
- Bergan, T. et al. Deterministic process groups in dOS. In 9th USENIX Symposium on Operating Systems Design and Implementation (OSDI) (Oct. 2010). Google ScholarDigital Library
- Boyd-Wickizer, S. et al. Corey: An operating system for many cores. In 8th USENIX Symposium on Operating Systems Design and Implementation (OSDI) (Dec. 2008). Google ScholarDigital Library
- Castro, M., Liskov, B. Practical byzantine fault tolerance. In 3rd USENIX Symposium on Operating Systems Design and Implementation (OSDI) (Feb. 1999), 173--186. Google ScholarDigital Library
- Dunlap, G.W. et al. ReVirt: Enabling intrusion analysis through virtual-machine logging and replay. In 5th USENIX Symposium on Operating Systems Design and Implementation (Dec. 2002). Google ScholarDigital Library
- Dunlap, G.W. et al. Execution replay for multiprocessor virtual machines. In Virtual Execution Environments (VEE) (Mar. 2008). Google ScholarDigital Library
- Ford, B. PIOS: Parallel instructional operating system, 2010. http://zoo.cs.yale.edu/classes/cs422/pios.Google Scholar
- git: the fast version control system. http://git-scm.com/.Google Scholar
- Haeberlen, A., Kouznetsov, P., Druschel, P. PeerReview: Practical accountability for distributed systems. In 21st ACM Symposium on Operating Systems Principles (SOSP) (Oct. 2007). Google ScholarDigital Library
- Kaashoek, F. et al. 6.828: Operating system engineering. http://pdos.csail.mit.edu/6.828/.Google Scholar
- Kahn, G. The Semantics of a Simple Language for Parallel Programming", In Information Processing '74: Proceedings of the IFIP Congress (1974), pp. 471--475.Google Scholar
- Leblanc, T.J., Mellor-Crummey, J.M. Debugging parallel programs with instant replay. IEEE Trans. Comput. C-36, 4 (Apr. 1987), 471--482. Google ScholarDigital Library
- Lee, E. The problem with threads. Computer, 39, 5 (May 2006), 33--42. Google ScholarDigital Library
- Musuvathi, M. et al. Finding and reproducing heisenbugs in concurrent programs. In 8th USENIX Symposium on Operating Systems Design and Implementation (OSDI) (Berkeley, California, USA, 2008), USENIX Association. Google ScholarDigital Library
- Olszewski, M., Ansel, J., Amarasinghe, S. Kendo: Efficient deterministic multithreading in software. In 14th International Conference on Architectural Support for Programming Languages and Operating Systems (ASPLOS) (Mar. 2009). Google ScholarDigital Library
- OpenMP Architecture Review Board. OpenMP application program interface version 3.0, May 2008.Google Scholar
- Parker, D.S. Jr. et al. Detection of mutual inconsistency in distributed systems. IEEE Trans. Software Eng. SE-9, 3 (May 1983). Google ScholarDigital Library
- Wei, J., Pu, C. TOCTTOU vulnerabilities in UNIX-style file systems: An anatomical study. In 4th USENIX Conference on File and Storage Technologies (FAST) (Dec. 2005). Google ScholarDigital Library
Index Terms
- Efficient system-enforced deterministic parallelism
Recommendations
Efficient system-enforced deterministic parallelism
OSDI'10: Proceedings of the 9th USENIX conference on Operating systems design and implementationDeterministic execution offers many benefits for debugging, fault tolerance, and security. Current methods of executing parallel programs deterministically, however, often incur high costs, allow misbehaved software to defeat repeatability, and ...
Exploiting parallelism in deterministic shared memory multiprocessing
Multi-threaded programs on shared-memory hardware tend to be non-deterministic, which brings challenges to software debugging and testing. Current deterministic implementations eliminate nondeterminism of multi-threaded programs by trading much ...
Comments