论文部分内容阅读
随着多核处理器的发展和多线程程序的普及,多线程技术的应用越来越广泛。但是在多线程程序中,当多个线程之间运行推进顺序不合适时,就可能造成死锁。死锁会导致多线程程序无法运行,甚至软件系统崩溃。因此如何有效地检测多线程程序死锁是软件测试和开发领域的重要研究课题之一。目前主流的静态死锁检测方法主要包括基于并发模型分析和基于数据流分析。基于数据流分析的死锁检测结果因为保守分析容易造成误判,基于并发模型分析不能很好地支持多线程程序建模,并且大部分研究主要针对Java程序的死锁检测,对使用Posix线程库开发的C多线程程序研究不多。针对这些问题,本文基于Posix线程库开发的C多线程程序,在调研现有死锁检测技术的基础上,结合程序静态分析技术提出一种基于Petri网模型的多线程死锁检测方法,该方法适用于两个或者多个线程的死锁检测。论文的主要工作如下：1)对多线程程序进行指针别名分析。在Linux平台上使用GCC编译器对程序预处理,得到控制流图CFG、SSA形式的中间代码和函数依赖关系。然后基于SSA形式的中间代码进行指针别名分析,得到锁、函数指针的可能值和所有线程的函数调用图。2)描述多线程程序转换为Petri网模型的方法。在得到函数调用图的基础上对函数调用图进行优化,目的是减少程序Petri网的规模。优化过程包括删除与锁操作无关的函数、函数内的优化和使用lockset技术分析锁相关函数等。然后对锁操作函数和优化后的函数调用图进行Petri网建模,这样得到一个与源程序并发语义等价的Petri网模型。3)设计一种基于Petri网的死锁检测算法。首先根据多线程程序中锁的使用特点,定义一个用来描述互斥锁、自旋锁和读写锁操作的特殊Petri网。然后分析这个特殊Petri网的动态性质,并提出基于混合整数规划的死锁检测算法,通过求解该算法来检测程序是否存在死锁。最后从理论上证明算法是否有解与多线程程序是否死锁之间的等价关系。4)基于上述方法的实现,本文对Apache、OpenLDAP、FastDFS、SQLite和Pfscan等多线程程序进行测试,实验结果表明本文提出的死锁检测方法能够有效地检测多线程程序中潜在的死锁。与已有的死锁检测研究相比,该方法的时间开销更小,适合处理大规模的多线程程序。