在C++中使用乐观锁和内存顺序

Question

我想知道 'optimistic locks'（如此处所述：https://db.in.tum.de/~leis/papers/artsync.pdf）如何在 C++ 中用于非原子数据以及应使用哪些内存顺序。

我对上述论文的理解是，以下代码将同步 t1 和 t2，而 t1 将打印两个更新的变量或 none.

static constexpr uint64_t locked_bit = (1ULL << 63);

std::atomic<int> data1 = 0;
std::atomic<int> data2 = 0;
std::atomic<uint64_t> versioned_lock = 0;

int main() {
    std::thread t1([&]{
        restart:
        auto s = versioned_lock.load();
        if (s & locked_bit)
            goto restart;

        auto local_data1 = data1.load();
        auto local_data2 = data2.load();
        if (s == versioned_lock.load()) {
            // data has not been overwritten yet, can safely use local_data
            std::cout << local_data1 << " " << local_data2 << std::endl;
        } else {
            // possible race, local_data might be garbage?
        }
    });

    std::thread t2([&]{
        auto current_lock_version = versioned_lock.load();
        current_lock_version++;
        versioned_lock.store(current_lock_version | locked_bit);
        data1.store(1234);
        data2.store(4321);
        versioned_lock.store(current_lock_version);
    });

    t1.join();
    t2.join();
}

我的问题是：

这是没有 UB 的有效 C++ 代码吗？
我关于同步的假设是否正确？ t1 实际上会打印“0 0”或“1234 4321”吗？
reading/writing 到 versioned_lock 应该使用什么内存顺序？它应该是 memory_order_seq_cst 还是可以限制较少？如果 data1 和 data2 是非原子的（只是 int 或什至一些更复杂的数据类型）它也会工作吗并且它会影响所需的内存顺序（或者可能需要atomic_thread_fence)?

Answer 1

Is this a valid C++ code with no UB?

我也这么认为。在这样的程序中获得 UB 的通常方法是数据竞赛，但这只有在写入 non-atomic 变量时才会发生同时，此程序中的每个共享变量都是原子的。

Are my assumption about synchronization correct? Will t1 actually print either "0 0" or "1234 4321"?

是的。这个版本所有的加载和存储都是seq_cst，所以他们以某种总顺序出现，我将使用 < 来表示。设 L1、L2 表示两个负载 versioned_lock在t1，而S1、S2在t2有两家店。

如果S1、S2都出现在L1之前，那么两个新值都会被看到然后我们打印 1234 4321，这很好。如果 S1、S2 都出现在 L2 之后，那么我们打印 0 0，这也很好。如果 S1 或 S2 出现在两者之间 L1 和 L2，然后 L1 和 L2 return 不同的值，我们不打印任何东西，这又很好。

剩下的唯一顺序是 S1 < L1 < L2 < S2。在这种情况下 L1 returns 设置了锁定位的值，因此我们重新开始循环而不是打印。

What memory orders should be used for reading/writing to versioned_lock? Should it be memory_order_seq_cst or can it be something less restrictive?

我认为满足以下条件：

static constexpr uint64_t locked_bit = (1ULL << 63);

std::atomic<int> data1 = 0;
std::atomic<int> data2 = 0;
std::atomic<uint64_t> versioned_lock = 0;

int main() {
    std::thread t1([&]{
        restart:
        auto s = versioned_lock.load(std::memory_order_acquire); // L1
        if (s & locked_bit)
            goto restart;

        auto local_data1 = data1.load(std::memory_order_relaxed);
        auto local_data2 = data2.load(std::memory_order_relaxed);
        std::atomic_thread_fence(std::memory_order_acquire);    // AF
        if (s == versioned_lock.load(std::memory_order_relaxed)) { // L2
            // data has not been overwritten yet, can safely use local_data
            std::cout << local_data1 << " " << local_data2 << std::endl;
        } else {
            // possible race, local_data might be garbage?
        }
    });

    std::thread t2([&]{
        auto current_lock_version = versioned_lock.load(std::memory_order_relaxed);
        current_lock_version++;
        versioned_lock.store(current_lock_version | locked_bit, std::memory_order_relaxed); // S1
        std::atomic_thread_fence(std::memory_order_release); // RF
        data1.store(1234, std::memory_order_relaxed);
        data2.store(4321, std::memory_order_relaxed);
        versioned_lock.store(current_lock_version, std::memory_order_release); // S2
    });

    t1.join();
    t2.join();
}

即清除和测试锁定的 versioned_lock 的访问位必须被释放和获取，数据的存储必须是前面是释放栅栏，数据加载后跟获得栅栏。直觉上，这应该可以防止数据访问从保护它们的锁访问之间泄漏出去。（你也可以让所有的数据存储被释放然后放下释放栅栏，但那是不必要的 strong：我们不关心两个数据存储是否分别重新排序其他。如果我们有更多的数据元素，那将产生更大的不同。这同样适用于使数据加载获取的选项。）

为了证明这有效，请注意我们必须避免的两个结果是 1234 0 和 0 4321。所以假设data1returns1234的负载（data2returns4321的情况等价）。由于这是由 t2 存储的值，释放栅栏 (RF) 与获取栅栏 (AF) 同步。现在 S1 排在 RF 之前，AF 排在 L2 之前，所以我们得出结论，S1 发生在 L2 之前。因此L2不能return0；它要么 returns locked_bit 要么 1.

如果 L1 return 与 L2 的值不同，那么我们将不会打印。如果 L1 returns locked_bit 我们也不会打印。剩下的一种情况是L1和L2都return1。这种情况下，L1读取了S2写入的值，L1/S2是acquire/release，所以S2和L1同步。数据存储在 S2 之前排序，L1 在数据加载之前排序，因此两个数据存储都发生在两个数据加载之前。因此我们看到两个新值，并打印 1234 4321.

Will it work also if data1 and data2 are non-atomic (just int or even some more complex data type)?

不，那根本行不通。该算法中没有任何内容可以阻止来自冲突的 data1, data2 的存储和负载；就是这样当它们发生冲突时，我们对版本锁的测试告诉我们不要使用数据。但是如果它们不是原子的，那么冲突的存储和负载将是一场数据竞争，无论我们是否使用，都会导致未定义的行为数据与否。

在C++中使用乐观锁和内存顺序

Using optimistic locks in C++ and memory order

c++

synchronization

locking

stdatomic

optimistic-locking