V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
alexapollo
V2EX  ›  程序员

一个无锁编程的问题

  •  
  •   alexapollo ·
    geekan · 2014-09-15 15:20:45 +08:00 · 6093 次点击
    这是一个创建于 3721 天前的主题,其中的信息可能已经有所发展或是发生改变。
    在写程序的时候,见到一个蛮巧妙的思路(一写者,多读者):
    维持两块内存,A1、A2,代表同一个对象
    假如一开始读A1,那么就写A2,写完以后置一个标志位,让读写者倒换,也即之后的读者就读A2了,而写者写A1。

    有人见过类似的思路吗?它是否有一个名字?
    我想了很久,只觉得它很类似read-copy-update,但RCU在用户态用起来好像有点麻烦。不知道有没有更方便的实现?
    26 条回复    2021-01-29 13:02:30 +08:00
    isayme
        1
    isayme  
       2014-09-15 15:57:14 +08:00
    还在 读A1的时候 进行 读写者倒换 怎么办?
    这种情况, 还是老老实实加个读写锁吧.
    yuelang85
        2
    yuelang85  
       2014-09-15 15:59:03 +08:00
    这种思路很多人都做过。你这个还欠一个 二者数据同步机制。

    我也不知叫啥,求答案。

    哦,对了,mysql有一种常见做法,叫“读写分离”,跟你的有些出入,他是不互换角色,而是只从”从库“读取,只写入到”主库“,从库定期从主库同步数据。
    yuelang85
        3
    yuelang85  
       2014-09-15 15:59:37 +08:00
    @isayme 下一个请求才切换。
    shoumu
        4
    shoumu  
       2014-09-15 16:21:15 +08:00
    A1和A2的数据同步还是涉及到同步问题了啊?
    zhangdawei
        5
    zhangdawei  
       2014-09-15 16:28:23 +08:00
    linux中,内核里面有个“读写自旋锁”,
    http://os.chinaunix.net/a2006/0909/1003/000001003383.shtml
    可以参考下,linux内核里面考虑读写、异步、死锁、原子操作这些功能想了很多招。
    Mutoo
        6
    Mutoo  
       2014-09-15 16:47:04 +08:00
    这个叫 double-buffer 吧

    http://gameprogrammingpatterns.com/double-buffer.html
    参见最后 see also 上面的例子
    alexapollo
        7
    alexapollo  
    OP
       2014-09-15 19:59:14 +08:00
    @yuelang85
    @shoumu
    恩,这块是定期刷配置用的,无状态,所以还比较简单,不用考虑数据同步
    @zhangdawei
    就是觉得rwlock性能稍微差一些(在我这场景里),所以想换个lock-free的方法
    nelson
        8
    nelson  
       2014-09-15 20:32:00 +08:00
    弄个二值变量就可以了吧。。
    变量=A,reader读A;writer要写的话写B,写完将变量置为B;变量=B反之。
    就是有可能reader会读到上次的数据,但可以保证不会读到脏数据
    ETiV
        9
    ETiV  
       2014-09-15 20:39:24 +08:00 via iPhone
    OpenGL 里叫双 buffer

    当前显示的显存区域就是LZ说的读
    另外后台渲染的显存区域就是用来写的了

    然后等待屏幕垂直刷新更新完成后(垂直同步),交换两个buffer的指针……
    semicircle21
        10
    semicircle21  
       2014-09-15 21:51:53 +08:00
    这个思路有限制, 可能是你描述的不完整, 我觉得不是完全无锁的, 就是写线程换 A/B 的时机, 需要和读操作同步. 假设1读 1写:
    1) 读线程 读到标志A1
    2) 写线程 切换到标志 A1
    3) 写线程 写入到 A1 区域
    4) 读线程 从 A1 读入脏数据
    对 A/B 这个标志位的访问还是需要用锁控制的.
    SoloCompany
        11
    SoloCompany  
       2014-09-15 22:02:43 +08:00
    copy-on-write-modification
    和你说的类似,只不过 CPW 是即抛型

    但你确定,如果不用拷贝,你的双缓存状态怎么保持一致?

    附 wiki 参考 http://en.wikipedia.org/wiki/Copy-on-write
    alexapollo
        12
    alexapollo  
    OP
       2014-09-15 23:51:20 +08:00   ❤️ 1
    @nelson 二值变量?没有搜到相关的资料,有没有相关阅读?思路就是这个。
    @ETiV 恩,你说的这个就是标准RCU了。但看起来更像是1读1写的场景,会简化一些。
    @semicircle21
    1) 读线程 读到标志A1
    2) 写线程 写A2
    3) 写线程 写完后切换读标志为A2
    4) 读线程 第二次读,从A2开始读取
    5) 写线程 第二次写,从A1开始写
    alexapollo
        13
    alexapollo  
    OP
       2014-09-15 23:57:34 +08:00
    @semicircle21 仔细想了一下,是有道理的,这个模型可能存在隐患。
    1) 读线程读A1过程中,被调度给写线程
    2) 写线程串行无打断写了一次A2,切换标志,下次写A1读A2
    3) 写线程写A1开始,被调度走
    3) 读线程还在读A1,调度回来了,此时A1是脏数据
    pright
        14
    pright  
       2014-09-16 00:11:36 +08:00
    @alexapollo 变量只允许读线程切换,就没这个问题。不过这种方案只适合单读单写,不然还得加锁。这个其实就是简化的ring buffer。
    alexapollo
        15
    alexapollo  
    OP
       2014-09-16 00:23:07 +08:00
    @pright 理解你的想法,多读者时,可能存在部分读者读A1,部分读A2的场景,这个场景无法写入

    那么用ring的角度来看,还是有可行方法的(近似),假设一个数组 A[N],0是初始cursor,有个bitmap表示数组哪些项被读者占用了,每次写的时候,尝试寻找未被占用的A[i],如果找到了,那么就update,并且令cursor=i,这样在N足够大时,风险是比较小的,注意这里要保持服务有损,也即如果所有A[i]都被读者占用时,返回错误
    alexapollo
        16
    alexapollo  
    OP
       2014-09-16 00:26:34 +08:00
    @SoloCompany 之前研究过一段COW,但不是很理解。它讲的是程序需要修改某个变量时,就自己复制一份,然后改掉自己用。这个过程可以保护其他线程不受影响,但我需要的是修改这个变量,全局的,最后必须要所有线程都感知到它的修改。
    pright
        17
    pright  
       2014-09-16 00:31:21 +08:00
    @alexapollo 倒是不存在读者读不同区域的问题,因为标志为A1,肯定大家都是读A1,主要问题是无法断定什么时候该切换标志为A2了,除非读者个数是确定的。

    ring buffer的一般实践是用读写指针的,保证写指针不越过读指针,在单读单写情况下可以无锁。
    SoloCompany
        18
    SoloCompany  
       2014-09-16 01:15:36 +08:00 via iPad
    @改完之后当然需要回写,当然回写的时候野生需要锁得,只是锁的粒度就小多了,另外你的语言支持 violate 关键字之类的语义的话(如java),是可以无锁的,如果对状态一致性有要求,可以增加修改计数器来判断是否有并发写入,在发现有并发写的时候重新执行cow过程
    alexapollo
        19
    alexapollo  
    OP
       2014-09-16 02:23:49 +08:00
    @pright 我们的思路不同。我的思路是,在写者写完之后置换标志,此时如果置读标志为A1,那么之后都会读A1,但可能有部分读者还在读A2,没有完成操作。
    我不是很理解你的思路,能不能详细讲讲?
    alexapollo
        20
    alexapollo  
    OP
       2014-09-16 02:28:17 +08:00
    @SoloCompany 使用C++。C里有violate关键字,但我没有用过。似乎它很少被使用。
    是的,我明白你的意思,可以用rwlock配合来一个很短时间的锁:一个赋值过程的锁。

    有道理。之前我也有类似的思路,你这么一说就理顺了,多谢啦~
    xylophone21
        21
    xylophone21  
       2014-09-16 09:26:24 +08:00
    WKPlus
        22
    WKPlus  
       2014-09-16 12:56:08 +08:00
    见过很多这类应用,双buffer切换呀,应用场景是这样的:
    1.多线程服务端程序,使用本地文件作为词表,有一个线程专门来检查文件是否更新,检测到更新之后,需要把新文件load到内存中的
    2.每次前端有请求过来的时候,使用内存中的词表做查询,对内存中的词表只要求完整性(即不能使用更新了一半的词表),但是及时性要求不是那么高

    所以做法就如题主所说,开了两个buffer,在读buffer 0的时候就写buffer 1,写完之后更新读buffer的标识(原子操作)即可。

    这里其实有一个race condition:
    如果有线程在读buffer 0,然后buffer 1写完成了,标识读buffer为1,又检测到更新开始写buffer 0,如果原来读buffer 0的线程还没有结束,就可能出现数据不完整的情况。

    但在实际上,是不会发生的,因为每次更新完文件之后,至少要等待5min才会去检测文件是否更新,而我们服务最长的请求处理时间不会有5min这么长,所以上面的race condition就不会发生,因此也就可以无锁了。
    semicircle21
        23
    semicircle21  
       2014-09-16 13:43:02 +08:00
    @alexapollo 是的, 应用这个思路要有一些前提的, 我又想了一下, 对标志位加锁也不能保证不读到脏数据. 关键是改标志位的时候, 要有前提条件或机制保证此时没有正在读的线程.
    我感觉, 一般无锁/同步问题都是具体问题具体分析的, 有一些常用的 Pattern, 但能直接用上的很少. 因为涉及到的细节很多, 比如时间短的操作, 在kernel 里可以关中断自旋锁来保证同步, 但在多处理器场景又不行了, 然后还要保证访问的内存是已经在 cache 里的, 否则怎么也不会是"时间短的"...
    所以, 针对一般情况, 如果仅仅是追求数据吞吐量, Share information by queue, 比 memory 靠谱多了.
    glogo
        24
    glogo  
       2014-09-16 20:43:47 +08:00
    那标志位的读写不需要同步吗
    nelson
        25
    nelson  
       2014-09-17 23:52:30 +08:00
    @alexapollo 其实就是i = (i + 1) % 2
    不过这种方法确实会像LSSS+说的,读A的过程中连续写了两次数据(B、A),会导致读到脏数据
    pslydhh
        26
    pslydhh  
       2021-01-29 13:02:30 +08:00
    用户态 RCU 哪里有资料介绍吗
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   实用小工具   ·   5305 人在线   最高记录 6679   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 21ms · UTC 08:41 · PVG 16:41 · LAX 00:41 · JFK 03:41
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.