Ticket Lock的Relaxed Atomics优化-白红宇

Tick lock是mutual lock的一种简单实现：

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

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

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

假设你想要在不同语言中声明一个原子整型，下面是你可能会做的：

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

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

                  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 = atomic_fetch_add(&self->ingress, 1);          
       
                  20                    
       
                  21               while (lingress != 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处不明显的优化，我们可以在上述代码的基础上利用releaxed atomics实现。让我们一个一个看。

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

代码如下：

                  01           void ticket_mutex_lock(ticket_mutex_t * self)          
       
                  02                    
       
                  03          { 
         
                  04                    
       
                  05           long lingress = 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't even need to do an acquire-barrier.         
       
                  10                    
       
                  11           if (lingress == atomic_load_explicit(&self->egress, memory_order_relaxed)) return ;          
       
                  12                    
       
                  13           while (lingress != atomic_load(&self->egress)) { 
          
                  14                    
       
                  15           sched_yield();  // Replace this with thrd_yield() if you use <threads.h>          
       
                  16                    
       
                  17          }         
       
                  18                    
       
                  19          // This thread has acquired the lock on the mutex         
       
                  20                    
       
                  21          }

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

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

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

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

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

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

最后的代码如下：

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

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

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

这是我喜爱C11/C++1x内存模型的原因。

可以在github上找到C11 Ticket Lock源代码：

转载自