虛擬時間及其在數據競爭檢測中的應用

禹 振，蘇小紅，王甜甜，馬培軍

(哈爾濱工業大學 計算機科學與技術學院，150001哈爾濱)

虛擬時間能精確刻畫并發事件的發生順序，為并發計算的性質分析［1］、缺陷檢測［2］和故障恢復與調試［3］奠定基礎，因此無論在非共享內存的分布式系統還是共享內存的多核/多處理器并發系統中都得到了廣泛應用.

虛擬時間起源于分布式系統.與內存分離的分布式系統不同，共享內存的多線程并發系統容易遭遇數據競爭［4-5］，即對某一共享內存單元，存在來自不同線程的2個無序訪問，且有1個為寫訪問.檢測數據競爭的關鍵在于檢測對共享內存單元的2個訪問是否是無序的.虛擬時間可以為內存訪問事件分配時鐘，從而2個訪問之間的順序關系能通過比較時鐘獲得.

現已有針對不同應用場景的多種時鐘機制.本文略去各種時鐘機制的應用背景，將它們統稱為虛擬時間;建立抽象的分布式執行模型，統一描述虛擬時間的3種基本實現形式及相關優化與改進技術;討論將虛擬時間應用到共享內存并發系統的數據競爭檢測中需要解決的關鍵問題，并以4個應用實例為例展示基于虛擬時間的數據競爭檢測系統的時鐘分配和競爭檢測機制.

1 問題描述

圖1所示的分布式系統由3臺異構計算機組成，每個計算機上運行一個進程，進程之間消息的下標表示消息發生的順序.在分布式系統中，由于時鐘震蕩頻率不同，不同處理器在同一時間的機器時間可能不同，而在不同時間的機器時間又可能相同，這就導致難以為不同處理器或者進程中發生的事件確定相對順序.例如，假設圖1中進程p1、p2和p3各自所在機器的震蕩頻率分別為6、8和10，則基于局部時鐘的通信圖如圖2所示．其中當p3給p2發送消息msg3時，由于p2的時鐘走的比p3的慢，所以接收到msg3時，本機的時鐘56比msg3附帶的發送時鐘60小．這是不合理的，因為事件的接收時間應遲于其發送時間．

圖1 分布式系統示例

圖2 局部時鐘的通信圖

為解決這一問題，研究者們提出虛擬時間［6-11］，又稱邏輯時間，作為分布式系統的全局時間，使得系統中的事件可以通過比較其發生時被賦予的時鐘來確定事件的先后順序.

2 模型與概念

一個分布式計算，即分布式程序，由n個異步執行的進程p1，p2，…，pi，…，pn構成．每個進程執行3類操作:發送消息、接收消息和本地計算．進程之間由通信網絡互連、不共享內存、只通過傳遞消息進行通信．

定義1(分布式執行的抽象模型) 單個進程pi(1≤i≤n)的執行產生事件序列中的事件具有自然序，即事件按照其發生時的順序構成全序關系．整個分布式計算的執行對應的事件集合E={e|e∈E(pi)，i=1，2，…，n}，事件之間的順序關系由happens-before［10］描述．

對于任意的事件e∈E，Dsp(e)表示事件e的進程號，Usp(e，Dsp(e))表示事件e在事件序列E(pDsp(e))中的序號．假如事件是消息發送操作，則其發送的消息表示為msg對于任意消息表示進程pi發送的操作，表示進程pj接收進程pi發送的的操作．本文定義happens-before關系來為E中事件排序.

定義2(happens-before關系)對于事件ε，ω∈E，ε和ω具有happens-before(簡稱hb)關系，記為ε→ω，當且僅當:1)Dsp(ε)=Dsp(ω)=i，且Usp(ε，i)＜Usp(ω，i);2)Dsp(ε)=i，Dsp(ω)=j，i≠j，且存在消息msg，使得ε=Snd(msg，i)和ω=Rcv(msg，j);3)存在φ∈E，使得ε→φ且φ→ω．

hb關系是反自反的、反對稱的和可傳遞的．如果兩個事件不具有hb關系，則稱之為并發事件.按照hb關系對E中事件進行排序，則得到全體事件的一個偏序圖．

定義3(抽象虛擬時間系統)一個虛擬時間系統的構成為:事件集合E、虛擬時間T和映射函數C．其中C是從E到T的映射T=C(E)，表示為集合E中的每個事件e分配一個虛擬時鐘C(e)，所有事件的虛擬時鐘構成虛擬時間T．

定義4(弱連貫和強連貫［12］)對于一個虛擬時間系統和E中具有hb關系的兩個事件ε和ω，如果ε→ω?C(ε)＜C(ω)，則稱該虛擬時間系統為弱連貫的;如果ε→ω?C(ε)＜C(ω)，則稱之為強連貫的．

在虛擬時間系統的3種基本實現形式中，標量時間系統是弱連貫的，而向量時間系統和矩陣時間系統都是強連貫的.

3 虛擬時間系統

3.1 標量時間系統

標量時間系統由文獻［6］提出.在標量時間系統中，初始時刻各個進程ps(1≤s≤n)的標量時鐘為0，進程ps的當前時鐘記為Cs，消息msg的時鐘為Cmsg，Cmsg為消息發送進程在發送msg時的時鐘．若表示進程ps正要執行的事件，則事件的時鐘根據如下規則更新:

1)如果該事件不是消息接收事件，則Cs=Cs+d(d通常取1)，然后

2)如果該事件是消息msg接收事件，則Cs=

圖3是基于標量時間系統的通信圖.其中，p2根據接收到的消息msg3所攜帶的時鐘60，將自己的時鐘從56改為61;類似地，p1在接收到消息msg4時，將自己的時鐘改為70．標量時間不能保證如果兩個事件的標量時鐘存在大小關系，則兩個事件具有hb關系．例如圖3中，假設p1在標量時鐘18時發生事件a，p2在標量時鐘24時發生事件b，則雖然C(a)＜C(b)，但并不存在a→b．因此標量時間系統是弱連貫的．

圖3 標量時間系統的通信圖

3.2 向量時間系統

向量時間系統由文獻［7-8］提出．假設分布式計算中共有n個進程參與，則初始時刻各個進程pv(1≤v≤n)的向量時鐘為［0，0，…，0］(共n個0)．進程pv的當前時鐘記為Cv，它是一個n維向量，其第v維分量Cv［v］表示進程pv的執行進展，其第k維分量Cv［k］表示進程pv對進程pk的最新知識，即pv是否了解pk發生了多少事件，pv是否了解pk的執行進展．消息msg攜帶消息發送進程發送消息時的時鐘Cmsg表示進程pv正要執行的事件．事件的時鐘根據如下規則更新:

1)如果該事件不是消息接收事件，則僅更新Cv的第v維分量:Cv［v］=Cv［v］+d(d通常取1)，然后

2)如果該事件是消息msg的接收事件，則對于1≤k≤n，Cv［k］=max(Cv［k］，Cmsg［k］);并且Cv［v］=Cv［v］+d(d通常取1)，然后

圖4中，初始時刻3個進程p1，p2和p3的向量時鐘都為［000］．當各自的第1個事件發生后，3個進程的時鐘分別變為［100］，［010］和［001］．當進程p1的第2個事件發生時，根據向量時鐘更新規則1)，該事件被分配時鐘［200］;由于該事件是消息發送事件，故發送的消息msg上攜帶時鐘［200］．當進程p2接收到消息msg時，根據向量時鐘更新規則2)，p2的消息接收事件被分配時鐘［220］．

向量時間系統是強連貫的，任意2個事件a和b，如果C(a)≤C(b)，則a→b;反之，如果a→b，則一定有C(a)≤C(b)．在向量時間系統中，僅根據事件的向量時鐘就可以判斷兩個事件是否具有hb關系．例如圖4中的事件a和b，它們的向量時鐘分別是［340］和［232］，因為既不存在C(a)≤C(b)，又不存在C(b)≤C(a)，故它們是并發事件．

圖4 向量時間系統的通信圖

3.3 矩陣時間系統

矩陣時間系統由文獻［9-11］提出.假設分布式計算中共有n個進程參與，則初始時刻各個進程pm(1≤m≤n)的矩陣時鐘為n×n的0矩陣．進程pm的當前時鐘Cm為一個n×n矩陣，其中:元素Cm［m，m］表示進程pm的執行進展，Cm［m，k］(1≤k，m≤n)表示進程pm對進程pk執行進展的最新知識，Cm［k，l］(1≤k，l，m≤n)表示進程pm最近所知道的對進程pk對進程pl執行進展的最新知識的知識．消息msg攜帶消息發送進程發送消息時的時鐘Cmsg，表示進程pm正要執行的事件，其時鐘根據如下規則更新:

1)如果該事件不是消息接收事件，則僅更新Cm的第m行第m列元素:Cm［m，m］=Cm［m，m］+d(d通常取1)，然后C()=Cm;

2)如果該事件是消息msg的接收事件，且該消息來自進程pj(1≤j≤n，j≠k)，則1≤k≤n，Cm［m，k］=max(Cm［m，k］，Cmsg［j，k］);1≤k，l≤n，Cm［k，l］=max(Cm［k，l］，Cmsg［k，l］);Cm［m，m］=Cm［m，m］+d(d通常取1)，然后C()=Cm．

圖5中，初始時刻3個進程p1，p2和p3的矩陣時鐘都為當各自的第1個事件發生后，3個進程的時鐘分別變為，當進程p1的第2個事件發生時，根據矩陣時鐘更新規則1)，該事件被分配時鐘;由于該事件是消息發送事件，故發送的消息msg上攜帶時鐘當進程p2接收到消息msg時，根據矩陣時鐘更新規則2)，p2的消息接收事件被分配為時鐘

圖5 矩陣時間系統的通信圖

矩陣時間系統是強連貫的，任意事件a和b，如果a→b當且僅當C(a)≤C(b)．例如圖5中的事件a和b，它們的矩陣時鐘分別是和，既不存在C(a)≤C(b)，又不存在C(b)≤C(a)，因此它們是并發事件．

4 虛擬時間的改進與優化技術

4.1 丟棄過時時鐘

當某個事件發生時，并不需要與所有已發生的事件進行時鐘比較，而只需要與一些事件進行比較即可，因為另一些事件在該事件發生前或者發生時已經“過時”.

4.1.1 列投影技術［12］

圖6使用列投影技術丟棄過時時鐘，矩陣下方的橫線表示對矩陣的每一列求取最小值．進程p3的第2個事件e23發生時，被賦予矩陣時鐘由于，因此p3知道所有進程p1，p2，p3都知道進程p1已執行了2個事件．此后任何事件e的時鐘的第1行第1列肯定≥2，且→e．因此p1的前2個事件a和b在今后的時鐘比較時可以忽略．

圖6 列投影技術丟棄過時時鐘

4.1.2 探詢(Snooping)技術［13］

列投影技術對過時信息的計算依賴于事件的矩陣時鐘，而后者只能根據進程內執行進展或者進程間消息傳遞而更新，速度較慢.這就導致列投影技術對系統全局進展的最新知識較滯后.鑒于此，探詢技術不再被動等待進程間的消息傳遞，而是主動探詢各個進程的最新進展，從而獲得對系統全局進展的實時知識.圖7使用探尋技術對圖4所示的通信圖進行過時時鐘丟棄.進程p1的第2個事件的時鐘在圖4中是［200］，在圖7中的snooping時鐘是．探尋技術在計算事件b的snooping時鐘時，主動去詢問進程p2和p3的當前時鐘，分別得到［010］和［001］，然后結合p1的當前時鐘構成b的snooping時鐘.一旦得到事件的snooping時鐘，探詢技術就采用列投影技術來計算可被丟棄的時鐘.在p3的第2個事件發生時，探尋技術丟棄進程p1的前2個事件的時鐘，這與列投影技術一樣;在p1的第3個事件發生時，探尋技術丟棄p2的前3個事件的時鐘，這是列投影技術無法做到的．

圖7 探詢技術丟棄過時時鐘

4.2 減少消息帶寬

文獻［14］發現如果從上次向進程pj發送消息以來，進程pi的時鐘向量的第i1，i2，…，in1個分量變為v1，v2，…，vn1，則下次pi向pj發送消息時，只需發送發生變化的分量＜(i1，v1)，(i2，v2)，…，(in1，vn1)＞．進程pj接收到該壓縮格式的向量時鐘后，如圖8所示更新自己的時鐘:對于k=i1，i2，…，in1，Cj［k］=max(Cj［k］，vk)．

圖8使用Singhal技術傳遞消息.其中p3傳遞第3個消息給p2時，消息上附帶的信息是＜(3，4)，(4，1)＞．這是由于上次p3給p2傳遞消息時，p3的時鐘是［0020］，而當前p3時鐘是［0041］，向量時鐘的第3項從2變為4，第4項從0變為1．p2接收到該消息后，將自己的時鐘從［1320］變為［1441］．

圖8 使用Singhal技術傳遞消息

4.3 可折疊時鐘

可折疊時鐘［15］(accordion clock)只維護對于當前活躍的進程的知識.對于尚未啟動或者已經結束的進程，可折疊時鐘不維護對于它們的任何信息.可折疊時鐘的時鐘長度隨著分布式計算中進程的啟動和結束而伸展與收縮，從而總是維護對于“必要”進程的知識.

可折疊時鐘的分量具有形式(s，pid)，其中s表示進程pid的本地時鐘．圖9使用可折疊時鐘為分布式計算中的事件進行排序．其中，初始時刻3個進程的p1，p2和p3的可折疊時鐘都為空．當各自的第1個事件發生后，3個進程的時鐘分別變為［(1，1)］，［(1，2)］和［(1，3)］．當進程的第2個事件發生時，該事件被分配時鐘［(2，1)］;由于該事件是消息發送事件，故發送的消息msg上攜帶時鐘［(2，1)］．當進程p2接收到消息msg時，p2的消息接收事件被分配時鐘［(2，1)，(2，2)］．

圖9 可折疊時間系統的通信圖

5 虛擬時間的數據競爭檢測

將虛擬時間應用在數據競爭檢測中，面臨3個問題:1)哪些事件是消息發送和接收事件;2)哪些事件需要為其分配時鐘;3)哪些事件需要進行并發檢測.已有研究［16-19］將以下事件作為消息發送/接收事件:fork/線程入口點，線程退出點/join，unlock/lock，signal/wait;為以下事件分配時鐘:消息發送/接收事件，內存訪問事件;對以下事件進行并發檢測:內存訪問事件.

本文介紹了基于向量時間的4個數據競爭檢測系統，即Dij+系統，FastClock系統，Weaker-than系統和Threadset系統.

5.1 Dij+系統

Dij+系統為每個共享變量x維護2個時鐘向量awx和arx，分別代表各個線程對x的最新寫訪問和讀訪問.Dij+如下更新共享變量的2個時鐘向量:在t的某個時間幀中，a是對x的第1個訪問，如果a是讀訪問，則arx［t］=Ct［t］;如果a是寫訪問，則awx［t］=Ct［t］．Dij+在t執行完a后，檢測數據競爭:是否存在某個線程u，使得如果a是讀訪問，則awx［u］＞Ct［u］;如果a是寫訪問，則awx［u］＞Ct［u］或者arx［u］＞Ct［u］．

Dij+能保證若x上存在數據競爭，則至少一個會被檢測出來.圖10解釋了Dij+的時鐘更新機制，其中所有事件都是對x的寫訪問事件.在圖10(a)中，來自不同線程的兩個事件a和b具有hb關系，則按照hb定義，c1和c2也與b具有hb關系，因此無需保存c1和c2對x的訪問信息．在圖10(b)中，a和b是并發的，而且c1和c2也可能與b是并發的;這種情況下Dij+可能漏檢c1(或c2)和b構成的數據競爭，但能保證檢測到a和b這一對數據競爭．

圖10 Dij+時鐘更新機制的原因

5.2 Fastclock系統

若有n個線程，則Dij+對線程t的每個讀寫操作，需要耗費O(n)時間來檢測它是否與其他線程的讀寫操作存在數據競爭．假如事先知道某個線程w對共享變量x的訪問是到當時為止所有線程對x的最新訪問，則當線程t對x進行訪問a時，只需進行以下比較來檢測數據競爭:awx［w］＞Ct［w］或者arx［w］＞Ct［w］．此比較的時間復雜度是常量級的，即O(1)．因此awx和arx只需存儲最新讀寫共享變量的線程的本地時鐘和線程號，稱為epoch(形式為c@t)，存儲空間也由O(n)降為O(1)．

FastClock時鐘更新機制如下:如果多個讀訪問并發訪問x，則arx是epoch形式的向量時鐘，以同時記錄多個讀訪問;如果多個讀訪問順序訪問x，則arx是標量時鐘;如果多個讀訪問并發訪問x后，遇到對x的寫訪問，則arx從向量時鐘變為變量時鐘;無論多個寫訪問順序或者并發訪問x，awx都是標量時鐘.FastClock競爭檢測機制與Dij+類似.

5.3 Weaker-than系統

對于給定的2個事件p和q，以及將來發生的任何事件r，如果IsRace(q，r)蘊含IsRace(p，r)，則說事件p相對于事件q來說受到(鎖)的保護更弱(weaker-than)，更易于與其他事件構成數據競爭．其中IsRace(e1，e2)用于判斷2個訪存事件e1和e2是否構成數據競爭對．對于p和q，Weaker-than只保留更弱者p，而丟棄q，并且將來發生的事件r，都將與p進行hb關系比較，而不與q進行比較．Weaker-than系統與Dij+系統一樣，保證如果共享變量上x上存在數據競爭，則它至少會檢測到其中一個．

5.4 Threadset系統

與Dij+類似，Threadset為每個共享變量x維護一個并發訪問集Sx，其中保存著epoch形式的時鐘.與Dij+不同的是，Sx不區分共享變量的讀訪問與寫訪問，因此可能將2個讀訪問報告為數據競爭．Sx使用可折疊時鐘表示，其大小隨并發訪問的數目增大或者縮小．Sx中使用hb關系來檢測兩個訪問是否并發:當線程t讀訪問或者寫訪問x時，Threadset將(t，Ct(t))添加到Sx中，然后檢查是否存在(u，k)∈Sx，使得k≤Ct(u);如果存在的話，則說明(u，k)代表的訪問與本訪問具有hb關系，故從Sx中刪除(u，k)，Sx中剩余元素都是有可能相互并發的訪問．但單獨使用Sx，Threadset不能判斷是否有數據競爭發生，還需要x的鎖集信息Lx．Threadset結合hb算法和鎖集算法［20-21］來檢測數據競爭．

6 結 論

1)提出虛擬時間和虛擬時鐘的概念，給出虛擬時間系統的形式化定義，對虛擬時間和虛擬時鐘的概念作出區分.

2)建立抽象的分布式執行模型，在同一框架下統一描述虛擬時間的3種基本實現形式和相關改進優化技術.

3)總結將虛擬時間應用到數據競爭檢測時需要解決的關鍵問題，以4個數據競爭檢測器為例說明基于虛擬時間的數據競爭檢測系統的時鐘分配和競爭檢測機制.

4)本模型清晰準確地刻畫虛擬時間的不同實現形式，有助于降低基于虛擬時間檢測數據競爭的應用難度.

［1］羅軍，王宏，李文生.基于向量時鐘模型的NoSQL最終一致性的研究［J］.計算機工程與應用，2013，49(23):100-102.

［2］宋慶禎.開放式協同環境下分布式事務提交和恢復機制的研究［D］.廣西:廣西大學，2005.

［3］劉磊，黃河，唐志敏.支持多核并行程序確定性重放的高效訪存沖突記錄方法［J］.計算機研究與發展，2011，49(1):64-75.

［4］LU S，PARK S，SEO E，et al.Learning from mistakes:a comprehensive study on real world concurrency bug characteristics［J］.ACM SIGPLAN Notices，2008，43(3):329-339.

［5］霍瑋，于洪濤，馮曉兵，等.靜態檢測中斷驅動程序的數據競爭［J］.計算機研究與發展，2011，48(12):2290-2299.

［6］LAMPORT L.Time，clocks，and the ordering of events in a distributed system［J］.Communications of the ACM，1978，21(7):558-565.

［7］MATTERN F.Virtual time and global states of distributed systems［J］.Parallel and Distributed Algorithms，1989，1(23):215-226.

［8］FIDGE C.Logical time in distributed computing systems［J］.Computer，1991，24(8):28-33.

［9］FISCHER M J，MICHAEL A.Sacrificing serializability to attain high availability of data in an unreliable network［C］//Proceedings of the 1st ACM SIGACT-SIGMOD symposium on Principles of database systems.New York:ACM，1982:70-75.

［10］WUU G T J，BERNSTEIN A J.Efficient solutions to the replicated log and dictionary problems［J］.Operating systems review，1986，20(1):57-66.

［11］SARIN S K，LYNCH N A.Discarding obsolete information in a replicated database system［J］.IEEE Transactions on Software Engineering.1987，13(1):39-47.

［12］RAYNAL M，SINGHAL M.Logical time:Capturing causality in distributed systems［J］.Computer，1996，29(2):49-56.

［13］DE BOSSCHERE K，RONSSE M.Clock snooping and its application in on-the-fly data race detection［C］//Proceedings of the 3rd International Symposium on Parallel Architectures，Algorithms，and Networks.Piscataway，NJ:IEEE，1997:324-330.

［14］SINGHAL M，KSHEMKALYANI A.An efficient implementation of vector clocks［J］.Information Processing Letters，1992，43(1):47-52.

［15］CHRISTIAENS M，DE BOSSCHERE K.Accordion clocks:Logical clocks for data race detection［C］//Proceedings of the 7th International European Conference on Parallel Processing.Berlin，Heidelberg:Springer，2001:494-503.

［16］CHOI J D，LEE K，LOGINOV A，et al.Efficient and precise datarace detection for multithreaded object oriented programs［J］.ACM SIGPLAN Notices，2002，37(5):258-269.

［17］FLANAGAN C，FREUND S N.FastTrack:efficient and precise dynamic race detection［J］.ACM Sigplan Notices，2009，44(6):121-133.

［18］POZNIANSKY E，SCHUSTER A.MultiRace:efficient on-the-fly data race detection in multithreaded C++programs［J］.Concurrency and Computation:Practice and Experience，2007，19(3):327-340.

［19］YU Y，RODEHEFFER T，CHEN W.Racetrack:efficient detection of data race conditions via adaptive tracking［J］.ACM SIGOPS Operating Systems Review，2005，39(5):221-234.

［20］ZHOU P，TEODORESCU R，ZHOU Y.HARD:Hardware-assisted lockset-based race detection［C］//Proceedings of the 13th International Symposium on High Performance Computer Architecture.Piscataway，NJ:IEEE，2007:121-132.

［21］XIE Xinwei，XUE Jingling，ZHANG Jie.Acculock:Accurate and efficient detection of data races［J］.Software:Practice and Experience，2013，43(5):543-576.