C++ Concurrency in Action [6] | CH06 Designing Lock-based Concurrent Data Structure
目录
警告
本文最后更新于 2023-12-19,文中内容可能已过时。
- 设计并发数据结构要考虑两点,一是确保访问 thread-safe,二是提高并发度
- thread-safe 基本要求如下
- 数据结构的不变量(invariant)被一个线程破坏时,确保不被线程看到此状态
- 提供操作完整的函数来避免数据结构接口中固有的 race condition
- 注意数据结构出现异常时的行为,以确保不变量不被破坏
- 限制锁的范围,避免可能的嵌套锁,最小化死锁的概率
- 作为数据结构的设计者,要提高数据结构的并发度,可以从以下角度考虑
- 部分操作能否在锁的范围外执行
- 数据结构的不同部分是否被不同的 mutex 保护
- 是否所有操作需要同级别的保护
- 在不影响操作语义的前提下,能否对数据结构做简单的修改提高并发度
- 总结为一点,即最小化线程对共享数据的轮流访问,最大化真实的并发量
- thread-safe 基本要求如下
thread-safe queue
- 之前实现过的 thread-safe stack 和 queue 都是用一把锁定保护整个数据结构,这限制了并发性,多线程在成员函数中阻塞时,同一时间只有一个线程能工作。这种限制主要是因为内部实现使用的是 std::queue,为了支持更高的并发,需要更换内部的实现方式,使用细粒度的(fine-grained)锁。最简单的实现方式是包含头尾指针的单链表,不考虑并发的单链表实现如下
|
|
- 即使用两个 mutex 分别保护头尾指针,这个实现在多线程下也有明显问题。push 可以同时修改头尾指针,会对两个 mutex 上锁,另外仅有一个元素时头尾指针相等,push 写和 try_pop 读的 next 节点是同一对象,产生了竞争,锁的也是同一个 mutex
- 该问题很容易解决,在头节点前初始化一个 dummy 节点即可,这样 push 只访问尾节点,不会再与 try_pop 竞争头节点
|
|
- 接着加上锁,锁的范围应该尽可能小
|
|
- push 中创建新值和新节点都没上锁,多线程可用并发创建新值和新节点。虽然同时只有一个线程能添加新节点,但这只需要一个指针赋值操作,锁住尾节点的时间很短,try_pop 中对尾节点只是用来做一次比较,持有尾节点的时间同样很短,因此 try_pop 和 push 几乎可以同时调用。try_pop 中锁住头节点所做的也只是指针赋值操作,开销较大的析构在锁外进行,这意味着虽然同时只有一个线程能 pop_head,但允许多线程删除节点并返回数据,提升了 try_pop 的并发调用数量
- 最后再结合 std::condition_variable 实现 wait_and_pop,即得到与之前接口相同但并发度更高的 thread-safe queue
|
|
thread-safe map
- 并发访问 std::map 和 std::unordered_map 的接口的问题在于迭代器,其他线程删除元素时会导致迭代器失效,因此 thread-safe map 的接口设计就要跳过迭代器
- 为了使用细粒度锁,就不应该使用标准库容器。可选的关联容器数据结构有三种,一是二叉树(如红黑树),但每次查找修改都要从访问根节点开始,也就表示根节点需要上锁,尽管沿着树向下访问节点时会解锁,但这个比起覆盖整个数据结构的单个锁好不了多少
- 第二种方式是有序数组,这比二叉树还差,因为无法提前得知一个给定的值应该放在哪,于是同样需要一个覆盖整个数组的锁
- 第三种方式是哈希表。假如有一个固定数量的桶,一个 key 属于哪个桶取决于 key 的属性和哈希函数,这意味着可以安全地分开锁住每个桶。如果使用读写锁,就能将并发度提高相当于桶数量的倍数
|
|
thread-safe list
|
|
Buy me a coffee~
支付宝
微信