2008 Reports

Static Deadlock Detection in SHIM with an Automata Type Checking System

Vasudevan, Nalini; Edwards, Stephen A.; Smith, Dave Aaron

With the advent of multicores, concurrent programming languages are become more prevelant. Data Races and Deadlocks are two major problems with concurrent programs. SHIM is a concurrent programming language that guarantees absence of data races through its semantics. However, a program written in SHIM can deadlock if not carefully written. In this paper, we present a divide-and-merge technique to statically detect deadlocks in SHIM. SHIM is asynchronous, but we can greatly reduce its state space without loosing precision because of its semantics.