//?互斥鎖
type?Mutex?struct?{
?state?int32??//?狀態(tài)
?sema??uint32??//?信號量
}


const?(
?mutexLocked?=?1?<<?iota?//?1
?mutexWoken?//?2
?mutexStarving?//?4
?mutexWaiterShift?=?iota?//?3

?starvationThresholdNs?=?1e6?//?判斷是否要進(jìn)入饑餓狀態(tài)的閾值
)

//?上鎖
func?(m?*Mutex)?Lock()?{
?// fastpath：期望當(dāng)前鎖沒有被占用，可以快速獲取到鎖， CAS 修改 state 最后一位的值為1（標(biāo)記鎖是否被占用）
?if?atomic.CompareAndSwapInt32(&m.state,?0,?mutexLocked)?{
??return
?}
?//?Slow?path?:?單獨(dú)抽出來放到一個(gè)函數(shù)里，方便?fast?path?被內(nèi)聯(lián)
?m.lockSlow()
}

func?(m?*Mutex)?lockSlow()?{
?var?waitStartTime?int64?//?//?記錄等待時(shí)間
?starving?:=?false?//?當(dāng)前的?goroutine?是否已經(jīng)饑餓了（如果已經(jīng)饑餓，就會將?state?的饑餓狀態(tài)置為?1）
?awoke?:=?false??//?當(dāng)前的?goroutine?是否被喚醒的
?iter?:=?0?//?自旋次數(shù)
?old?:=?m.state?//?保存當(dāng)前的?state?狀態(tài)
?for?{
????
????/*
????自旋：如果滿足如下條件，就會進(jìn)入 if 語句，然后 continue，不斷自旋:
????1.?鎖被占用，且不處于饑餓模式（饑餓狀態(tài)直接去排隊(duì)，不允許嘗試獲取鎖）
????2.?基于當(dāng)前自旋的次數(shù)，再次自旋有意義?runtime_canSpin(iter)
????
????那么退出自旋的條件也就是：
????1.?鎖被釋放了，當(dāng)前處于沒被占用狀態(tài)（說明等到了，該goroutine就會立即去獲取鎖）
??2.?mutex進(jìn)入了饑餓模式，不自旋了，沒意義（饑餓狀態(tài)會直接把鎖交給等待隊(duì)列隊(duì)首的goroutine）
??3.?不符合自旋狀態(tài)（自旋次數(shù)太多了，自旋失去了意義）
????
????如下代碼是位操作：
????mutexLocked|mutexStarving?=?00000...101
????mutexLocked?=?00000...001
????如果要滿足 old &?00000...101 =?00000...001，需要 old = ...0*1,即狀態(tài)為：鎖被占用，且不處于饑餓狀態(tài)?
????
????runtime_canSpin(iter)?會根據(jù)自旋次數(shù)，判斷是否可以繼續(xù)自旋
????*/
??if?old&(mutexLocked|mutexStarving)?==?mutexLocked?&&?runtime_canSpin(iter)?{
???
??????/*
??????如果?
???????1.?當(dāng)前goroutine不是被喚醒的?(awoke=false)?
???????2.?鎖狀態(tài)喚醒標(biāo)志位為0（old&mutexWoken?==?0）?
???????3.?等待者數(shù)量不為0?（old>>mutexWaiterShift?!=?0??右移三位得到的就是等待者數(shù)量）
??????
???????那么利用CAS，將?state?的喚醒標(biāo)記置為1，標(biāo)記自己是被喚醒的?（將state的喚醒標(biāo)記置為1，說明外面有喚醒著的goroutine，那么在釋放鎖的時(shí)候，就不去等待隊(duì)列叫號了，畢竟已經(jīng)有喚醒的了）
???????
???????如果有其他?goroutine?已經(jīng)設(shè)置了?state?的喚醒標(biāo)記位，那么本次就會失敗
??????*/

???if?!awoke?&&?old&mutexWoken?==?0?&&?old>>mutexWaiterShift?!=?0?&&
????atomic.CompareAndSwapInt32(&m.state,?old,?old|mutexWoken)?{
????awoke?=?true
???}
???runtime_doSpin()
??????
??????//?迭代次數(shù)加一
???iter++
??????
??????//?獲取最新的狀態(tài)
???old?=?m.state
??????
??????//?想再次自旋，看看鎖釋放了沒
???continue
??}
????
????//?到這里，說明退出了自旋，當(dāng)前鎖沒被占用?或者??系統(tǒng)處于饑餓模式?或者?自旋次數(shù)太多導(dǎo)致不符合自旋條件
??
????//?new?代表當(dāng)前goroutine?基于當(dāng)前狀態(tài)要設(shè)置的新狀態(tài)
??new?:=?old
????
????//?只要不是饑餓狀態(tài)，就需要獲取鎖（饑餓狀態(tài)直接去排隊(duì)，不能搶鎖）
??if?old&mutexStarving?==?0?{
???new?|=?mutexLocked
??}
????
????//?鎖被占用?或者?處于饑餓模式下，新增一個(gè)等待者
??if?old&(mutexLocked|mutexStarving)?!=?0?{
???new?+=?1?<<?mutexWaiterShift
??}
????
????//?當(dāng)前?goroutine?已經(jīng)進(jìn)入饑餓了，且鎖還沒有釋放，需要把?Mutex?的狀態(tài)改為饑餓狀態(tài)
??if?starving?&&?old&mutexLocked?!=?0?{
???new?|=?mutexStarving
??}
????
????//?如果是被喚醒的，把喚醒標(biāo)志位置0，表示外面沒有被喚醒的goroutine了（搶到就獲得鎖、搶不到就睡眠，把喚醒標(biāo)志置0）
??if?awoke?{
???
??????//?由于是被喚醒的，new?里面的?喚醒標(biāo)記位一定是?1
???if?new&mutexWoken?==?0?{
????throw("sync:?inconsistent?mutex?state")
???}
??????
??????//?a?&^?b?的意思就是?清零a中，ab都為1的位，即清除喚醒標(biāo)記
???new?&^=?mutexWoken
??}
????
????/*
??????利用CAS,將狀態(tài)設(shè)置為新的
??????1.?如果是饑餓狀態(tài)，只增加一個(gè)等待者數(shù)量
??????2.?正常狀態(tài)，加鎖標(biāo)記置為?1，如果鎖已被占用增加一個(gè)等待者數(shù)量
??????3.?如果當(dāng)前?goroutine?已經(jīng)饑餓了，將?饑餓標(biāo)記?置為?1
??????4.?如果是被喚醒的，清除喚醒標(biāo)記
????*/
????
??if?atomic.CompareAndSwapInt32(&m.state,?old,?new)?{
??????
??????//?如果改狀態(tài)之前，鎖未被占用?且?處于正常模式，那么就相當(dāng)于獲取到鎖了
???if?old&(mutexLocked|mutexStarving)?==?0?{
????break?
???}
??????
??????//?到這里說明：1. 之前鎖被占用??或者 2.之前是處于饑餓狀態(tài)?
??????
??????//?判斷之前是否等待過（是否從隊(duì)列里喚醒的），之前等待過，再次排隊(duì)放在隊(duì)首
???queueLifo?:=?waitStartTime?!=?0
??????
??????//?如果之前沒等過（新來的），設(shè)置等待起始時(shí)間當(dāng)前時(shí)間
???if?waitStartTime?==?0?{
????waitStartTime?=?runtime_nanotime()
???}
??????
?????//?之前排過隊(duì)的老人，放到等待隊(duì)列隊(duì)首；新人放到隊(duì)尾，然后等待獲取信號量
???runtime_SemacquireMutex(&m.sema,?queueLifo,?1)
??????
??????//?鎖被釋放，goroutine?被喚醒
??????
??????//?設(shè)置當(dāng)前?goroutine?饑餓狀態(tài)，如果之前已經(jīng)饑餓，或者距離等待開始時(shí)間超過了?1ms，也變饑餓
???starving?=?starving?||?runtime_nanotime()-waitStartTime?>?starvationThresholdNs
??????
??????//?獲取最新的狀態(tài)
???old?=?m.state
??????
??????//?如果 state 饑餓標(biāo)記為1，說明當(dāng)前在饑餓模式，饑餓模式下被喚醒，已經(jīng)獲取到鎖了；
??????//?饑餓狀態(tài)下，釋放鎖沒有更新等待者數(shù)量和饑餓標(biāo)記，需要獲得鎖的goroutine去更新狀態(tài)
???if?old&mutexStarving?!=?0?{

????????//?正確性校驗(yàn)：
????????//?1.?鎖還是鎖住的狀態(tài)（鎖已經(jīng)釋放給當(dāng)前goroutine了，不應(yīng)該被鎖?。?
????//?2.?或者有被喚醒的goroutine（饑餓模式下不應(yīng)該有醒著的goroutine，都應(yīng)該去乖乖等著）
????//?3.?或者當(dāng)前goroutine?的等待者數(shù)量為0（當(dāng)前goroutine就是等待者）
????//?這三種情況不應(yīng)該出現(xiàn)，與預(yù)期狀態(tài)不符
????????
????if?old&(mutexLocked|mutexWoken)?!=?0?||?old>>mutexWaiterShift?==?0?{
?????throw("sync:?inconsistent?mutex?state")
????}
????????
????????//?加鎖，減去一個(gè)等待者
????delta?:=?int32(mutexLocked?-?1<<mutexWaiterShift)
????????
????????//?如果當(dāng)前的?goroutine?非饑餓，或者等待者只有一個(gè)（也就是只有當(dāng)前goroutine，等待隊(duì)列空了），可以取消饑餓狀態(tài)，進(jìn)入正常狀態(tài)
????if?!starving?||?old>>mutexWaiterShift?==?1?{
?????delta?-=?mutexStarving
????}
????????
????????//?修改狀態(tài)：
????????//?加鎖，減去一個(gè)等待者：m.state + mutexLocked - 1<<mutexWaiterShift :?
????????//?滿足非饑餓條件，加鎖，減去一個(gè)等待者，取消饑餓狀態(tài)：
????????//?m.state?+?mutexLocked?-?1<<mutexWaiterShift?-?mutexStarving:?
????atomic.AddInt32(&m.state,?delta)
????????
????????//?饑餓模式下被喚醒，相當(dāng)于獲得鎖了，可以結(jié)束
????break
???}
??????
??????//?之前是處于鎖被占用且非饑餓狀態(tài)，被喚醒，去繼續(xù)搶鎖
???awoke?=?true
??????
??????//?新喚醒的，自旋數(shù)量置0
???iter?=?0
??}?else?{
??????
??????//?修改新狀態(tài)失敗，狀態(tài)有更新，需要重試
???old?=?m.state
??}
?}
}

func?(m?*Mutex)?Unlock()?{

?//?Fast?path:?把鎖標(biāo)記清除
?new?:=?atomic.AddInt32(&m.state,?-mutexLocked)
?if?new?!=?0?{
??//?清除完鎖標(biāo)記，發(fā)現(xiàn)還有其他狀態(tài)，比如等待隊(duì)列不為空，需要喚醒其他?goroutine
??m.unlockSlow(new)
?}
}

func?(m?*Mutex)?unlockSlow(new?int32)?{
??
??/*?狀態(tài)正確性校驗(yàn)：
????1.?如果解鎖一個(gè)上鎖狀態(tài)的鎖，最后一位則為1，fast?path?中?new?已經(jīng)減去了1,?此時(shí)?new?最后一位應(yīng)當(dāng)為0
???2.?如果解鎖一個(gè)未上鎖狀態(tài)的鎖，最后一位則為0，fast?path?中?new?已經(jīng)減去了1,?此時(shí)?new?最后一位應(yīng)當(dāng)為1
????如果?(new+mutexLocked)&mutexLocked?==?0，說明?new?當(dāng)前最后一位是1，那么就是解鎖了一個(gè)沒有上鎖的鎖，狀態(tài)有誤
?*/
?if?(new+mutexLocked)&mutexLocked?==?0?{
??throw("sync:?unlock?of?unlocked?mutex")
?}
??
??//?正常模式，非饑餓，可能需要喚醒隊(duì)列中的?goroutine，饑餓狀態(tài)直接移交鎖
?if?new&mutexStarving?==?0?{
??old?:=?new
??for?{

??????/*?系統(tǒng)運(yùn)轉(zhuǎn)正常，鎖可以正確交接，可以直接返回了：
??????? 1. 沒有等待者了?(沒有等鎖的了，去喚醒誰？)
????????2.?有喚醒狀態(tài)的?goroutine??(自旋狀態(tài)的?goroutine，將喚醒狀態(tài)置為1)
???????3.?有?goroutine?已經(jīng)獲取了鎖?(Unlock方法已經(jīng)將鎖標(biāo)記置為了0，可能自旋的此時(shí)已經(jīng)搶到了鎖)
??????*/
???if?old>>mutexWaiterShift?==?0?||?old&(mutexLocked|mutexWoken|mutexStarving)?!=?0?{
????return
???}
??????
??????//?沒有喚醒狀態(tài)的?goroutine，喚醒一個(gè)去搶鎖
???//?減去一個(gè)等待者，并且將?喚醒標(biāo)記?置為?1
???new?=?(old?-?1<<mutexWaiterShift)?|?mutexWoken
???if?atomic.CompareAndSwapInt32(&m.state,?old,?new)?{
????????//?第二個(gè)參數(shù)為false,?喚醒隊(duì)首的?goroutine?去搶鎖(不一定能搶到)
????runtime_Semrelease(&m.sema,?false,?1)
????return
???}
??????
??????//?上面?CAS?失敗，可能由于新增了一個(gè)等待者，for?循環(huán)重試
???old?=?m.state
??}
?}?else?{
??
????/*
?????1.?第二個(gè)參數(shù)為?true，直接將鎖的所有權(quán)，交給等待隊(duì)列的第一個(gè)等待者
???2.?注意，此時(shí)沒有設(shè)置?mutexLocked?=1?，被喚醒的?goroutine?會設(shè)置
???3.?雖然沒有設(shè)置?mutexLocked?，但是饑餓模式下,?Mutex?始終被認(rèn)為是鎖住的，都會直接排隊(duì)等待移交鎖
????*/
??runtime_Semrelease(&m.sema,?true,?1)
?}
}