Gro*_*ovy 1 c++ multithreading posix stl thread-safety
我使用std :: map来实现我的本地哈希表,它将由多个线程同时访问.我做了一些研究,发现std :: map不是线程安全的.所以我将在地图上使用互斥锁进行插入和删除操作.我打算使用单独的互斥锁,每个映射条目一个,以便可以单独修改它们.
我是否还需要将查找操作放在关键部分？查找操作会受插入/删除操作的影响吗？有没有比使用可以处理所有事情的std :: map更好的实现？
二叉树不是特别适合多线程,因为重新平衡可以在树范围的修改中退化.此外,全局互斥体将非常负面地访问性能.
我强烈建议使用已编写的线程安全容器.例如,英特尔TBB包含一个concurrent_hash_map.
但是,如果你想学习,这里有一些关于构建并发排序关联容器的提示(我相信完整的介绍不仅仅是我无法触及的,而且也不合适,在这里).
读/写
您可能希望使用Reader/Writer Mutex而不是常规Mutex.这意味着并行读取,而写入保持严格顺序.
自己的树
您还可以构建自己的红黑或AVL树.通过每个节点使用Reader/Writer Mutex扩充树结构.这允许您仅阻止部分树,而不是整个结构,即使在重新平衡时也是如此.例如,带有足够远的键的插入物可以是平行的.
跳过列表
链接列表更适合并发操作,因为您可以轻松地隔离修改后的区域.
一个跳跃列表建立在这个实力,但增强了结构提供为O(log n)的密钥访问.
行走列表的典型方法是使用手动习惯用法,即在释放当前节点之一之前获取下一个节点的互斥锁.跳过列表添加第二个维度,因为您可以在两个节点之间潜水,从而释放它们(并让其他步行者先行).
实现比二叉搜索树简单得多.
一贯
另一个有趣的部分是持久性(或半持久性)数据结构的概念,通常在函数式编程中找到.二进制搜索树特别适合它.
基本思想是永远不会更改节点(或其内容).你通过共享一个可变头来实现这一点,这将指向更高版本.
主要优点是地图的版本始终可用.也就是说,即使另一个线程正在执行插入或删除,您也可以随时读取.此外,因为读访问只需要单个并发读取(复制根指针时),所以它们几乎无锁,因此具有出色的性能.
引用计数(内在)是这些节点的朋友.
注意:树的副本非常便宜:)
我不知道C++中并发Skip List或并发半持久二进制搜索树的任何实现.
| 归档时间： |
|
| 查看次数： |
6471 次 |
| 最近记录： |