16

前言

我最近遇到了一些同步问题,这导致我使用自旋锁原子计数器。然后我又搜索了一下,这些是如何工作的,并找到了std::memory_order和内存屏障(mfence,lfencesfence)。

所以现在,似乎我应该对自旋锁使用获取/释放,对计数器使用放松

一些参考

x86 MFENCE - 内存围栏
x86 LOCK - 断言 LOCK# 信号

问题

这三个操作的机器代码(编辑:见下文)是什么(lock = test_and_set,unlock = clear,increment = operator++ = fetch_add),默认(seq_cst)内存顺序和获取/释放/放松(按这些顺序)三个操作)。有什么区别(哪些内存屏障在哪里)和成本(多少 CPU 周期)?

目的

我只是想知道我的旧代码(未指定使用的内存顺序 = seq_cst)到底有多糟糕,以及我是否应该创建一些class atomic_counter派生自std::atomic但使用宽松的内存排序 (以及在某些地方使用获取/释放而不是互斥锁的良好自旋锁)。 ..或使用来自boost库的东西——到目前为止我一直避免boost)

我的知识

到目前为止,我确实理解自旋锁保护的不仅仅是它本身(但也保护了一些共享资源/内存),因此,必须有一些东西可以使多个线程/核心的一些内存视图保持一致(即那些获取/释放和内存栅栏) ) . 原子计数器只为自己而存在,只需要那个原子增量(不涉及其他内存,我读它时并不真正关心它的值,它信息丰富,可能是几个周期的旧,没问题)。有一些LOCK前缀和一些指令,比如xchg隐含地拥有它。我的知识到此结束,我不知道缓存和总线是如何真正工作的以及背后是什么(但我知道现代 CPU 可以重新排序指令,并行执行它们并使用内存缓存和一些同步)。谢谢你的解释。

PS:我现在有旧的32位PC,只能看到lock addl和简单xchg,没有别的-所有版本看起来都一样(解锁除外),memory_order在我的旧PC上没有区别(除了解锁,释放使用move而不是xchg)。对于 64 位 PC 来说会是这样吗?(编辑:见下文)我必须关心内存顺序吗?(回答:不,不多,解锁时释放可以节省几个周期,仅此而已。)

编码:

#include <atomic>
using namespace std;

atomic_flag spinlock;
atomic<int> counter;

void inc1() {
    counter++;
}
void inc2() {
    counter.fetch_add(1, memory_order_relaxed);
}
void lock1() {
    while(spinlock.test_and_set()) ;
}
void lock2() {
    while(spinlock.test_and_set(memory_order_acquire)) ;
}
void unlock1() {
    spinlock.clear();
}
void unlock2() {
    spinlock.clear(memory_order_release);
}

int main() {
    inc1();
    inc2();
    lock1();
    unlock1();
    lock2();
    unlock2();
}

g++ -std=c++11 -O1 -S ( 32bit Cygwin,缩短输出)

__Z4inc1v:
__Z4inc2v:
    lock addl   $1, _counter    ; both seq_cst and relaxed
    ret
__Z5lock1v:
__Z5lock2v:
    movl    $1, %edx
L5:
    movl    %edx, %eax
    xchgb   _spinlock, %al      ; both seq_cst and acquire
    testb   %al, %al
    jne L5
    rep ret
__Z7unlock1v:
    movl    $0, %eax
    xchgb   _spinlock, %al      ; seq_cst
    ret
__Z7unlock2v:
    movb    $0, _spinlock       ; release
    ret

x86_64bit 的更新:(mfenceunlock1

_Z4inc1v:
_Z4inc2v:
    lock addl   $1, counter(%rip)   ; both seq_cst and relaxed
    ret
_Z5lock1v:
_Z5lock2v:
    movl    $1, %edx
.L5:
    movl    %edx, %eax
    xchgb   spinlock(%rip), %al     ; both seq_cst and acquire
    testb   %al, %al
    jne .L5
    ret
_Z7unlock1v:
    movb    $0, spinlock(%rip)
    mfence                          ; seq_cst
    ret
_Z7unlock2v:
    movb    $0, spinlock(%rip)      ; release
    ret
4

4 回答 4

12

x86 主要具有强大的内存模型,所有常见的存储/加载都隐式地具有释放/获取语义。例外情况只有 SSE 非临时存储操作需要sfence像往常一样订购。所有带有前缀的读-修改-写(RMW)指令都LOCK暗示了完整的内存屏障,即seq_cst。

因此在 x86 上,我们有

  • test_and_set可以用lock bts(用于按位操作)lock cmpxchg、 或lock xchg(或仅xchg暗示lock)进行编码。lock inc如果需要公平,其他自旋锁实现可以使用类似(或 dec)的指令 。不可能try_lock使用释放/获取栅栏来实现(至少mfence无论如何你都需要独立的内存屏障)。
  • clearlock and(for bit-wise) or编码lock xchg,但是,更有效的实现将使用普通的 write ( mov) 而不是锁定指令。
  • fetch_add用 编码lock add

删除lock前缀并不能保证 RMW 操作的原子性,因此不能将此类操作严格解释为具有memory_order_relaxedC++ 视图。但是在实践中,您可能希望在安全的情况下(在构造函数中,处于锁定状态)通过更快的非原子操作访问原子变量。

根据我们的经验,执行哪个 RMW 原子操作并不重要,它们执行的周期数几乎相同(mfence 大约是锁操作的 x0.5)。您可以通过计算原子操作(和 mfence)的数量以及内存间接(缓存未命中)的数量来估计同步算法的性能。

于 2014-08-18T12:56:32.887 回答
10

我推荐:x86-TSO: A Rigorous and Usable Programmer's Model for x86 Multiprocessors

您的 x86 和 x86_64 确实非常“表现良好”。特别是,它们不会重新排序写入操作(并且任何推测性写入在 cpu/核心的写入队列中时都会被丢弃),并且它们不会重新排序读取操作。但是,它们会尽可能早地开始读取操作,这意味着读取和写入可以重新排序。(读取写入队列中的内容会读取排队的值,因此不会重新排序同一位置的读取/写入。)所以:

  • read-modify-write 操作需要LOCKs ,这使得它们隐含地成为 memory_order_seq_cst

    因此,对于这些操作,通过削弱内存排序(在 x86/x86_64 上),您将一无所获。一般建议是“保持简单”并坚持使用memory_order_seq_cst,这很高兴不会为 x86 和 x86_64 花费任何额外费用。

    对于比奔腾更新的任何东西,如果 cpu/core 已经对受影响的内存具有“独占”访问权限,LOCK则不会影响其他 cpu/core,并且可能是一个相对简单的操作。

  • memory_order_acquire/_release不需要mfence任何其他开销。

    因此,对于原子加载/存储,如果获取/释放就足够了,那么对于 x86/x86_64,这些操作是“免税的”。

  • memory_order_seq_cst确实需要mfence...

...这值得理解。

(注意:我们在这里讨论的是处理器如何处理编译器生成的指令。编译器对操作的重新排序是一个非常相似的问题,但这里没有解决。)

停止 cpu/核心,直到所有挂起的mfence写入都从写入队列中清除。特别是,mfence在写队列为空之前,任何跟在后面的读操作都不会开始。考虑两个线程:

  initial state: wa = wb = 0

  thread 'A'                    thread 'B'
    wa = 1 ;  (mov [wa] ← 1)      wb = 1 ;   (mov [wb] ← 1)
    a  = wb ; (mov ebx ← [wb])    b  = wa ;  (mov ebx ← [wa])

留给自己的设备,x86/x86_64 可以产生 (a = 1, b = 1), (a = 0, b = 1), (a = 1, b = 0)(a = 0, b = 0)。如果您期望memory_order_seq_cst,最后一个是无效的——因为您无法通过任何操作的交错来获得它。发生这种情况的原因是 和 的写入在各自的 cpu/核心队列中排队,并且 和 的读取都可以被调度并且都可以在任一写入之前完成。要实现memory_order_seq_cst,您需要:wawbwawbmfence

  thread 'A'                    thread 'B'
    wa = 1 ;  (mov [wa] ← 1)      wb = 1 ;   (mov [wb] ← 1)
        mfence ;                      mfence
    a  = wb ; (mov ebx ← [wb])    b  = wa ;  (mov ebx ← [wa])

由于线程之间没有同步,因此结果可能是(a = 0, b = 0) 之外的任何值。有趣的是,这mfence是为了线程本身的利益,因为它可以防止读取操作在写入完成之前开始。其他线程唯一关心的是写入发生的顺序,x86/x86_64 在任何情况下都不会重新排序。

因此,要实现memory_order_seq_cst atomic_load()atomic_store(),有必要mfence在一个或多个存储之后和加载之前插入一个。在将这些操作作为库函数实现的情况下,常见的约定是将 添加mfence到所有存储中,而使负载“裸露”。(逻辑是加载比存储更常见,并且将开销添加到存储似乎更好。)


至少对于自旋锁,您的问题似乎归结为自旋解锁操作是否需要mfence,以及它有什么区别。

C11atomic_flag_clear()隐含地是memory_order_seq_cstmfence需要 an 。C11atomic_flag_test_and_set()不仅是一个读-修改-写操作,而且是隐含的memory_order_seq_cst —— 并且LOCK做到了。

C11 在threads.h 库中不提供自旋锁。但是您可以使用atomic_flag-- 尽管对于您的 x86/x86_64,您需要PAUSE处理指令问题。问题是,您是否需要 memory_order_seq_cst为此,特别是对于 unlock ?我认为答案是否定的,诀窍是这样做:atomic_flag_test_and_set_explicit(xxx, memory_order_acquire)atomic_flag_clear(xxx, memory_order_release).

FWIW,glibcpthread_spin_unlock()没有mfence. gcc 也没有__sync_lock_release()(这是明确的“释放”操作)。但是 gcc_atomic_clear()与 C11 对齐atomic_flag_clear(),并采用内存顺序参数。

mfence解锁有什么区别?显然,这对管道造成了很大的破坏,而且由于没有必要,因此确定其影响的确切规模并没有太多收获,这将取决于具体情况。

于 2014-08-25T14:16:23.697 回答
4

自旋锁不使用 mfence,mfence 只强制序列化/刷新当前核心的数据。栅栏本身与原子操作没有任何关系。

对于自旋锁,您需要某种原子操作来将数据交换到内存位置。有许多不同的实现,针对不同的需求:例如,它是在内核还是用户空间工作?是公平锁吗?

x86 的一个非常简单和愚蠢的自旋锁看起来像这样(我的内核使用这个):

typedef volatile uint32_t _SPINLOCK __attribute__ ((aligned(16)));
static inline void _SPIN_LOCK(_SPINLOCK* lock) {
__asm (
       "cli\n"
       "lock bts %0, 0\n"
       "jnc 1f\n"
       "0:\n"
       "pause\n"
       "test %0, 1\n"
       "je 0b\n"
       "lock bts %0, 0\n"
       "jc 0b\n"
       "1:\n"
       :
       : "m"(lock)
       :
       );
}

逻辑很简单

  1. 测试并交换一下,如果为零,则表示未使用锁,我们得到了它。
  2. 如果bit不为零,则表示该锁已被其他人占用,这是pausecpu制造商推荐的提示,以免它紧盯着cpu烧毁。
  3. 循环直到你得到锁

注意 1. 您也可以使用内部函数和扩展实现自旋锁,它应该非常相似。

注意 2. Spinlock 不是通过循环来判断的,一个理智的实现应该很快,例如,上面的实现你应该在设计良好的使用中首先尝试获取锁,如果没有,修复算法或拆分锁以防止/减少锁竞争。

注意 3. 您还应该考虑其他方面,例如公平性。

于 2014-08-18T12:41:48.353 回答
0

关于

和成本(多少个 CPU 周期)?

至少在 x86 上,执行内存同步(原子操作、栅栏)的指令具有非常可变的 CPU 周期延迟。它们等待处理器存储缓冲区刷新到内存,这取决于存储缓冲区的内容。

例如,如果一个原子操作紧跟在一个memcpy()将多个高速缓存行推送到主存储器的之后,则延迟可能在 100 纳秒内。相同的原子操作,但在一系列仅寄存器的算术指令之后,可能只需要几个时钟周期。

于 2017-12-27T09:31:36.363 回答