x86上的原子计数器和自旋锁的成本(_64)

Question

前言

我最近遇到了一些同步问题,这使我成为自旋锁和原子计数器.然后,我正在寻找多一点,这些工作是如何找到的std :: memory_order及记忆力障碍(mfence,lfence和sfence).

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

一些参考

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库的东西 - 到目前为止我已经避免了提升).

我的知识

到目前为止,我确实理解自旋锁比自身保护更多(但也有一些共享资源/内存),因此,必须有一些东西可以使一些内存视图对于多个线程/内核(即获取/释放和内存围栏)保持一致).原子计数器只为自己而存在,只需要原子增量(不涉及其他内存,当我读它时我并不真正关心它的价值,它是信息性的,可以是几个循环旧,没问题).有一些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(32位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:(见mfence中unlock1)

_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

Answer 1

x86主要是强大的内存模型,所有常用的存储/加载都隐含了释放/获取语义.唯一的例外是SSE非临时存储操作,需要sfence像往常一样进行排序.所有带有LOCK前缀的读 - 修改 - 写(RMW)指令都意味着全内存屏障,即seq_cst.

因此在x86上,我们有

• test_and_set可以用lock bts(用于逐位运算)lock cmpxchg,或lock xchg(或仅仅xchg暗示lock)进行编码.其他自旋锁实现可以使用像lock inc(或dec)这样的指令, 如果它们需要例如公平性.try_lock使用发布/获取栅栏是不可能实现的(至少你需要独立的内存屏障mfence).
• clear用lock and(按位)编码lock xchg,但更高效的实现将使用普通write(mov)而不是锁定指令.
• fetch_add用lock add.编码.

删除lock前缀不能保证RMW操作的原子性,因此这些操作不能严格解释为memory_order_relaxed在C++视图中.但是在实践中,您可能希望在安全时(在构造函数中,在锁定下)通过更快的非原子操作访问原子变量.

根据我们的经验,执行RMW原子操作究竟是什么并不重要,它们执行的循环次数几乎相同(并且mfence约为锁定操作的x0.5).您可以通过计算原子操作数(和mfences)以及内存间接数(缓存未命中数)来估计同步算法的性能.

Answer 2

我建议:x86-TSO:一个严格且可用的程序员x86多处理器模型.

你的x86和x86_64确实非常"表现良好".特别是,它们不会重新排序写操作(并且任何推测性写入在它们位于cpu/core的写入队列中时都会被丢弃),并且它们不会重新排序读取操作.但是,它们将尽可能早地启动读取操作,这意味着可以重新读取读取和写入操作.(东西坐在写队列是读取排队值,所以读取的/写入同一个位置都不会重新排序.)所以:

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

  因此,对于这些操作,您无需通过削弱内存排序(在x86/x86_64上)获得任何收益.一般的建议是"保持简单"并坚持使用memory_order_seq_cst,这对于x86和x86_64来说并不会花费额外的成本.

  对于比Pentium更新的任何东西,如果cpu/core已经对受影响的内存进行"独占"访问,LOCK则不会影响其他cpu/core ,并且可能是一个相对简单的操作.

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

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

• memory_order_seq_cst确实需要mfence......

......这值得理解.

(注意:我们在这里谈论处理器对编译器生成的指令所做的事情.编译器对操作的重新排序是一个非常类似的问题,但这里没有解决.)

一个mfence摊位的CPU /核心,直到所有的未决写被清除出写入队列.特别是,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/core的队列中写入和排队,并且可以调度和读取,并且可以在写入之前完成.要实现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,以及它有什么不同.

atomic_flag_clear()隐含地,C11 是memory_order_seq_cst,mfence需要a.C11 atomic_flag_test_and_set()不仅是一个读 - 修改 - 写操作,而且还隐含着memory_order_seq_cst - 并且LOCK这样做.

C11在threads.h库中没有提供自旋锁.但你可以使用atomic_flag- 虽然对于你的x86/x86_64,你有PAUSE指令问题需要处理.问题是,你需要 memory_order_seq_cst吗,特别是解锁？我认为答案是否定的,而且诀窍是:atomic_flag_test_and_set_explicit(xxx, memory_order_acquire)和atomic_flag_clear(xxx, memory_order_release).

FWIW,glibc pthread_spin_unlock()没有mfence.gcc也没有__sync_lock_release()(明确是"释放"操作).但是gcc _atomic_clear()与C11对齐atomic_flag_clear(),并采用内存顺序参数.

mfence解锁有什么区别？显然,它对管道非常具有破坏性,并且由于没有必要,因此根据具体情况确定其影响的确切规模并没有多大成果.