性能為王，系統的性能提升是每一個工程師的追求。目前，性能優化主要集中在消除系統軟件堆棧中的低效率上或繞過高開銷的系統操作。例如，內核旁路通過在用戶空間中移動多個操作來實現這個目標，還有就是為某些類別的應用程序重構底層操作系統.
在許多領域中，專有化似乎是追求更好性能的答案，集中在應用程序和內核，甚至是在不同的內核子系統之間。特別地，專有化可以構建應用程序向系統請求某些功能的上下文。雖然，應用程序專有化和內核繞過了存儲、網絡化和加速器，但是，內核中的并發控制可能是整體性能的關鍵。
1. 操作系統的性能：內核鎖
內核鎖是一種用于控制進程訪問共享資源的機制。在Linux內核中，內核鎖是通過在進程創建時分配一個特殊的鎖來實現的。當一個進程需要訪問共享資源時，內核會檢查該進程是否已經持有該鎖，如果沒有，則將該進程加入到等待鎖定的隊列中，等待其他進程釋放該鎖。
內核鎖對于實現應用程序的良好性能和可伸縮性至關重要.然而，內核同步原語通常是不可見的，并且是應用程序開發人員無法觸及的。設計鎖定算法并驗證它們的正確性已經具有挑戰性，而增加硬件的異構性使其更加具有挑戰性。開發人員缺乏對鎖正在操作的環境的認識，如優先級倒置和鎖持有人優先等問題，本質上是缺乏上下文。
能否有一種方法能讓用戶空間的應用程序可以調優內核中的并發控制呢？
例如，用戶可以對持有一組鎖的特定任務或系統調用進行優先級排序。用戶可以強制執行特定于硬件的策略，例如非對稱多處理感知鎖定，并且可以根據給定的工作負載決定對讀寫的優先級。如果允許開發人員調優內核中的各種鎖，更改它們的參數和行為，甚至在不同的鎖實現之間進行更改，或許可以進一步提升系統的性能。
軟件堆棧專有化是提高應用程序性能的新方式，提出為了性能目的將代碼推送到內核，通過避免增加內核數量瓶頸來提高應用程序的可伸縮性。隨著時間的推移，即使是像Linux這樣的宏內核，也已經開始允許用戶空間的應用程序自定義內核行為。開發人員可以使用eBPF為跟蹤、安全甚至性能目的定制內核。
除了eBPF，Linux的開發人員也在使用io_uring，一個在用戶空間和內核之間的共享內存環緩沖區，以加快異步IO操作。此外，如今的應用程序可以完全在用戶空間中處理按需分頁。
應用程序來控制底層內核的并發機制，這為鎖的設計者和應用程序開發人員提供了各種機會。
2. 鎖：過去、現在和未來
硬件是決定鎖的可伸縮性的主要因素，從而影響應用程序的可伸縮性。例如，對于基于隊列的鎖，當多個線程同時獲得鎖時，可以減少過多流量。同時，分層鎖使用批處理來使高速緩存線抖動的問題最小化。
SHFLLock提出了一種通過解耦鎖策略與實現來設計鎖算法的新思想，實現較少的內核內存開銷和性能下降。主要引入了一個shuffler程序的概念，它重新排序隊列或修改等待線程的狀態。盡管ShflLocks提供了一種強制執行策略的方法，但還可以試圖將重點放在一組簡單的鎖獲取/發布API上的通用策略上。為了迎合應用的需求，通過分析影響給定工作負載的特定內核鎖，應用程序的開發人員應該以受控和安全的方式定義他們的策略，并動態地更新鎖獲取策略，使用shuffler執行政策。
3 典型場景：調度等待鎖的線程
等待鎖的線程可以以兩種不同的方式進行調度：基于鎖的獲取順序的獲取感知調度，以及基于線程在關鍵段內花費的時間的占用感知調度。
3.1采集感知的調度
鎖開關，使開發人員能夠在各種鎖的算法之間進行切換。有三種突出的情況：
- 從中性的讀寫器鎖設計切換到每個cpu或基于numa的閱讀器設計，以滿足讀密集型工作負載.例如，頁面錯誤和枚舉一個目錄中的文件.另一種情況是從中立的讀寫鎖切換到純粹的寫鎖；一個例子是在一個目錄中創建多個文件。
- 從基于Numa的鎖設計切換到具有Numa感知的組合方法，其中鎖持有人代表等待線程執行操作.這種方法具有更好的性能，因為它至少刪除了一個高速緩存的傳輸。
- 之間的開關阻塞和非阻塞鎖，反之亦然，例如，通過關閉SHFLLock的shuffler功能的停止/喚醒策略，將阻塞讀切換為非阻塞讀寫鎖（rwlock）。
這種方法帶來了兩個好處：首先，開發人員可以刪除臨時同步，例如使用非阻塞鎖和使用等待事件實現停止/喚醒策略，這在Btrfs文件系統中是常用的。第二，允許開發人員通過動態地多路復用多個策略來統一鎖的設計。
3.1.1 鎖繼承
一個進程可能會獲取多個鎖來執行一個操作。例如，Linux中的一個進程最多可以獲得12個鎖（例如，重命名操作），或者平均獲得4個鎖來執行內存或文件元數據管理操作。
不幸的是，這種鎖的模式引發了基于隊列的鎖問題，一些線程必須等待更長的時間才能獲得頂級鎖，這是由另一個線程等待另一個鎖。例如，假設線程t1想要獲得兩個鎖，L1，然后L2作為一個操作，而t2只想收回L1的操作。由于這些鎖定協議是基于fifo的，所以t1可能在隊列的最后獲得L2，而t2正在等待獲得L1。開發人員可以為內核提供更多的上下文：要么是t1獲取所有鎖在一起，或t1聲明它已經持有的鎖，可以給它一個更高的優先級來獲得下一個鎖L2。
應用程序可能希望優先考慮系統調用路徑或一組任務，以獲得更好的性能。開發人員可以通過對任務優先級上下文進行編碼，并將此信息傳遞給受影響的鎖。對于系統調用，開發人員可以共享關于一組鎖和關鍵路徑上的優先級線程的信息。然后，shuffler程序將優先考慮這些線程，而不是等待指定應用程序的鎖的其他線程。
3.1.2 公開調度程序的語義
通常，超額訂閱硬件資源，如CPU或內存，可以得到更好的資源利用率，對于兩個用戶空間運行時系統，以及虛擬機。雖然超額訂閱提高了硬件利用率，但它也引入了雙重調度問題。系統監控程序可以安排一個vCPU作為鎖持有人或VM中的下一個鎖服務。管理程序可以將vCPU調度信息公開給shuffler程序，以根據服務的運行時間配額對其進行優先排序。
3.1.3 可適應的停止/喚醒策略
所有的封閉鎖都遵循旋轉后停車的策略，即它們在旋轉一段時間后自己停車。這個旋轉時間主要是特別的，也就是說，服務員要么根據時間配額旋轉一定時間，要么在沒有任務要執行的情況下繼續旋轉。現在，應用程序開發人員可以在分析關鍵部分的長度后公開時間上下文，以最小化能源消耗和喚醒信息，以按時安排下一個服務員，以最小化喚醒延遲。此外，開發人員可以進一步對睡眠信息進行編碼，在鎖定之前喚醒服務員，以減少長時間的喚醒延遲。該方法也適用于副虛擬化的自旋鎖以避免護航效應.
3.2 占用調度
3.2.1 優先級繼承
當持有鎖的低優先級任務被正常優先級任務調度出去，等待同一鎖時，就會發生優先級反轉。在Linux IO堆棧中說明了這個問題：當調度IO請求時，一個想要獲得一個鎖的正常任務可以調度一個持有相同鎖的較低優先級的后臺任務。鎖的調度即后臺任務，導致IO性能下降。
3.2.2 任務公平的合作調度
這引入了一類新的問題，稱為調度器顛覆問題，其中兩個任務在不同的時間內獲得鎖。保持時間較長的任務顛覆了操作系統的調度目標。操作系統通過跟蹤關鍵區域大小和懲罰長時間的任務來解決這個問題。盡管這個解決方案解決了這個問題，但即使對于可能不會從中受益的應用程序，它也加強了調度的公平性。
3.2.3 在非對稱多核處理器（AMP）機器上的任務公平鎖定
在一個處理器中具有不同的計算能力核心，這種體系結構上使用的基本鎖原語存在一種調度程序顛覆問題，應用程序吞吐量可能由于較弱內核的計算能力較慢而崩潰。為了實現更快的進程，開發人員可以在更快的核心上分配關鍵鎖，也可以重新排序等待獲得鎖的線程隊列，以改進整個鎖。
3.2.4 實時調度
與實時系統中的調度類似，應用程序開發人員可以創建鎖策略，總是調度線程以保證SLO。在這里，鎖可以設計為一個基于階段公平的算法.這種方法還允許消除抖動，并保證延遲關鍵應用程序的尾部延遲的上限。
3.3 動態鎖的分析
應用程序開發人員可以配置文件有關任何內核鎖的信息。選擇要配置的鎖使開發人員能夠在不同的粒度級別上配置。例如，它們可以配置在內核中運行的所有自旋鎖、特定函數中的鎖、代碼路徑或名稱空間，甚至是單個鎖實例。這種方法使應用程序開發人員受益，能夠通過只分析感興趣的部分來更好地理解底層同步。
開發者也可以對性能合約進行推理，基于各種shuffler策略甚至是一組策略提供的某些擔保，這些性能合約會影響應用程序的性能。
4.一種內核鎖的優化框架
重新定義內核鎖所使用的決策和行為，并公開為API，用戶定義的代碼替換這些公開的API，用戶可以根據自己的需要定制鎖定功能。例如，在加入等待隊列之前是否要旋轉可以是一個API，這樣用戶就可以做出決定。用戶首先編寫自己的代碼來根據用例修改內核中的鎖協議，然后操作系統替換內核內部帶注釋的鎖函數，流程示意如下：
用戶指定了一個鎖策略（1），eBPF驗證者在編譯后驗證它，同時考慮到eBPF限制和互斥安全屬性（2,3）。然后，驗證者將通知用戶驗證結果(4)，如果成功，則將編譯后的eBPF代碼存儲在文件系統（5）中。最后，使用現場補丁模塊替換指定鎖（6）的注釋函數。
4.1 API
各種API支持了鎖策略的靈活實現，同時保障了安全，操作系統底層實現依賴于eBPF來修改內核鎖。通過使用eBPF和鎖API，為內核中的一組鎖實例實現了所需的策略。一個用戶可以編碼多個策略，它被轉換為原生代碼，并由eBPF驗證者進行安全檢查。驗證器在將本機代碼加載到內核中之前執行符號執行，例如內存訪問控制或只允許白名單的輔助函數。
4.2 安全性
除了eBPF驗證器，ShflLocks有單獨的鎖獲取階段和一個重新排序等待隊列的階段。用戶依賴API函數來比較當前節點和洗牌器節點與是否對當前節點進行重新排序，也可以設計調度器協同鎖，通過對臨界切片長度較小的節點進行優先級排序，從而降低對節點的優先級。
雖然不正確的用戶實現可能會破壞公平性保證的策略，但是可以在運行時檢查并確保互斥屬性。此外，內核沒有任何死鎖問題，API不修改鎖行為，只返回移動節點的決定。開發人員能夠通過實現每個調用所需的行為，以細粒度的方式配置他們的鎖。雖然不會改變鎖函數的行為，但重量配置分析策略可能會增加關鍵部分的長度，從而導致性能下降。
此外，eBPF公開了鏈接多個eBPF程序的功能，用戶可以使用這些程序來編寫策略。最后，我們還依賴于現場調度的數據結構，用于修改鎖定原語所使用的數據結構。例如，可以擴展基于隊列的鎖節點數據結構，并將額外的信息用于為特定的用例編碼信息。在不執行用戶空間代碼的最壞情況下，動態修改鎖算法可能會產生高達20%的開銷。
4.3 組合策略
通過調優內核并發控制，應用程序可以對軟件堆棧有更多的控制。應用程序開發人員提供了一組需要應用鎖的策略。組合多個策略是一項困難的任務，特別是當某些策略可能發生沖突的時候。通過利用程序合成來自動化這個過程，或許可以將安全屬性完全移動到用戶空間中的驗證，也可以提供一種安全的方式來組成相互沖突的策略。
用戶不能添加太多的策略，因為它們的執行可能會落在關鍵路徑上。允許一個特權用戶修改內核鎖，該模型僅適用于使用整個系統的一個用戶。然而，為了處理云環境中的多租戶，需要一個感知租戶的策略編寫器，它不違反用戶之間的隔離。在用戶空間中綜合策略以避免此類沖突，并在鎖算法中添加運行時檢查，這些檢查只在策略可以影響特定行為時使用。
除了鎖之外，還有其他在內核中大量使用的同步機制，如RCU, seqlocks ，等待事件等擴展，將進一步允許應用程序提高其性能。也就是說，用戶空間應用程序還有它們自己的、本質上是通用的鎖。相比之下，現有的技術，如庫插入，只允許在應用程序開始執行時對不同的鎖實現進行一次更改。
5.小結
內核鎖的同步原語對一些應用程序的性能和可伸縮性有巨大的影響，然而，控制內核同步原語對于應用程序開發人員來說是無法實現的。如果使用上下文并發控制，它允許用戶空間應用程序微調內核并發原語。這是一種思考軟件堆棧專有化的方法，在一定程度上加速了內核同步領域的創新。
【參考資料】
- 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.
