如何設計一個真正高性能的spin_lock?

01-13

如何設計一個真正高性能的spin_lock?
目前多數網站上放出的Spin_lock都不是合格的代碼，都是有嚴重性能問題的。
例如： Usage examples - 1.60.0 還有下面這個
class Spin_lock { public: Spin_lock( void ); void lock( void ); bool try_lock( void ); void unlock( void );
Spin_lock( const Spin_lock ) = delete; Spin_lock operator = ( const Spin_lock ) = delete; private: std::atomic_flag d_atomic_flag; }; Spin_lock::Spin_lock() { d_atomic_flag.clear( std::memory_order_relaxed ); return; } void Spin_lock::lock( void ) { while( d_atomic_flag.test_and_set( std::memory_order_acquire ) ) { } return; } bool Spin_lock::try_lock( void ) { if( d_atomic_flag.test_and_set( std::memory_order_acquire ) ) return false; return true; }
void Spin_lock::unlock( void ) { d_atomic_flag.clear( std::memory_order_release ); return; }
atomic的exchange/test_and_set/CAS一般都需要serialization，即在執行這條指令前,CPU必須要完成前面所有對memory的訪問指令(read and write)。

這是非常heavy的操作，使得CPU無法對指令進行reorder，從而優化執行。
因為每一次atomic的exchange/test_and_set/CAS都必須讀-寫 state 這個變數。這就要涉及到多個CPU之間cache coherence的問題。
當CPU1讀state的時候，如果這個state沒有在CPU1的cache中，就需要從memory中讀入，因為CPU又需要寫這個變數，所以在把這個變數讀入cache的時候，如果其他CPU已經cache了這個變數，就需要invalidate它們。這樣在CPU1把lock讀入自己的cache中時，這塊cacheline所cache的state就是CPU1所獨佔的，CPU1就可以更改它的值了。如果多個CPU在競爭這個spinlock的話，每一次atomic的exchange/test_and_set/CAS都需要完成以上的操作，在系統匯流排上會產生大量的traffic，開銷是非常大的，而且unlock的CPU還必須同其它正在競爭spinlock的CPU去競爭cacheline ownership. 隨著CPU數目的增多，性能會成衰減的非常快。
目前包括C++ 准標準庫Boost庫在內的spin_lock都存在一些缺陷導致的性能問題。很多版本要麼過於簡單，出現上面的問題，要麼使用了usleep()/nanosleep()等代碼, 例如：linux下usleep(0)/nanosleep(0)實際測試是50微秒的延遲時間，而我們的鎖佔用總時長可能只有1-40個微秒。

應用層用spinlock的最大問題是不能跟kernel一樣的關中斷（cli/sti），假設並發稍微多點，線程1在lock之後unlock之前發生了時鐘中斷，一段時間後才會被切回來調用unlock，那麼這段時間中另一個調用lock的線程不就得空跑while了？這才是最浪費cpu時間的地方。所以不能關中斷就只能sleep了，怎麼著都存在巨大的衝突代價。

尤其是多核的時候，假設 Kernel 中任務1跑在 cpu1上，任務 2跑在 cpu2上，任務1進入lock之前就把中斷關閉了，不會被切走，調用unlock的時候，不會花費多少時間，cpu2上的任務2在那循環也只會空跑幾個指令周期。

看看 Kernel 的 spinlock:

#define _spin_lock_irq(lock) do { local_irq_disable(); preempt_disable(); _raw_spin_lock(lock); __acquire(lock); } while (0)

看到裡面的 local_irq_disable() 了么？實現如下：

#define local_irq_disable() __asm__ __volatile__("cli": : :"memory")

倘若不關閉中斷，任務1在進入臨界區的時候被切換走了，50ms以後才能被切換回來，即使原來臨界區的代碼只需要0.001ms就跑完了，可cpu2上的任務2還會在while那裡乾耗50ms，所以不能禁止中斷的話只能用 sleep來避免空跑while浪費性能。

所以不能關閉中斷的應用層 spinlock 是殘廢的，nop都沒大用。

不要覺得mutex有多慢，現在的 mutex實現，都帶 CAS，首先會在應用層檢測衝突，沒衝突的話根本不會不會切換到內核態，直接用戶態就搞定了，即時有衝突也會先嘗試spinlock一樣的 try 幾次（有限次數），不行再進入休眠隊列。比傻傻 while 下去強多了。

前段時間關注過這個問題，推薦一個 PPT:

http://web.cecs.pdx.edu/~walpole/class/cs533/winter2011/slides/8b.pdf

基本上所有可以優化的點都談到了：

1. 從 spin-on-test-and-set 到 spin-on-read，減少匯流排 traffic。

2.重試退讓策略（Backoff），靜態退讓、指數退讓或者隨機退讓等。Backoff 其實是將衝突按照時間分散。

3.排隊模式（Queuing），也就是將衝突按照空間拆分。排隊有很多種變種了，比如前面有人提到的基於 ticket 票據的，基於鏈表的MCS 鎖和 CLH Lock。

Spin Lock 還有個關鍵問題就是 while 循環不應該空跑，通常推薦執行 rep;nop 指令，比如 Erlang 里的 i386 的 spinlock 實現：

for(;;) { if (__builtin_expect(ethr_native_spin_trylock(lock) != 0, 1)) break; do { __asm__ __volatile__("rep;nop" : "=m"(lock-&>lock) : : "memory"); } while (ethr_native_spin_is_locked(lock)); }

因為 rep;nop 等價於 pause 指令，並且：

From Intelamp;amp;#x27;s instruction reference:

Improves the performance of spin-wait loops. When executing a 「spin-wait loop,」 a Pentium 4 or Intel Xeon processor suffers a severe performance penalty when exiting the loop because it detects a possible memory order violation. The PAUSE instruction provides a hint to the processor that the code sequence is a spin-wait loop. The processor uses this hint to avoid the memory order violation in most situations, which greatly improves processor performance. For this reason, it is recommended that a PAUSE instruction be placed in all spin-wait loops.

補充一個各種 spin lock 實現參考項目：

cyfdecyf/spinlock: Different implementations of spinlock.

可以看看我們優化的自旋鎖代碼（近一年寫出60幾行的代碼），性能數據顯示比linux kernel queued spinlock最大提升2倍。

http://www.newsmth.net/nForum/article/CSArch/45019

https://lkml.org/lkml/2016/4/15/2

也許我會被摺疊，但是我個人推薦於

嘗試獲取鎖一定次數X還不行，就去做別的事情吧。沒有必要在那裡空轉。讓你的進程流程允許「yield」。

回來的時候，循環2X次去嘗試獲取吧。。。這樣指數提升，優先順序高的話就初始值設大點。

下面是我設計的一個高性能spin_lock,

下列代碼可以挑戰目前所有linux下的spin_lock版本。

有不服的可以挑戰。

class Spin_lock

{

public:

Spin_lock( void );

void lock( void );

bool try_lock( void );

void unlock( void );

Spin_lock( const Spin_lock ) = delete;

Spin_lock operator = ( const Spin_lock ) = delete;

private:

std::atomic& d_atomic_bool;

};

Spin_lock::Spin_lock()

{

d_atomic_bool.store( false, std::memory_order_relaxed );

return;

}

void Spin_lock::lock( void )

{

while( d_atomic_bool.exchange( true, std::memory_order_acquire ) ) {

while( 1 ) {

_mm_pause(); // pause指令延遲時間大約是12納秒

if( !d_atomic_bool.load( std::memory_order_relaxed ) ) break;

std::this_thread::yield(); // 在無其他線程等待執行的情況下，延遲時間113納秒

// 在有其他線程等待執行情況下，將切換線程

if( !d_atomic_bool.load( std::memory_order_relaxed ) ) break;

continue;

}

continue;

}

return;

}

bool Spin_lock::try_lock( void )

{

return !d_atomic_bool.exchange( true, std::memory_order_acquire );

}

void Spin_lock::unlock( void )

{

d_atomic_bool.store( false, std::memory_order_release ); // 設置為false

return;

}

我們的核心lock()代碼中關鍵的第1行

while( d_atomic_bool.exchange( true, std::memory_order_acquire ) )

首先是使用了更高效率的exchange, 要比CAS指令有更高的效率，是內存讀寫模式，每次都要獨佔cache，並且將其他CPU的cache設置為invalide, 如果只有這1行代碼，那麼如果兩個以上CPU在等待這把鎖，將交替將64位元組Cacheline內存反覆同步，數據衝突激烈，影響其他線程的內存操作，降低整體性能, 影響全部CPU的工作效率, 因為產生了內存爭用, 產生了匯流排爭用

因此我們提供了第2行關鍵檢測代碼：

if( !d_atomic_flag.load( std::memory_order_relaxed ) ) break

該指令主要是為了減少CAS指令循環對內存匯流排帶來的不良影響, 這個循環只有在鎖被釋放後, 才會跳出循環, 但是這個指令消耗的資源極少。這組指令是只讀模式檢查, 只需要鎖沒有被釋放, 這裡繼續循環, 但是這組spin是沒有競爭狀態的, 不會對內存和cache產生任何影響, 只要鎖不釋放, 永遠不會內存匯流排的爭奪, 因此大大提高了整體的效率

不用才是性能最好的，內核都避免使用spinlock，用戶態代碼還去使用，低效的設計下去追求指令級別的性能，舍本求末

@郭忠明說的方法是test and test-and-set lock。

他的代碼的問題是，剛進入lock 就調用

while( d_atomic_bool.exchange( true, std::memory_order_acquire ) )

帶來了不必要的匯流排 traffic

正確的做法是 CAS 前先 test

// code from wiki boolean locked := false // shared lock variable procedure EnterCritical() { do { while (locked == true) skip or pause // spin until lock seems free } while TestAndSet(locked) // actual atomic locking }

不過這都是小問題。test and test-and-set lock 真正的問題是鎖沒有公平性，會有飢餓。

我自己實現spin lock 傾向於ticket lock。

std::atomic& ticket; // init as 0 std::atomic& serve; // init as 0


void lock() {

    auto my_tick = tick++;

    while (my_tick != serve) {

        // pause and wait

    }

}

void unlock() { serve++; }

對比test test lock, ticket lock更公平些，實現起來也不難，overhead 適中。

有興趣的同學可以再看下MCS lock。同樣兼顧性能和公平，但是實現起來複雜些，memory 使用上也多一點。

你需要mcs lock,最新linux內核也用這東西

核真的多用queued spinlock 緩解cache coherence問題做個鏈表每個人cas不同的地方

內存順序都不能接受就別用鎖了..X86上acquire release語義如果在沒有contention的時候還是很輕的

我怎麼覺得高性能和spinlock本身就是很互斥都兩個詞啊

spin_lock的使用場景是你預知很快能獲得資源，快速把cpu用起來。

如果說要提高性能，且從spin_lock角度解決，是要解決怎麼才能讓cpu快速通知你可以用，是需要硬體配合的。

如何設計一輛真正高性能的馬車？

其實你需要的可能是一樣汽車，高性能的程序都將是無鎖的設計。

什麼場景需要spinlock呢？