基于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 条评论
登录 后参与评论

相关文章

来自专栏新智元

【重磅】谷歌TensorFlow 1.0发布,智能手机也能玩转深度学习

【新智元导读】 近日,谷歌开源深度学习框架 TensorFlow 发布了完整的1.0版本,不仅改进了库中的机器学习功能,而且对 Python 和 Java 用户...

3127
来自专栏专知

【下载】PyTorch实现的神经网络翻译框架——机器翻译工具包 nmtpytorch

【导读】机器翻译是自然语言处理的重要组成部分,其目的是使用计算机自动将文本翻译成其他语言的形式。近年来,端到端的神经机器翻译发展迅速,已经成为机器翻译系统的新主...

3969
来自专栏Windows Community

Windows Developer Day - Windows AI Platform

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

33011
来自专栏直播开发

FLV视频文件格式图示

FLV协议是一种常见的视频文件格式,现在很多的直播中经常使用到http-flv协议,即在http上传送flv格式数据。由于笔者从事直播系统后台开发,对flv格...

2022
来自专栏算法channel

机器学习|PageRank算法原理

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

3596
来自专栏PPV课数据科学社区

《Kaggle项目实战》 泰坦尼克:从R开始数据挖掘(一)

摘要: 你是否为研究数据挖掘预测问题而感到兴奋?那么如何开始呢,本案例选自Kaggle上的数据竞赛的一个数据竞赛项目《泰坦尼克:灾难中的机器学习》,案例涉及一...

3556
来自专栏大数据文摘

想入门深度学习不会搭建环境?手把手教你在Amazon EC2上安装Keras

5212
来自专栏Soul Joy Hub

tensorflow架构

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

3518
来自专栏人工智能LeadAI

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

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

4609
来自专栏炉边夜话

利用Oprofile对多核多线程进行性能分析

在对应用程序不断调优的过程中,除了制定完备的测试基准(Benchmark)外,还需要一把直中要害的利器——性能分析工具。

1742

扫码关注云+社区

领取腾讯云代金券