如何使用原子增量和比较和交换操作处理整数溢出？

Question

我正在编写一些实现（无符号）整数计数器的代码。

1. 它可以从任意数量的线程中使用。
2. 线程每次都应该获得唯一的值，直到溢出。
3. 如果整数类型范围溢出，则应返回零。
4. 我可以使用原子增量函数（返回旧值）和原子比较和交换函数。

到目前为止，我提出的所有场景都受到溢出竞争条件的影响。是否可以在这些限制下实现计数器？

Answer 1

您可以通过比较和交换来构建一切。一般算法是

int DoSomeAtomicCalculation()
{
    static int value;
    int capture, newValue;
    do {
        capture = value;
        newValue = some_function_based_on(capture);
    } while (!compare_and_swap(value, capture, newValue));
    return newValue;
}

（我假设 compare_and_swap 接受一个变量、一个比较值和一个交换值，如果比较成功（并且交换值），则返回 true发生）。