簡單分析Linux Mutex機制
說明：
Kernel版本：4.14
ARM64處理器，Contex-A53，雙核
使用工具：Source Insight 3.5， Visio
1. 概述
Mutex互斥鎖是Linux內核中用于互斥操作的一種同步原語；互斥鎖是一種休眠鎖，鎖爭用時可能存在進程的睡眠與喚醒，context的切換帶來的代價較高，適用于加鎖時間較長的場景；
互斥鎖每次只允許一個進程進入臨界區(qū)，有點類似于二值信號量；
互斥鎖在鎖爭用時，在鎖被持有時，選擇自選等待，而不立即進行休眠，可以極大的提高性能，這種機制（
optimistic spinning）也應用到了讀寫信號量上；互斥鎖的缺點是互斥鎖對象的結構較大，會占用更多的CPU緩存和內存空間；
與信號量相比，互斥鎖的性能與擴展性都更好，因此，在內核中總是會優(yōu)先考慮互斥鎖；
互斥鎖按為了提高性能，提供了三條路徑處理：快速路徑，中速路徑，慢速路徑；
前戲都已經(jīng)講完了，來看看實際的實現(xiàn)過程吧。
2. optimistic spinning
2.1 MCS鎖
上文中提到過
Mutex在實現(xiàn)過程中，采用了optimistic spinning自旋等待機制，這個機制的核心就是基于MCS鎖機制來實現(xiàn)的；MCS鎖機制是由John Mellor Crummey和Michael Scott在論文中《algorithms for scalable synchronization on shared-memory multiprocessors》提出的，并以他倆的名字來命名；MCS鎖機制要解決的問題是：在多CPU系統(tǒng)中，自旋鎖都在同一個變量上進行自旋，在獲取鎖時會將包含鎖的cache line移動到本地CPU，這種cache-line bouncing會很大程度影響性能；MCS鎖機制的核心思想：每個CPU都分配一個自旋鎖結構體，自旋鎖的申請者（per-CPU）在local-CPU變量上自旋，這些結構體組建成一個鏈表，申請者自旋等待前驅節(jié)點釋放該鎖；osq(optimistci spinning queue)是基于MCS算法的一個具體實現(xiàn)，并經(jīng)過了迭代優(yōu)化；
【文章福利】小編推薦自己的Linux內核技術交流群:【749907784】整理了一些個人覺得比較好的學習書籍、視頻資料共享在群文件里面，有需要的可以自行添加哦！?。。ê曨l教程、電子書、實戰(zhàn)項目及代碼)? ?
2.2 osq流程分析
optimistic spinning，樂觀自旋，到底有多樂觀呢？當發(fā)現(xiàn)鎖被持有時，optimistic spinning相信持有者很快就能把鎖釋放，因此它選擇自旋等待，而不是睡眠等待，這樣也就能減少進程切換帶來的開銷了。
看一下數(shù)據(jù)結構吧：
osq_lock如下：
osq加鎖有幾種情況：
無人持有鎖，那是最理想的狀態(tài)，直接返回；
有人持有鎖，將當前的Node加入到OSQ隊列中，在沒有高優(yōu)先級任務搶占時，自旋等待前驅節(jié)點釋放鎖；
自旋等待過程中，如果遇到高優(yōu)先級任務搶占，那么需要做的事情就是將之前加入到OSQ隊列中的當前節(jié)點，從OSQ隊列中移除，移除的過程又分為三個步驟，分別是處理prev前驅節(jié)點的next指針指向、當前節(jié)點Node的next指針指向、以及將prev節(jié)點與next后繼節(jié)點連接；
加鎖過程中使用了原子操作，來確保正確性；
osq_unlock如下：
解鎖時也分為幾種情況：
無人爭用該鎖，那直接可以釋放鎖；
獲取當前節(jié)點指向的下一個節(jié)點，如果下一個節(jié)點不為NULL，則將下一個節(jié)點解鎖；
當前節(jié)點的下一個節(jié)點為NULL，則調用
osq_wait_next，來等待獲取下一個節(jié)點，并在獲取成功后對下一個節(jié)點進行解鎖；從解鎖的情況可以看出，這個過程相當于鎖的傳遞，從上一個節(jié)點傳遞給下一個節(jié)點；
在加鎖和解鎖的過程中，由于可能存在操作來更改osq隊列，因此都調用了osq_wait_next來獲取下一個確定的節(jié)點：
3. mutex
3.1 數(shù)據(jù)結構
終于來到了主題了，先看一下數(shù)據(jù)結構：
在使用mutex時，有以下幾點需要注意的：
一次只能有一個進程能持有互斥鎖；
只有鎖的持有者能進行解鎖操作；
禁止多次解鎖操作；
禁止遞歸加鎖操作；
mutex結構只能通過API進行初始化；
mutex結構禁止通過
memset或者拷貝來進行初始化；已經(jīng)被持有的mutex鎖禁止被再次初始化；
mutex不允許在硬件或軟件上下文（
tasklets, timer）中使用；
3.2 加鎖流程分析
從mutex_lock加鎖來看一下大概的流程：
mutex_lock為了提高性能，分為三種路徑處理，優(yōu)先使用快速和中速路徑來處理，如果條件不滿足則會跳轉到慢速路徑來處理，慢速路徑中會進行睡眠和調度，因此開銷也是最大的。
3.2.1 fast-path
快速路徑是在
__mutex_trylock_fast中實現(xiàn)的，該函數(shù)的實現(xiàn)也很簡單，直接調用atomic_long_cmpxchg_release(&lock->owner, 0UL, curr)函數(shù)來進行判斷，如果lock->owner == 0表明鎖未被持有，將curr賦值給lock->owner標識curr進程持有該鎖，并直接返回；lock->owner不等于0，表明鎖被持有，需要進入下一個路徑來處理了；
3.2.2 mid-path
中速路徑和慢速路徑的處理都是在
__mutex_lock_common中實現(xiàn)的；__mutex_lock_common的傳入?yún)?shù)為(lock, TASK_INTERRUPTIBLE, 0, NULL, _RET_IP_, false)，該函數(shù)中很多路徑覆蓋不到，接下來的分析也會剔除掉無效代碼；
中速路徑的核心代碼如下：
當發(fā)現(xiàn)mutex鎖的持有者正在運行（另一個CPU）時，可以不進行睡眠調度，而可以選擇自選等待，當鎖持有者正在運行時，它很有可能很快會釋放鎖，這個就是樂觀自旋的原因；
自旋等待的條件是持有鎖者正在臨界區(qū)運行，自旋等待才有價值；
__mutex_trylock_or_owner函數(shù)用于嘗試獲取鎖，如果獲取失敗則返回鎖的持有者?；コ怄i的結構體中owner字段，分為兩個部分：1）鎖持有者進程的task_struct（由于L1_CACHE_BYTES對齊，低位比特沒有使用）；2）MUTEX_FLAGS部分，也就是對應低三位，如下：MUTEX_FLAG_WAITERS：比特0，標識存在非空等待者鏈表，在解鎖的時候需要執(zhí)行喚醒操作；MUTEX_FLAG_HANDOFF：比特1，表明解鎖的時候需要將鎖傳遞給頂部的等待者；MUTEX_FLAG_PICKUP：比特2，表明鎖的交接準備已經(jīng)做完了，可以等待被取走了；mutex_optimistic_spin用于執(zhí)行樂觀自旋，理想的情況下鎖持有者執(zhí)行完釋放，當前進程就能很快的獲取到鎖。實際需要考慮，如果鎖的持有者如果在臨界區(qū)被調度出去了，task_struct->on_cpu == 0，那么需要結束自旋等待了，否則豈不是傻傻等待了。mutex_can_spin_on_owner：進入自旋前檢查一下，如果當前進程需要調度，或者鎖的持有者已經(jīng)被調度出去了，那么直接就返回了，不需要做接下來的osq_lock/oqs_unlock工作了，節(jié)省一些額外的overhead；osq_lock用于確保只有一個等待者參與進來自旋，防止大量的等待者蜂擁而至來獲取互斥鎖；for(;;)自旋過程中調用__mutex_trylock_or_owner來嘗試獲取鎖，獲取到后皆大歡喜，直接返回即可；mutex_spin_on_owner，判斷不滿足自旋等待的條件，那么返回，讓我們進入慢速路徑吧，畢竟不能強求；
3.2.3 slow-path
慢速路徑的主要代碼流程如下：
從
for(;;)部分的流程可以看到，當沒有獲取到鎖時，會調用schedule_preempt_disabled將本身的任務進行切換出去，睡眠等待，這也是它慢的原因了；
3.3 釋放鎖流程分析
釋放鎖的流程相對來說比較簡單，也分為快速路徑與慢速路徑，快速路徑只有在調試的時候打開；
慢速路徑釋放鎖，針對三種不同的
MUTEX_FLAG來進行判斷處理，并最終喚醒等待在該鎖上的任務；
原文作者：LoyenWang
