虚拟时间及其在数据竞争检测中的应用

禹振, 苏小红, 王甜甜, 马培军

(哈尔滨工业大学 计算机科学与技术学院, 150001 哈尔滨)



摘要:

为将虚拟时间机制应用于数据竞争检测,提出描述虚拟时间3种基本实现形式的统一模型. 先建立分布式执行的抽象模型,在此模型下统一描述虚拟时间的3种基本实现形式,即标量时间系统、向量时间系统和矩阵时间系统,并以向量时间系统和矩阵时间系统为例介绍虚拟时间的4种优化技术,最后讨论将虚拟时间应用到共享内存并发系统的数据竞争检测中需要解决的问题以及4个应用实例. 结果表明,提出的模型能统一描述虚拟时间的不同实现形式,并能降低基于虚拟时间检测数据竞争的应用难度.

关键词:  虚拟时间  逻辑时间  向量时钟  并发缺陷  数据竞争

DOI：10.11918/j.issn.0367-6234.2015.01.011

分类号:TP311

基金项目:国家自然科学基金(61173021;61202092).



Virtual time and its application to data race detection

YU Zhen, SU Xiaohong, WANG Tiantian, MA Peijun

(School of Computer Science and Technology, Harbin Institute of Technology, 150001 Harbin, China)

Abstract:

Aiming at applying virtual time mechanism to data race detection, a model is proposed to uniformly describe different implementation forms of virtual time. We firstly establish an abstract model for a distributed execution. Based on this model, we give a unified description on virtual time’s three basic implementation forms: scalar time system, vector time system and matrix time system. Furthermore, we take vector time system and matrix time system for examples to illustrate four optimization techniques for virtual time. At last, we discuss the problems to be solved when applying virtual time to data races detection in shared-memory concurrent systems and four application examples. The model proposed in this paper unifies different implementation forms of virtual time and reduces the difficulty of applying virtual time to data race detection.

Key words:  virtual time  logical time  vector clock  concurrency bug  data race