C++11 无锁自动更新 2 个变量

Question

我想更新 atomicX当一个线程找到一个新的最小值来改变它。当它确实设置了新的最小值时，我还想更改一个变量 y , 原子地。有没有办法在没有锁的情况下做到这一点？

同时在多个线程上执行的线程函数示例:

uint64_t x = atomicX;
int y = g();

for(int newX = 0; newX < x; ++newX)
{
    if(f(newX))
    {
        while(newX < x && !atomicX.compare_exchange_strong(x, newX));
        // also set atomicY to y if the exchange happened above
        break;
    }

    x = atomicX;
}

我可以这样使用锁:

int y = g();

for(uint64_t newX = 0; newX < atomicX; ++newX)
{
    if(f(newX))
    {
        mutex.lock();
        if(newX < atomicX)
        {
            atomicX = newX;
            atomicY = y; // atomicY no longer needs to be atomic
        }
        mutex.unlock()
        break;
    }
}

我也愿意接受任何更清晰的结构，或其他方式一起完成。我不喜欢我必须拥有相同的 newX < x条件两次，否则我必须打破循环。

Answer 1

有一个相当简单且可能足够便携的解决方案，即使用指针和 CAS:

struct XY {
  uint64_t x;
  uint32_t y;
};
std::atomic<XY *> globalXY;

然后棘手的一点就是弄清楚如何分配和释放这些对象而不会产生过多的成本或 ABA 问题。

为了清楚起见，代码最终会是这样的:

XY *newXY = somehow_allocate_objects();
XY *oldXY = globalXY;
int oldX = oldXY->x;
newXY->y = g();

for(int newX = 0; newX < oldX; ++newX) {
    if(f(newX)) {
        // prepare newXY before swapping
        newXY->x = newX;
        while(newX < oldX && !globalXY.compare_exchange_strong(oldXY, newXY)) {
            // oldXY was updated, reload oldX
            oldX = oldXY->x;
        }
        // globalXY->x,y both updated by pointer CAS
        break;
    }
    oldXY = globalXY;
    oldX = oldXY->x;
}

---

作为引用，最终的结论是这些线程是长期存在的，因此为每个线程静态分配一个 XY 实例就足够了。