中国科学院软件研究所机构知识库
Advanced  
ISCAS OpenIR  > 软件所图书馆  > 期刊论文
Title:
Dynamic Testing for Deadlocks via Constraints
Author: Cai, Y ; Lu, Q
Keyword: Deadlock triggering ; scheduling ; should-happen-before relation ; constraint ; reliability ; verification
Source: IEEE TRANSACTIONS ON SOFTWARE ENGINEERING
Issued Date: 2016
Volume: 42, Issue:9, Pages:825-842
Indexed Type: SCI
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.
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.
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.
Language: 英语
WOS ID: WOS:000384666100002
Citation statistics:
Content Type: 期刊论文
URI: http://ir.iscas.ac.cn/handle/311060/17306
Appears in Collections:软件所图书馆_期刊论文

Files in This Item:
File Name/ File Size Content Type Version Access License
07423814.pdf(2043KB)----限制开放 联系获取全文

Recommended Citation:
Cai, Y,Lu, Q. Dynamic Testing for Deadlocks via Constraints[J]. IEEE TRANSACTIONS ON SOFTWARE ENGINEERING,2016-01-01,42(9):825-842.
Service
Recommend this item
Sava as my favorate item
Show this item's statistics
Export Endnote File
Google Scholar
Similar articles in Google Scholar
[Cai, Y]'s Articles
[Lu, Q]'s Articles
CSDL cross search
Similar articles in CSDL Cross Search
[Cai, Y]‘s Articles
[Lu, Q]‘s Articles
Related Copyright Policies
Null
Social Bookmarking
Add to CiteULike Add to Connotea Add to Del.icio.us Add to Digg Add to Reddit
所有评论 (0)
暂无评论
 
评注功能仅针对注册用户开放,请您登录
您对该条目有什么异议,请填写以下表单,管理员会尽快联系您。
内 容:
Email:  *
单位:
验证码:   刷新
您在IR的使用过程中有什么好的想法或者建议可以反馈给我们。
标 题:
 *
内 容:
Email:  *
验证码:   刷新

Items in IR are protected by copyright, with all rights reserved, unless otherwise indicated.

 

 

Valid XHTML 1.0!
Copyright © 2007-2019  中国科学院软件研究所 - Feedback
Powered by CSpace