Mutex互斥锁设计思路详解和源码探究

　　序言
　　Mutex通常用于并发环境下控制多个协程对临界资源的访问，使得并发的协程之间可以互斥地操作同一份资源。这篇文章我们就来理解一下Golang中互斥锁的设计思想以及对互斥锁的实现源码进行探究。
　　之前发布过一篇简短的解析，感觉不够详细因此重新发一篇文章深入剖析一下。源码解析
　　下面是源码中Mutex的定义，其实现了Locker接口。AMutexisamutualexclusionlock。ThezerovalueforaMutexisanunlockedmutex。AMutexmustnotbecopiedafterfirstuse。typeMutexstruct｛stateint32semauint32｝ALockerrepresentsanobjectthatcanbelockedandunlocked。typeLockerinterface｛Lock（）Unlock（）｝const（mutexLocked1iotamutexislockedmutexWokenmutexStarvingmutexWaiterShiftiotaMutexfairness。Mutexcanbein2modesofoperations：normalandstarvation。InnormalmodewaitersarequeuedinFIFOorder，butawokenupwaiterdoesnotownthemutexandcompeteswithnewarrivinggoroutinesovertheownership。NewarrivinggoroutineshaveanadvantagetheyarealreadyrunningonCPUandtherecanbelotsofthem，soawokenupwaiterhasgoodchancesoflosing。Insuchcaseitisqueuedatfrontofthewaitqueue。Ifawaiterfailstoacquirethemutexformorethan1ms，itswitchesmutextothestarvationmode。Instarvationmodeownershipofthemutexisdirectlyhandedofffromtheunlockinggoroutinetothewaiteratthefrontofthequeue。Newarrivinggoroutinesdonttrytoacquirethemutexevenifitappearstobeunlocked，anddonttrytospin。Insteadtheyqueuethemselvesatthetailofthewaitqueue。Ifawaiterreceivesownershipofthemutexandseesthateither（1）itisthelastwaiterinthequeue，or（2）itwaitedforlessthan1ms，itswitchesmutexbacktonormaloperationmode。Normalmodehasconsiderablybetterperformanceasagoroutinecanacquireamutexseveraltimesinarowevenifthereareblockedwaiters。Starvationmodeisimportanttopreventpathologicalcasesoftaillatency。starvationThresholdNs1e6）源码注释翻译
　　Mutex是互斥锁。零值状态下是非上锁状态，第一次使用后不允许再被拷贝。
　　Mutex有两种工作模式：正常模式和饥饿模式。
　　在正常模式下，所有的goroutine会按照先进先出的顺序等待锁的释放。但是一个刚被唤醒的goroutine不会直接获取到锁，而是会和新来的请求锁的goroutine去竞争锁。新来的goroutine具有一个优势：它正在CPU上执行而且可能有好几个新来的goroutine同时在请求锁，所以刚刚被唤醒的goroutine有很大可能在锁竞争中失败。在这种情况下，这个被唤醒的goroutine在竞争锁失败之后会加入到等待队列的最前面。如果一个等待的goroutine超过1ms后仍然没有获取锁，那么它将会把锁转变为饥饿模式。
　　在饥饿模式下，锁的所有权将从执行unlock的goroutine直接交给等待队列中的第一个goroutine。新来的goroutine将不能再去尝试竞争锁，即使锁是unlock状态也不会去进行自旋操作，而是进入等待队列的尾部等待被唤醒。
　　如果一个被唤醒的goroutine获取到了锁，并且满足以下其中一个条件，那么他会将锁换为正常工作模式：a。它是等待队列中的最后一个。b。它等待的时间小于1ms。
　　正常模式具有较好的性能，因为一个goroutine可以连续多次获取锁，即使还有其他的阻塞等待锁的goroutine也不需要进入休眠阻塞。饥饿模式对防止尾部延迟的问题是非常重要的。解读
　　可以看到golang将Mutex设计成了两种工作模式，默认初始化时是正常模式，这种模式下一个请求锁的groutine将会有很高的效率获取到锁。饥饿模式下会优先将锁给到那些等待时间最久的协程。为什么这么设计
　　其实从注释中我们就可以解读出这么设计的原因，那就是为了提高加锁效率。
　　正常来说，如果是我们自己设计一个锁，必定是先尝试获取锁，如果获取失败则进入等待队列休眠等待锁释放时被唤醒。这样每当锁释放时都要唤醒一个协程。被唤醒的协程等待runtime调度并且协程切换才能继续获取锁，比较耗费性能，如果此时存在正在运行中的请求锁的协程，那就可以让该协程优先获取锁，提高加锁的效率（所谓来的早不如来的巧）。显而易见，这种行为在某些情况下会导致处于等待中的协程长时间获取不到锁的情况，因此需要设计饥饿模式，在该模式下被释放的锁会优先给到饥饿的协程，这样就保证了锁的公平性。
　　在理解了Mutex的设计思想之后我们再去看源码的具体实现，按照我们上面的思路去逐一分析关键代码。定义typeMutexstruct｛stateint32semauint32｝const（mutexLocked1iota加锁标识位掩码mutexWoken唤醒标识位掩码mutexStarving饥饿标识位掩码mutexWaiterShiftiota休眠等待协程计数起始位的偏移）state是个复合变量，用不同bit位标识锁的当前状态。
　　第0位标识是否被加锁。m。statemutexLocked！0表示锁被持有。第1位标识是否存在被唤醒的协程。m。statemutexWoken！0表示存在被唤醒的协程。第2位标识锁当前所处的工作模式。m。statemutesStarving！0表示锁处于饥饿模式。331位用于记录处于休眠等待的协程的数量。countm。statemutexWaiterShift。
　　sema是信号量，用于等待goroutine的唤醒操作。加锁Locklocksm。Ifthelockisalreadyinuse，thecallinggoroutineblocksuntilthemutexisavailable。如果Mutex已经处于加锁状态，那么调用Lock函数的协程将会阻塞直到加锁成功。func（mMutex）Lock（）｛Fastpath：grabunlockedmutex。如果锁是初始化状态则尝试加锁，成功直接返回ifatomic。CompareAndSwapInt32（m。state，0，mutexLocked）｛ifrace。Enabled｛race。Acquire（unsafe。Pointer（m））｝return｝Slowpath（outlinedsothatthefastpathcanbeinlined）否则调用lockSlow去和其他协程竞争锁。m。lockSlow（）｝func（mMutex）lockSlow（）｛varwaitStartTimeint64当前协程阻塞等待的开始时间starving：false当前协程是否饥饿awoke：false当前协程是否是被唤醒的iter：0当前协程已经自旋的次数old：m。state获取当前锁的状态for｛用于自旋以及被唤醒后的逻辑处理Dontspininstarvationmode，ownershipishandedofftowaiterssowewontbeabletoacquirethemutexanyway。饥饿模式下是直接将锁交给下一位，所以我们这里是不可以获取锁的，所以只有正常模式可以自旋，饥饿模式直接阻塞。正常模式在锁没有释放的情况下自旋一段时间，如果期间锁被释放能更快的获取到锁。ifold（mutexLockedmutexStarving）mutexLockedruntimecanSpin（iter）｛Activespinningmakessense。TrytosetmutexWokenflagtoinformUnlocktonotwakeotherblockedgoroutines。自旋时尝试设置唤醒位来告诉Unlock操作不要再唤醒阻塞的协程，因为已经有正在运行的协程了，所以就不要再多余唤醒。（这个实现就是满足我们上面理解的优先将锁给到正在执行中的协程的设计）这里需要满足3个条件：1。如果当前协程是被唤醒的或者当前协程已经成功设置了woken位，就没必要再设置了。2。如果已经有被唤醒的协程就没必要再设置了。3。如果没有在阻塞等待的协程也就没必要设置了，因为unlock本身也不会执行唤醒操作。if！awokeoldmutexWoken0oldmutexWaiterShift！0atomic。CompareAndSwapInt32（m。state，old，oldmutexWoken）｛awoketrue｝runtimedoSpin（）iteroldm。statecontinue｝走到这里就有三种情况1。锁已经被释放，可以竞争锁了2。超出自旋次数限制且锁还没释放，需要排队等待3。锁已经处于饥饿模式，需要排队等待1和2两种情况都处在正常模式下，均可以去竞争锁，情况3只能休眠。new：oldDonttrytoacquirestarvingmutex，newarrivinggoroutinesmustqueue。非饥饿模式下可以尝试获取锁ifoldmutexStarving0｛newmutexLocked｝饥饿模式下只能进等待队列了ifold（mutexLockedmutexStarving）！0｛new1mutexWaiterShift｝Thecurrentgoroutineswitchesmutextostarvationmode。Butifthemutexiscurrentlyunlocked，dontdotheswitch。Unlockexpectsthatstarvingmutexhaswaiters，whichwillnotbetrueinthiscase。如果当前协程已经饥饿且锁还被持有则将锁切换为饥饿模式。如果当前锁已释放就不要切换，因为饥饿模式下必须要有等待者（因为饥饿模式下解锁时会直接把锁给到等待的协程），这种情况下不一定有等待的协程。ifstarvingoldmutexLocked！0｛newmutexStarving｝ifawoke｛Thegoroutinehasbeenwokenfromsleep，soweneedtoresettheflagineithercase。ifnewmutexWoken0｛throw（sync：inconsistentmutexstate）｝如果当前协程是被唤醒的，需要重置唤醒位newmutexWoken｝ifatomic。CompareAndSwapInt32（m。state，old，new）｛状态设置成功如果当前锁是释放状态且工作在正常模式下则加锁成功。ifold（mutexLockedmutexStarving）0｛breaklockedthemutexwithCAS｝当前可能状态有：锁处于饥饿模式或者还在被持有中Ifwewerealreadywaitingbefore，queueatthefrontofthequeue。如果waitStartTime！0说明是被唤醒的，则重新进入队列的头部等待下次被唤醒。queueLifo：waitStartTime！0ifwaitStartTime0｛waitStartTimeruntimenanotime（）｝runtimeSemacquireMutex（m。sema，queueLifo，1）阻塞排队判断是否已经饥饿starvingstarvingruntimenanotime（）waitStartTimestarvationThresholdNsoldm。stateifoldmutexStarving！0｛Ifthisgoroutinewaswokenandmutexisinstarvationmode，ownershipwashandedofftousbutmutexisinsomewhatinconsistentstate：mutexLockedisnotsetandwearestillaccountedaswaiter。Fixthat。如果当前协程被唤醒且Mutex处于饥饿模式，锁的拥有者将锁交到当前协程但是锁处于不一致的状态：mutexLocked还没有被设置并且当前协程还被算成一个等待者，需要修复状态。ifold（mutexLockedmutexWoken）！0oldmutexWaiterShift0｛throw（sync：inconsistentmutexstate）｝delta：int32（mutexLocked1mutexWaiterShift）if！starvingoldmutexWaiterShift1｛Exitstarvationmode。Criticaltodoithereandconsiderwaittime。Starvationmodeissoinefficient，thattwogoroutinescangolockstepinfinitelyoncetheyswitchmutextostarvationmode。如果当前为非饥饿模式或者自己是等待队列里的最后一个，则调整锁模式为正常模式deltamutexStarving｝atomic。AddInt32（m。state，delta）break｝非饥饿模式下被唤醒后重新竞争锁，没有优势awoketrueiter0｝else｛oldm。state竞争失败重来一次｝｝ifrace。Enabled｛race。Acquire（unsafe。Pointer（m））｝｝快速加锁
　　atomic。CompareAndSwapInt32（m。state，0，mutexLocked）用于判断锁是否为初始状态并尝试加锁，如果加锁成功则直接返回，提高加锁效率；如果加锁失败说明锁已被占用，则调用lockSlow去做相应的操作。自旋满足下面条件能进入自旋状态：
　　1。当前互斥锁的状态是非饥饿状态，并且已经被锁定了。
　　2。自旋次数不超过4次。
　　3。cpu个数大于一，必须要是多核cpu。
　　4。处于空闲状态或自旋状态的procs加上本协程小于gomaxprocs。
　　5。当前p的待执行队列为空。Activespinningforsync。Mutex。go：linknamesyncruntimecanSpinsync。runtimecanSpingo：nosplitfuncsyncruntimecanSpin（iint）bool｛ifiactivespinncpu1gomaxprocsint32（sched。npidlesched。nmspinning）1｛returnfalse｝ifp：getg（）。m。p。ptr（）；！runqempty（p）｛returnfalse｝returntrue｝slowLock总结在自旋的过程中会尝试设置mutexWoken来通知解锁操作不去唤醒其他已经休眠的协程，在自旋模式下，当前的协程就能更快的获取到锁。自旋完成之后，就会去计算当前的锁的状态，如果当前处在饥饿模式下则不会去请求锁。状态计算完成之后就会尝试使用CAS操作获取锁，如果获取成功就会直接退出循环。如果没有获取到就调用runtimeSemacquireMutex（m。sema，queueLifo，1）方法休眠当前协程。协程被唤醒之后会先判断当前是否处在饥饿状态。1。如果处在饥饿状态就会获得互斥锁，如果等待队列中只存在当前协程或者当前协程不饥饿（如果当前协程超过等待超过1ms还没有获取到锁就会饥饿），会将互斥锁切换成正常模式。2。如果不是饥饿模式就会设置唤醒和饥饿标记、重置自旋次数并重新执行获取锁的循环。runtimeSemacquireMutex实现细节Semacquirewaitsuntils0andthenatomicallydecrementsit。Itisintendedasasimplesleepprimitiveforusebythesynchronizationlibraryandshouldnotbeuseddirectly。Semacquire等待直到s0并且自动减少s值，这是专门为同步库设计的简单的睡眠原语，不应该被直接使用。funcruntimeSemacquire（suint32）SemacquireMutexislikeSemacquire，butforprofilingcontendedMutexes。Iflifoistrue，queuewaiterattheheadofwaitqueue。skipframesisthenumberofframestoomitduringtracing，countingfromruntimeSemacquireMutexscaller。SemacquireMutex跟Semacquire类似，不过是为了互斥锁特殊优化的，如果lifo为true直接将当前goroutine放在阻塞队列首位。funcruntimeSemacquireMutex（suint32，lifobool，skipframesint）加锁流程图
　　解锁Unlockunlocksm。ItisaruntimeerrorifmisnotlockedonentrytoUnlock。AlockedMutexisnotassociatedwithaparticulargoroutine。ItisallowedforonegoroutinetolockaMutexandthenarrangeforanothergoroutinetounlockit。解锁一个没有锁定的互斥量会报运行时错误。一个加锁的Mutex并不和特定的协程绑定，允许一个协程对mutex加锁然后安排另一个协程解锁。func（mMutex）Unlock（）｛ifrace。Enabled｛m。staterace。Release（unsafe。Pointer（m））｝Fastpath：droplockbit。new：atomic。AddInt32（m。state，mutexLocked）ifnew！0｛如果new等于零表示没有其他任何需要通知的协程。直接返回Outlinedslowpathtoallowinliningthefastpath。TohideunlockSlowduringtracingweskiponeextraframewhentracingGoUnblock。m。unlockSlow（new）｝｝func（mMutex）unlockSlow（newint32）｛解锁一个未加锁的Mutex会报错if（newmutexLocked）mutexLocked0｛throw（sync：unlockofunlockedmutex）｝锁释放后的后续处理工作：1。正常模式下唤醒一个等待的协程竞争锁。2。饥饿模式下唤醒等待队列首位的协程获取锁。ifnewmutexStarving0｛old：newfor｛Iftherearenowaitersoragoroutinehasalreadybeenwokenorgrabbedthelock，noneedtowakeanyone。Instarvationmodeownershipisdirectlyhandedofffromunlockinggoroutinetothenextwaiter。Wearenotpartofthischain，sincewedidnotobservemutexStarvingwhenweunlockedthemutexabove。Sogetofftheway。如果没有等待的协程或者已经有被唤醒的协程或者锁已经被重新抢到或者锁已经变成饥饿模式，则直接退出。ifoldmutexWaiterShift0old（mutexLockedmutexWokenmutexStarving）！0｛return｝Grabtherighttowakesomeone。将等待着减一并且设置唤醒位new（old1mutexWaiterShift）mutexWokenifatomic。CompareAndSwapInt32（m。state，old，new）｛唤醒等待goroutineruntimeSemrelease（m。sema，false，1）return｝oldm。state｝｝else｛Starvingmode：handoffmutexownershiptothenextwaiter，andyieldourtimeslicesothatthenextwaitercanstarttorunimmediately。Note：mutexLockedisnotset，thewaiterwillsetitafterwakeup。ButmutexisstillconsideredlockedifmutexStarvingisset，sonewcominggoroutineswontacquireit。饥饿模式下直接唤醒队首的协程并且让出时间片使其可以立即运行注意：此时mutexLocked还未设置，被唤醒的协程在被唤醒后会进行设置，但是在饥饿模式下Mutex会仍然被认为在加锁状态，因此新来的goroutine不会获取到锁runtimeSemrelease（m。sema，true，1）｝｝
　　解锁主要做三部分工作：
　　尝试快速解锁。正常工作模式下尝试唤醒一个等待中的协程去竞争锁（如果已经有别的协程抢到了锁或者已经存在唤醒中的协程或者没有需要等待的协程或者锁被设置成了饥饿模式，则不再进行操作）。饥饿工作模式下直接唤醒第一个等待的协程把锁交给它（饥饿模式下一定有等待加锁的协程）。runtimeSemrelease详解SemreleaseatomicallyincrementssandnotifiesawaitinggoroutineifoneisblockedinSemacquire。Itisintendedasasimplewakeupprimitiveforusebythesynchronizationlibraryandshouldnotbeuseddirectly。Ifhandoffistrue，passcountdirectlytothefirstwaiter。skipframesisthenumberofframestoomitduringtracing，countingfromruntimeSemreleasescaller。Semrelease自动增加s的值并且唤醒一个阻塞的goroutine。如果handoff等于true，直接将count传递给第一个等待者！funcruntimeSemrelease（suint32，handoffbool，skipframesint）饥饿模式解锁
　　解锁后state有mutexStarving标识，无mutexLocked标识。被唤醒的协程会设置mutexLocked状态并将等待的协程数减1。需要注意的是并不会马上清除mutexStarving标识而是一直在饥饿模式下工作，直到遇到第一个符合条件的协程才会清除mutexStarving标识。
　　在饥饿模式下，如果有新的协程来请求抢占锁，mutex会被认为还处于锁状态，所以新来的协程不会进行抢占锁操作。解锁流程图：
　　总结
　　本文通过对Mutex的设计思想的深入分析和对源码实现的探索全面的讲解了GolangMutex互斥锁的设计。
　　总结得出Mutex通过正常模式和饥饿模式两种模式来平衡锁的效率和公平性。
　　希望对阅读这篇文章的你对锁的理解有所帮助，如果文章中存在错误之处欢迎指出，我们共同进步。推荐阅读
　　Golang实用教程：协程的应用技巧
　　Golang内存模型