并行程序的原子性验证算法研究  

Atomicity detection algorithms for concurrent programs

作　　者：林菲[1] 

机构地区：[1]杭州电子科技大学软件学院,浙江杭州310018

出　　处：《计算机工程与设计》2010年第2期352-355,共4页Computer Engineering and Design

基　　金：浙江省教育厅2008年科研基金项目(Y200804394)

摘　　要：原子性保证并行程序中的多线程以正确方式交互,大多主流的编程语言都没有提供确保原子性的内部机制。为了提高测试程序原子性的效率与准确性,提出了一种自动检测并行程序中违反原子性错误的算法。基于状态转换,建立了原子性的形式化定义。在此基础上,利用线程锁设计了具体的算法模型以及实现中需注意的细节,同时给出自动修正错误的设计思路和建议。结合常用的基准数据结构,对模型和算法进行了实验,实验结果表明了该算法的正确性和有效性。Atomicity is an important specification that enables multi-threaded programs interact correctly, but most modem programming languages provide no built-in support to ensure atomicity. To improve the efficiency and correctness ofatomicity detection, an algorithm to detect atomicity violations is presented. The formalized definition of atomicity is established by means of states transition, based on which algorithm model and implementation method are constructed. Design method for automated code generation to correct the detected errors is also given. The correctness and practicability of algorithm is proved by experimental results.

关 键 词：并行程序 原子性 状态 死锁 代码生成 

分 类 号：TP301[自动化与计算机技术—计算机系统结构]