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

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如果比较成功(并且发生了交换)则返回.