閱讀123 返回首頁    go 阿裏雲 go 技術社區[雲棲]

Ticket Lock的Relaxed Atomics優化

Tick lock是mutual lock的一種簡單實現：

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

它是由John Mellor-Crummey和Michael Scott在1991年提出的（pdf中2.2節），感謝C++11和C11中新的內存模型，我們可以對單個變量進行具有屏障或者不具有屏障的原子操作。當屏障沒有使用，隻有原子性保證時，我們稱之為“relaxed atomic”：

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

注意在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實現。讓我們一個一個看。

  1. 在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時，我會詳細說明。

 

  1. 在unlock()方法中，我們可以使用atomic_load()和atomic_store()來替代atomic_fetch_add()。

unlock()方法中並沒有在一個原子操作中同時讀/寫的需求，因為同一時間隻有一個線程可以調用這個方法。這說明我們可以這樣實現egress變量的增加操作：使用atomic_load()讀取egress變量的當前值，然後使用atomic_store()操作將當前值加1寫入egress變量。

 

  1. 在前麵提到的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源代碼：

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

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

最後更新：2017-05-23 17:03:21

  上一篇：go  Java設計模式：策略模式
  下一篇：go  Harris’s Linked List