鎖的開銷鎖的開銷是巨大的，特別是對於多核多處理來講。
引入多處理，本身就是為了將並行化處理以提高性能，然而由於存在共享臨界區，而這個臨界區同時只能有一個線程訪問(特別是對於寫操作)，那麼本來並行的執行流在這裡被串行化了，形象地看，這裡好像是寬闊馬路上的一個瓶頸，由於串行化是本質上存在的，因此該瓶頸就是不可消除的。問題是線程執行流如何度過這個瓶頸，很顯然，它們誰都繞不開，現在問題是是它們到達這個瓶頸時該怎麼辦。
很顯然，斗毆搶先是一種不合理但實用的簡單方案，樸素的自旋鎖就是這麼設計的。然而，更加紳士的做法就是，既然暫時得不到通行權，那麼自己先讓出道路，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的開銷更小
好像沒寫完的樣子.....
