我最近遇到了一些同步问题,这导致我spinlocks和atomic counters。然后我正在寻找更多,这些如何工作,并发现std::memory_order和记忆障碍(mfence
,lfence
和sfence
)。
所以现在,似乎我应该使用获取/释放螺旋锁并放松计数器。
x86 MFENCE - Memory Fence x86 LOCK - Assert LOCK# Signal
这三个操作(lock = test_and_set,unlock = clear,increment = operator++ = fetch_add)的默认(seq_cst)内存顺序和获取/释放/放松的机器代码(编辑:见下文)是什么(按此顺序排列三个操作)。有什么区别(哪些内存屏障在哪里)和成本(多少CPU周期)?
我只是想知道我的旧代码(没有指定内存顺序=使用seq_cst)真的是多么糟糕,如果我应该创建一些class atomic_counter
派生自std::atomic
但是使用轻松的内存排序(以及带有获取/释放而不是互斥的一些好的自旋锁)地方......或者使用来自boost库的东西 - 到目前为止我已经避免了提升。
到目前为止,我确实理解自旋锁比自身保护更多(但也有一些共享资源/内存),因此,必须有一些东西可以使一些内存视图对于多个线程/内核(即获取/释放和内存围栏)保持一致)。原子计数器只为自己而存在,只需要原子增量(不涉及其他内存,当我读它时我并不真正关心它的价值,它是信息性的,可以是几个循环旧,没问题)。有一些LOCK
前缀和一些指令,如xchg
暗含它。在这里,我的知识结束了,我不知道缓存和总线是如何工作的以及背后的原因(但我知道现代CPU可以重新排序指令,并行执行它们并使用内存缓存和一些同步)。谢谢你的解释。
P.S。:我现在有旧的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();
}
__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
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
x86主要是strong memory model,所有通常的存储/加载都隐含地释放/获取语义。唯一的例外是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
编码,但更高效的实现将使用普通写(mov
)而不是锁定指令。fetch_add
用lock add
编码。删除lock
前缀不能保证RMW操作的原子性,因此这些操作不能严格解释为在C ++视图中具有memory_order_relaxed
。但是在实践中,您可能希望在安全时(在构造函数中,在锁定下)通过更快的非原子操作访问原子变量。
根据我们的经验,执行RMW原子操作究竟是什么并不重要,它们执行的循环次数几乎相同(并且mfence约为锁定操作的x0.5)。您可以通过计算原子操作数(和mfences)以及内存间接数(缓存未命中数)来估计同步算法的性能。
我建议:x86-TSO: A Rigorous and Usable Programmer's Model for x86 Multiprocessors。
你的x86和x86_64确实非常“表现良好”。特别是,它们不会重新排序写操作(并且任何推测性写入在它们位于cpu / core的写入队列中时都会被丢弃),并且它们不会重新排序读取操作。但是,它们将尽可能早地启动读取操作,这意味着可以重新读取读取和写入操作。 (读取写入队列中的某些内容会读取排队的值,因此不会重新排序相同位置的读取/写入。)所以:
LOCK
s,它隐含地使它们成为memory_order_seq_cst。
因此,对于这些操作,您无需通过削弱内存排序(在x86 / x86_64上)获得任何收益。一般的建议是“保持简单”并坚持使用memory_order_seq_cst,这对于x86和x86_64来说并不会花费额外的成本。
对于比奔腾更新的任何东西,如果cpu / core已经对受影响的内存进行“独占”访问,则LOCK
不会影响其他cpu / core,并且可能是一个相对简单的操作。mfence
或任何其他开销。
因此,对于原子加载/存储,如果获取/释放足够,那么对于x86 / x86_64,这些操作是“免税”的。mfence
............这值得理解。
(注意:我们在这里谈论处理器对编译器生成的指令所做的事情。编译器对操作的重新排序是一个非常类似的问题,但这里没有解决。)
mfence
会停止cpu / core,直到所有挂起的写入都从写入队列中清除。特别是,在写队列为空之前,任何跟随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,那么最后一个是无效的 - 因为你不能通过任何交错操作得到它。这可能发生的原因是wa
和wb
的写入在相应的cpu / core的队列中排队,并且wa
和wb
的读取都可以被调度,并且可以在写入之前完成。要实现memory_order_seq_cst,您需要一个mfence
:
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
,以及它有什么不同。
隐含地,C11 atomic_flag_clear()
是memory_order_seq_cst,需要mfence
。 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
对解锁有什么不同?显然,它对管道非常具有破坏性,并且由于没有必要,因此根据具体情况确定其影响的确切规模并没有多大成果。
spinlock不使用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)
:
);
}
逻辑很简单
pause
是cpu制造商推荐的提示,因此它不会以严密的外观刻录cpu。注意1.您也可以使用内在函数和扩展来实现自旋锁,它应该非常相似。
注意2. Spinlock不是通过循环来判断的,一个理智的实现应该是相当快的,对于即时,上面的实现你应该首先尝试使用精心设计的用法,如果没有,修复算法或拆分锁以防止/减少锁争用。
注3.您还应该考虑其他事项,如公平。
Re
和成本(多少CPU周期)?
至少在x86上,执行内存同步(原子操作,防护)的指令具有非常可变的CPU周期延迟。它们等待处理器存储缓冲区刷新到内存,这会根据存储缓冲区内容而发生很大变化。
例如,如果在将多个高速缓存线推出到主存储器的memcpy()
之后原子操作是直的,则延迟可以是100纳秒。相同的原子操作,但在一系列仅寄存器算术指令之后,可能只需要几个时钟周期。