資料整理: jserv
在〈藉由 spinlock 的調整,改善多核處理器建立 TCP 連線效能〉一文,spinlock 被拆解為 percpu 並予以分析,但未涵蓋 spinlock 本身的效能和可擴展能力 (scalability) 議題,本文繼續探討。
本文啟發自 dog250 的文章
開始探討主題前,先說明本文的術語:
cpu0
和 cpu1
一類的寫法;示意如下圖:
出處: Intel® Performance Counter Monitor - A Better Way to Measure CPU Utilization
假設在實驗環境中中央處理器擁有 16 核,其中每個處理器 (processor) 封裝著有 2 個實體核,也就是說,每個處理器具備兩個獨立 (private) cache 的核,佈局如下:
由於系統實作的可擴展能力考量,目前大多數中央處理器架構在 cache coherence 處理機制大致可分以下兩種:
理解這些,特別是理解點對點 unicast 方式的 one by one 處理時延會隨著核數的增加而線性增加為後面的內容埋下了伏筆。
Linux 核心中存在多種 spinlock (自旋鎖) 被大規模使用,最初是 wild spinlock,再來採納 ticket spinlock。
一如 "wild" 在漢語的意思「粗暴、未經馴化」,這種 spinlock 非常簡單,就由一個整數構成:
其上鎖和解鎖操作如下:
然而在這貌似簡單的程式背後,卻猶如野生環境中動物間頻繁廝殺的競爭,為何呢?
根據上面的中央處理器佈局圖,我們可知各處理器核之間的 processor affinity (趨向的程度) 不同,特定中央處理器核的 cache line 更新同步到不同核的 cache line 的時間亦不同,這就意味著等待 spinlock 的中央處理器中哪個核先察覺到 lock->lock
的變化,該核就能優先獲得鎖。
這將大幅損害等鎖者之間的公平性。這就好比一群人不排隊上火車,體格好的乘客總是優先登車一樣。
為了解決這個公平性問題,ticket spinlock 登場,後者相較於 wild spinlock 的設計,新增一個紀錄等鎖期間單調遞增的 ticket 欄位,確保先到者先獲得鎖,從而保證公平性。
以下是 Linux ticket spinlock 的簡化實作程式碼,為了行文便利,以下的程式碼中所有的遞增 (如 i++
) 操作均為 atomic (有如原子般不可切割),避免鎖中鎖。
這段程式碼展現標準的佇列,類似銀行叫號系統,每個辦理業務的抽取一個號碼牌,然後按照號碼的先後,循序進行服務。
若僅是閱讀程式碼,確實沒看到什麼可議之處,但只要深究就會發現潛藏的危機。以下是從 cache 的角度,分析上述 spinlock 的執行過程,搭配下列程式碼來進行實驗:
各步驟如下:
步驟 1: CPU0 申請鎖,持有本地 ticket 到申請者的 cache
步驟 2: 執行鎖定區域指令的同時,其它 CPU 核企圖獲取鎖而自旋
步驟 3:CPU0 釋放鎖
我們可發現,步驟 3 過於複雜。目前許多中央處理器實作偏好用點對點 unicast 的方式來更新 cache line (因為 broadcast 方式對匯流排頻寬有要求,隨著中央處理器核數的增加,實作複雜度會提高,也限制整體擴展能力),因此步驟 3 裡頭更新每個 cache line 是個循序執行的過程,若是 write invalidate 方式,就需要更多的存取指令,這些對於理解 Linux ticket spinlock 的可擴展能力至關重要!
顯然隨著處理器核數的增加,步驟 3 對於 spinlock 請求增加的執行時間會線性增長,最終,當 spinlock 的請求量達到一定規模時,多核中央處理器非但無法提高效能,反而由於 cache line 更新的時間過久,反過來損害效能。
注意,wild spinlock 同樣存在這個問題,wild spinlock 背後的 cache coherence 過程和 ticket spinlock 完全一致,只是 ticket spinlock 嚴格規定誰將下一個獲得鎖,而 wild spinlock 並不能。
我們已定性地描述 Linux ticket spinlock 的實作會有什麼問題,為定量地衡量這種實作會帶來哪些具體的後果,需要簡述 Linux ticket spinlock (此後簡稱 Linux spinlock) 對應到經典的 Markov chain 模型。
為闡釋 Linux spinlock 的具體效能表現和帶來的衝擊,必然要建立一個模型,本模型結合排隊理論,可精確描述和預測 Linux spinlock 行為。
考慮以下圖示:
這是個 Markov chain,其中一共有 即 個狀態,每一個狀態 ,表示系統中有 個中央處理器核正在自旋等待鎖, 表示狀態 轉換到狀態 的頻率,也就是相當於請求鎖的頻率,而 則表示狀態 轉換到狀態 的頻率,也就是相當於釋放鎖的頻率。
簡化起見,我們忽略掉 spinlock 到達的細節,假設在中央處理器單一核上平均每隔 (應是指數分佈,Exponential distribution) 會請求一次 spinlock,因此單一核的請求 spinlock 的頻率 (rate) 即是 (應是 Poisson 分佈,法語的 pois 發音類似英語的 pwa,於是 Poisson 音似漢語「玻頌」,讀音可參考 Wiktionary 上的音訊)。進而推廣到多核中央處理器平台,於是請求 spinlock 的頻率和空閒核的數量成正比。假設現有 核中央處理器系統上已有 k 個核在自旋等鎖,那麼 個核上 spinlock 的到達頻率則是 ,因此,從上圖中的 得到:
註:以上敘述對照參考文獻 Non-scalable locks are dangerous 的 Section 3.2,原文是 rate,剛好是 ,翻成「頻率」較易懂。
現在考慮釋放鎖的過程導致的狀態轉換。
先理解狀態 的意義, 這裡指的是 Service,相應的對應 則表示 Arrival,所謂的服務時間指的是從目前核獲得 spinlock 到該 spinlock 成功轉給下個核的時間區段!這時間區段包括兩個部分,一是執行 lock/unlock 之間程式碼的時間 E
,另一是 unlock 操作中消耗的時間,我們把這部分時間設為 R
,現在的問題就變成根據上述資訊,求出 R 的表達式。
討論中有個假設,即我們設想實驗的平台對 cache coherence 中 update 的管理方式是點對點、循序的 unicast 方式,而非 broadcast 的方式。假設處理一個核的 update 時間為 c
,那麼在 k
個核同時自旋等鎖的條件下,所有的中央處理器核的 cache line 全部更新的時間就是 ,由於 ticket spinlock 具備嚴格順序,而 cache line update 的到達先後卻不可控制,因此下個獲得鎖的核的 cache line 得到更新的時間平均值為 ,即平均在這個時間後,下個核即可成功獲取鎖,從 spin_lock
自旋狀態返回。因此我們可知:
以上關於 和 的表達式非常好理解,可見請求的到達頻率,是 spinlock 的頻率是和空閒核數量的關聯,即不在自旋狀態的核數量成正比,顯然空閒核越多,請求越容易到達,相反,spin_unlock
的頻率,即 ,則是和目前自旋狀態的核數量成反比的,至少是負相關的,因為自旋狀態的核越多,更新這麼多核的 cache line 的時間開銷就越大,這意味著服務頻率 就會越低。
有了上面基本的結論,搭配下面一個穩態 Markov chain 狀態轉換率守恆的基本原則,即可導出模型本身:
假設 P0, P1, P2, …, Pn 是系統處在這 個狀態的機率,顯然 。當系統處在穩態時,下方式子成立:
這是一個遞推的開始,我們可求出 關於 的表達式,然後模型裡的參數就可以去用實際值填充。最終透過上面的三個式子推導出來的公式為:
有了這個式子,我們便可求出任意時刻系統中處在自旋等鎖狀態的 CPU 總量:
模型最終在於解釋歷史紀錄和預測未來表現,在上面的基礎上,我們導出一個加速比的概念,即在 個 CPU 的系統中爭搶特定的 spinlock,CPU 總量 中有多少 CPU 未處在自旋等鎖的狀態。顯然,它的值為:
隨著 的增加,S 也增加,這意味著增加中央處理器核數量確實緩解 spinlock 帶來的序列化 (serial) 問題,但是不幸的是,情況並非如此。該模型顯示出的 曲線顯示出當總核數 增加到一定程度,加速比會斷崖跌落 (CPU 一多,one by one 的 cache line 操作太重太耗時),這意味著在達到某種條件的情況下,增加核數反而會損害系統效能。
除了影響擴展能力,cache line 的操作超出預料有著巨大影響!
再看 的表達式:
這個式子是限制 spinlock 擴展能力的根源。注意這裡的 ,它對 spinlock 整體擴展能力受限的程度的影響至關重要!我們進一步可將式子抽象為:
然後我們來看一下
曲線的走勢:
回到我們的模型, 越大,cache coherence 時間線性增長的影響就越不明顯,只有在 比較小時,我們才會深受 spinlock 擴展能力受限之害。然而 spinlock 的應用場合不就是 critical section 範圍很小之際嗎?
假設我們的 critical section 範圍確實很小,那麼
和 之間就近似反比關係,如此事態就嚴重多。它的根源在於 cache coherence 的時間是 的而不是常數級 ,因此我們也就有了解決問題的方向。下一節詳述。
問題已經很明確,如何迴避顯然已至關重要。
既然問題出在共用變數上自旋導致的 cache coherence 開銷過大,那改成在私有變數上自旋即可,這顯然是一個 的操作,替掉之前擴展能力有限的 操作即可。
為了做到這一點,需要重新設計 spinlock 的資料結構。本節所描述的新的 spinlock 正是 MCS spinlock,可參照 MCS locks and qspinlocks 一文。
讓我們從程式碼的角度來看為何 MCS spinlock 可解決 cache coherence 導致擴展能力受限的問題。
mcs spinlock 在 Linux 的實作在 kernel/locking/mcs_spinlock.h
檔案,不過直到 4.14 版,Linux 並沒有哪個子系統採用這個新的 spinlock,不管怎樣,既然程式碼在手,我們便可自行運用。
和 ticket spinlock 的描述一致:
可見其特點在於在自旋變數納入佇列實體本身。在 mcs spinlock 中,一個 mcs_spinlock 結構體的實例 (instance) 就是個佇列實體,它擁有自己的自旋變數 locked
,即它只需要不斷查驗自身的 locked
變數即可。
如你所見,mcs_spin_unlock 操作僅操作 next 的 locked
欄位,後者屬於在某個 CPU 上自旋等待的 mcs spinlock 物件,不會觸發全域的 cache coherence 刷新!
上述的 mcs spinlock 實作之所以可解決因 cache coherence 而導致的開銷隨著處理器核數的增加線性增加的問題,就是因為一個簡單的動作,即傳球代替搶球。 ticket spinlock 的問題在於,既然已知誰是下一個持有鎖的等待者,為什麼不直接將控制權交給它呢?為什麼還要有一個全域盲搶的動作呢?
從前述程式碼列表中,也許你已發現 Linux 的 MCS spinlock 的實作議題:它的 API 改變,這意味著你無法對核心既有 ticket spinlock 進行無縫轉換。我們期望形如下方的函式:
由於同個中央處理器核同時僅能等待一個 spinlock,這件事簡單,可如下實作:
是不是更清楚?至此完成 spinlock 的討論。
針對 spinlock 改進策略的另一種體現,由阿里巴巴集團提交: aliworkqueue: Adaptive lock integration on multi-core platform
Wire-latency(RC delay) dominate modern computer performance, conventional serialized works cause cache line ping-pong seriously, the process spend lots of time and power to complete.specially on multi-core platform.
However if the serialized works are sent to one core and executed ONLY when contention happens, that can save much time and power, because all shared data are located in private cache of one core.
We call the mechanism as Adaptive Lock Integration.
(ali workqueue)
參照解說: 介绍 aliworkqueue
Aliworkqueue 除了考慮到 spinlock 本身加鎖解鎖對 cache coherence 的影響,還考慮 spinlock 保護的 critical section 操作的共享資料讀寫對 cache coherence 的影響,如此一來,本文上述的 Markov chain 模型就要進行修訂,因為 critical section 的操作時間不再視作常數 ,而它也要作為一個和中央處理器核數相關的量參與到模型的構建中。