Automated type-based analysis of data races and atomicity
Authors:
Open Access
- 15 June 2005
- conference paper
- Published by Association for Computing Machinery (ACM)
- p. 83-94
Abstract
Concurrent programs are notorious for containing errors that are difficult to reproduce and diagnose at run-time. This motivated the development of type systems that statically ensure the absence of some common kinds of concurrent programming errors including data races and atomicity violations. A method is atomic if every execution of the concurrent program is equivalent to an execution in which the atomic method is executed without being interleaved with other concurrently executed methods. Atomicity is a common correctness requirement in concurrent programs; atomicity violations may indicate incorrect synchronization. This paper presents Extended Parameterized Atomic Java (EPAJ), a type system for specifying and verifying atomicity in Java programs. EPAJ combines Flanagan and Qadeer's atomicity types [11] with a new and significantly more expressive type system for analyzing data races, called Extended Parameterized Race-Free Java (EPRFJ), allowing a more accurate analysis of atomicity. The paper also presents a type discovery algorithm to automatically obtain EPRFJ types, and a static interprocedural type inference algorithm that, given EPRFJ types, infers atomicity types. These algorithms can be incorporated into testing and debugging tools, benefiting users who know nothing about type systems. We report our experience with a prototype implementation.Keywords
This publication has 14 references indexed in Scilit:
- Types for safe lockingACM Transactions on Programming Languages and Systems, 2006
- Type inference for atomicity2005
- Type Inference for Parameterized Race-Free Java2004
- Type Inference Against RacesLecture Notes in Computer Science, 2004
- A type and effect system for atomicity2003
- Framework for testing multi‐threaded Java programsConcurrency and Computation: Practice and Experience, 2003
- Assuring and evolving concurrent programs2002
- Type-based race detection for Java2000
- EraserACM Transactions on Computer Systems, 1997
- A lattice-theoretical fixpoint theorem and its applicationsPacific Journal of Mathematics, 1955