中国科学院软件研究所机构知识库
Advanced  
ISCAS OpenIR  > 计算机科学国家重点实验室  > 学位论文
题名:
并发数据结构可线性化错误的定位研究
作者: 张振亚
答辩日期: 2017-05-21
导师: 张昱
专业: 计算机软件与理论
授予单位: 中国科学院大学
授予地点: 北京
学位: 硕士
摘要:
随着多核技术的发展,多线程并发程序在现代软件应用中发挥着越来越重要的作用。与传统的顺序程序相比,并发程序将任务分配到多个线程之上并发执行,提高了程序执行效率,也充分发挥了多核技术所带来的优势。
然而,并发程序的执行具有不确定性,即,相同的程序多次执行所得到的输出往往是不同的。这种性质使得程序的错误不容易被检测,并且即使被检测到也不容易重现以及定位。
可线性化是一种重要的并发程序正确性的标准。当前,已有的工作主要致力于基于粗粒度迹模型对并发执行历史的可线性化性质进行检测。然而,这些工作无法进一步对可线性化错误进行分析,进而确定引发错误的根本原因。而基于细粒度模型的错误定位工作不适合应用于大规模测试用例,且这些工作主要针对于一般的并发错误而非可线性化错误。
本文针对并发数据结构可线性化错误的定位问题,设计了一个包含粗粒度与细粒度两个层面的解决方案。
在粗粒度层面,我们的目的是构造一个包含操作数量较少,但足够引发可线性化错误的测试用例。这个工作分为两个阶段:首先,获取一条不可线性化的并发执行历史;然后,在这条执行历史中定位至引发这个可线性化错误的并发操作集合,从而构造目标测试用例。我们还提出了一系列优化措施,以提高错误定位的能力与效率。
在细粒度层面,我们的目的是找出对可线性化错误的产生有着决定性作用的数据竞争。基于细粒度迹模型,我们提出了关键数据竞争序列的概念来刻画程序错误,并构建了一种交叉树模型,其中包含了并发程序所有可能的细粒度执行,每个结点对应一个数据竞争。我们根据每条路径的可线性化性质来标记各个结点,然后说明了如何在其中识别关键数据竞争序列。
基于以上工作,我们开发了两个原型工具,CGVT与FGVT,分别用于粗粒度及细粒度的错误定位。实验结果证明,它们能够对实际的Java程序进行检测及定位,并且有着良好的效率。
内容类型: 学位论文
URI标识: http://ir.iscas.ac.cn/handle/311060/18969
Appears in Collections:计算机科学国家重点实验室 _学位论文

Files in This Item:
File Name/ File Size Content Type Version Access License
毕业论文-张.pdf(1603KB)学位论文--限制开放 联系获取全文

作者单位: 中国科学院软件研究所

Recommended Citation:
张振亚. 并发数据结构可线性化错误的定位研究[D]. 北京. 中国科学院大学. 2017-05-21.
Service
Recommend this item
Sava as my favorate item
Show this item's statistics
Export Endnote File
Google Scholar
Similar articles in Google Scholar
[张振亚]'s Articles
CSDL cross search
Similar articles in CSDL Cross Search
[张振亚]‘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-2018  中国科学院软件研究所 - Feedback
Powered by CSpace