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

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

虚拟时间能精确刻画并发事件的发生顺序，为并发计算的性质分析［1］、缺陷检测［2］和故障恢复与调试［3］奠定基础，因此无论在非共享内存的分布式系统还是共享内存的多核/多处理器并发系统中都得到了广泛应用.

虚拟时间起源于分布式系统.与内存分离的分布式系统不同，共享内存的多线程并发系统容易遭遇数据竞争［4-5］，即对某一共享内存单元，存在来自不同线程的2个无序访问，且有1个为写访问.检测数据竞争的关键在于检测对共享内存单元的2个访问是否是无序的.虚拟时间可以为内存访问事件分配时钟，从而2个访问之间的顺序关系能通过比较时钟获得.

现已有针对不同应用场景的多种时钟机制.本文略去各种时钟机制的应用背景，将它们统称为虚拟时间;建立抽象的分布式执行模型，统一描述虚拟时间的3种基本实现形式及相关优化与改进技术;讨论将虚拟时间应用到共享内存并发系统的数据竞争检测中需要解决的关键问题，并以4个应用实例为例展示基于虚拟时间的数据竞争检测系统的时钟分配和竞争检测机制.

1 问题描述

图1所示的分布式系统由3台异构计算机组成，每个计算机上运行一个进程，进程之间消息的下标表示消息发生的顺序.在分布式系统中，由于时钟震荡频率不同，不同处理器在同一时间的机器时间可……