1. TAS lock (test-and-set)
這是最簡單的spinlock，CPU會在硬件上提供一些指令來幫助OS實現spinlock，
比如x86就有xchg, LOCK指令前綴等指令。。。
test_and_set()可以利用這些指令對某個memory地址，來原子地完成：
寫入true到這個地址，同時返回這個地址儲存的舊的值。
void spin_lock(lock)
{
while (test_and_set(lock, true));
}
void spin_unlock(lock)
{
atomic_set(lock, false);
}
在SMP(shared bus)的環境裡，TAS lock的性能非常差。
首先test_and_set一般都需要serialization，即在執行這條指令前,
CPU必須要完成前面所有對memory的訪問指令(read and write)。
這是非常heavy的操作，使得CPU無法對指令進行reorder，從而優化執行。
其次，因為每一次test_and_set都必須讀-寫lock這個變量。這就要涉及到
多個CPU之間cache coherence的問題。
當CPU1讀lock的時候，如果這個lock沒有在CPU1的cache中，就需要從memory中讀入，
因為CPU又需要寫這個變量，所以在把這個變量讀入cache的時候，如果其他CPU已經
cache了這個變量，就需要invalidate它們。這樣在CPU1把lock讀入自己的cache中時，
這塊cacheline所cache的lock就是CPU1所獨占的，CPU1就可以更改它的值了。
如果多個CPU在競爭這個spinlock的話，每一次test_and_set都需要完成以上的操作，
在系統總線上會產生大量的traffic，開銷是非常大的，而且unlock的CPU還必須同其它正在
競爭spinlock的CPU去競爭cacheline ownership. 隨著CPU數目的增多，性能會成衰減的非常快。
###################################################################
2. TTAS (test-and-test-and-set)
void spin_lock(lock)
{
while (test_and_set(lock, true))
while (lock != false);
}
實際代碼(kernel 2.3)：
注意這裡lock初始值為0 ，也就是當該值為0時為未鎖，為1時為上鎖 。 該定義在2.4之後被翻轉。
extern inline void spin_lock(spinlock_t *plock)
{
1:
lock ; btsl $0,plock; （btsl 指令：根據位偏移0值從位串plock中取出一位放入CF中，然後將位串中的該位置成1）
jc 2f;
注意，下一條指令的物理位置其實不是testb,而是跳出該函數。因為下面定義了一個 專門的區(.text.lock)來存放一段代碼。它們和前邊的”js 2f”並不在一個區（section）裡,原因是在大多數情況下，spin lock是能獲取成功的，從.section 到.previous的這一段代碼並不經常被調用，如果把它跟別的常用指令混在一起，會浪費指令 緩存的空間。
.section .text.lock,”ax”
2:
testb $1,plock;
rep;nop;
注意這裡rep其實不一定根據ecx寄存器的值來做循環，編譯器其實會把rep；nor翻譯成pause 指令，告訴處理器所執行的代碼序列是一個 spin-wait loop。處理器會根據這個提示而避開內存序列沖突(memory order violation)，也就是說對 spin-wait loop 不做緩存，不做指令重新排序等動作。這樣就可以大大的提高了處理器的性能。正是基於此，才建議在 spin-wait loops 中使用 paSUSE 指令。PAUSE指令的另外一個功能是讓 Pentium4 處理器在執行 spin-wait loop 時可以減少電源的消耗。
在等待資源而執行自旋鎖等待時，Pentium4 處理器以極快的速度執行自旋等待時，將會消耗很多電能，但使用 pause 指令則可以極大的減少處理器的電能消耗。
jne 2b;
jmp 1b;
.previous
}
TTAS lock的改進是，當有CPU(CPU0)已經抓住了這把鎖的話，CPU1就只會以只讀的方式
cache這個lock。這樣做的好處好處就是，CPU1在等待這把鎖的時候，不會在總線上
產生traffic，和其它CPU一起競爭cacheline的ownership。
第一次的test_and_set還是和TAS lock一樣，需要invalidate CPU0的cacheline,
這樣的話CPU1獨占的擁有了cache lock變量的cacheline。當它發現鎖已經被別人鎖住了，
CPU1就開始進入第二層循環。
如果CPU2這時也想搶這把鎖，它執行test_and_set時，會invalidate CPU1的cacheline。
它也發現鎖已經被鎖住了，進入第二層循環。
這時CPU1想讀lock這個變量的時候，會cache miss，會把read的請求發到系統總線上，
從memory中讀入lock的值，同時CPU2的cache controller會發現總線上的這次交易，它
會把自己cache了lock的cacheline的狀態轉為shared。
這樣CPU1和CPU2的cache裡都cache了lock，第二層循環就都只在CPU內部執行，不會產生
總線交易。
當CPU0釋放鎖的時候，會invalidate CPU1和CPU2的cacheline，CPU1/CPU2會cache miss，
重新讀入lock，發現鎖已經被釋放了，就會進行一個test_and_set()，誰先完成就搶到了
鎖，另一個就必須重新循環等待鎖的釋放。
TTAS lock在自己的local cache copy上spinning被稱為local spinning。是設計高效
的spinlock非常重要的一個原理。
#######################################################################
3. TTAS with random backoff
TTAS lock有一個問題是在釋放鎖的時候，會產生大量的總線交易，因為所有在競爭的
CPU都會去作一個test_and_set().
在local spinning的時候，如果引入一定的延時(就像以太網的collision avoidance機制)，
這樣就會有效的降低在鎖釋放時系統總線的競爭。
在2.6.25之前，Linux kernel x86的spinlock的實現就是這一類型的。
static inline void __raw_spin_lock(raw_spinlock_t *lock)
{
asm volatile(“\n
1:\t”
LOCK_PREFIX ” ; decb %0\n\t”
decb將lock->lock減1，它前邊的lock指令表示在執行decb的時候，要鎖住
內存總線（memory bus），另外的CPU不能訪問內存，以保證decb指令的原子性。
注意，decb並不是原子操作（atomic operation），它需要將變量從內存讀出來，
放入寄存器（register），減1，再寫入內存。如果在這時候另外的CPU也進行同樣的操作的
時候，那麼decb的執行結果就會不確定，也就是說，操作的原子性遭到了破壞。另外這裡不必擔心decb到底執行多少次（負多少），因為在unlock時 ，lock->lock 會直接被寫值為1。
“jns 3f\n”
如果decb的結果小於0，表示無法取得spin lock，則執行下一條指令（rep）。
如果decb的結果大於或等於0，表示已經獲得spin lock，則跳到標簽為3的指令，實際就是跳出整段代碼，函數返回。
“2:\t”
“rep;nop\n\t”
“cmpb $0,%0\n\t”
“jle 2b\n\t”
“jmp 1b\n”
“3:\n\t”
: “+m” (lock->slock) : : “memory”);
memory強制gcc編譯器假設RAM所有內存單元均被匯編指令修改，這樣cpu中的registers和cache中已緩存的內存單元中的數據將作廢。cpu將不得不在需要的時候重新讀取內存中的數據。這就阻止了cpu又將registers，cache中的數據用於去優化指令，而避免去訪問內存。這種技術叫做內存屏障(memory barrier)
}
首先是做一個test_and_set （LOCK; decb lock)，如果發現已經被鎖住了，就
random backoff (rep; nop)，然後作local test (cmpb)。
【注意這裡rep其實不一定根據ecx寄存器的值來做循環，編譯器其實會把rep；nor翻譯成pause 指令，告訴處理器所執行的代碼序列是一個 spin-wait loop。處理器會根據這個提示而避開內存序列沖突(memory order violation)，也就是說對 spin-wait loop 不做緩存，不做指令重新排序等動作。這樣就可以大大的提高了處理器的性能。正是基於此，才建議在 spin-wait loops 中使用 pasuse 指令。PAUSE指令的另外一個功能是讓 Pentium4 處理器在執行 spin-wait loop 時可以減少電源的消耗。
在等待資源而執行自旋鎖等待時，Pentium4 處理器以極快的速度執行自旋等待時，將會消耗很多電能，但使用 pause 指令則可以極大的減少處理器的電能消耗。】
【
PAUSE指令雖然是在Intel P4處理器開始出現的，但是它可以向後與所有的IA32處理器兼容。在早期的IA32 CPU中，PAUSE就像NOP指令。Intel P4和Intel Xeon處理器將PAUSE實現成一個預定義的延遲(pre-defined delay)。這種延遲是有限的，而且一些處理器可以為0。PAUSE指令不改變處理器的架構狀態（也就是說，它實際上只是執行了一個延遲——並不做任何其他事情——的操作）。
所以這裡說的TTAS with random backoff中的延遲應該就是指這裡的pause指令。pause指令的引入一方面使cpu內部的內存序列沖突減少（具體我也不清楚，可能是指令預取和亂序執行之類的），一方面減少電源消耗（省事了能不省電嗎），一方面還做了預定義延遲。如果沒有這個延遲，測試總共兩條指令，多個cpu同時循環時一同發現解鎖情況而競爭總線的概率很大，有了延遲，同時發現的概率大大減少，也許有的cpu根本無法發現中間鎖的歸屬已經發生變化了。這大概就是文中所說的第三代使用硬件來減少競爭的spin_lock。至於為什麼第二代的TTAS中也會出現pause指令，大概是筆誤吧，只能如此理解了
】
static inline void __raw_spin_unlock(raw_spinlock_t *lock)
{
asm volatile(“movb $1,%0″ : “+m” (lock->slock) :: “memory”);
}
######################################################################
4. FIFO ticket spinlock (solved the fairness problem)
TTAS with random backoff還有一個公平性的問題，當鎖釋放時，誰能搶到鎖是隨機的。並不是等待
最久的那個競爭者會得到鎖。這樣就可能造成一個thread會busy looping很長的時間而得不到鎖。
Linux kernel x86的ticket spinlock是有Nick Piggin實現的，在2.6.25中被接受。
(git commit id is: 314cdbefd1fd0a7acf3780e9628465b77ea6a836)
LWN上有一篇文章介紹了ticket spinlock的原理(http://lwn.net/Articles/267968/)。
一個spinlock被分成了兩個部分，owner是現在擁有鎖的lock owner的ticket id，Next是��一個能拿到鎖的ticket id，初始化的時候Owner = Next = 0。當current lock owner釋放鎖的時候，會把Owner域加1，這樣當拿著Next的鎖競爭者發現Owner已經變成自己的ticket id的時候，就認為自己拿到了鎖了。
static __always_inline void __ticket_spin_lock(raw_spinlock_t *lock)
{
short inc = 0×0100;
asm volatile (
LOCK_PREFIX “xaddw %w0, %1\n”
“1:\t”
“cmpb %h0, %b0\n\t”
“je 2f\n\t”
“rep ; nop\n\t”
“movb %1, %b0\n\t”
/* don’t need lfence here, because loads are in-order */
“jmp 1b\n”
“2:”
: “+Q” (inc), “+m” (lock->slock)
:
: “memory”, “cc”);
}
1. 初始化 -> slock: owner = next = 0
2. CPU0第一個拿到了鎖 -> slock: owner = 0, next = 1
3. 當CPU1也想競爭這把鎖的時候，xaddw -> slock: owner = 0, next = 2 同時
inc: owner = 0, next = 1
它發現inc: owner != next (注意它是在測試inc這個變量），就等待(rep; nop)，然後把s
lock的owner讀入inc。如果CPU0釋放了鎖，它會把slock:owner加1。這樣CPU1就會發現
inc:next = 1,owner = 1，它就認為自己拿到了鎖。
4. 如果在CPU0釋放鎖之前，CPU2也來競爭這把鎖的話，CPU2: slock: owner = 0, next = 3
inc: owner = 0, next = 2。當CPU0釋放鎖的時候，inc:owner = 1, next = 2，它仍然會
繼續循環，等待CPU1釋放鎖。
references:
1. For SMP cache coherence, please see chapter 4 of Computer Architecture-A
Quantitative Approach.
2. Linux kernel source code.
3. For TAS, TTAS concept refer to chapter 7 of The Art of Multiprocessor
Programming.
關於intel cpu 中的總線lock ：
從 P6 處理器開始，如果指令訪問的內存區域已經存在於處理器的內部緩存中，則“lock” 前綴並不將引線 LOCK 的電位拉低，而是鎖住本處理器的內部緩存，然後依靠緩存一致性協議保證操作的原子性。
4.2) IA32 CPU調用有lock前綴的指令，或者如xchg這樣的指令，會導致其它的CPU也觸發一定的動作來同步自己的Cache。
CPU的#lock引腳鏈接到北橋芯片(North Bridge)的#lock引腳，當帶lock前綴的執行執行時，北橋芯片會拉起#lock
電平，從而鎖住總線，直到該指令執行完畢再放開。 而總線加鎖會自動invalidate所有CPU對 _該指令涉及的內存_
的Cache，因此barrier就能保證所有CPU的Cache一致性。
4.3) 接著解釋。
lock前綴(或cpuid、xchg等指令)使得本CPU的Cache寫入了內存，該寫入動作也會引起別的CPU invalidate其Cache。
IA32在每個CPU內部實現了Snoopying(BUS-Watching)技術，監視著總線上是否發生了寫內存操作(由某個CPU或DMA控
制器發出的)，只要發生了，就invalidate相關的Cache line。 因此，只要lock前綴導致本CPU寫內存，就必將導致
所有CPU去invalidate其相關的Cache line。
