并发数据结构可线性化错误的定位研究

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

条目包含的文件
文件名称/大小	文献类型	版本类型	开放类型	使用许可
毕业论文-张.pdf（1603KB）	学位论文		开放获取	CC BY-NC-SA	请求全文