基于两个atomic int的无锁计数器实现问题求助

我需要实现一个无锁结构，能返回严格升序的64位值，现有两个std::atomic_uint32_t变量，计划将它们拼接成unsigned long long类型。设计逻辑是：优先递增第一个变量，当它达到UINT32_MAX时，递增第二个变量并将第一个变量置0。

但我写的代码存在类似ABA的问题——当某线程将第一个变量置0时，其他线程可能读取到错误的组合值，且没有正确递增第二个变量，导致代码无法正常运行。

结构体定义如下：

struct MyStruct {
    std::atomic_uint32_t *firstmem, *secondmem;

    MyStruct(std::atomic_uint32_t & mem1, std::atomic_uint32_t & mem2)  {
        firstmem = &mem1;
        secondmem = &mem2;
    }

    unsigned long long get();
};

问题代码：

unsigned int second = secondmem -> load(), first = firstmem->load();
while (true) {
    unsigned int nfirst = first + 1, nsecond = second;
    if (first == UINT32_MAX) {
        nfirst = 0;
        nsecond = second + 1;
    }
    if (!secondmem->compare_exchange_strong(second, nsecond)) {
        continue;
    }
    if (!firstmem->compare_exchange_strong(first, nfirst)) {
        continue;
    }
    if (secondmem->compare_exchange_strong(second, second)) {
        return convertInts(nsecond, nfirst);
    }
}

问题分析 #

原代码的核心错误在于操作顺序和并发窗口：

• 先更新secondmem再更新firstmem，会导致中间状态不一致：其他线程可能读到已经递增的secondmem和未置0的firstmem（仍为UINT32_MAX），进而重复递增secondmem，破坏序列的严格升序。
• 最后的compare_exchange_strong(second, second)完全无效，它只是检查secondmem的值未变，但无法解决之前操作的原子性问题。
• 当更新firstmem失败时，已经递增的secondmem没有回滚，导致后续线程获取的second值错误。

修复后的代码 #

#include <cstdint>
#include <atomic>

unsigned long long convertInts(unsigned int second, unsigned int first) {
    return (static_cast<unsigned long long>(second) << 32) | first;
}

unsigned long long MyStruct::get() {
    while (true) {
        // 加载当前的两个原子值，后续CAS会验证值是否未被修改
        unsigned int current_second = secondmem->load(std::memory_order_acquire);
        unsigned int current_first = firstmem->load(std::memory_order_acquire);

        unsigned int new_first, new_second;
        if (current_first == UINT32_MAX) {
            new_first = 0;
            new_second = current_second + 1;
        } else {
            new_first = current_first + 1;
            new_second = current_second;
        }

        // 不需要更新second，直接尝试原子更新first
        if (new_second == current_second) {
            if (firstmem->compare_exchange_strong(current_first, new_first,
                                                  std::memory_order_release,
                                                  std::memory_order_acquire)) {
                return convertInts(new_second, new_first);
            }
            // CAS失败，重新加载最新值重试
            continue;
        }

        // 需要更新second时，先原子更新second，成功后再更新first
        if (secondmem->compare_exchange_strong(current_second, new_second,
                                               std::memory_order_release,
                                               std::memory_order_acquire)) {
            // 尝试将first置0，若失败说明其他线程已修改first，无需回滚second——
            // 因为当前second对应的first值已耗尽，递增后的second是合法的
            if (firstmem->compare_exchange_strong(current_first, new_first,
                                                  std::memory_order_release,
                                                  std::memory_order_acquire)) {
                return convertInts(new_second, new_first);
            }
        }
        // 无论哪种CAS失败，都重新加载最新值进入下一轮循环
    }
}

修复说明 #

• 操作顺序优化：不需要更新second时直接操作first，减少不必要的并发冲突；需要更新second时，先完成second的原子更新，再处理first。
• 避免无效回滚：即使first的CAS失败，也不回滚second——因为此时first已被其他线程修改，说明当前second对应的所有first值已经耗尽，second的递增是合理的，后续线程会基于新的first值继续生成序列。
• 内存序保证：使用std::memory_order_acquire/release确保原子操作的可见性，避免编译器或CPU的指令重排序导致的异常。
• 移除无效检查：删掉了无意义的compare_exchange_strong(second, second)，依赖CAS的原子性来保证操作的有效性。

内容的提问来源于stack exchange，提问作者Altick