基本的自旋锁互斥实现顺序

Question

有一种流行的自旋锁互斥锁版本在 Internet 上流传，您可能会在 Anthony Williams 的书（C++ Concurrency in Action）中遇到它。在这里：

class SpinLock
{
    std::atomic_flag locked;
public:
    SpinLock() :
        locked{ATOMIC_FLAG_INIT}
    {
    }
    void lock() 
    {
        while(locked.test_and_set(std::memory_order_acquire));
    }
    void unlock() 
    {
        locked.clear(std::memory_order_release);
    }
};

我不明白的是为什么每个人都使用std::memory_order_acquire作为test_and_set，这是一个RMW操作。为什么不是std::memory_acq_rel？假设我们有 2 个线程同时尝试获取锁：

T1: test_and_set -> ret false
T2: test_and_set -> ret false

这种情况应该是可能的，因为我们有 2 个 acquire 操作，它们之间没有形成任何 sync with 关系。是的，在我们解锁互斥量之后，我们有一个 release 操作，它会导致随后的 release sequence 并且生活变得丰富多彩，每个人都很开心。但是为什么在release sequence为首之前是安全的呢？

由于很多人都提到了那个实现，我想它应该可以正常工作。那我错过了什么？

更新 1：

我完全理解操作是原子的，lock和unlock之间的操作不能超出临界区。这不是问题。问题是我没有看到上面的代码如何防止 2 个互斥锁同时进入临界区。为了防止它发生，2 lock 之间应该有 happens before 关系。有人可以使用 C++ 标准概念告诉我代码是完全安全的吗？

更新 2：

好的，我相信我们已经接近正确答案了。我在标准中发现了以下内容：

[atomics.order]条款11

Atomic read-modify-write operations shall always read the last value (in the modification order) written before the write associated with the read-modify-write operation.

在这个重要的说明上，我可以很高兴地结束这个问题，但我仍然有疑问。 in the modification order 部分呢？标准对此很清楚：

[intro.multithread]条款8

All modifications to a particular atomic object M occur in some particular total order, called the modification order of M . If A and B are modifications of an atomic object M and A happens before(as defined below) B, then A shall precede B in the modification order of M , which is defined below.

因此根据 RMW 操作具有最新写入值的子句，最新的写入操作应该发生在读取部分或 RMW 操作之前。问题不是这种情况。对吧？

更新 3：

我越来越认为自旋锁的代码有问题。这是我的推理。 C++ 指定 3 种类型的操作：

获取、释放、获取-释放 - 这些是同步操作。
放松 - 这些不是同步操作
RMW - 这些操作具有 "special" 特征

让我们从 RMW 开始，看看它们有什么特别之处。首先，它们是形成 release sequence 的宝贵资产，其次，它们具有上面引用的特殊条款（[atomics.order] 第 11 条）。我发现没什么特别的。

Acquire/release 是同步操作，release sync with acquire 所以形成了 happens before 关系。宽松的操作只是普通的原子操作，根本不参与修改顺序。

我们的代码中有什么？我们有一个 RMW 操作，它使用获取内存语义，所以每当达到第一次解锁（释放）时，它都有两个角色：

与前面的release

sync with

它参加了release sequence。但这只有在第一个 unlock 完成后才是正确的。

在此之前，如果我们有 2+ 个线程同时是运行我们的 lock 代码，那么我们可以同时输入 pass lock 因为 2 acquire 操作不'形成任何一种关系。它们就像轻松的操作一样无序。由于它们是无序的，我们不能使用任何关于 RMW 操作的特殊子句，因为没有 happens before 关系，因此 locked 标志没有修改顺序。

所以要么是我的逻辑有问题，要么是代码有问题。请知道真相的人对此发表评论。

Answer 1

如你所说，test_and_set是一个RMW操作。然而，对于测试来说，重要的只是读取正确的值。因此，memory_order_acquire 似乎就足够了。

另见 table Constants http://en.cppreference.com/w/cpp/atomic/memory_order

Answer 2

我认为您缺少的是 test_and_set 是原子的，句号。没有使此操作不是原子操作的内存排序设置。如果我们只需要一个原子测试和设置，我们可以指定任何内存顺序。

然而，在这种情况下，我们需要的不仅仅是原子 "test and set" 操作。我们需要确保在我们确认锁是我们的之后执行的内存操作不会在我们观察到互斥锁被解锁之前重新排序。（因为这些操作不会是原子操作。）

考虑：

一些不受互斥锁保护的数据读取。
某些数据写入不受互斥体保护。
我们尝试锁定互斥量。
我们看到互斥量已锁定，但无法锁定它。
我们看到互斥量已解锁并自动锁定它。
一些受互斥体保护的数据读取。
一些写入受互斥体保护的数据。

不能发生的一件事是什么？这是第 6 步和第 7 步中的读写以某种方式重新排序到第 5 步之前，在互斥锁的保护下踩到另一个线程访问共享数据。

test_and_set 操作已经是原子操作，因此第 4 步和第 5 步本质上是安全的。并且步骤 1 和 2 不能修改受保护的数据（因为它们发生在我们尝试锁定之前）所以在我们的锁定操作周围重新排序它们没有坏处。

但是第 6 步和第 7 步——在我们观察到锁已解锁以便我们可以自动锁定它之前，不得重新排序这些步骤。那将是一场灾难。

memory_order_acquire 的定义：“具有此内存顺序的加载操作对受影响的内存位置执行获取操作：在此加载之前，当前线程中的内存访问不能重新排序."

正是我们所需要的。

Answer 3

Could someone show me, using the C++ standard notions, that the code is perfectly safe?

我最初和你有同样的担忧。我认为关键是理解对 std::atomic_flag 变量的操作对于所有 processors/cores 都是原子的。无论指定的内存顺序如何，单独线程中的两个原子 'test and set' 操作不能同时成功，因为它们不可能是原子的；该操作必须应用于实际变量，而不是 缓存的本地副本 （我认为，这甚至不是 C++ 中的概念）。

完整的推理链：

29.7 p5（说到测试和设置操作）：

Effects: Atomically sets the value pointed to by object or by this to true. Memory is affected according to the value of order. These operations are atomic read-modify-write operations (1.10). Returns: Atomically, the value of the object immediately before the effects.

1.10 p6:

All modifications to a particular atomic object M occur in some particular total order, called the modification order of M ...

因此，如果在这种情况下有两个线程同时尝试锁定自旋锁，则其中一个必须先行，另一个先行。我们现在只需要证明第二个线程必然会 return 标志已经设置，从而防止该线程进入临界区。

第6段接着说：

... If A and B are modifications of an atomic object M and A happens before (as defined below) B, then A shall precede B in the modification order of M , which is defined below. [ Note: This states that the modification orders must respect the “happens before” relationship. — end note ]

在两个线程中发生的两个test-and-set操作之间没有"happens before"关系，所以我们无法确定哪个在修改顺序上先；然而，由于 p6 中的第一句话（说明有一个总排序），一个肯定在另一个之前。现在，从 29.3 p12:

Atomic read-modify-write operations shall always read the last value (in the modification order) written before the write associated with the read-modify-write operation.

这说明第二个test-and-set必须看到第一个test-and-set写入的值。任何 acquire/release 的选择都不会影响这个。

因此，如果执行两个测试和设置操作"simultaneously"，它们将被赋予任意顺序，第二个将看到第一个设置的标志值. 因此，为测试和设置操作指定的内存顺序约束无关紧要；它们用于在获取自旋锁期间控制对其他变量的写入顺序。

回复"Update 2"问题：

So according to that clause for an RMW operation to have the latest written value, the latest write operation should happen before the reading part or RMW operation. Which is not the case in the question. Right?

正确的是没有"happen before"关系，但是错误的是RMW操作需要这样的关系才能保证最新的写入值。您列为“[atomics.order] 条款 11”的语句不需要 "happens before" 关系，只是在原子标志的 "modification order" 中一个操作在另一个操作之前。第8条说会有这样一个订单，并且是一个总订单：

All modifications to a particular atomic object M occur in some particular total order, called the modification order of M ...

...然后继续说总排序必须与任何 "happens before" 关系一致：

... If A and B are modifications of an atomic object M and A happens before (as defined below) B, then A shall precede B in the modification order of M, which is defined below.

但是，在没有"happens before"关系的情况下，还是有总排序的——只是这个排序有一定程度的随意性。即如果A和B之间不存在"happens before"关系，则不指定A排在B之前还是排在B之后。但一定是其中之一，因为有一个特定总订单.

那为什么需要memory_order_acquire呢？

自旋锁等互斥锁通常用于保护其他非原子变量和数据结构。在锁定自旋锁时使用 memory_order_acquire 可确保从此类变量中读取的值将看到正确的值（即由先前持有自旋锁的任何其他线程写入的值）。对于解锁，还需要 memory_order_release 以允许其他线程看到写入的值。

acquire/release 既防止编译器重新排序 reads/writes 超过锁的 acquisition/release，并确保生成任何必要的指令以确保适当级别的高速缓存一致性.

进一步证据：

首先，这篇来自 29.3 的笔记：

Note: Atomic operations specifying memory_order_relaxed are relaxed with respect to memory ordering. Implementations must still guarantee that any given atomic access to a particular atomic object be indivisible with respect to all other atomic accesses to that object. — end note

这实质上是说指定的内存排序不会影响原子操作本身。访问必须"be indivisible with respect to all other atomic accesses" 包括来自其他线程的访问。允许两个测试和设置操作读取相同的值将有效地划分至少其中一个，因此它不再是原子的。

此外，从 1.10 第 5 段开始：

In addition, there are relaxed atomic operations, which are not synchronization operations, and atomic read-modify-write operations, which have special characteristics.

（测试集属于后一类）尤其是：

“Relaxed” atomic operations are not synchronization operations even though, like synchronization operations, they cannot contribute to data races.

（强调我的）。两个线程都同时执行原子测试和设置（并且都执行 'set' 部分）的情况将是这样的数据竞争，因此本文再次表明这不可能发生。

1.10 p8:

Note: The specifications of the synchronization operations define when one reads the value written by another. For atomic objects, the definition is clear.

表示一个线程读取另一个线程写入的值。它说对于原子对象的定义是明确的，这意味着不需要其他同步 - 对原子对象执行操作就足够了；效果将立即被其他线程看到。

特别是 1.10 p19:

[ Note: The four preceding coherence requirements effectively disallow compiler reordering of atomic operations to a single object, even if both operations are relaxed loads. This effectively makes the cache coherence guarantee provided by most hardware available to C ++ atomic operations. — end note ]

请注意缓存一致性，即使存在宽松负载。这清楚地表明测试和设置一次只能在一个线程中成功，因为失败要么缓存一致性被破坏，要么操作不是原子的。

基本的自旋锁互斥实现顺序

Basic spin-lock mutex implementation ordering

c++

multithreading

atomic