0

如何在没有锁定或在 C++ 中使用互斥体/信号量的情况下防止竞争条件？我正在处理一个嵌套的 for 循环，在该循环中我将在数组中设置一个值：

for (int i = 0; i < m; ++i)
  for (int j = 0; j < n; ++j)
    for (int k = 0; k < o; ++k)
      array[k] += foo(...);

或多或少，我想处理这个问题，以便我可以确保同时运行的不同线程不会同时写入 array[k]。关于如何解决这个问题的任何建议？

编辑：我在 Linux 机器上运行，我还必须使用 Intel 编译器。我将使用“icc”而不是“gcc”来编译代码。

4

7 回答 7

4

对于这个特定的循环，把它翻过来。穿k在外面，然后你就可以换k=0到不同的线程k=1，依此类推。

只要foo()不依赖于 array[k] 其中 k != 它是当前 k，那么你就是黄金。

于 2010-04-26T06:27:29.050 回答
3

假设 windows 并且array包含类型的元素，LONG您可以执行以下操作：

for (int i = 0; i < m; ++i) 
   for (int j = 0; j < n; ++j) 
      for (int k = 0; k < o; ++k)  {
          LONG val = foo(...);
          InterlockedAdd( &array[k], val);
      }

如果您不在 Windows 中工作，您的平台可能有一组类似的 API。只要您的平台有一种InterlockedCompareExchange()API，您就可以编写自己的InterlockedAdd().

类似于以下内容（免责声明 - 未经测试）：

 int InterlockedAdd( int volatile* pDest, int operand)
 {
      int curval = *pDest;
      int oldval;

      do {
           oldval = curval;
           curval = InterlockedCompareExchange( pDest, oldval + operand, oldval);
      } while (curval != oldval);

      return oldval+operand;
 }

据我所知，Boost 仅对原子/互锁操作的支持有限，显然仅足以支持引用计数的原子操作。我不认为 Boost 中对互锁操作的支持不仅仅是实现细节（我目前正在处理一个有点旧的 Boost 版本，所以可能不再是这种情况了）。

有一些可移植的库支持原子比较和交换以及其他原子操作作为接口的文档部分：

另请注意，C++0x 将支持比较/交换之类的原子操作——我不确定当前 C++ 编译器的支持级别是多少（它似乎不是 VS 2010）。

于 2010-04-26T06:27:41.123 回答
2

假设数组包含整数，请使用 gcc 的atomic builtins。__sync_fetch_and_add应该做的伎俩。

于 2010-04-26T06:26:52.640 回答
2

你想要的方式，是做不到的！（见 sbi 的评论）

您可以使用共享内存，但仍然会有锁。
您也可以只使用一个线程来写入和读取数组。如果您认为为它设置正确的协议更容易，请继续。

无论如何，使用锁（直接或间接）已经给出了很好的解决方案。随便挑一个吧：）

于 2010-04-26T06:54:46.533 回答
0

在线程之间划分最里面的循环。线程 T1 处理 [0,L) 范围内的索引，线程 T2 处理 [L, 2L) 范围内的索引等。L=o/n 其中 n 是线程数。这假定 foo() 调用不使用可能同时计算的其他位置。

编辑：正如其他人所建议的那样，使用互锁操作将给出正确的结果，但可能会严重降低性能。（如果内部循环很短，许多线程将争夺少数内存位置，这将有效地序列化您的程序。）

于 2010-04-26T06:28:58.720 回答
0

最简单的方法（虽然不是最有效的！）是将循环包装在“关键”部分中。

请参阅此处Wikipedia ，这将在任何给定时间将循环代码限制为单个线程。

于 2010-04-26T06:34:50.627 回答
0

正如其他人所建议的那样，使用互锁操作将给出正确的结果，但可能会严重降低性能。（如果内部循环很短，许多线程将争夺少数内存位置，这将有效地序列化您的程序。）链接|标志

不是真的，我的朋友。实际上联锁操作优于各种锁定。更准确地说：所有同步对象（临界区、互斥体、事件等）都绝对是按照互锁操作来实现的。事实上，互锁操作是唯一可以保证同步一致性的处理器指令。根本不可能在不使用互锁操作的情况下实现同步对象。

另一个问题是锁定的范围。您可能想说，内部循环内的同步范围（使用同步对象或直接使用互锁操作实现）可能会导致性能下降，因为它执行了很多次。

嗯，这是真的。但另一方面，您只在所需的持续时间内锁定您需要的内容。因此，您可以防止潜在的同步冲突。

于 2010-04-26T14:03:01.680 回答