TicketLock的RelaxedAtomics优化

原文地址作者&＃xff1a;Pedro Ramalhete&＃xff0c;译者&＃xff1a;周可人&＃xff0c;校对&＃xff1a;梁海舰

Tick lock是mutual lock的一种简单实现&＃xff1a;

http://web.mit.edu/6.173/www/currentsemester/readings/R06-scalable-synchronization-1991.pdf

它是由John Mellor-Crummey和Michael Scott在1991年提出的&＃xff08;pdf中2.2节&＃xff09;&＃xff0c;感谢C&＃43;&＃43;11和C11中新的内存模型&＃xff0c;我们可以对单个变量进行具有屏障或者不具有屏障的原子操作。当屏障没有使用&＃xff0c;只有原子性保证时&＃xff0c;我们称之为“relaxed atomic”&＃xff1a;

http://en.cppreference.com/w/cpp/atomic/memory_order

注意在C11/C&＃43;&＃43;11内存模型中&＃xff0c;一个原子变量并不具有内在的“顺序一致性”或者“relaxed”性质&＃xff0c;然而我们可以在每次访问的时选择它的行为。

原子修饰符只能保证原子性&＃xff0c;即这个变量会被单步读或写。其他语言&＃xff0c;如Java和Scala则不同&＃xff0c;它们可以保证几乎所有的原生类型提供原子性保证&＃xff0c;从而表现为“relaxed atomic”。并且&＃xff0c;所有被声明为顺序一致性的变量可以在整个程序中保持性质&＃xff08;除非在Java中使用sun.misc.unsafe&＃xff09;。尽管这个细微的差异可能看起来并不重要&＃xff0c;但是当我们的目标是从同步或是并发算法中挖掘最大性能时&＃xff0c;就需要关注这个差异了。

假设你想要在不同语言中声明一个原子整型&＃xff0c;下面是你可能会做的&＃xff1a;

 01C11 (can be relaxed or sequentially consistent)
 02 
 03 _Atomic int x; 
 04 
 05C&＃43;&＃43;11 or C&＃43;&＃43;14 (can be relaxed or sequentially consistent)
 06 
 07 atomic<int> x; 
 08 
 09Java (sequentially consistent)
 10 
 11 volatile int x; 

当具备上述信息时&＃xff0c;我们可以写出一个简单的Ticket Lock C11版本的实现&＃xff0c;如下所示&＃xff1a;

 01 typedef struct 
 02 
 03{
 04 
 05     _Atomic long ingress; 
 06 
 07     char padding[64];      // To avoid false sharing between ingress and egress 
 08 
 09     _Atomic long egress; 
 10 
 11} ticket_mutex_t;
 12 
 13   
 14 
 15 void ticket_mutex_lock(ticket_mutex_t * self) 
 16 
 17{
 18 
 19     long lingress &＃61; atomic_fetch_add(&self->ingress, 1); 
 20 
 21     while (lingress !&＃61; atomic_load(&self->egress)) { 
 22 
 23         sched_yield(); 
 24 
 25     } 
 26 
 27     // This thread has acquired the lock on the mutex 
 28 
 29}
 30 
 31   
 32 
 33 void ticket_mutex_unlock(ticket_mutex_t * self) 
 34 
 35{
 36 
 37     atomic_fetch_add(&self->egress, 1); 
 38 
 39}

这里有3处不明显的优化&＃xff0c;我们可以在上述代码的基础上利用releaxed atomics实现。让我们一个一个看。

在lock方法中&＃xff0c;当egress变量第一次被读取的时候&＃xff0c;我们可以用relaxed load优化。

代码如下&＃xff1a;

 01 void ticket_mutex_lock(ticket_mutex_t * self) 
 02 
 03{
 04 
 05 long lingress &＃61; atomic_fetch_add(&self->ingress, 1); 
 06 
 07// If the ingress and egress match, then the lock as been acquired and
 08 
 09// we don&＃39;t even need to do an acquire-barrier.
 10 
 11 if (lingress &＃61;&＃61; atomic_load_explicit(&self->egress, memory_order_relaxed)) return ; 
 12 
 13 while (lingress !&＃61; atomic_load(&self->egress)) { 
 14 
 15 sched_yield();  // Replace this with thrd_yield() if you use  
 16 
 17}
 18 
 19// This thread has acquired the lock on the mutex
 20 
 21}

我们这样做的原因是atmoic_fetch_add(ingress)将会获取一个barrier&＃xff0c;这代表着atomic_load_explicit(egress, memory_order_relaxed)将永远不能在atomic_fetch_add()之前被执行&＃xff0c;但是它可以获得一个最新的egress的值&＃xff0c;至少在atomic_fetch_add(ingress)执行之后。这意味着egress变量的值将永远不会比atomic_fetch_add(ingress)所返回的值更大。

在x86架构中&＃xff0c;这个优化并不会带来效率提升&＃xff0c;因为获得屏障是没有代价的&＃xff0c;这代表节省一个屏障并不能带来任何收益。但是在其他架构中——如ARMv8&＃xff0c;这个优化将带来少量的收益。当我可以在ARMv8上开发&＃xff0c;并且配有支持C11/C&＃43;&＃43;11的gcc时&＃xff0c;我会详细说明。

在unlock()方法中&＃xff0c;我们可以使用atomic_load()和atomic_store()来替代atomic_fetch_add()。

unlock()方法中并没有在一个原子操作中同时读/写的需求&＃xff0c;因为同一时间只有一个线程可以调用这个方法。这说明我们可以这样实现egress变量的增加操作&＃xff1a;使用atomic_load()读取egress变量的当前值&＃xff0c;然后使用atomic_store()操作将当前值加1写入egress变量。

在前面提到的atomic_load()操作可以是relaxed。

步骤2可以通过relaxed atomic_load()进一步优化。在lock()方法中&＃xff0c;atomic_fetch_add()有一个获取屏障的操作&＃xff0c;或者在糟糕的情况下&＃xff0c;这个屏障在while循环中的atomic_load()&＃xff0c;用来保证当前线程获得最新的egress值。我们可以保证在这个屏障和unlock()之间没有其他线程调整egress变量&＃xff0c;所以这样做是安全的。

最后的代码如下&＃xff1a;

 1 void ticket_mutex_unlock( ticket_mutex_t * self) 
 2 
 3{
 4 
 5 long legress &＃61; atomic_load_explicit(&self-> egress, memory_order_relaxed); 
 6 
 7atomic_store(&self-> egress, legress&＃43;1);
 8 
 9}

上述是一些关于如何使用relaxed atomics来优化代码的例子。

现在&＃xff0c;我们可以实际地说这些特殊优化所带来的提升是非常小的&＃xff0c;并且一些优化是令人费解的&＃xff0c;更是难以证明其正确性的。有利的一点是这个代码仍然是跨平台的。你可以在x86&＃xff0c;ppc&＃xff0c;mips&＃xff0c;arm上运行它&＃xff0c;因为内存模型的一致性&＃xff0c;你有信心保证代码仍然是安全的。

这是我喜爱C11/C&＃43;&＃43;1x内存模型的原因。

可以在github上找到C11 Ticket Lock源代码&＃xff1a;

https://github.com/pramalhe/ConcurrencyFreaks/blob/master/C11/locks/ticket_mutex.h

https://github.com/pramalhe/ConcurrencyFreaks/blob/master/C11/locks/ticket_mutex.c