Institutional Repository
| Dynamic Testing for Deadlocks via Constraints | |
| Cai, Y; Lu, Q | |
| 2016 | |
| Source | IEEE TRANSACTIONS ON SOFTWARE ENGINEERING
 |
| ISSN | 0098-5589 |
| Volume | 42Issue:9Pages:825-842 |
| English Abstract | Existing deadlock detectors are either not scalable or may report false positives when suggesting cycles as potential deadlocks. Additionally, they may not effectively trigger deadlocks and handle false positives. We propose a technique called ConLock(+), which firstly analyzes each cycle and its corresponding execution to identify a set of scheduling constraints that are necessary conditions to trigger the corresponding deadlock. The ConLock(+) technique then performs a second run to enforce the set of constraints, which will trigger a deadlock if the cycle is a real one. Or if not, ConLock(+) reports a steering failure for that cycle and also identifies other similar cycles which would also produce steering failures. For each confirmed deadlock, ConLock(+) performs a static analysis to identify conflicting memory access that would also contribute to the occurrence of the deadlock. This analysis is helpful to enable developers to understand and fix deadlocks. ConLock(+) has been validated on a suite of real-world programs with 16 real deadlocks. The results show that across all 811 cycles, ConLock(+) confirmed all of the 16 deadlocks with a probability of >= 80 percent. For the remaining cycles, ConLock(+) reported steering failures and also identified that five deadlocks also involved conflicting memory accesses.; Existing deadlock detectors are either not scalable or may report false positives when suggesting cycles as potential deadlocks. Additionally, they may not effectively trigger deadlocks and handle false positives. We propose a technique called ConLock(+), which firstly analyzes each cycle and its corresponding execution to identify a set of scheduling constraints that are necessary conditions to trigger the corresponding deadlock. The ConLock(+) technique then performs a second run to enforce the set of constraints, which will trigger a deadlock if the cycle is a real one. Or if not, ConLock(+) reports a steering failure for that cycle and also identifies other similar cycles which would also produce steering failures. For each confirmed deadlock, ConLock(+) performs a static analysis to identify conflicting memory access that would also contribute to the occurrence of the deadlock. This analysis is helpful to enable developers to understand and fix deadlocks. ConLock(+) has been validated on a suite of real-world programs with 16 real deadlocks. The results show that across all 811 cycles, ConLock(+) confirmed all of the 16 deadlocks with a probability of >= 80 percent. For the remaining cycles, ConLock(+) reported steering failures and also identified that five deadlocks also involved conflicting memory accesses. |
| Indexed Type | SCI |
| Keyword | Deadlock Triggering Scheduling Should-happen-before Relation Constraint Reliability Verification |
| Department | Chinese Acad Sci, Inst Software, State Key Lab Comp Sci, Beijing, Peoples R China. Chinese Acad Sci, Inst Software, Technol Ctr Software Engn, Beijing, Peoples R China. |
| Language | 英语 |
| WOS ID | WOS:000384666100002 |
| Citation statistics | |
| Content Type | 期刊论文 |
| URI | http://ir.iscas.ac.cn/handle/311060/17306 |
| Collection | 中国科学院软件研究所 |
| Recommended Citation GB/T 7714 | Cai, Y,Lu, Q. Dynamic Testing for Deadlocks via Constraints[J]. IEEE TRANSACTIONS ON SOFTWARE ENGINEERING,2016,42(9):825-842. |
| APA | Cai, Y,&Lu, Q.(2016).Dynamic Testing for Deadlocks via Constraints.IEEE TRANSACTIONS ON SOFTWARE ENGINEERING,42(9),825-842. |
| MLA | Cai, Y,et al."Dynamic Testing for Deadlocks via Constraints".IEEE TRANSACTIONS ON SOFTWARE ENGINEERING 42.9(2016):825-842. |
| Files in This Item: | ||||||
| File Name/Size | DocType | Version | Access | License | ||
| 07423814.pdf（2043KB） | 开放获取 | License | Application Full Text | |||
Items in the repository are protected by copyright, with all rights reserved, unless otherwise indicated.
Edit Comment