性能為王，系統(tǒng)的性能提升是每一個(gè)工程師的追求。目前，性能優(yōu)化主要集中在消除系統(tǒng)軟件堆棧中的低效率上或繞過高開銷的系統(tǒng)操作。例如，內(nèi)核旁路通過在用戶空間中移動(dòng)多個(gè)操作來實(shí)現(xiàn)這個(gè)目標(biāo)，還有就是為某些類別的應(yīng)用程序重構(gòu)底層操作系統(tǒng).

在許多領(lǐng)域中，專有化似乎是追求更好性能的答案，集中在應(yīng)用程序和內(nèi)核，甚至是在不同的內(nèi)核子系統(tǒng)之間。特別地，專有化可以構(gòu)建應(yīng)用程序向系統(tǒng)請求某些功能的上下文。雖然，應(yīng)用程序?qū)Ｓ谢蛢?nèi)核繞過了存儲、網(wǎng)絡(luò)化和加速器，但是，內(nèi)核中的并發(fā)控制可能是整體性能的關(guān)鍵。

1. 操作系統(tǒng)的性能：內(nèi)核鎖

內(nèi)核鎖是一種用于控制進(jìn)程訪問共享資源的機(jī)制。在Linux內(nèi)核中，內(nèi)核鎖是通過在進(jìn)程創(chuàng)建時(shí)分配一個(gè)特殊的鎖來實(shí)現(xiàn)的。當(dāng)一個(gè)進(jìn)程需要訪問共享資源時(shí)，內(nèi)核會(huì)檢查該進(jìn)程是否已經(jīng)持有該鎖，如果沒有，則將該進(jìn)程加入到等待鎖定的隊(duì)列中，等待其他進(jìn)程釋放該鎖。

內(nèi)核鎖對于實(shí)現(xiàn)應(yīng)用程序的良好性能和可伸縮性至關(guān)重要.然而，內(nèi)核同步原語通常是不可見的，并且是應(yīng)用程序開發(fā)人員無法觸及的。設(shè)計(jì)鎖定算法并驗(yàn)證它們的正確性已經(jīng)具有挑戰(zhàn)性，而增加硬件的異構(gòu)性使其更加具有挑戰(zhàn)性。開發(fā)人員缺乏對鎖正在操作的環(huán)境的認(rèn)識，如優(yōu)先級倒置和鎖持有人優(yōu)先等問題，本質(zhì)上是缺乏上下文。

能否有一種方法能讓用戶空間的應(yīng)用程序可以調(diào)優(yōu)內(nèi)核中的并發(fā)控制呢？

例如，用戶可以對持有一組鎖的特定任務(wù)或系統(tǒng)調(diào)用進(jìn)行優(yōu)先級排序。用戶可以強(qiáng)制執(zhí)行特定于硬件的策略，例如非對稱多處理感知鎖定，并且可以根據(jù)給定的工作負(fù)載決定對讀寫的優(yōu)先級。如果允許開發(fā)人員調(diào)優(yōu)內(nèi)核中的各種鎖，更改它們的參數(shù)和行為，甚至在不同的鎖實(shí)現(xiàn)之間進(jìn)行更改，或許可以進(jìn)一步提升系統(tǒng)的性能。

軟件堆棧專有化是提高應(yīng)用程序性能的新方式，提出為了性能目的將代碼推送到內(nèi)核，通過避免增加內(nèi)核數(shù)量瓶頸來提高應(yīng)用程序的可伸縮性。隨著時(shí)間的推移，即使是像Linux這樣的宏內(nèi)核，也已經(jīng)開始允許用戶空間的應(yīng)用程序自定義內(nèi)核行為。開發(fā)人員可以使用eBPF為跟蹤、安全甚至性能目的定制內(nèi)核。

除了eBPF，Linux的開發(fā)人員也在使用io_uring，一個(gè)在用戶空間和內(nèi)核之間的共享內(nèi)存環(huán)緩沖區(qū)，以加快異步IO操作。此外，如今的應(yīng)用程序可以完全在用戶空間中處理按需分頁。

應(yīng)用程序來控制底層內(nèi)核的并發(fā)機(jī)制，這為鎖的設(shè)計(jì)者和應(yīng)用程序開發(fā)人員提供了各種機(jī)會(huì)。

2. 鎖：過去、現(xiàn)在和未來

硬件是決定鎖的可伸縮性的主要因素，從而影響應(yīng)用程序的可伸縮性。例如，對于基于隊(duì)列的鎖，當(dāng)多個(gè)線程同時(shí)獲得鎖時(shí)，可以減少過多流量。同時(shí)，分層鎖使用批處理來使高速緩存線抖動(dòng)的問題最小化。

SHFLLock提出了一種通過解耦鎖策略與實(shí)現(xiàn)來設(shè)計(jì)鎖算法的新思想，實(shí)現(xiàn)較少的內(nèi)核內(nèi)存開銷和性能下降。主要引入了一個(gè)shuffler程序的概念，它重新排序隊(duì)列或修改等待線程的狀態(tài)。盡管ShflLocks提供了一種強(qiáng)制執(zhí)行策略的方法，但還可以試圖將重點(diǎn)放在一組簡單的鎖獲取/發(fā)布API上的通用策略上。為了迎合應(yīng)用的需求，通過分析影響給定工作負(fù)載的特定內(nèi)核鎖，應(yīng)用程序的開發(fā)人員應(yīng)該以受控和安全的方式定義他們的策略，并動(dòng)態(tài)地更新鎖獲取策略，使用shuffler執(zhí)行政策。

3 典型場景：調(diào)度等待鎖的線程

等待鎖的線程可以以兩種不同的方式進(jìn)行調(diào)度：基于鎖的獲取順序的獲取感知調(diào)度，以及基于線程在關(guān)鍵段內(nèi)花費(fèi)的時(shí)間的占用感知調(diào)度。

3.1采集感知的調(diào)度

鎖開關(guān)，使開發(fā)人員能夠在各種鎖的算法之間進(jìn)行切換。有三種突出的情況：

1. 從中性的讀寫器鎖設(shè)計(jì)切換到每個(gè)cpu或基于numa的閱讀器設(shè)計(jì)，以滿足讀密集型工作負(fù)載.例如，頁面錯(cuò)誤和枚舉一個(gè)目錄中的文件.另一種情況是從中立的讀寫鎖切換到純粹的寫鎖；一個(gè)例子是在一個(gè)目錄中創(chuàng)建多個(gè)文件。
2. 從基于Numa的鎖設(shè)計(jì)切換到具有Numa感知的組合方法，其中鎖持有人代表等待線程執(zhí)行操作.這種方法具有更好的性能，因?yàn)樗辽賱h除了一個(gè)高速緩存的傳輸。
3. 之間的開關(guān)阻塞和非阻塞鎖，反之亦然，例如，通過關(guān)閉SHFLLock的shuffler功能的停止/喚醒策略，將阻塞讀切換為非阻塞讀寫鎖（rwlock）。

這種方法帶來了兩個(gè)好處：首先，開發(fā)人員可以刪除臨時(shí)同步，例如使用非阻塞鎖和使用等待事件實(shí)現(xiàn)停止/喚醒策略，這在Btrfs文件系統(tǒng)中是常用的。第二，允許開發(fā)人員通過動(dòng)態(tài)地多路復(fù)用多個(gè)策略來統(tǒng)一鎖的設(shè)計(jì)。

3.1.1 鎖繼承

一個(gè)進(jìn)程可能會(huì)獲取多個(gè)鎖來執(zhí)行一個(gè)操作。例如，Linux中的一個(gè)進(jìn)程最多可以獲得12個(gè)鎖（例如，重命名操作），或者平均獲得4個(gè)鎖來執(zhí)行內(nèi)存或文件元數(shù)據(jù)管理操作。

不幸的是，這種鎖的模式引發(fā)了基于隊(duì)列的鎖問題，一些線程必須等待更長的時(shí)間才能獲得頂級鎖，這是由另一個(gè)線程等待另一個(gè)鎖。例如，假設(shè)線程t1想要獲得兩個(gè)鎖，L1，然后L2作為一個(gè)操作，而t2只想收回L1的操作。由于這些鎖定協(xié)議是基于fifo的，所以t1可能在隊(duì)列的最后獲得L2，而t2正在等待獲得L1。開發(fā)人員可以為內(nèi)核提供更多的上下文：要么是t1獲取所有鎖在一起，或t1聲明它已經(jīng)持有的鎖，可以給它一個(gè)更高的優(yōu)先級來獲得下一個(gè)鎖L2。

應(yīng)用程序可能希望優(yōu)先考慮系統(tǒng)調(diào)用路徑或一組任務(wù)，以獲得更好的性能。開發(fā)人員可以通過對任務(wù)優(yōu)先級上下文進(jìn)行編碼，并將此信息傳遞給受影響的鎖。對于系統(tǒng)調(diào)用，開發(fā)人員可以共享關(guān)于一組鎖和關(guān)鍵路徑上的優(yōu)先級線程的信息。然后，shuffler程序?qū)?yōu)先考慮這些線程，而不是等待指定應(yīng)用程序的鎖的其他線程。

3.1.2 公開調(diào)度程序的語義

通常，超額訂閱硬件資源，如CPU或內(nèi)存，可以得到更好的資源利用率，對于兩個(gè)用戶空間運(yùn)行時(shí)系統(tǒng)，以及虛擬機(jī)。雖然超額訂閱提高了硬件利用率，但它也引入了雙重調(diào)度問題。系統(tǒng)監(jiān)控程序可以安排一個(gè)vCPU作為鎖持有人或VM中的下一個(gè)鎖服務(wù)。管理程序可以將vCPU調(diào)度信息公開給shuffler程序，以根據(jù)服務(wù)的運(yùn)行時(shí)間配額對其進(jìn)行優(yōu)先排序。

3.1.3 可適應(yīng)的停止/喚醒策略

所有的封閉鎖都遵循旋轉(zhuǎn)后停車的策略，即它們在旋轉(zhuǎn)一段時(shí)間后自己停車。這個(gè)旋轉(zhuǎn)時(shí)間主要是特別的，也就是說，服務(wù)員要么根據(jù)時(shí)間配額旋轉(zhuǎn)一定時(shí)間，要么在沒有任務(wù)要執(zhí)行的情況下繼續(xù)旋轉(zhuǎn)?，F(xiàn)在，應(yīng)用程序開發(fā)人員可以在分析關(guān)鍵部分的長度后公開時(shí)間上下文，以最小化能源消耗和喚醒信息，以按時(shí)安排下一個(gè)服務(wù)員，以最小化喚醒延遲。此外，開發(fā)人員可以進(jìn)一步對睡眠信息進(jìn)行編碼，在鎖定之前喚醒服務(wù)員，以減少長時(shí)間的喚醒延遲。該方法也適用于副虛擬化的自旋鎖以避免護(hù)航效應(yīng).

3.2 占用調(diào)度

3.2.1 優(yōu)先級繼承

當(dāng)持有鎖的低優(yōu)先級任務(wù)被正常優(yōu)先級任務(wù)調(diào)度出去，等待同一鎖時(shí)，就會(huì)發(fā)生優(yōu)先級反轉(zhuǎn)。在Linux IO堆棧中說明了這個(gè)問題：當(dāng)調(diào)度IO請求時(shí)，一個(gè)想要獲得一個(gè)鎖的正常任務(wù)可以調(diào)度一個(gè)持有相同鎖的較低優(yōu)先級的后臺任務(wù)。鎖的調(diào)度即后臺任務(wù)，導(dǎo)致IO性能下降。

3.2.2 任務(wù)公平的合作調(diào)度

這引入了一類新的問題，稱為調(diào)度器顛覆問題，其中兩個(gè)任務(wù)在不同的時(shí)間內(nèi)獲得鎖。保持時(shí)間較長的任務(wù)顛覆了操作系統(tǒng)的調(diào)度目標(biāo)。操作系統(tǒng)通過跟蹤關(guān)鍵區(qū)域大小和懲罰長時(shí)間的任務(wù)來解決這個(gè)問題。盡管這個(gè)解決方案解決了這個(gè)問題，但即使對于可能不會(huì)從中受益的應(yīng)用程序，它也加強(qiáng)了調(diào)度的公平性。

3.2.3 在非對稱多核處理器（AMP）機(jī)器上的任務(wù)公平鎖定

在一個(gè)處理器中具有不同的計(jì)算能力核心，這種體系結(jié)構(gòu)上使用的基本鎖原語存在一種調(diào)度程序顛覆問題，應(yīng)用程序吞吐量可能由于較弱內(nèi)核的計(jì)算能力較慢而崩潰。為了實(shí)現(xiàn)更快的進(jìn)程，開發(fā)人員可以在更快的核心上分配關(guān)鍵鎖，也可以重新排序等待獲得鎖的線程隊(duì)列，以改進(jìn)整個(gè)鎖。

3.2.4 實(shí)時(shí)調(diào)度

與實(shí)時(shí)系統(tǒng)中的調(diào)度類似，應(yīng)用程序開發(fā)人員可以創(chuàng)建鎖策略，總是調(diào)度線程以保證SLO。在這里，鎖可以設(shè)計(jì)為一個(gè)基于階段公平的算法.這種方法還允許消除抖動(dòng)，并保證延遲關(guān)鍵應(yīng)用程序的尾部延遲的上限。

3.3 動(dòng)態(tài)鎖的分析

應(yīng)用程序開發(fā)人員可以配置文件有關(guān)任何內(nèi)核鎖的信息。選擇要配置的鎖使開發(fā)人員能夠在不同的粒度級別上配置。例如，它們可以配置在內(nèi)核中運(yùn)行的所有自旋鎖、特定函數(shù)中的鎖、代碼路徑或名稱空間，甚至是單個(gè)鎖實(shí)例。這種方法使應(yīng)用程序開發(fā)人員受益，能夠通過只分析感興趣的部分來更好地理解底層同步。

開發(fā)者也可以對性能合約進(jìn)行推理，基于各種shuffler策略甚至是一組策略提供的某些擔(dān)保，這些性能合約會(huì)影響應(yīng)用程序的性能。

4.一種內(nèi)核鎖的優(yōu)化框架

重新定義內(nèi)核鎖所使用的決策和行為，并公開為API，用戶定義的代碼替換這些公開的API，用戶可以根據(jù)自己的需要定制鎖定功能。例如，在加入等待隊(duì)列之前是否要旋轉(zhuǎn)可以是一個(gè)API，這樣用戶就可以做出決定。用戶首先編寫自己的代碼來根據(jù)用例修改內(nèi)核中的鎖協(xié)議，然后操作系統(tǒng)替換內(nèi)核內(nèi)部帶注釋的鎖函數(shù)，流程示意如下：

用戶指定了一個(gè)鎖策略（1），eBPF驗(yàn)證者在編譯后驗(yàn)證它，同時(shí)考慮到eBPF限制和互斥安全屬性（2,3）。然后，驗(yàn)證者將通知用戶驗(yàn)證結(jié)果(4)，如果成功，則將編譯后的eBPF代碼存儲在文件系統(tǒng)（5）中。最后，使用現(xiàn)場補(bǔ)丁模塊替換指定鎖（6）的注釋函數(shù)。

4.1 API

各種API支持了鎖策略的靈活實(shí)現(xiàn)，同時(shí)保障了安全，操作系統(tǒng)底層實(shí)現(xiàn)依賴于eBPF來修改內(nèi)核鎖。通過使用eBPF和鎖API，為內(nèi)核中的一組鎖實(shí)例實(shí)現(xiàn)了所需的策略。一個(gè)用戶可以編碼多個(gè)策略，它被轉(zhuǎn)換為原生代碼，并由eBPF驗(yàn)證者進(jìn)行安全檢查。驗(yàn)證器在將本機(jī)代碼加載到內(nèi)核中之前執(zhí)行符號執(zhí)行，例如內(nèi)存訪問控制或只允許白名單的輔助函數(shù)。

4.2 安全性

除了eBPF驗(yàn)證器，ShflLocks有單獨(dú)的鎖獲取階段和一個(gè)重新排序等待隊(duì)列的階段。用戶依賴API函數(shù)來比較當(dāng)前節(jié)點(diǎn)和洗牌器節(jié)點(diǎn)與是否對當(dāng)前節(jié)點(diǎn)進(jìn)行重新排序，也可以設(shè)計(jì)調(diào)度器協(xié)同鎖，通過對臨界切片長度較小的節(jié)點(diǎn)進(jìn)行優(yōu)先級排序，從而降低對節(jié)點(diǎn)的優(yōu)先級。

雖然不正確的用戶實(shí)現(xiàn)可能會(huì)破壞公平性保證的策略，但是可以在運(yùn)行時(shí)檢查并確保互斥屬性。此外，內(nèi)核沒有任何死鎖問題，API不修改鎖行為，只返回移動(dòng)節(jié)點(diǎn)的決定。開發(fā)人員能夠通過實(shí)現(xiàn)每個(gè)調(diào)用所需的行為，以細(xì)粒度的方式配置他們的鎖。雖然不會(huì)改變鎖函數(shù)的行為，但重量配置分析策略可能會(huì)增加關(guān)鍵部分的長度，從而導(dǎo)致性能下降。

此外，eBPF公開了鏈接多個(gè)eBPF程序的功能，用戶可以使用這些程序來編寫策略。最后，我們還依賴于現(xiàn)場調(diào)度的數(shù)據(jù)結(jié)構(gòu)，用于修改鎖定原語所使用的數(shù)據(jù)結(jié)構(gòu)。例如，可以擴(kuò)展基于隊(duì)列的鎖節(jié)點(diǎn)數(shù)據(jù)結(jié)構(gòu)，并將額外的信息用于為特定的用例編碼信息。在不執(zhí)行用戶空間代碼的最壞情況下，動(dòng)態(tài)修改鎖算法可能會(huì)產(chǎn)生高達(dá)20%的開銷。

4.3 組合策略

通過調(diào)優(yōu)內(nèi)核并發(fā)控制，應(yīng)用程序可以對軟件堆棧有更多的控制。應(yīng)用程序開發(fā)人員提供了一組需要應(yīng)用鎖的策略。組合多個(gè)策略是一項(xiàng)困難的任務(wù)，特別是當(dāng)某些策略可能發(fā)生沖突的時(shí)候。通過利用程序合成來自動(dòng)化這個(gè)過程，或許可以將安全屬性完全移動(dòng)到用戶空間中的驗(yàn)證，也可以提供一種安全的方式來組成相互沖突的策略。

用戶不能添加太多的策略，因?yàn)樗鼈兊膱?zhí)行可能會(huì)落在關(guān)鍵路徑上。允許一個(gè)特權(quán)用戶修改內(nèi)核鎖，該模型僅適用于使用整個(gè)系統(tǒng)的一個(gè)用戶。然而，為了處理云環(huán)境中的多租戶，需要一個(gè)感知租戶的策略編寫器，它不違反用戶之間的隔離。在用戶空間中綜合策略以避免此類沖突，并在鎖算法中添加運(yùn)行時(shí)檢查，這些檢查只在策略可以影響特定行為時(shí)使用。

除了鎖之外，還有其他在內(nèi)核中大量使用的同步機(jī)制，如RCU, seqlocks ，等待事件等擴(kuò)展，將進(jìn)一步允許應(yīng)用程序提高其性能。也就是說，用戶空間應(yīng)用程序還有它們自己的、本質(zhì)上是通用的鎖。相比之下，現(xiàn)有的技術(shù)，如庫插入，只允許在應(yīng)用程序開始執(zhí)行時(shí)對不同的鎖實(shí)現(xiàn)進(jìn)行一次更改。

5.小結(jié)

內(nèi)核鎖的同步原語對一些應(yīng)用程序的性能和可伸縮性有巨大的影響，然而，控制內(nèi)核同步原語對于應(yīng)用程序開發(fā)人員來說是無法實(shí)現(xiàn)的。如果使用上下文并發(fā)控制，它允許用戶空間應(yīng)用程序微調(diào)內(nèi)核并發(fā)原語。這是一種思考軟件堆棧專有化的方法，在一定程度上加速了內(nèi)核同步領(lǐng)域的創(chuàng)新。

【參考資料】

• https://git.kernel.org/pub/scm/linux/kernel/git/torvalds/linux. git/tree/include/uapi/linux/bpf.h?h=v5.4.
• https://www.kernel.org/doc/html/ latest/livepatch/shadow-vars.html.
• https://github.com/ antonblanchard/will-it-scale.
• https://doi.org/10.1109/ECRTS.2009.14
• https://www.kernel.org/doc/Documentation/locking/mutex-design.txt.
• Kernel Live Patching，https://lwn.net/Articles/619390/
• lockstat: documentation. https://lwn.net/Articles/252835/
• http://www.brendangregg.com/blog/2019-12-02/ bpf-a-new-type-of-software.html.