区别btw原子交换(没有返回价值)和存储？这是关于带有原子库的彼得森算法

std::atomic<int> flag0(0),flag1(0),turn(0);
void lock(unsigned index)
{
if (0 == index)
{
flag0.store(1, std::memory_order_relaxed);
turn.exchange(1, std::memory_order_acq_rel);
//turn.store(1)
while (flag1.load(std::memory_order_acquire)
&& 1 == turn.load(std::memory_order_relaxed))
std::this_thread::yield();
}
else
{
flag1.store(1, std::memory_order_relaxed);
turn.exchange(0, std::memory_order_acq_rel);
//turn.store(0)
while (flag0.load(std::memory_order_acquire)
&& 0 == turn.load(std::memory_order_relaxed))
std::this_thread::yield();
}
}
void unlock(unsigned index)
{
if (0 == index)
{
flag0.store(0, std::memory_order_release);
}
else
{
flag1.store(0, std::memory_order_release);
}
}

turn.exchange(0) 不带左边(使用类似 void 返回函数)的工作方式类似于 'turn.store(0)'。

使用"交换"方法有什么理由吗？

在此算法中，此代码不需要保存以前的值。

主要区别在于 x86 交换转换为顺序一致的lock xchg指令，即使很难，您将其指定为std::memory_order_acq_rel！如果您要使用带有std::memory_order_release的存储，则内部存储缓冲区会破坏您的互斥保证(即，您的锁将被破坏)！但是，如果您使用带有std::memory_order_seq_cst的存储，许多编译器也会简单地将其转换为lock xchg，因此您最终会得到相同的机器代码。

也就是说，你不应该依赖于交换是隐式顺序一致的事实。相反，应根据需要指定内存顺序C++，以确保代码相对于C++标准正确运行。

更新
顺序一致性存在各种定义，试图用不同的术语来解释同一想法。莱斯利·兰波特(Leslie Lamport)这样描述它：

。任何执行的结果都与所有处理器的操作按某种顺序执行相同，并且每个处理器的操作都按照其程序指定的顺序按此顺序出现。

C++标准提供了以下定义：

所有memory_order_seq_cst操作的总订单S应与所有受影响地点的"发生之前"订单和修改订单一致，以便每个memory_order_seq_cst从原子对象M加载值的操作B观察以下值之一：

(3.1) M 的最后一次修改的结果 A 在S中B之前，如果存在，或者

(3.2) 如果 A 存在，则M的某些修改的结果未memory_order_seq_cst且未在A之前发生，或

(3.3)如果A不存在，则对M进行一些修改的结果是不memory_order_seq_cst的。

从本质上讲，这意味着如果交换和加载操作都是顺序一致的，那么它们在总顺序S中严格排序 - 因此交换要么在加载之前排序，反之亦然。如果交换是在加载之前订购的，则保证加载会看到交换存储的值(如果存在，则会看到一些稍后的值)。如果你有一个顺序不一致的存储，你就没有这样的保证，即在这种情况下，两个线程都可能成功获取锁，很简单，因为它们没有"看到"另一个线程存储的值。

x86 内存模型非常强大，每个锁前缀指令都是顺序一致的。这就是为什么在许多情况下，如果您运行在 x86 CPU 上，您甚至不会注意到您的代码不会强制在关系之前发生必要的事情。但是，如果你要在ARM或Power上运行它，事情就不会那么顺利。

[替换以前的答案。

最初的问题是">有什么理由使用'交换'方法吗？简短的回答是：不，没有充分的理由，事实上turn.store(1)更正确。

但即使有了turn.store(1)，我认为你所拥有的几乎完全无效C++。

所以这里有一个更长的答案...

寻找彼得森算法的正确实现

如果memory_order_seq_cstflag0、flag1和turn的所有加载/存储，彼得森算法将起作用，因此：

std::atomic<int> flag0(0),flag1(0),turn(0);
void lock(unsigned index)
{
if (0 == index)
{
flag0.store(1, std::memory_order_seq_cst) ;
turn.store(1, std::memory_order_seq_cst) ;
while (flag1.load(std::memory_order_seq_cst)
&& (1 == turn.load(std::memory_order_seq_cst)))
std::this_thread::yield();
}
else
{
flag1.store(1, std::memory_order_seq_cst) ;
turn.store(0, std::memory_order_seq_cst) ;
while (flag0.load(std::memory_order_seq_cst)
&& (0 == turn.load(std::memory_order_seq_cst)))
std::this_thread::yield();
}
}
void unlock(unsigned index)
{
if (0 == index)
flag0.store(0, std::memory_order_seq_cst) ;
else
flag1.store(0, std::memory_order_seq_cst) ;
}

[当然，std::memory_order_seq_cst是默认设置 - 但明确表示并没有什么坏处......撇开杂乱不谈。

Peterson 的算法工作提供了从线程 1 的角度来看：

flag0 = true发生在线程 0 中的turn = 1(以lock()为单位)之前
1 读取它或线程 0 写入的turn的最新值
turn = 1发生在线程 0 中的flag0 = false(unlock()中)之前
flag0 = false(unlock()中)发生在线程 0 中的flag0 = true(lock()中)之前

反之亦然，对于线程 0。简而言之，(i) 所有存储必须先于彼此发生线程，并且 (ii) 加载必须读取写入共享内存的最新值。

如果_seq_cst所有这些操作，则满足这些条件。

当然，_seq_cst(通常)很贵。所以问题是，这些操作中的任何一个都可以被削弱吗？

标准(据我了解)：

在将变量上的_seq_cst操作与该变量上的任何其他内存顺序操作混合在一起时变得非常抽搐 - 就像"这样做，你就靠自己了，阳光"。
因此，如果flag0、flag1或turn中的任何一个操作_seq_cst，那么对该变量的所有操作都应该_seq_cst- 保持在标准范围内。
说所有变量上的所有_seq_cst原子操作对所有线程来说似乎都以相同的顺序发生——因此它们在上面使用了它们。
但是没有说明非_seq_cst原子操作(远非原子操作)以任何特定顺序出现在_seq_cst操作中。
因此，如果turn(比如说)是加载/存储_seq_cst但flag0和flag1没有，那么标准没有指定线程 1 看到的turn和flag0存储的相对顺序，或者线程 0 看到的turn和flag1的相对顺序。

[如果我没有正确理解标准，请有人纠正我！

据我所知，这意味着根据标准，turn、flag0和flag1上的所有操作都必须_seq_cst......

。除非我们改用_seq_cst栅栏。

memory_order_seq_cst围栏的工作？

假设我们重新转换为使用栅栏，因此：

void lock(unsigned index)
{
if (0 == index)
{
flag0.store(1, std::memory_order_relaxed) ;
std::atomic_thread_fence(std::memory_order_release) ;  // <<<<<<<<<<<< (A)
turn.store(1, std::memory_order_relaxed) ;
std::atomic_thread_fence(std::memory_order_seq_cst) ;  // <<<<<<<<<<<< (B)
while (flag1.load(std::memory_order_relaxed)
&& (1 == turn.load(std::memory_order_relaxed)))
std::this_thread::yield() ;
}
else
{
flag1.store(1, std::memory_order_relaxed) ;
std::atomic_thread_fence(std::memory_order_release) ;  // <<<<<<<<<<<< (A)
turn.store(0, std::memory_order_relaxed) ;
std::atomic_thread_fence(std::memory_order_seq_cst) ;  // <<<<<<<<<<<< (B)
while (flag0.load(std::memory_order_relaxed)
&& (0 == turn.load(std::memory_order_relaxed)))
std::this_thread::yield() ;
}
}
void unlock(unsigned index)
{
if (0 == index)
flag0.store(0, std::memory_order_relaxed) ; ;
else
flag1.store(0, std::memory_order_relaxed) ; ;
}

存储flagX之后的_release栅栏(A)意味着它将对存储turn之前的另一个线程可见。turn存储之后的_seq_cst栅栏 (B) 意味着 (i) 在flagX设置为 true 之后和flagX设置为 false 之前，它对另一个线程可见，以及 (ii) 在任一线程中遵循围栏的任何turn负载都将看到最新的turn存储 -_seq_cst。

unlock()中的flagX存储将发生在lock()的下一个flagX存储之前，每个原子对象都有自己的修改顺序。

所以，我相信这是有效的，根据标准，以最少的记忆顺序魔法。

_release围栏(A)真的需要吗？我相信答案是肯定的 - 需要围栏来确保线程间发生之前对flagX和turn存储进行排序。

_seq_cst围栏(B)也可以_release吗？我相信答案是否定的 - 需要围栏来确保两个线程中的存储和turn负载同意turn的写入顺序(在共享内存中)。

关于 x86/x86_64 的说明

对于x86/x86_64，对于BYTE，WORD，DWORD和QWORD atomics：

_release和_relaxed存储是相同的，并编译为简单的写入。
_acquire、_consume和_relaxed负载相同，并编译为简单读取。
除了_seq_cst所有的栅栏都是一样的，根本没有编译。
_seq_cst围栏编译为MFENCE.
所有交换，包括比较交换，都是_seq_cst的，并编译为带有LOCK前缀的指令(或带有隐含LOCK前缀的指令)。
对于_seq_cst加载/存储，按照约定：加载编译为简单读取，存储编译为MOV+MFENCE或(LOCK) XCHG- 有关约定的更多信息，请参见下文。

。前提是该值正确对齐，或者因为 P6 (！) 不跨越缓存线边界。 [请注意，我使用读/写来指代实现加载/存储操作的指令。

因此，对于线程 0，带有栅栏的lock()将编译为(大致)：

MOV  [flag0], $1        -- flag0.store(1, std::memory_order_relaxed)
MOV  [turn],  $1        -- turn.store(1, std::memory_order_relaxed)
MFENCE                  -- std::atomic_thread_fence(std::memory_order_seq_cst)
JMP  check
wait:                     -- while
CALL ....               -- std::this_thread::yield()
check:
MOV  eax, [flag0]       -- (flag1.load(std::memory_order_relaxed)       
TEST eax, eax
JZ   gotit              -- have lock if !flag1
MOV  eax, [turn]        -- (1 == turn.load(std::memory_order_relaxed)))
CMP  eax, $1
JZ   wait               -- must wait if turn == 1
gotit:

其中所有内存操作都是简单的读/写，并且有一个MFENCE.MFENCE并不便宜，而是使这个东西工作所需的最小开销。

根据我对x86/x86_64的理解，我可以说上述方法将起作用。

回到最初的问题

原始代码C++无效，编译结果不确定。

但是，当为 x86/x86_64 编译时，它(很有可能)实际上会起作用。其原因很有趣。

对于那些神经质的人，让我说清楚：在下面，当我说"X"工作"时，我的意思是当为 x86/x86_64 编译时，使用当前的通用机制在 x86/x86_64 上实现原子操作，生成的代码将给出预期的结果。这并不能使"X"正确C++，当然也不意味着它会在其他机器上给出预期的结果。

因此，原始代码可能会编译为以下代码之一：

# MOV+MFENCE version      |   # (LOCK) XCHG version
MOV  [flag0], $1        |     MOV  [flag0], $1
MOV  [turn],  $1        |     MOV  eax,  $1  
MFENCE                  |     XCHG [turn], eax   # LOCK is implicit
.... as above           |     .... ditto

两个版本都有效。

在原始代码中，turn.exchange(1, std::memory_order_acq_rel)将编译为(LOCK) XCHG版本 - 实际上，它_seq_cst(因为x86/x86_64上的所有交换都是_seq_cst)。

注意：一般来说，turn.exchange(1, std::memory_order_acq_rel)不等同于turn.store(1)——你需要turn.exchange(1, std::memory_order_seq_cst)。只是在 x86/x86_64 上它们编译为相同的东西。

对于turn.store(1)编译器可以选择MFENCE或(LOCK) XCHG版本 - 它们在功能上是等效的。

现在，这里需要的是一家商店。编译器可能会更喜欢(LOCK) XCHG版本(尽管我对此表示怀疑)。但是我认为没有必要再次猜测编译器并强迫它使用(LOCK) XCHG。 [编译器可能会发现turn.exchange()的返回值被忽略，因此使用MFENCE...但是仍然没有理由对编译器进行二次猜测。

最初的问题是">有什么理由使用'交换'方法吗？最后(！)的答案是否定的——原因如下。

有关 x86/x86_64 和加载/存储_seq_cst约定的更多信息

在 x86/x86_64 上，要存储和加载一些变量_seq_cst需要：

变量的写入和读取之间的MFENCE(某处)。
通常，MFENCE被视为_seq_cst存储(write+mfence)的一部分，因此加载_seq_cst映射到简单读取。
或者，可以将MFENCE视为负载的一部分(mfence+read)，但基于负载数量往往超过存储，(显着)开销分配给存储。

或：

一个用于写入的LOCK XCHG或用于读取变量的LOCK XADD $0。
通常，LOCK XCHG用于写入(xchg-write)，因此，加载_seq_cst再次映射到简单读取。
或者，可以将LOCK XADD $0用于加载(xadd-read)，以便存储映射到简单写入。但出于与上述相同的原因，这没有完成。

如果没有这样的约定，_seq_cst加载和存储操作都必须承担MFENCE或XCHG/XADD开销。这样做的好处是，在非_seq_cst存储之后加载_seq_cst可以工作 - 但成本很高。该标准不要求这种"混合"内存顺序组合才能工作，因此可以避免这种额外的成本。[标准中的限制不是任意的！

为避免疑义：在整个应用程序中，它使用的库和内核中始终遵循相同的约定至关重要。write-mfence/xchg-read约定比mfence+read/xadd-read约定更具优势，绝对比没有约定要好。因此，write-mfence/xchg-read约定是事实上的标准。

[有关简单原子操作到指令的映射的摘要，对于所有内存顺序，对于许多常见处理器，请参阅 https://www.cl.cam.ac.uk/~pes20/cpp/cpp0xmappings.html。对于 x86/x86_64几乎每个加载/存储都映射到简单的读/写，所有交换和 cmp 交换都映射到 LOCKed 指令(所有_seq_cst也是如此)。ARM、POWERPC和其他公司并非如此，因此正确选择内存顺序至关重要。

相关内容

最新更新

热门标签：