c++ - 从并发关联容器中删除 (concurrent_unordered_map)

标签 c++ multithreading concurrency tbb

我一直在寻找并发关联容器,我从 Thead Building Blocks 中找到了 concurrent_unordered_map,它似乎可以满足我的所有需求。即使我阅读了文档,我也没有找到一个关于删除如何工作的例子。

A concurrent_unordered_map supports concurrent insertion and traversal, but not concurrent erasure. The interface has no visible locking. It may hold locks internally, but never while calling user-defined code. It has semantics similar to the C++11 std::unordered_map except as follows:

这到底是什么意思?只要我只是从一个线程中删除这张 map 是否安全?如果没有,我该怎么做?

最佳答案

proposal for standardization of concurrent maps解释为什么并发容器没有 erase。 (搜索“为什么不支持并发删除”部分。)

C++ 标准库中的容器负责删除它们的内容。内容在容器“中”,就像元素在数组“中”一样。 operator[] 返回对包含对象的引用,一旦返回引用,容器就不知道请求线程将“挂起”引用多长时间。因此,如果另一个线程要求删除该元素,则容器不知道该元素是否可以安全删除。

我一直在尝试想出一些解决该限制的方法,但对删除问题的解释带来了一个更大的问题:它始终是调用者的责任以保护对存储在 map 中的元素的并发访问。

例如:假设您有一个从 intfloat 的并发映射,并且您这样做:

thread A                   thread B
the_map[99] = 0.0;
                   ...
the_map[99] = 1.0;         if (the_map[99] == 1.0) ...  // data race!!!

这是数据竞争的原因是,即使表达式 the_map[99] 受到保护,它也会返回一个引用,对其访问不 protected 。由于对引用的访问不 protected ,因此只允许读取引用指向的内存。 (或者您需要锁定对该内存的所有访问)。

这是我能想到的最便宜的替代方案(而且它真的很贵):

typedef concurrent_unordered_map<MyKey_t, atomic<MyMapped_t*> > MyContainer_t;

现在查找一个项目意味着:

MyMapped_t* x = the_map[a_key].load();

插入一个项目是:

the_map[a_key].store(ptr_to_new_value);

删除一个项目是:

the_map[a_key].store(0);

测试一个项目是否真的在 map 中是:

if (the_map[a_key].load() != 0) ...

最后,如果您要进行任何类型的条件删除(或修改),它必须更复杂:

MyMapped_t* x;
do {
  x = the_map[a_key].load();
} while (condition_for_erasing(x) && !the_map[a_key].compare_exchange_strong(x, 0));

(上面是错误的,因为它受到 the ABA problem 的影响。)

即便如此:这仍然不能保护您免受同时修改底层 MyMapped_t 的影响,并且需要您完成 MyMapped_t 的所有构造、存储管理和销毁是你自己。

:(

关于c++ - 从并发关联容器中删除 (concurrent_unordered_map),我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/16747498/

相关文章:

java - 在 "Java Concurrency In Practice"之后阅读更多并发示例?

go - 为什么即使有锁,GO 也会出现 'concurrent map writes' panic ?

c++ - Linux,C++,使用 poll/select 等待事件(不阻塞执行线程)

C++ 使用 cout << 避免换行

c# - 连接池-一个进程-多个线程

c - 如何安排 pthread_cond_signal() 以使其始终跟随另一个线程上的 pthread_cond_wait()?

java - 确定 Java ThreadPoolExecutor 中执行任务的优先级

c++ - 将 void* 引用为 float 时数据丢失

c++ - 通过引用将派生类指针传递给期望基指针的函数

concurrency - 多个 goroutine 打印到标准输出是否安全?