c++ - 无锁地从不同线程更改和读取 unordered_map 的元素

Question

我在代码中有一个unordered_map，它有一个固定数量的元素被初始化在我的程序启动时

std::unorderd_map<int, bool> flags;
//Initialize all needed values in the map
// Start thread T1
// Start thread T2

所有条目在开始时都初始化为 false。有两个线程(T1 和 T2)。 T1 可以更改映射中每个条目的值。 T2 只是定期读取条目。在这种情况下，我需要使用锁吗？ unordered_map 中的元素总数在程序的整个生命周期内保持不变。

Answer 1

是的，这会导致问题。标准 (§ [intro.races]/21.2) 中的措辞是:

The execution of a program contains a data race if it contains two potentially concurrent conflicting actions, at least one of which is not atomic, and neither happens before the other, except for the special case for signal handlers described below. Any such data race results in undefined behavior.

因此，如果您仅从多个线程中读取，您不会得到“冲突操作”，但即使是一个线程写入，您也需要同步访问。

在 unordered_map 的特定情况下，我可以看到同时写入和读取可能导致非常严重的问题的情况。

unordered_map 使用带有碰撞链接的哈希表。这意味着如果两个(或更多)键散列为相同的值，它们都存储在同一个“桶”中，这基本上是值的链表。所以，在 unordered_map 中查找内容可能涉及遍历链表。

经验表明，在典型情况下，我们通常可以预期集合中的某些元素比其他元素更频繁地被访问，通常遵循众所周知的 80:20 规则(20% 的元素将占 80%的访问)。

既然如此，优化哈希表的一种方法是尽量将最常访问的元素保留在各自链表的头部。为此，写入一个值不仅可以修改值本身，还可以将其节点移动到(或朝向)链表的开头。因此，您的读取线程可能会尝试遍历链表，就像写入线程试图在链表中向前移动节点一样，因此链表当时完全损坏(例如，包含一个 next 指针'尚未初始化)。

因此，即使您不进行任何插入或删除操作，并且将映射中的值从 bool 更改为至 std::atomic<bool> ，您仍然有潜在的竞争条件。您确实需要使用锁来保护对 map 本身的访问。