基于Happens-before的数据竞争方法汇总 （三）

在上一篇文章中提到了基于happens-before关系的FastTrack动态数据竞争检测方法，这篇文章中介绍的Loft方法是在FastTrack方法上进行了进一步地改进。

Reference :

http://www.cs.cityu.edu.hk/~wkchan/papers/issre2011-cai+chan.pdf

FastTrack方法中对每一个共享内存单元的写访问保留一个epoch形式的轻量级逻辑时钟，而同一个共享内存单元的并发读访问则会暂时保留向量时钟形式的逻辑时钟，在每次写访问之后，会清除读访问的向量时钟。因此整体上来看，对于读写访问的数据竞争检测复杂度为O(1)。但是对于同步操作中的同步对象，向量时钟相关的操作复杂度还是O(n)。

Loft提出了一些特殊的场景，能够最大化的减少同步对象上不必要的一些向量时钟。下图展示了一个很常见的消费者-生产者多线程程序，其中对于pool的访问通过锁保护。可以发现，由于加锁解锁操作在循环中，每迭代一次，m上的向量时钟都会被更新两次，但是假设其中某个线程一直以相同的状态自旋的话，那么m上向量时钟更新就是冗余的。

锁上冗余的向量时钟更新操作

Loft中主要针对锁上的一些向量时钟更新，提出了6中如下图所示常见的场景。

场景示意图

这里为了方便描述，给出两个函数：

• lastThread(m) : 最近释放锁m的线程
• lastLock(t) : 线程t最近释放的锁

场景1

lastThread(m)=t，即最近释放锁m的线程是t，这里e1表示的就是释放m操作rel(m)，而e*表示的就是获得m操作acq(m)。当e1发生的时候，我们会将当前线程t的向量时钟拷贝给锁m，而当e*发生的时候，由于中间没有其他线程获得过m，因此m上的向量时钟不会改变，并且当前线程t在e1->e*的过程中向量时钟只会递增，那么锁m上的向量时钟肯定是线程t上向量时钟的子集，因此当acq(m)操作发生的时候，当前线程t的向量时钟并不需要更新，那么此时这种join操作就被认为是冗余的。

场景3

lastThread(m)=t 并且 lastLock(t)=m，即最近释放锁m的线程是t，同时线程t最近释放过的锁是m。这里e1表示就是释放m操作rel(m)，而e*表示的就是最后一个释放m操作rel(m)，而e2表示就是和e*对应的获得m操作acq(m)。这里当e1发生的时候，线程t的向量时钟会拷贝给锁m，当e2发生的时候，线程t并没有释放或是获得其他锁，同时锁m也没有被其他线程获得或是释放，这两个条件表明线程t和锁m上的向量时钟在这段时间内都没有改变过。因此e2发生时，当前线程t与锁m上的向量时钟进行join操作是冗余的，同时，当e*发生的时候，线程t拷贝向量时钟到锁m上的操作也是冗余的。

场景5

lastThread(m)!=t 并且 lastLock(t)=m，即最近释放锁m的线程不是t，同时线程t最近释放过的锁是m。这里e1表示就是线程t释放锁m操作rel(m)，e*表示就是线程t最后释放锁m操作rel(m)，而e2表示就是和e*对应的获得锁m操作acq(m)。这里当e1发生的时候，线程t的向量时钟会拷贝给锁m。当其他线程根据e1中m的向量时钟更新自己的向量时钟，并且又将最新的向量时钟拷贝给了m，此时线程t上的向量时钟肯定是m上的向量时钟的子集。当e2发生的时候，由于锁m中间被其他线程获得并释放过，因此m的向量时钟肯定变化了，因此，此时线程t的向量时钟需要和锁m上的向量时钟进行join操作，此时线程t和锁m上的向量时钟就完全一致了。当e*发生的时候，由于线程t并没有获得其他锁，因此向量时钟并不会改变，因此线程t拷贝给锁m的向量时钟是冗余的。

其他三种场景没有冗余操作，可以按照上面的思路进行验证。

Loft方法对于频繁加锁解锁操作相对于FastTrack可以更进一步的减少时间复杂度。