基于共享变量访问频度的多线程程序数据竞争检测方法研究

摘要

随着多核体系结构的崛起，多线程编程目前已经广泛使用到多个领域，如科学计算、桌面应用程序、网络服务器和移动设备。然而，多线程程序设计也给编程人员带来新的挑战和问题。数据竞争是多线程编程中一类常见的错误，开发人员由于没有合理使用同步保护机制造成的这种错误故障十分普遍。基于Happens-before关系的数据竞争动态检测算法能够检测程序实际运行产生的数据竞争，无误报产生，但是存在着检测开销过大、无法实时在线部署等问题。
　　对大量的程序共享变量使用情况监测显示，共享变量访问存在着不一致性，并且越是高频访问的共享变量，其发生数据竞争的概率越小，因为一旦存在数据竞争很容易在早期被程序员发现和修复。基于共享变量访问频度的数据竞争检测算法通过对共享变量访问频度进行统计，结合共享变量的访问频度与数据竞争发生概率之间的关联性，为拥有不同访问频度特征的共享变量分派不同的采样率，从而对不同的变量实施不同采样率的基于Happens-before关系的数据竞争动态检测，可以有效降低动态数据竞争的检测开销。该方法特别适用于长时间作业应用的在线实时动态竞争检测部署，尤其适用于共享变量访问频度不对称场景。
　　实验结果表明，对于DaCapo基准测试程序套件，基于共享变量访问频度的自适应采样动态检测算法，相比单纯地对所有变量使用相同采样率的检测算法，数据竞争检测准确率基本相当，但能有效减少检测算法执行对基准测试程序带来的时间下降和最大内存使用。由此可以看出，利用基于共享变量访问频度的自适应采样动态检测算法，能够有效降低检测开销，解决传统检测方法难以实时在线检测部署的问题。

目录

封面

声明

中文摘要

英文摘要

目录

1 绪论

1.1 课题背景

1.2 国内外研究现状

1.3 研究目的及意义

1.4 主要研究内容

1.5 本文组织结构

2 基于共享变量访问频度的数据竞争动态检测算法设计

2.1基于共享变量访问频度的数据竞争动态检测算法简介

2.2 数据竞争检测基本原理

2.3 事件分析方法

2.4 采样实现方法

2.5自适应采样实现方法

2.6 准确率与开销理论分析

2.7 小结

3 基于共享变量访问频度的数据竞争动态检测算法实现

3.1 基于共享变量访问频度的数据竞争动态检测算法实现平台

3.2 关键技术点

3.3 自适应采样实现

3.4 小结

4 算法测试与分析

4.1 测试环境

4.2 性能测试

4.3 可扩展性和局限性

4.4 小结

5 总结与展望

致谢

参考文献

附录1 攻读学位期间参加的主要科研项目

附录2 攻读学位期间录用会议论文

附录3 攻读学位期间申请的国家发明专利