Stefan Savage
Michael Burrows
Abstract
Multithreaded programming is difficult and error prone. It is easy to make a mistake in synchronization that produces a data race, yet it can be extremely hard to locate this mistake during debugging. This article describes a new tool, called Eraser, for dynamically detecting data races in lock-based multithreaded programs. Eraser uses binary rewriting techniques to monitor every shared-monory reference and verify that consistent locking behavior is observed. We present several case studies, including undergraduate coursework and a multithreaded Web search engine, that demonstrate the effectiveness of this approach.
- BERSHAD, B. N., SAVAGE, S., PARDYAK, P., SIRER, E. G., FIUCZYNSKI, M., BECKER, D., EGGERS, S., AND CHAMBERS, C. 1995. Extensibility, safety and performance in the SPIN operating system. In Proceedings of the 15th ACM Symposium on Operating Systems Principles (Copper Mountain, Colo., Dec.). ACM, New York, 267-284. Google Scholar
- DETLEFS, D. L., LEINO, R. M., NELSON, G., AND SAXE, J.B. 1997. Extended static checking. Tech. Rep. Res. Rep. 149, Systems Research Center, Digital Equipment Corp., Palo Alto, Calif.Google Scholar
- DINNING, A. AND SCHONBERG, E. 1990. An empirical comparison of monitoring algorithms for access anomaly detection. In Proceedings of the 2nd ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming (Seattle, Wash., Mar.). ACM, New York, 1-10. Google Scholar
- DINNING, n. AND SCHONBERG, E. 1991. Detecting access anomalies in programs with critical sections. In Proceedings of the ACM/ ONR Workshop on Parallel and Distributed Debugging. ACM SIGPLAN Not. 26, 12 (Dec.), 85-96. Google Scholar
- HOARE, C. 1974. Monitors: An operating system structuring concept. Commun. ACM 17, 10 (Oct.), 549-557. Google ScholarDigital Library
- KLEIMAN, S. AND EYKHOLT, J. 1995. Interrupts as threads. ACM Oper. Syst. Rev. 29, 2 (Apr.), 21-26. Google ScholarDigital Library
- LAMPORT, L. 1978. Time, clocks, and the ordering of events in a distributed system. Commun. ACM 21, 7 (July), 558-565. Google ScholarDigital Library
- LAMPSON, B. AND REDELL, D. 1980. Experiences with processes and monitors in Mesa. Commun. ACM 23, 2 (Feb.), 104-117. Google ScholarDigital Library
- LEE, E. K. AND THEKKATH, C.A. 1996. Petal: Distributed virtual disks. In Proceedings of the 7th International Conference on Architectural Support for Programming Languages and Operating Systems (Cambridge, Mass, Oct.). ACM, New York, 84-93. Google Scholar
- MANASSE, M. S. AND NELSON, G. 1991. Trestle reference manual. Res. Rep. 68, Systems Research Center, Digital Equipment Corp., Palo Alto, Calif.Google Scholar
- MELLOR-CRUMMEY, g. 1991. On-the-fly detection of data races for programs with nested fork-join parallelism. In Proceedings of the 1991 Supercomputer Debugging Workshop (Albuquerque, N. Mex., Nov.). 1-16. Google Scholar
- MELLOR-CRUMMEY, g. 1993. Compile-time support for efficient data race detection in shared-memory parallel programs. In Proceedings of the ACM/ ONR Workshop on Parallel and Distributed Debugging (San Diego, Calif., May). ACM, New York, 129-139. Google Scholar
- NETZER, R. H. B. 1991. Race condition detection for debugging shared-memory parallel programs. Ph.D. thesis, Univ. of Wisconsin-Madison, Madison, Wisc. Google Scholar
- PERKOVIC, D. AND KELEHER, P. 1996. Online data-race detection via coherency guarantees. In Proceedings of the 2nd USENIX Symposium on Operating Systems Design and Implementation (Seattle, Wash., Oct.). USENIX Assoc., Berkeley, Calif., 47-58. Google Scholar
- SCALES, D. J., GHARACHORLOO, K., AND THEKKATH, C. A. 1996. Shasta: A low overhead, software-only approach for supporting fine-grain shared memory. In Proceedings of the 7th International Conference on Architectural Support for Programming Languages and Operating Systems (Cambridge, Mass., Oct.). ACM, New York, 174-185. Google Scholar
- SRIVASTAVA, A. AND EUSTACE, A. 1994. ATOM" A system for building customized program analysis tools. In Proceedings of the 1994 ACM SIGPLAN Conference on Programming Language Design and Implementation (Orlando, Fla., June). ACM, New York, 196-205. Google Scholar
- SUNSOFT. 1994. lock_lint user's guide. SunSoft Manual, Sun Microsystems, Inc., Palo Alto, Calif.Google Scholar
Index Terms
- Eraser: a dynamic data race detector for multithreaded programs
Recommendations
TRADE: Precise Dynamic Race Detection for Scalable Transactional Memory Systems
As other multithreaded programs, transactional memory (TM) programs are prone to race conditions. Previous work focuses on extending existing definitions of data race for lock-based applications to TM applications, which requires all transactions to be ...
RecPlay: a fully integrated practical record/replay system
This article presents a practical solution for the cyclic debugging of nondeterministic parallel programs. The solution consists of a combination of record/replay with automatic on-the-fly data race detection. This combination enables us to limit the ...
The theory of deadlock avoidance via discrete control
POPL '09Deadlock in multithreaded programs is an increasingly important problem as ubiquitous multicore architectures force parallelization upon an ever wider range of software. This paper presents a theoretical foundation for dynamic deadlock avoidance in ...
Comments