C++11无锁更新两个变量的原子性

Question

C++11无锁更新两个变量的原子性

c++multithreadingc++11atomiccompare-and-swap

4

我希望当一个线程找到一个新的最小值来改变它时，能够更新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 条件，或者必须打破循环。

- David

1

你是否有类似于 struct s { int x; int y; }; std::atomic<s> 这样的东西？在你的平台上它很可能是无锁的。这里可以查看示例。 - dyp

@dyp 我排除了它，因为我认为它不会是无锁的。这最终将在多个平台上运行，我宁愿选择一些我可以合理地假设在所有平台上都是无锁的东西（例如atomic<int>）。 - David

2

只有 std::atomic_flag 在所有平台上都保证是无锁的。 - dyp

@dyp 我不需要真正的担保，只需要一个强有力的“它在任何现代设备上都应该是无锁的”。 - David

在“任何现代机器”上，int 是32位，而指针是64位。如果 std::atomic 对于 void* 和 struct {int x; int y;}; 都不是无锁的话，我会感到惊讶。 - Casey

显示剩余7条评论

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Useless · Accepted Answer

有一个相当简单且可能足够可移植的解决方案，即使用指针和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 实例就足够了。