Go 互斥鎖的實現原理？

Go sync包提供了兩種鎖類型：互斥鎖sync.Mutex 和 讀寫互斥鎖sync.RWMutex，都屬于悲觀鎖。

概念

Mutex是互斥鎖，當一個 goroutine 獲得了鎖后，其他 goroutine 不能獲取鎖（只能存在一個寫者或讀者，不能同時讀和寫）

使用場景

多個線程同時訪問臨界區，為保證數據的安全，鎖住一些共享資源， 以防止并發訪問這些共享數據時可能導致的數據不一致問題。

獲取鎖的線程可以正常訪問臨界區，未獲取到鎖的線程等待鎖釋放后可以嘗試獲取鎖

底層實現結構

互斥鎖對應的是底層結構是sync.Mutex結構體，，位于 src/sync/mutex.go中

type Mutex struct {
     state int32
     sema  uint32
 }

state表示鎖的狀態，有鎖定、被喚醒、饑餓模式等，并且是用state的二進制位來標識的，不同模式下會有不同的處理方式

sema表示信號量，mutex阻塞隊列的定位是通過這個變量來實現的，從而實現goroutine的阻塞和喚醒

addr = &sema
func semroot(addr *uint32) *semaRoot {
   return &semtable[(uintptr(unsafe.Pointer(addr))>>3)%semTabSize].root  
}
root := semroot(addr)
root.queue(addr, s, lifo)
root.dequeue(addr)

var semtable [251]struct {
   root semaRoot
   ...
}

type semaRoot struct {
  lock  mutex  
  treap *sudog // root of balanced tree of unique waiters.  
  nwait uint32 // Number of waiters. Read w/o the lock.  
}

type sudog struct {
    g *g  
    next *sudog  
    prev *sudog
    elem unsafe.Pointer // 指向sema變量
    waitlink *sudog // g.waiting list or semaRoot  
    waittail *sudog // semaRoot
    ...
}

操作

鎖的實現一般會依賴于原子操作、信號量，通過atomic 包中的一些原子操作來實現鎖的鎖定，通過信號量來實現線程的阻塞與喚醒

加鎖

通過原子操作cas加鎖，如果加鎖不成功，根據不同的場景選擇自旋重試加鎖或者阻塞等待被喚醒后加鎖

func (m *Mutex) Lock() {
    // Fast path: 幸運之路，一下就獲取到了鎖
    if atomic.CompareAndSwapInt32(&m.state, 0, mutexLocked) {
        return
    }
    // Slow path：緩慢之路，嘗試自旋或阻塞獲取鎖
    m.lockSlow()
}

解鎖

通過原子操作add解鎖，如果仍有goroutine在等待，喚醒等待的goroutine

func (m *Mutex) Unlock() {  
   // Fast path: 幸運之路，解鎖
   new := atomic.AddInt32(&m.state, -mutexLocked)  
   if new != 0 {  
            // Slow path：如果有等待的goroutine，喚醒等待的goroutine
            m.unlockSlow()
   }  
}

注意點：

• 在 Lock() 之前使用 Unlock() 會導致 panic 異常
• 使用 Lock() 加鎖后，再次 Lock() 會導致死鎖（不支持重入），需Unlock()解鎖后才能再加鎖
• 鎖定狀態與 goroutine 沒有關聯，一個 goroutine 可以 Lock，另一個 goroutine 可以 Unlock

Go 互斥鎖正常模式和饑餓模式的區別？

在Go一共可以分為兩種搶鎖的模式，一種是正常模式，另外一種是饑餓模式。

正常模式(非公平鎖)

在剛開始的時候，是處于正常模式（Barging），也就是，當一個G1持有著一個鎖的時候，G2會自旋的去嘗試獲取這個鎖

當自旋超過4次還沒有能獲取到鎖的時候，這個G2就會被加入到獲取鎖的等待隊列里面，并阻塞等待喚醒

正常模式下，所有等待鎖的 goroutine 按照 FIFO(先進先出)順序等待。喚醒的goroutine 不會直接擁有鎖，而是會和新請求鎖的 goroutine 競爭鎖。新請求鎖的 goroutine 具有優勢：它正在 CPU 上執行，而且可能有好幾個，所以剛剛喚醒的 goroutine 有很大可能在鎖競爭中失敗，長時間獲取不到鎖，就會切換到饑餓模式

饑餓模式(公平鎖)

當一個 goroutine 等待鎖時間超過 1 毫秒時，它可能會遇到饑餓問題。 在版本1.9中，這種場景下Go Mutex 切換到饑餓模式（handoff），解決饑餓問題。

starving = runtime_nanotime()-waitStartTime > 1e6

正常模式下，所有等待鎖的 goroutine 按照 FIFO(先進先出)順序等待。喚醒的goroutine 不會直接擁有鎖，而是會和新請求鎖的 goroutine 競爭鎖。新請求鎖的 goroutine 具有優勢：它正在 CPU 上執行，而且可能有好幾個，所以剛剛喚醒的 goroutine 有很大可能在鎖競爭中失敗，長時間獲取不到鎖，就會切換到饑餓模式

那么也不可能說永遠的保持一個饑餓的狀態，總歸會有吃飽的時候，也就是總有那么一刻Mutex會回歸到正常模式，那么回歸正常模式必須具備的條件有以下幾種：

• G的執行時間小于1ms
• 等待隊列已經全部清空了

當滿足上述兩個條件的任意一個的時候，Mutex會切換回正常模式，而Go的搶鎖的過程，就是在這個正常模式和饑餓模式中來回切換進行的。

delta := int32(mutexLocked - 1<<mutexWaiterShift)  
if !starving || old>>mutexWaiterShift == 1 {  
    delta -= mutexStarving
}
atomic.AddInt32(&m.state, delta)

小結：

對于兩種模式，正常模式下的性能是最好的，goroutine 可以連續多次獲取鎖，饑餓模式解決了取鎖公平的問題，但是性能會下降，其實是性能和公平的 一個平衡模式。

Go 互斥鎖允許自旋的條件？

線程沒有獲取到鎖時常見有2種處理方式：

• 一種是沒有獲取到鎖的線程就一直循環等待判斷該資源是否已經釋放鎖，這種鎖也叫做自旋鎖，它不用將線程阻塞起來， 適用于并發低且程序執行時間短的場景，缺點是cpu占用較高
• 另外一種處理方式就是把自己阻塞起來，會釋放CPU給其他線程，內核會將線程置為「睡眠」狀態，等到鎖被釋放后，內核會在合適的時機喚醒該線程，適用于高并發場景，缺點是有線程上下文切換的開銷

Go語言中的Mutex實現了自旋與阻塞兩種場景，當滿足不了自旋條件時，就會進入阻塞

允許自旋的條件：

• 鎖已被占用，并且鎖不處于饑餓模式。
• 積累的自旋次數小于最大自旋次數（active_spin=4）。
• cpu 核數大于 1。
• 有空閑的 P。
• 當前 goroutine 所掛載的 P 下，本地待運行隊列為空。

if old&(mutexLocked|mutexStarving) == mutexLocked && runtime_canSpin(iter) {  
    ...
    runtime_doSpin()   
    continue  
}


func sync_runtime_canSpin(i int) bool {  
    if i >= active_spin 
    || ncpu <= 1 
    || gomaxprocs <= int32(sched.npidle+sched.nmspinning)+1 {  
          return false  
     }  
   if p := getg().m.p.ptr(); !runqempty(p) {  
      return false  
 }  
   return true  
}

自旋：

func sync_runtime_doSpin() {
    procyield(active_spin_cnt)
}    

如果可以進入自旋狀態之后就會調用?runtime_doSpin?方法進入自旋，?doSpin?方法會調用?procyield(30)?執行30次?PAUSE?指令，什么都不做，但是會消耗CPU時間