问题 gcc中的原子计数器


我必须要有一个时刻,因为这应该很容易,但我似乎无法让它正常工作。

什么是在GCC中实施原子计数器的正确方法?

即我想要一个从0到4的计数器并且是线程安全的。

我这样做(这是进一步包装在一个类,但不是在这里)

static volatile int _count = 0;
const int limit = 4;

int get_count(){
  // Create a local copy of diskid
  int save_count = __sync_fetch_and_add(&_count, 1);
  if (save_count >= limit){
      __sync_fetch_and_and(&_count, 0); // Set it back to zero
  }
  return save_count;
}

但它从1到4(包括1和4),然后从大约到零。
它应该从0到3。通常我会用mod运算符做一个计数器,但我没有 知道如何安全地做到这一点。

也许这个版本更好。你能看到它或提供的任何问题吗? 更好的解决方案。

int get_count(){
   // Create a local copy of diskid
   int save_count = _count;
   if (save_count >= limit){
      __sync_fetch_and_and(&_count, 0); // Set it back to zero
      return 0;
   }

   return save_count;
 }

实际上,我应该指出,每个线程获得不同的值并不是绝对关键的。如果两个线程碰巧同时读取相同的值,则不会出现问题。但他们随时都不能超过限制。


9771
2017-11-12 03:56


起源



答案:


你的代码不是原子的(而你的第二个 get_count 甚至没有增加计数器值)!

count 在开始时是3并且两个线程同时调用 get_count。其中一个将首先完成原子添加并增加 count 如果第二个线程足够快,它可以将其增加到 5 在第一个线程将其重置为零之前。

此外,在您的回绕处理中,您重置 count 到0而不是 save_count。这显然不是预期的。

这是最简单的 limit 是2的力量。不要自己做减少,只需使用

return (unsigned) __sync_fetch_and_add(&count, 1) % (unsigned) limit;

或者

return __sync_fetch_and_add(&count, 1) & (limit - 1);

这只对每次调用执行一次原子操作,安全且非常便宜。对于通用限制,您仍然可以使用 %,但如果计数器溢出,那将打破序列。您可以尝试使用64位值(如果您的平台支持64位原子)并且只希望它永远不会溢出;不过这是一个坏主意。正确的方法是使用原子比较交换操作。你做这个:

int old_count, new_count;
do {
  old_count = count;
  new_count = old_count + 1;
  if (new_count >= limit) new_count = 0; // or use %
} while (!__sync_bool_compare_and_swap(&count, old_count, new_count));

该方法也推广到更复杂的序列和更新操作。

也就是说,这种类型的无锁操作很难做到,在某种程度上依赖于未定义的行为(所有当前的编译器都是正确的,但在C ++ 0x实际上没有明确定义的内存模型之前没有C / C ++标准)和容易打破。我建议使用一个简单的互斥锁/锁,除非你已经对它进行了分析并发现它是一个瓶颈。


13
2017-11-12 04:32



__sync_fetch_and_add“每次调用执行一次原子操作”取决于CPU - 问题中未指定。它可能是根据你的比较和交换方法实现的,这是我过去在Sun硬件上使用的(好吧,我的前同事的实现,可爱地命名为“atomic_robin”:-))。 - Tony Delroy
我不是在谈论执行的指令数量;有不同的方法来实现exchange-add,但只要它们实际只写入内存(“commit”)一次,它们就是等价的。关键是你不能用几个小原子构建一个“大”原子基元;他们没有写作。您可以使用多个步骤,但最终(提交)步骤必须是使一切可见的单个原子操作。如果最后有多个这样的步骤,则会自动出现竞争条件。 - Fabian Giesen
嘿谢谢。这正是我所追求的。不知道我的第二个解决方案是什么。我想是因为缺乏睡眠让我编写了如此优秀的代码。 - Matt
我不明白为什么如果计数器以非2次幂限制溢出,序列将会中断。有人可以解释一下吗? - Julien-L


答案:


你的代码不是原子的(而你的第二个 get_count 甚至没有增加计数器值)!

count 在开始时是3并且两个线程同时调用 get_count。其中一个将首先完成原子添加并增加 count 如果第二个线程足够快,它可以将其增加到 5 在第一个线程将其重置为零之前。

此外,在您的回绕处理中,您重置 count 到0而不是 save_count。这显然不是预期的。

这是最简单的 limit 是2的力量。不要自己做减少,只需使用

return (unsigned) __sync_fetch_and_add(&count, 1) % (unsigned) limit;

或者

return __sync_fetch_and_add(&count, 1) & (limit - 1);

这只对每次调用执行一次原子操作,安全且非常便宜。对于通用限制,您仍然可以使用 %,但如果计数器溢出,那将打破序列。您可以尝试使用64位值(如果您的平台支持64位原子)并且只希望它永远不会溢出;不过这是一个坏主意。正确的方法是使用原子比较交换操作。你做这个:

int old_count, new_count;
do {
  old_count = count;
  new_count = old_count + 1;
  if (new_count >= limit) new_count = 0; // or use %
} while (!__sync_bool_compare_and_swap(&count, old_count, new_count));

该方法也推广到更复杂的序列和更新操作。

也就是说,这种类型的无锁操作很难做到,在某种程度上依赖于未定义的行为(所有当前的编译器都是正确的,但在C ++ 0x实际上没有明确定义的内存模型之前没有C / C ++标准)和容易打破。我建议使用一个简单的互斥锁/锁,除非你已经对它进行了分析并发现它是一个瓶颈。


13
2017-11-12 04:32



__sync_fetch_and_add“每次调用执行一次原子操作”取决于CPU - 问题中未指定。它可能是根据你的比较和交换方法实现的,这是我过去在Sun硬件上使用的(好吧,我的前同事的实现,可爱地命名为“atomic_robin”:-))。 - Tony Delroy
我不是在谈论执行的指令数量;有不同的方法来实现exchange-add,但只要它们实际只写入内存(“commit”)一次,它们就是等价的。关键是你不能用几个小原子构建一个“大”原子基元;他们没有写作。您可以使用多个步骤,但最终(提交)步骤必须是使一切可见的单个原子操作。如果最后有多个这样的步骤,则会自动出现竞争条件。 - Fabian Giesen
嘿谢谢。这正是我所追求的。不知道我的第二个解决方案是什么。我想是因为缺乏睡眠让我编写了如此优秀的代码。 - Matt
我不明白为什么如果计数器以非2次幂限制溢出,序列将会中断。有人可以解释一下吗? - Julien-L


你很幸运,因为你想要的范围恰好恰好适合2位。

简单的解决方案:让volatile变量永远计数。但在阅读之后,只使用最低的两位(val & 3)。 Presto,0-3原子计数器。


2
2017-11-12 04:30



或者只是使用mod - Inverse
@Inverse:mod可以慢得多......并且是一个更安全的赌注。 - Tony Delroy
那是个很好的观点。虽然我需要限制的值是任意的。它来自配置文件。 - Matt
@Tony:我很确定编译器可以优化 x % 4 至 x & 3 - Inverse
是的,编译器将进行优化 x % 4 至 x & 3。但不要被愚弄,因为 % 接受一个不是2的幂的rhs,它会更普遍。事实上,我的优化仅适用于2的幂,因为当计数器最终溢出时,它将按顺序计数2次幂,但跳过任何其他模数。 - Ben Voigt


在纯C中创建任何原子都是不可能的,即使是 volatile。你需要asm。 C1x将具有特殊的原子类型,但在那之前你会遇到asm。


0
2017-11-12 03:58



对不起,我不应该把它标记为C.这是C ++,但不是使用c1x。 - Matt
纯C,当然,但他也标记了gcc,所以内在函数/内置函数是最好的选择。 - Matt Joiner
的确,我的坏。 - R..
链接和引用+1的原子类型,因为它将在许多年内有用。 - Matt Joiner


你有两个问题。

__sync_fetch_and_add 将返回 以前 价值(即在加一之前)。所以在这一步 _count 成为3,你的本地人 save_count变量正在回归 2。所以你实际上必须增加 _count 取决于 4 在它回归之前 3

但即使最重要的是,你也是专门寻找的 >= 4 在你把它重新设置为0之前。如果你只是想要它高达三,那就是使用错误限制的问题。


0
2017-11-12 04:03