相关疑难解决方法(0)

编写多线程应用程序时,遇到的最常见问题之一是竞争条件.

我对社区的问题是:

什么是比赛条件？你怎么发现它们？你怎么处理它们？最后,你如何防止它们发生？

我正在编写一个程序,用于计算国际象棋变体的终结表基础.填充tablebase的算法如下:

1. 从一大堆开始unsigned char,每个成员代表一个位置(我们总是假设它是白色的).即使位置丢失也是数组成员,如果赢了则是奇数,如果它是0xff无效的,0xfe如果它是平局的话.
2. 迭代数组,标记每个非法位置0xff,白色与其匹配的每个位置0x00以及所有其他位置0x0fe.
3. 迭代数组,只考虑标记的位置0xfe.检查是否存在是导致其数组成员为偶数的位置,如果有,写一加那个位置为对应于CURREN位置上的成员数量的举动.如果所有的移动导致由奇数显示位置(即这是一个失去位置),纪念这个位置一加最高这些数字来表示防御最强的花费多长时间.
4. 重复步骤3,直到阵列不再更改.

为了速度,我想并行化第三步.仔细阅读会产生在每次迭代中,我们只会将一个值(迭代次数)写入数组.以下策略获得:

• 将数组拆分为n个部分,让每个部分使用一个线程.让当前的迭代为i.
• 如果线程读取来自阵列的成员,它等于我,对待它,如果它被设置为0xfe,因为这意味着该成员刚刚被另一个线程同时写入.

现在显然这个程序中存在竞争条件,但是没关系,因为如果没有任何粉红色的大象(如果a char是原子写的则不能存在),我们总能得到正确的结果.但是,由于在纸面上存在竞争条件,C编译器可能会声明我的程序未定义并格式化我的硬盘.

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

简化问题描述

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

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

由于我们只将0更改为2,因此我们处理数组条目的顺序并不重要,即使我们并行执行竞争条件(因为我们同时读取/写入相同的对象) .如何在不牺牲性能的情况下告诉编译器它不应该关心竞争条件？