Loading...
Please wait, while we are loading the content...
Similar Documents
Compositional deadlock detection for rendezvous communication (2009)
| Content Provider | CiteSeerX |
|---|---|
| Author | Shao, Baolin Vasudevan, Nalini Edwards, Stephen A. |
| Description | Concurrent programming languages are growing in importance with the advent of multi-core systems. However, concurrent programs suffer from problems, such as data races and deadlock, absent from sequential programs. Unfortunately, traditional race and deadlock detection techniques fail on both large programs and small programs with complex behaviors. In this paper, we present a compositional deadlock detection technique for a concurrent language—SHIM—in which tasks run asynchronously and communicate using synchronous CSP-style rendezvous. Although SHIM guarantees the absence of data races, a SHIM program may still deadlock if the communication protocol is violated. Our previous work used NuSMV, a symbolic model checker, to detect deadlock in a SHIM program, but it did not scale well with the size of the problem. In this work, we take an incremental, divide-and-conquer approach to deadlock detection. In practice, we find our procedure is faster and uses less memory than the existing technique, especially on large programs, making our algorithm a practical part of the compilation chain. |
| File Format | |
| Language | English |
| Publisher Date | 2009-01-01 |
| Publisher Institution | In Proceedings of the International Conference on Embedded Software (Emsoft |
| Access Restriction | Open |
| Subject Keyword | Complex Behavior Compilation Chain Previous Work Data Race Small Program Symbolic Model Checker Concurrent Language Shim Divide-and-conquer Approach Shim Program Communication Protocol Traditional Race Compositional Deadlock Detection Compositional Deadlock Detection Technique Multi-core System Deadlock Detection Technique Sequential Program Practical Part Large Program Rendezvous Communication Concurrent Programming Language Concurrent Program |
| Content Type | Text |
| Resource Type | Article |
