一個Linux核心的自旋鎖設計-接力巢狀堆疊式自旋鎖

鎖的開銷鎖的開銷是巨大的，特別是對於多核多處理來講。

引入多處理，本身就是為了將並行化處理以提高效能，然而由於存在共用臨界區，而這個臨界區同時只能有一個執行緒存取(特別是對於寫操作)，那麼本來並行的執行流在這裡被序列化了，形象地看，這裡好像是寬闊馬路上的一個瓶頸，由於序列化是本質上存在的，因此該瓶頸就是不可消除的。問題是執行緒執行流如何度過這個瓶頸，很顯然，它們誰都繞不開，現在問題是是它們到達這個瓶頸時該怎麼辦。

很顯然，鬥毆搶先是一種不合理但實用的簡單方案，樸素的自旋鎖就是這麼設計的。然而，更加紳士的做法就是，既然暫時得不到通行權，那麼自己先讓出道路，sleep一會兒，這種方式就是sleep-wait方式，與之對應的就是持續spin-wait方式。問題是執行緒本身如何對這二者做出明智的選擇。事實上，這種選擇權交給了程式，而不是執行中的執行緒。

不要試圖比較sleep-wait和spin-wait的效能，它們都是損耗了效能-因為序列化。其中，sleep-wait的開銷在切換(涉及到進程，執行緒的切換比較，比如暫存器上下文，堆疊，某些處理器上cache重新整理，MMU tlb重新整理等)，而spin-wait的開銷很顯然，就是持續浪費CPU週期，雖然沒有切換的開銷，但事實上，它這段時間什麼也做不了。

為什麼要引入spin-wait這種方式呢？因為如果始終是sleep-wait，那麼sleep執行緒A切換到別的執行緒B後，鎖被釋放了，系統不一定能保證sleep的那個執行緒可以獲得CPU從而切回來，即便如此，付出巨大的切換代價，有時間隔很短，執行緒B並沒有由於執行緒A的紳士行為獲得收益，這種姿態顯然是不值得的，還不如保留本質，持續鬥毆。

和中斷相比，鎖的開銷更加巨大，如果可以通過關中斷的方式換取無鎖操作，那麼這是值得的，但是(最討厭且永恆的“但是”)，你要考慮關中斷的副作用，比如增加了處理延遲，然後你必須拿這種新的代價和鎖的開銷進行對比，權衡這種交易是否值得。

要開始本文了，為了簡便起見，我不會給出太多的和處理器相關的細節，而是集中針對自旋鎖本身。這些細節比如CPU cache機制，快取一致性協定，記憶體屏障，Intel的pause指令，流水線，匯流排鎖等，還好，這些概念都是可以很方便baidu出來的，不用去牆外。

關於自旋鎖

Linux核心一開始就引入了自旋鎖，所謂的自旋鎖在等待鎖過程中的行為就是原地打轉，有人會覺得這浪費了CPU週期，但是你要明白，系統設計就是一場博弈，雖然不是零和，但是也要盡力尋找折中點，然而卻沒有兩全其美的方案。

如果不原地打轉，又該如何呢？很顯然就是切換到別的執行緒，等待持鎖者釋放鎖的時候，再將它喚醒，然而這裡又有兩次鬥毆，首先，如果有多方都競爭一個鎖，那麼全部將它們喚醒，提供一個鬥毆場地，等待一個勝出嗎？退而求其次，即便僅僅喚醒首先排隊的那個執行緒，task切換的開銷算進去了嗎？所以說，如果原地打轉浪費的CPU週期小於兩次切換開銷浪費的CPU週期，那麼原地打轉就是合理的，這麼說來，原地打轉的時間越短越好。

就是如此。自旋鎖的應用場合就是短時間持有臨界區的場合，它是一種短期鎖，如果占據臨界區過久，隨著原地打轉浪費的CPU週期的增加，其開銷將逐漸大於兩次切換(切換開銷是固定的-不考慮cache等)，因此，理論上，能算出自旋鎖在持鎖期間可以執行多少程式碼。爆炸！

Linux自旋鎖歷史概覽Linux自旋鎖發展了兩代，第一代自旋鎖是一種完全鬥毆模式的無序自旋鎖，也就是說，如果多個CPU同時爭搶一個自旋鎖，那麼待持鎖者解鎖的時候，理論上它們獲得鎖的機會是不固定的，和cache等一系列因素相關，這就造成了不公平，第一個開始爭搶的CPU不一定第一個獲得...這就需要引入一個秩序，於是第二代Ticket自旋鎖就設計出來了。

Ticket自旋鎖的設計非常巧妙，它將一個CPU變數，比如32位元的值分為高16位元和低16位元，每次lock的時候，CPU將高16位元原子加上0x01(通過鎖匯流排)，然後將該值和低16位元比較，如果相等則成功，如果不等則自旋的同時持續比較這兩個值，而unlock操作則是簡單遞增鎖的低16位元加0x01(理論上不需要鎖匯流排，因為不會有兩個及以上的CPU同時擁有鎖進行unlock操作，但是還是要考慮CPU的特性...)。這就是所謂的Ticket自旋鎖的全部。

最近遇到了鎖優化的問題，眾所周知，鎖優化是一個很精細的活兒，它既不能太複雜也不能太簡單，特別是自旋鎖的設計，更是如此。然而自旋鎖設計的優勢也很明顯，那就是它讓你少考慮很多問題：

1.一個CPU同時只能在一個自旋鎖上自旋；

2.一旦開始自旋，直到獲得鎖，中間不能放棄退出自旋。

自旋鎖的應用場合必須要明瞭，它不適合保護很大的臨界區，因為這將導致自旋過久，它也不適合大量CPU的情況，因為它會導致自旋延時的N倍，雖然一段臨界區很小，但是一個CPU自旋的時間可能是N倍，N為CPU的數量。這就引出了一個爭論，Ticket排隊自旋鎖真的比鬥毆型哄搶自旋鎖好嗎？如果不考慮cache親和，鬥毆型的自旋鎖可以將每個CPU自旋的時間收斂到平均時間，而Ticket自旋鎖將出現兩極分化，也就是說，最長自旋時間和最短自旋時間是一個固定的倍數關係，隨著CPU數量的增加，排隊公平導致的不合理性將加大，你要知道，任何情況下佇列都不可能超過一個臨界值，超過了不滿情緒將會增加，雖然這種長延時只是因為你來得晚導致的，看似很公平，實際上並不公平，因為並不清楚你來得晚的原因。

目前沒有一種好的方案解決這個問題，一般情況，如果佇列過長，工作人員會建議你一會兒再來看看，或者貼上大致的預估時間，你自己來絕對是排隊還是放棄。

try lock返回的預估資訊我建議在自旋鎖加鎖前，先try lock一次，正如現如今的實現一樣，然而這個try並沒有給出除了成功或者失敗之外的資訊，事實上更好的方式是，try，並且try返回一些有用的資訊，比如等待預估時間，隊長等統計資訊，以供呼叫者決定是就地自旋還是幹點別的。誰說核心中不能做巨量資料分析，很多統計資訊和建議都可以通過資料分析得到。

此外，對於該統計資訊，可以對spin操作本身進行優化，就是說，內部的pause指令可以進行優化，這對流水線是有益的。

我的自旋鎖設計

為什麼我要設計一個新的自旋鎖，一方面是我覺得Ticket自旋鎖多個CPU雖然靠遞增高位實現了排隊，但是它們同時不斷地檢測自旋鎖本身的值，cache有點浪費，所有的CPU cache上均會出現完全一樣的自旋鎖，並且一旦鎖被unlock，還會觸發cache一致性協定行為，另一方面，我覺得用一個32位元(或者隨便其它什麼CPU內部型別)分為高低兩部分來實現自旋鎖雖然巧妙但是又過於簡單，第三方面，我前些日子特別推崇小巧結構體實現的IP轉發表，如今又重溫更加小巧的Ticket自旋鎖，心裡總是有些嫉妒，所以怎麼也得按照我的思路來一個”符合我的觀念的“設計吧，事情就是這麼開始的。

在per CPU結構體上自旋如何解決執行緒間同步問題，這個問題確實不好解決，但是自己管自己，也就是操作本地資料，總是一個合理的思路。

為什麼要在自旋鎖本身上集體自旋呢？如果有500多個CPU，大家一起探測同一個記憶體地址，然後持鎖者釋放鎖，修改了該記憶體地址的CPU cache值，這將導致大量的cache一致性動作...為何不在自己的本地變數上自旋呢？如果持鎖者釋放鎖，那麼就將下一個等待者的本地變數置0，這意味著CPU只需要拿本地變數和0比較即可。

因此就需要有一個原生的地方儲存這個變數，我為每一個CPU申請了一個per CPU變數，內部儲存一個棧，用於實現嚴格的”後加鎖先解鎖“順序的自旋鎖，當然這樣對呼叫者有要求，或者說把棧改成一個空閒佇列，用於實現任意順序加鎖/解鎖得自旋鎖，這個對呼叫者沒有要求，但是可能會引起死鎖。

為了實現多個CPU同時爭搶自旋鎖的優雅排隊，勢必要維護一個佇列，單向推進的即可，沒有必要用list_head結構體。排入隊中的元素就是棧幀，而棧幀是per CPU的。操作棧幀只有三個機會：

自己加鎖時：加鎖時需要用自己的棧幀排隊，不可避免要操作連結串列，而可能同時有多個CPU的棧幀要排隊，因此需要保證整個排隊動作的單向連結串列操作是原子的，鎖匯流排是一個辦法。

自己自旋時：這個時段不涉及別的CPU，甚至自己的棧幀都不會到達別的CPU的cache中，棧幀是CPU本地變數。

排在前面的棧幀解鎖時：這個時候理論上也和其它CPU無關，因為佇列是嚴格順序的，取下一個即可，無需爭搶，但是有一種競爭情況，即開始取下一個棧幀時，佇列已經沒有下一個，然而按照空佇列處理時，卻有了下一個棧幀，這將使得剛剛排入的新棧幀永遠無法獲得鎖，因此這個動作必須是原子的。至於說取到下一個排隊棧幀，設定它時，就不用保證原子了，因為它就是它後面的它，一個棧幀不會排到兩個佇列，且排入了就不能放棄，別人也不會動它的。

設計框架圖示下面用一個圖示展示一下我的這個排隊自旋鎖的設計吧

自旋鎖分析看起來有點複雜了，那麼效能一定不高，其實確實比Ticket自旋鎖複雜，但是你能找到比Ticket自旋鎖更簡單優雅的設計嗎？

我不圖更簡單，但圖夠優雅。雖然我的一個原子操作序列比Ticket自旋鎖的單純加1操作複雜了很多，涉及到很多連結串列操作，但是我的區域性性利用會更好，特別是採用了per CPU機制，在集體自旋的時間段，CPU cache資料同步效率會更高，你要知道，自旋的時間和鎖匯流排的時間相比，那可久多了。採用陣列實現的堆疊(即便是空閒連結串列也一樣)，資料的區域性性利用效果會更好，也就說，一個CPU的所有自旋鎖的自旋體均在這個陣列中，這個陣列有多大，取決於系統同時持有的自旋鎖有多少。

未完成的虛擬碼以下是根據上述的圖示寫出的測試程式碼，程式碼未經優化，只是能跑。在使用者空間做過測試。

#define NULL    0 
 
/* 匯流排鎖定的開始與結束 */ 
#define LOCK_BUS_START 
#define LOCK_BUS_END 
 
/* pause指令對效能非常重要，具體可參閱Intel指令手冊， 
  然而它並不是有優化作用，而是減輕了惡化效果 
*/ 
#define cpu_relax() 
/* 記憶體屏障對於多核心特別重要 */ 
#define barrier() 
 
#define MAX_NEST    8 
 
/* 
 *  定義per CPU自旋棧的棧幀 
 * */ 
struct per_cpu_spin_entry { 
    struct per_cpu_spin_entry *next_addr; 
    char status; 
}; 
 
/* 
 *  定義自旋鎖的per CPU自旋棧 
 * */ 
struct per_cpu_stack { 
    /* per CPU自旋棧 */ 
    struct per_cpu_spin_entry stack[MAX_NEST]; 
 
    /* 為了清晰，將CPU ID和棧頂ID獨立為char型(僅支援256個CPU) */ 
    char top; 
    char cpuid; 
}; 
 
/* 
 *  定義自旋鎖 
 * */ 
typedef struct { 
    /* 為了程式碼清晰，減少bit操作，獨立使用一個8位元型別 */ 
    char    lock; 
 
    /* 指向的下一個要轉交給的per CPU棧幀 */ 
    struct per_cpu_spin_entry *next; 
 
    /* 指向排隊棧幀的最後一個per CPU棧幀 */ 
    struct per_cpu_spin_entry *tail; 
 
} relay_spinlock_t; 
 
static void relay_spin_lock(relay_spinlock_t *lock) 
{ 
    struct per_cpu_stack *local = .....按照per CPU變數去取值 
    struct per_cpu_spin_entry *entry; 
 
    local->top++; 
 
    local->stack[local->top].status = 0; 
    entry = &(local->stack[local->top]); 
 
    LOCK_BUS_START 
    if (unlikely(!lock->lock)) { 
        lock->tail = lock->next = entry; 
        entry->status = 1; 
        lock->lock = 1; 
        LOCK_BUS_END 
        return; 
    } else { 
        lock->tail->next_addr = entry; 
        lock->tail = entry; 
    } 
    LOCK_BUS_END 
 
    for (;;) { 
        if (entry->status == 0) { 
            break; 
        } 
        cpu_relax(); 
    } 
    barrier(); 
} 
 
static void relay_spin_unlock(relay_spinlock_t *lock) 
{ 
    struct per_cpu_stack *local = .....按照per CPU變數去取值 
    struct per_cpu_spin_entry *next; 
 
    LOCK_BUS_START 
    next = lock->next->next_addr; 
    LOCK_BUS_END 
 
    local->top--; 
 
    /* 在confirm之前，可以保證只有一個CPU在操作 */ 
    if (unlikely(!next)) { 
        lock->lock = 0; 
        lock->tail = lock->next = NULL; 
        return; 
    } 
 
confirm: 
    lock->next = next; 
    next->status = 0; 
} 

地址指標索引化改進請看上面的那個圖，多個CPU的per CPU自旋堆疊是地址獨立的，這就意味著我們要麼在棧幀中儲存一個指標，要麼就是採用base地址加偏移的方式，這樣可以省掉幾個位元組，採用對齊方案的話，一個棧幀的後幾個bit對於地址和偏移而言是不用的，所以就可以做status位，這些都是基本的空間優化。

我要做的就是把所有的CPU的自旋堆疊全部整合在一張表中，分為二維，一維代表CPU，一維代表棧幀，這樣就可以在棧幀中寫索引而不是地址了，這樣就能節省大量的記憶體了，除卻空間節省之外，連續記憶體的時間區域性性也更好利用。因為系統中所有的自旋鎖的自旋體，全部都在這一張表中了，整個系統的自旋鎖操作完全不離此表，它就像MMU一樣，全然成了一個服務性基礎設施。上述例子地址索引化後如下圖所示：

不限制解鎖順序改進採用堆疊的方式儲存自旋體，就要嚴格按照push的反順序pop，這就要求加鎖和解鎖操作要和push/pop操作完全一致。而這種限制雖然不錯，但並不必須，如果不要求解鎖順序，那就需要將堆疊做成空閒連結串列，它的操作如下圖所示：

這種空閒連結串列組織方式和UNIX檔案的空閒塊組織方式類似，另一個例子就是Linux核心的Slab分配器中的hot cache的組織方式。採用這種組織方式。這種方式的好處在於，最先釋放的最先被分配，這樣會cache會好一點。其實這是一種不受空間約束的堆疊，因此我不把它作為一種特殊的方式，也稱它為堆疊。

採用單連結串列而不是雙連結串列的一個原始是確實用不到雙向連結串列，另一個更加隱蔽的原因在於，單連結串列修改時只需要修改一個指標，而一個修改操作可以是原子的，鎖匯流排鎖cache的開銷更小

好像沒寫完的樣子.....

本文永久更新連結地址：http://www.linuxidc.com/Linux/2015-07/120039.htm