algorithm - 具有边界的原子的、可扩展的、单调的计数器

Question

我有一个关键代码路径，其中线程使用整数的原子增量来计算全局发生的事件数。这是相当快的，但仍然需要保存整数的缓存行在内核之间反弹。在 NUMA 系统中，这会产生大量 MESI 流量。

热拍的伪代码是所有线程都这样做:

const int CHECK_VALUE = 42;

int counterNew = counter++;
if (counterNew == CHECK_VALUE) {
  Do Final work
}

计数器单调递增，它必须达到的值是预先知道的。

至少一个线程必须断定全局计数器在递增 counter 后已达到 CHECK_VALUE。多个线程得出该结论是可以接受的(我总是可以在那时同步它们 - 因为那不再是热路径)。

如果我知道 counter 是单调的并且最终值是已知的，是否有可能比使用原子增量跟踪 counter 的值做得更好？

Answer 1

您可以使用原子 CAS 操作(比较和交换)来完成。在 i386 架构上，这是 CMPXCHG 指令。如果需要，你可以使用小汇编函数，在你的平台上实现 CAS，或者在这里问我关于英特尔实现。您的代码必须如下:

int local_cnt;
// Atomic increment counter 
do {
  local_cnt = counter;
} while(cas(&counter, local_cnt, local_cnt + 1) != local_cnt);

// check old counter value
if(local_cnt == CHECK_VALUE) { 
  // do something
}