基于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可以更进一步的减少时间复杂度。

原创声明,本文系作者授权云+社区发表,未经许可,不得转载。

如有侵权,请联系 yunjia_community@tencent.com 删除。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏Soul Joy Hub

tensorflow架构

TensorFlow 又是好久没有写博客了,上班以来,感觉时间过得飞快,每天时间很紧,过得有点累,不知道自己的博客能坚持到何时,且行且珍惜。 本片博文是参...

3509
来自专栏人人都是极客

五分钟喝不完一杯咖啡,但五分钟可以带你入门TensorFlow

本文是《人人都能学人工智能-TensorFlow系列》文章的第一篇,这个系列会对TensorFlow的基础使用,SoftMax,交叉熵,Dropout,CNN,...

47012
来自专栏cs

python统计一下自己的花费

1343
来自专栏人工智能头条

深度学习与自然语言处理之五:从RNN到LSTM

1334
来自专栏算法channel

机器学习|PageRank算法原理

01 — 网页排名主要考虑因素 学术界评判学术论文重要性通用方法是看论文的引用次数,原理很多时候都是可以通用的,学术界的思想可以应用到工业界。 google创始...

3426
来自专栏机器之心

业界 | 谷歌发布TensorFlow 1.3.0版本,新加多个分类器、回归器

3044
来自专栏Windows Community

Windows Developer Day - Windows AI Platform

本次 Windows Developer Day,最值得期待的莫过于 Windows AI Platform 了,可以说是千呼万唤始出来。观看直播的开发者们,留...

31811
来自专栏ThoughtWorks

GEEK的心思你别猜

#ThoughtWorkers好声音#第十二期(图片:网络) 都说Geek的世界高深莫测,无法轻易探究。有多高深? 就是写幻灯片都用文本格式,更Geek的做法...

2504
来自专栏Soul Joy Hub

tensorflow架构

原文 : http://blog.csdn.net/stdcoutzyx/article/details/51645396 Basic Concepts 张量(...

3398
来自专栏ATYUN订阅号

TF新工具AutoGraph:将Python转换为TensorFlow图

我们在这里向你介绍一个名为“AutoGraph”的TensorFlow新功能。AutoGraph将Python代码(包括控制流print()和其他Python原...

1144

扫码关注云+社区