在没有锁的情况下从不同线程更改和读取 unordered_map 的元素
Altering and reading elements of a unordered_map from different threads without lock
我在代码中有一个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 中的元素总数在程序的整个生命周期中保持不变。
不，如果您只是阅读而不是更改 T2 中的数据，那么您应该没问题。但是，您可能需要考虑同步线程，这样 T2 就不会在 T1 写入之前读取。
由于 T1 正在向 unordered_map 写入新值，您需要保护这些值免受并发访问，是的。是否使用 std::mutex、std::atomic 等，由您决定。但是你需要某种写入和读取之间的同步机制。否则，T1 可能会在 与 T2 试图读取相同值的 完全相同的时刻 写入新值，这将导致竞争问题。 T2 很容易最终收到陈旧或不完整的数据。
是的，这会导致问题。标准 (§ [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 使用具有冲突链接的散列 table。这意味着如果两个（或更多）键散列为相同的值，它们都存储在同一个“桶”中，这基本上是值的链表。因此，在 unordered_map 中查找内容可能涉及遍历链表。
经验表明，在典型情况下，我们通常可以预期集合中的某些元素比其他元素更频繁地被访问，通常遵循类似于众所周知的 80:20 规则（20% 的元素将被访问）占访问量的 80%）。
在这种情况下，优化散列的一种方法 table 是尝试将最常访问的元素保留在各自链表的头部。为此，写入一个值不仅可以修改值本身，还可以将其节点移动到（或朝向）链表的开头。因此，您的读取线程可能会尝试遍历链表，就像写入线程试图在链表中向前移动节点一样，因此链表当时已完全损坏（例如，包含 next 指针尚未初始化）。
因此，即使您不进行任何插入或删除，并将映射中的值从 bool 更改为 std::atomic<bool>，您仍然 仍然 有潜在的竞争条件。您确实需要使用锁来保护对地图本身的访问。
请使用锁。即使 T2 正在读取数据，您也不希望 T2 同时读取 T1 modifying/writing 到地图中。如果发生这种情况，您可能会出现具有未定义行为的竞争条件，其中 T2 从地图中读取了错误的项目。
回答这个问题的方法有很多。几乎都是“是的，这是个问题”。
如果 T1 在地图中插入或删除元素，则地图在执行查找时可能会在 T2 下发生变化。如果您非常幸运，这会导致持续崩溃。
假设 T1 只更新映射中的现有值，那么 T2 可以读取正在更新的值，并且可以为布尔值。这可以通过使用 unorderd_map<int, atomic<bool>>.
来避免
假设您避免了上述两个问题，您可能仍然会有数据竞争。某种锁可以避免这种情况。
[已添加]实际上，锁可以避免所有这三个问题。
std::unorderd_map<int, bool> flags;
...In this case, do I need to use a lock?
是的...您需要锁定整个 unordered_map。毕竟 - 即使你刚刚......
bool flag;
...您需要锁定。 Jerry Coffin 在他的回答中引用了相关的经文——为方便起见转载于此：§[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.
或者，您可以使用：
std::unorderd_map<int, std::atomic_bool> flags;
来自不同线程的 [container.requirements.dataraces] guarantees you can safely do concurrent find operations to lookup the atomic<bool> elements. std::unordered_map<...>::find returns an iterator by value, so each thread will have an independent object to dereference - there's no potential race there. Then reads/writes to the atomic_bool 显然可以安全地完成 - 这就是 atomic.
的重点
我在代码中有一个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 中的元素总数在程序的整个生命周期中保持不变。
不，如果您只是阅读而不是更改 T2 中的数据，那么您应该没问题。但是，您可能需要考虑同步线程，这样 T2 就不会在 T1 写入之前读取。
由于 T1 正在向 unordered_map 写入新值，您需要保护这些值免受并发访问，是的。是否使用 std::mutex、std::atomic 等，由您决定。但是你需要某种写入和读取之间的同步机制。否则，T1 可能会在 与 T2 试图读取相同值的 完全相同的时刻 写入新值，这将导致竞争问题。 T2 很容易最终收到陈旧或不完整的数据。
是的，这会导致问题。标准 (§ [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 使用具有冲突链接的散列 table。这意味着如果两个（或更多）键散列为相同的值，它们都存储在同一个“桶”中，这基本上是值的链表。因此，在 unordered_map 中查找内容可能涉及遍历链表。
经验表明，在典型情况下，我们通常可以预期集合中的某些元素比其他元素更频繁地被访问，通常遵循类似于众所周知的 80:20 规则（20% 的元素将被访问）占访问量的 80%）。
在这种情况下，优化散列的一种方法 table 是尝试将最常访问的元素保留在各自链表的头部。为此，写入一个值不仅可以修改值本身，还可以将其节点移动到（或朝向）链表的开头。因此，您的读取线程可能会尝试遍历链表，就像写入线程试图在链表中向前移动节点一样，因此链表当时已完全损坏（例如，包含 next 指针尚未初始化）。
因此，即使您不进行任何插入或删除，并将映射中的值从 bool 更改为 std::atomic<bool>，您仍然 仍然 有潜在的竞争条件。您确实需要使用锁来保护对地图本身的访问。
请使用锁。即使 T2 正在读取数据，您也不希望 T2 同时读取 T1 modifying/writing 到地图中。如果发生这种情况，您可能会出现具有未定义行为的竞争条件，其中 T2 从地图中读取了错误的项目。
回答这个问题的方法有很多。几乎都是“是的，这是个问题”。
如果 T1 在地图中插入或删除元素，则地图在执行查找时可能会在 T2 下发生变化。如果您非常幸运，这会导致持续崩溃。
假设 T1 只更新映射中的现有值，那么 T2 可以读取正在更新的值，并且可以为布尔值。这可以通过使用 unorderd_map<int, atomic<bool>>.
假设您避免了上述两个问题，您可能仍然会有数据竞争。某种锁可以避免这种情况。
[已添加]实际上，锁可以避免所有这三个问题。
std::unorderd_map<int, bool> flags;...In this case, do I need to use a lock?
是的...您需要锁定整个 unordered_map。毕竟 - 即使你刚刚......
bool flag;
...您需要锁定。 Jerry Coffin 在他的回答中引用了相关的经文——为方便起见转载于此：§[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.
或者，您可以使用：
来自不同线程的std::unorderd_map<int, std::atomic_bool> flags;
[container.requirements.dataraces] guarantees you can safely do concurrent find operations to lookup the atomic<bool> elements. std::unordered_map<...>::find returns an iterator by value, so each thread will have an independent object to dereference - there's no potential race there. Then reads/writes to the atomic_bool 显然可以安全地完成 - 这就是 atomic.