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

请教 C++多线程操作 deque 遇到的一个问题

  •  
  •   imiao · 2019-11-27 17:04:31 +08:00 · 3912 次点击
    这是一个创建于 1583 天前的主题,其中的信息可能已经有所发展或是发生改变。

    有一个 deque。
    线程 A 不停在队尾插入数据,当 deque 长度达到数量 N 的时候,从队头出队一条数据,并回收内存。
    线程 B 在收到某个触发条件时,需要拷贝当前队列中的所有数据,把数据存到本地。
    目前发现不加锁,存到本地的数据不正确。加锁的话,线程 A 会阻塞,线程 A 需要保证不阻塞。
    有没有较好的解决类似问题的方法?

    14 条回复    2019-12-06 11:49:03 +08:00
    augustheart
        1
    augustheart  
       2019-11-27 17:13:01 +08:00
    首先加锁是必须的,deque 不能保证线程安全,确切说 stl 就根本不保证线程安全。
    然后,你如果两个线程都不想堵塞,那放弃,没有这种方法。
    你如果只想保证 a 不堵塞,可以考虑使用在未获取到锁的时候直接放弃的方法。比如 windows 的 TryEnterCriticalSection,如果没有获取到锁就直接返回 false,然后进入下一次循环。不知道符不符合你的需求,但是肯定不堵塞了
    nightwitch
        2
    nightwitch  
       2019-11-27 17:23:52 +08:00
    上 Boost.Lockfree,里面有 queue 和 stack
    c0011
        3
    c0011  
       2019-11-27 17:26:07 +08:00
    无锁队列、读写锁
    liuminghao233
        4
    liuminghao233  
       2019-11-27 17:51:28 +08:00 via iPhone
    b 不会改数据 而且不是频繁拿锁的话
    用 try_lock a 如果 try_lock 失败就 copy 一份 然后在新副本操作
    要是 a 能拿到锁,就把新副本写进去
    top1ms
        5
    top1ms  
       2019-11-27 19:00:29 +08:00
    如题主所说 A 是生产端 B 是消费端 从题主的描述中 有一点我不明白 就是当队列满足 N 以后 队头拿一条数据出队 回收内存?代表队列中的数据可以不用完全消费 可以允许数据丢失吗? 先看你的问题 问题产生的原因是 不加锁重复消费导致数据不正确 加锁呢又导致线程 A 阻塞(这是一个大锁 一锁锁全部) 题主的做法应该是 B 拿出 A 所有数据时 上大锁 A 不能再插入数据了 等 B 处理完以后 清除队列里的数据 释放锁 A 才能插入数据 这样做很明显不好 因为 A 阻塞时(假设你是 web 环境) 只是数据没有入队 但是一样占用了内存空间!!! 而且造成网络阻塞 占用网络资源 所以我的解决思路是这样的 再不考虑生产端和消费端的效率情况下(最坏的情况就是 A 生产端能力大于 B 消费端能力 数据堆积 内存会爆)
    --------
    问题总结:
    1: 不上锁 数据重复性消费
    2: 上锁 锁的粒度大 B 操作时 A 不能操作
    3: 数据允许丢失?
    我的解决思路如下:
    1: 如果保证数据不丢失 队列满足 N 时 大于 N 的 找个地方把来不及入队的数据先存起来 如数据库 这样也解决了 部分 生产端能力>消费端能力的问题 再开启一个线程 C 去处理这类数据 不用做 数据重复校验 因为这都是没来得及入队的 B 只会取得队列里的数据。
    2: B 做数据重复性处理校验 上一个 number 值 这个 number 值可以是队列中的数据携带 可以是时间戳 记录我当前处理的位置
    3 :减小锁粒度 B 获取数据的时候 上锁 有一个全局变量 number 更新这个 number 释放锁 锁是共享资源的竞争 A B 共同竞争的这个小锁 是为了取得 number 值 B 对 number 值进行更新 A 拿 number 值清空队列中的数据 就相当于游标一样撒 A 获取锁的实际就是队列满的时候 然后根据 number 对队列进行清理

    --------
    考虑不周的 请指正
    alphaprogrammer
        6
    alphaprogrammer  
       2019-11-27 19:21:31 +08:00
    使用无锁 ringbuffer,buffer 内部存取指针,便于原子操作
    laminux29
        7
    laminux29  
       2019-11-27 20:16:27 +08:00
    首先,一般情况下,1 楼的回答是对的。其他回答什么无锁都是错的。

    其次,你这个业务,存在一个特殊性:R 与 W 都是线程 A,而线程 B 只有 R,这种情况可以参考数据库引擎的做法,使用日志,来解决锁问题。也就是说 A 只操作日志,B 可以直接操作队列,然后使用一个新线程负责处理日志、队列以及线程 B 的关系。但这种东西难度较大,比较有挑战。
    AlohaV2
        8
    AlohaV2  
       2019-11-27 20:17:48 +08:00
    Google 搜索“读写锁,写优先”能出来很多结果,C++11 的话应该可以了解一下 std::condition_variable.
    或者可以考虑无锁队列,如果读、写的线程各只有一个的话直接用 ring buffer: https://www.codeproject.com/Articles/43510/Lock-Free-Single-Producer-Single-Consumer-Circular
    imiao
        9
    imiao  
    OP
       2019-11-27 20:23:03 +08:00
    感谢 v 友们热心的回复。
    @augustheart A 线程是持续向队列插入数据,获取不到锁的时候数据不能丢,所以当获取不到锁不能简单就跳过
    @nightwitch 项目没有引入 boost,嫌弃有点大:)
    @liuminghao233 B 线程仅在拷贝这一步加一下锁,这样 A 线程阻塞的时间非常短,我可以试试
    @top1ms 1.队列中的数据只有实时的才有用,过期数据就丢弃了。2.生产端生产的数据是复用同一块内存的,通过拷贝存到队列里,而且队列固定长度,所以不会数据堆积。3.B 线程需要取得的数据是某一时间点队列中所有数据的拷贝。4.在 A 线程没有获取到锁时,临时将数据存到别的地方,单独开启一个线程 C 处理临时数据就无法满足 3。5.我有考虑把临时数据再插回队列里去,但因为 B 线程的触发条件不确定,不好确定临时数据插哪以及是否已经过期。
    @alphaprogrammer 大佬,我看了下环形缓冲区的介绍,似乎可以很好地解决我的问题。。。我去写代码了。
    @laminux29 这倒也给了我一个思路,将队列的长度加长大于 N,比如 2N,这样 B 在取数据的时候可以取队列中间的一段,至少可以某种程度上避免取出来的数据已经被回收的尴尬。
    araraloren
        10
    araraloren  
       2019-11-28 10:44:24 +08:00
    如果你的线程 A 处理所有的事情,数据会堆积吗??不行的话,拷贝一份数据开一个线程(或者使用线程池)去处理 B 应该干的事如何?
    imiao
        11
    imiao  
    OP
       2019-11-28 14:05:32 +08:00 via Android
    @araraloren 不行,线程 B 要一直运行等待某个条件
    araraloren
        12
    araraloren  
       2019-11-29 09:49:51 +08:00
    @imiao 所以 A 不能判断这个条件?? A 判断这个条件会堆积数据??
    freemon
        13
    freemon  
       2019-12-05 14:45:46 +08:00
    自旋锁走一波?
    imiao
        14
    imiao  
    OP
       2019-12-06 11:49:03 +08:00 via Android
    已经解决,通过队列加长的方式
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   我们的愿景   ·   实用小工具   ·   4056 人在线   最高记录 6543   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 31ms · UTC 05:16 · PVG 13:16 · LAX 22:16 · JFK 01:16
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.