设计问题：std :: map的线程安全性

作者: 满目山河
发布时间: 2024-01-26 04:32:19 (6月前)
转自：

6 条回复

0#
回复此人
不想吃东西 | 2019-08-31 10-32

<div class =“post-text”itemprop =“text”> 是的，如果插入或删除导致重新平衡，我相信 <code> find </code> 也可能受到影响。 </DIV>

编辑
1#
回复此人
نسر الصحراء | 2019-08-31 10-32

<div class =“post-text”itemprop =“text”> 您将需要将查找放入关键部分，但您可能希望有两个不同的锁，一个用于写入，另一个用于读取。写锁是独占的，但如果没有线程保持写锁，则几个线程可以同时读取而没有任何问题。 这样的实现可以与大多数STL实现一起使用，但是它不符合标准。 <code> std::map </code> 通常使用a来实现 <a href="http://en.wikipedia.org/wiki/Red%E2%80%93black_tree" rel="nofollow"> 红黑树 </A> 读取元素时不会改变。如果地图是使用a实现的 <a href="http://en.wikipedia.org/wiki/Splay_tree" rel="nofollow"> 张树 </A> 相反，树在查找期间会发生变化，一次只能读取一个线程。 在大多数情况下，我建议使用两把锁。 </DIV>

编辑
2#
回复此人
故人 | 2019-08-31 10-32

<div class =“post-text”itemprop =“text”> 从我所看到的，这里已经回答了类似的问题，答案也包括对这个问题的解释，以及更详细地解释线程安全性的链接。 <a href="https://stackoverflow.com/questions/1846186/thread-safety-of-stdmap-for-read-only-operations"> std :: map的线程安全性，用于只读操作 </A> </DIV>

编辑
3#
回复此人
不丶离 | 2019-08-31 10-32

<div class =“post-text”itemprop =“text”> 是的 - 您需要在关键部分中插入，删除和查找。有一些技术可以同时启用多个查找。 </DIV>

编辑
4#
回复此人
滔滔江水 | 2019-08-31 10-32

<div class =“post-text”itemprop =“text”> 二叉树不是特别适合多线程，因为重新平衡可以在树范围的修改中退化。此外，全局互斥体将非常负面地访问性能。 我强烈建议使用已编写的线程安全容器。例如， <a href="http://en.wikipedia.org/wiki/Intel_Threading_Building_Blocks" rel="noreferrer"> 英特尔TBB </A> 包含一个 <code> concurrent_hash_map </code> 。 如果你愿意的话 学习 但是，这里有一些关于构建并发排序关联容器的提示（我相信完整的介绍不仅仅是在我的范围之外，而且在这里也不合适）。 的 读/写 </强> 您可能希望使用Reader / Writer Mutex而不是常规Mutex。这意味着并行读取，而写入保持严格顺序。 的 自己的树 </强> 您还可以构建自己的红黑或AVL树。通过每个节点使用Reader / Writer Mutex扩充树结构。这允许你只阻止 部分 树的，而不是整个结构，即使重新平衡。 例如 带有足够远的键的插入物可以是平行的。 的 跳过列表 </强> 链接列表更适合并发操作，因为您可以轻松地隔离 改性 区。 一个 <a href="http://en.wikipedia.org/wiki/Skip_list" rel="noreferrer"> 跳过清单 </A> 建立在这种力量的基础上，但增加了结构以通过密钥提供O（log N）访问。 走一个列表的典型方法是使用 交出手 成语，也就是说，在释放当前节点之一之前，你抓住下一个节点的互斥锁。跳过列表添加第二个维度，因为您可以在两个节点之间潜水，从而释放它们（并让其他步行者先行）。 实现比二叉搜索树简单得多。 的 一贯 </强> 另一个有趣的部分是持久性（或半持久性）数据结构的概念，通常在函数式编程中找到。二进制搜索树特别适合它。 基本思想是永远不会更改节点（或其内容）。你这样做是通过共享一个可变的 头 ，这将指向更高版本。 <UL> <LI> 阅读：您复制当前头部，然后无需担心使用它（信息是不可变的） </LI> <LI> 写入：您将在常规树中修改的每个节点都被复制并修改了副本，因此每次都重建树的一部分（直到根），并更新 头 指向新的根。有一些有效的方法可以在树下降时进行重新平衡。 写入是顺序的 </LI> </UL> 主要优点是地图的版本始终可用。也就是说，你可以随时 读 即使另一个线程正在执行插入或删除。而且，因为 读 访问只需要一个 同时 读取（复制根指针时），它们几乎无锁，因此具有出色的性能。 引用计数（内在）是这些节点的朋友。 注意：树的副本非常便宜:) <HR /> 我不知道C ++中并发Skip List或并发半持久二进制搜索树的任何实现。 </DIV>

编辑

登录后才能参与评论