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

相关文章

来自专栏十月梦想

node处理机制,并发性测试

下面一个案例看一下非阻塞I/O处理机制,更好了解到node机制!其实三个特点就是一个事情,擅长I/O,擅长任务调度!

663
来自专栏Java架构

自己手写一个 SpringMVC 框架

1634
来自专栏有趣的django

Flask请求扩展和数据库连接池

1910
来自专栏程序小工

【实战】Tp5+小程序(三)--微信登录与令牌

ThinkPHP5 从入门到深入学习,结合实战项目深入理解 ThinkPHP5 的特性和使用方法。深入学习 api 开发,学习微信登录和令牌的相关知识,并理解微...

2852
来自专栏一枝花算不算浪漫

[数据库连接池] Java数据库连接池--DBCP浅析.

34214
来自专栏H2Cloud

利用LUA协程实现FUTURE模式

1. Future模式: 参见 http://www.cnblogs.com/zhiranok/archive/2011/03/26/Future_Patter...

3776
来自专栏JMCui

Netty 系列七(那些开箱即用的 ChannelHandler).

    Netty 为许多通用协议提供了编解码器和处理器,几乎可以开箱即用, 这减少了你在那些相当繁琐的事务上本来会花费的时间与精力。另外,这篇文章中,就不涉及...

853
来自专栏你不就像风一样

Netty入门(二)之PC聊天室

参看Netty入门(一):Netty入门(一)之webSocket聊天室 Netty4.X下载地址:http://netty.io/downloads.ht...

854
来自专栏python3

python3--threading模块(线程)

程序并不能单独运行,只有将程序装载到内存中,系统为它分配资源才能运行,而这种执行的程序就称之为进程。程序和进程的区别就在于:程序是指令的集合,它是进程运行的静态...

942
来自专栏禁心尽力

Redis的二八定律

常用命令: 1、setex key 有效时间 value ----------意思就是添加并设置该键值对的存活时间 2、mset key1 value1 key...

2686

扫码关注云+社区