參考來源：https://blog.csdn.net/qq_34337272/article/details/81252853
CAS算法（compare and swap）
?CAS算法是一種有名的無鎖算法。無鎖編程尼啡，即不使用鎖的情況下實現(xiàn)多線程之間的變量同步炬丸，也就是在沒有線程被阻塞的情況下實現(xiàn)變量的同步科侈，所以也叫非阻塞同步（Non-blocking Synchronization）。CAS算法涉及到三個操作數(shù)
- 需要讀寫的內(nèi)存值V
- 進行比較的值A(chǔ)
- 擬寫入的新值B
?當且僅當 V 的值等于 A時，CAS通過原子方式用新值B來更新V的值，否則不會執(zhí)行任何操作（比較和替換是一個原子操作）蜻懦。一般情況下是一個自旋操作姨夹，即不斷的重試。
自旋鎖
?自旋鎖是指當一個線程在獲取鎖的時候矾策，如果鎖已經(jīng)被其他線程獲取磷账，那么該線程將循環(huán)等待，然后不斷地判斷是否能夠被成功獲取贾虽，知直到獲取到鎖才會退出循環(huán)逃糟。
?獲取鎖的線程一直處于活躍狀態(tài)，但是并沒有執(zhí)行任何有效的任務(wù)蓬豁，使用這種鎖會造成busy-waiting绰咽。
?它是為實現(xiàn)保護共享資源而提出的一種鎖機制。其實地粪，自旋鎖與互斥鎖比較類似取募，它們都是為了解決某項資源的互斥使用。無論是互斥鎖蟆技，還是自旋鎖玩敏，在任何時刻，最多只能由一個保持者质礼，也就說旺聚，在任何時刻最多只能有一個執(zhí)行單元獲得鎖。但是兩者在調(diào)度機制上略有不同眶蕉。對于互斥鎖砰粹，如果資源已經(jīng)被占用，資源申請者只能進入睡眠狀態(tài)造挽。但是自旋鎖不會引起調(diào)用者睡眠碱璃，如果自旋鎖已經(jīng)被別的執(zhí)行單元保持，調(diào)用者就一直循環(huán)在那里看是否該自旋鎖的保持者已經(jīng)釋放了鎖刽宪，“自旋”一詞就是因此而得名厘贼。
golang實現(xiàn)自旋鎖
type spinLock uint32
func (sl *spinLock) Lock() {
for !atomic.CompareAndSwapUint32((*uint32)(sl), 0, 1) {
runtime.Gosched()
}
}
func (sl *spinLock) Unlock() {
atomic.StoreUint32((*uint32)(sl), 0)
}
func NewSpinLock() sync.Locker {
var lock spinLock
return &lock
}
可重入的自旋鎖和不可重入的自旋鎖
文章開始的時候的那段代碼，仔細分析一下就可以看出圣拄，它是不支持重入的嘴秸，即當一個線程第一次已經(jīng)獲取到了該鎖，在鎖釋放之前又一次重新獲取該鎖庇谆，第二次就不能成功獲取到岳掐。由于不滿足CAS，所以第二次獲取會進入while循環(huán)等待饭耳，而如果是可重入鎖串述，第二次也是應(yīng)該能夠成功獲取到的。
而且寞肖，即使第二次能夠成功獲取纲酗，那么當?shù)谝淮吾尫沛i的時候衰腌，第二次獲取到的鎖也會被釋放，而這是不合理的觅赊。
為了實現(xiàn)可重入鎖右蕊，我們需要引入一個計數(shù)器，用來記錄獲取鎖的線程數(shù)
type spinLock struct {
owner int
count int
}
func (sl *spinLock) Lock() {
me := GetGoroutineId()
if spinLock .owner == me { // 如果當前線程已經(jīng)獲取到了鎖吮螺，線程數(shù)增加一饶囚，然后返回
sl.count++
return
}
// 如果沒獲取到鎖，則通過CAS自旋
for !atomic.CompareAndSwapUint32((*uint32)(sl), 0, 1) {
runtime.Gosched()
}
}
func (sl *spinLock) Unlock() {
if rl.owner != GetGoroutineId() {
panic("illegalMonitorStateError")
}
if sl.count >0 { // 如果大于0鸠补，表示當前線程多次獲取了該鎖萝风，釋放鎖通過count減一來模擬
sl.count--
}else { // 如果count==0，可以將鎖釋放紫岩，這樣就能保證獲取鎖的次數(shù)與釋放鎖的次數(shù)是一致的了规惰。
atomic.StoreUint32((*uint32)(sl), 0)
}
}
func GetGoroutineId() int {
defer func() {
if err := recover(); err != nil {
fmt.Println("panic recover:panic info:%v", err) }
}()
var buf [64]byte
n := runtime.Stack(buf[:], false)
idField := strings.Fields(strings.TrimPrefix(string(buf[:n]), "goroutine "))[0]
id, err := strconv.Atoi(idField)
if err != nil {
panic(fmt.Sprintf("cannot get goroutine id: %v", err))
}
return id
}
func NewSpinLock() sync.Locker {
var lock spinLock
return &lock
}
自旋鎖的其他變種
1. TicketLock
TicketLock主要解決的是公平性的問題。
思路：每當有線程獲取鎖的時候被因，就給該線程分配一個遞增的id卿拴，我們稱之為排隊號，同時梨与，鎖對應(yīng)一個服務(wù)號堕花，每當有線程釋放鎖，服務(wù)號就會遞增粥鞋，此時如果服務(wù)號與某個線程排隊號一致缘挽，那么該線程就獲得鎖，由于排隊號是遞增的呻粹，所以就保證了最先請求獲取鎖的線程可以最先獲取到鎖壕曼，就實現(xiàn)了公平性。
可以想象成銀行辦理業(yè)務(wù)排隊等浊，排隊的每一個顧客都代表一個需要請求鎖的線程腮郊，而銀行服務(wù)窗口表示鎖，每當有窗口服務(wù)完成就把自己的服務(wù)號加一筹燕，此時在排隊的所有顧客中轧飞，只有自己的排隊號與服務(wù)號一致的才可以得到服務(wù)。
2. CLHLock
CLH鎖是一種基于鏈表的可擴展撒踪、高性能过咬、公平的自旋鎖，申請線程只在本地變量上自旋制妄，它不斷輪詢前驅(qū)的狀態(tài)掸绞，如果發(fā)現(xiàn)前驅(qū)釋放了鎖就結(jié)束自旋，獲得鎖耕捞。
3. MCSLock
MCSLock則是對本地變量的節(jié)點進行循環(huán)衔掸。
4. CLHLock 和 MCSLock
- 都是基于鏈表烫幕，不同的是CLHLock是基于隱式鏈表，沒有真正的后續(xù)節(jié)點屬性具篇，MCSLock是顯示鏈表纬霞，有一個指向后續(xù)節(jié)點的屬性。
- 將獲取鎖的線程狀態(tài)借助節(jié)點(node)保存,每個線程都有一份獨立的節(jié)點驱显，這樣就解決了TicketLock多處理器緩存同步的問題。
自旋鎖與互斥鎖
- 自旋鎖與互斥鎖都是為了實現(xiàn)保護資源共享的機制瞳抓。
- 無論是自旋鎖還是互斥鎖埃疫，在任意時刻，都最多只能有一個保持者孩哑。
- 獲取互斥鎖的線程栓霜，如果鎖已經(jīng)被占用，則該線程將進入睡眠狀態(tài)横蜒；獲取自旋鎖的線程則不會睡眠胳蛮，而是一直循環(huán)等待鎖釋放。
總結(jié)：
- 自旋鎖：線程獲取鎖的時候丛晌，如果鎖被其他線程持有仅炊，則當前線程將循環(huán)等待，直到獲取到鎖澎蛛。
- 自旋鎖等待期間抚垄，線程的狀態(tài)不會改變，線程一直是用戶態(tài)并且是活動的(active)谋逻。
- 自旋鎖如果持有鎖的時間太長呆馁，則會導致其它等待獲取鎖的線程耗盡CPU。
- 自旋鎖本身無法保證公平性毁兆，同時也無法保證可重入性浙滤。
- 基于自旋鎖，可以實現(xiàn)具備公平性和可重入性質(zhì)的鎖气堕。
- TicketLock:采用類似銀行排號叫好的方式實現(xiàn)自旋鎖的公平性纺腊，但是由于不停的讀取serviceNum，每次讀寫操作都必須在多個處理器緩存之間進行緩存同步送巡，這會導致繁重的系統(tǒng)總線和內(nèi)存的流量摹菠，大大降低系統(tǒng)整體的性能。
- CLHLock和MCSLock通過鏈表的方式避免了減少了處理器緩存同步骗爆，極大的提高了性能次氨，區(qū)別在于CLHLock是通過輪詢其前驅(qū)節(jié)點的狀態(tài)，而MCS則是查看當前節(jié)點的鎖狀態(tài)摘投。
- CLHLock在NUMA架構(gòu)下使用會存在問題煮寡。在沒有cache的NUMA系統(tǒng)架構(gòu)中虹蓄，由于CLHLock是在當前節(jié)點的前一個節(jié)點上自旋,NUMA架構(gòu)中處理器訪問本地內(nèi)存的速度高于通過網(wǎng)絡(luò)訪問其他節(jié)點的內(nèi)存，所以CLHLock在NUMA架構(gòu)上不是最優(yōu)的自旋鎖幸撕。
