c - 如何在不引入锁定的情况下编写并发读取和修改定义明确的数组的代码？

Question

我正在编写一个计算 endgame tablebase 的程序对于国际象棋变体。填充表库的算法是这样工作的:

1. 从一大堆 unsigned char 开始，每个成员代表一个位置(我们总是假设轮到白方了)。数组成员输了为偶数，赢了为奇数，无效为0xff，平局为0xfe。
2. 遍历数组，用 0xff 标记每个非法位置，用 0x00 标记白色的每个位置，用 0x0fe 标记所有其他位置.
3. 遍历数组，只考虑标记为 0xfe 的位置。检查是否有走法到数组成员为偶数的位置，如果有，则将1加上该位置的编号写入当前位置对应的成员。如果所有移动都导致由奇数表示的位置(即这是一个松散的位置)，请将此位置标记为这些数字中最高的一个，以指示最强的防御需要多长时间。
4. 重复第三步，直到数组不再变化。

为了提高速度，我想并行执行第三步。仔细阅读会发现在每次迭代中，我们只将一个值(迭代次数)写入数组。得到以下策略:

• 将数组分成n 个部分，让一个线程处理每个部分。令当前迭代为 i。
• 如果线程必须从数组中读取一个成员并且它等于 i，则将其视为已设置为 0xfe，因为这意味着该成员刚刚被另一个线程同时写入。

现在显然这个程序中存在竞争条件，但这并不重要，因为如果没有任何 pink elephants，我们总能得到正确的结果。 (如果 char 是原子写入的，则不存在)。然而，由于理论上存在竞争条件，C 编译器可能会声明我的程序未定义并格式化我的硬盘。

我该怎么做才能在不违反 C 内存模型的任何约束并且不会导致大幅减速(例如通过添加锁)的情况下并行化该算法？

简化问题描述

这是一个简化的算法，它演示了相同的概念，但去掉了所有不重要的东西:

1. 从数组 unsigned char a[n] 开始。每个数组成员要么是 0 要么是 1。
2. 对于每个设置为 0 的数组成员:如果其​​他一些数组成员等于 0 或 2，则将此数组成员设置为 2。检查的数组成员取决于我们要更新的数组成员的索引。索引和我们需要检查的数组成员之间没有简单的关系，它本质上是随机的。

因为我们只会将 0 更改为 2，所以我们处理数组条目的顺序并不重要，即使从技术上讲，如果我们并行这样做会存在竞争条件(因为我们同时读/写同一个对象)。我如何告诉编译器它不应该在不牺牲性能的情况下关心竞争条件？

Answer 1

这就是 C11 中 _Atomic 类型限定符的用途。你会将你的数组声明为

_Atomic unsigned char a[n];

这意味着数组的每个元素都可以原子地读取或写入。

在 C11 之前，没有执行此操作的标准方法，但通常，根据实现的不同，某些数据类型对于读取和写入是原子的。要了解它们是什么，您必须查看您正在使用的实现的文档。

---

请注意，C11 _Atomic 访问的默认内存顺序是memory_order_seq_cst(顺序一致性)，如果不需要，可以使用atomic_load_explicit 和 atomic_store_explicit 具有较弱内存顺序的操作(即在您的示例中为 memory_order_relaxed)