lockfree

無鎖

lockfree是用標準 C++11 編寫的無鎖定資料結構的集合，適用於從深度嵌入式到 HPC 的所有平台。

什麼是無鎖資料結構？

無鎖資料結構是執行緒和中斷安全的資料結構，可以並發使用，而無需使用互斥機制。它們對於進程間通訊最有用，並且在操作和執行緒數量方面通常比基於鎖的結構更好地擴展。

為什麼要使用lockfree

• 採用標準C++11編寫，相容於所有支援它的平台
• 所有資料結構在各自的用例中都是線程和中斷安全的
• 無動態分配
• 針對高效能進行了最佳化
• 麻省理工學院許可
• 適用於較新 C++ 版本的附加 API

有哪些可用的資料結構？

單生產者單一消費者資料結構

• 佇列 - 最適合單元素操作，速度極快，API 簡單，僅包含 2 個方法。
• 環形緩衝區 - 一種更通用的資料結構，能夠一次處理多個元素，使用標準庫副本，使其能夠非常快速地進行批次操作。
• 二分緩衝區 - 環形緩衝區的一種變體，能夠始終在緩衝區中提供線性空間，從而實現緩衝區內處理。
• 優先權佇列 - 佇列的一種變體，能夠為元素提供不同的優先權，對於訊號、事件和通訊資料包等非常有用。

這些資料結構的效能較高，通常應在只有一個執行緒/中斷推送資料而另一個執行緒/中斷檢索資料時使用。

多生產者多消費者資料結構

• 佇列 - 最適合單元素操作，速度極快，API 簡單，僅包含 2 個方法。
• 優先權佇列 - 佇列的一種變體，能夠為元素提供不同的優先權，對於訊號、事件和通訊資料包等非常有用。

這些資料結構更通用，同時支援多個生產者和消費者，但是與單一生產者單一消費者資料結構相比，它們具有儲存和效能開銷。它們還需要一些低階微控制器可能缺少的原子指令。

如何獲得

取得該庫的方式主要有以下三種：

• 使用 CMake FetchContent()
• 作為 git 子模組
• 從 GitHub 下載版本

配置

lockfree預設對索引使用cacheline對齊來避免FalseSharing現象，避免了cachecoherent系統上cacheline失效帶來的效能損失。這會將索引與LOCKFREE_CACHELINE_LENGTH對齊，預設為64 。

在嵌入式系統上， LOCKFREE_CACHE_COHERENT幾乎應始終設定為false以避免浪費記憶體。

此外，某些系統具有非典型的快取行長度（例如蘋果 M1/M2 CPU 的快取行長度為 128 位元組），在這些情況下應相應地設定LOCKFREE_CACHELINE_LENGTH 。

已知的限制

lockfree中的所有資料結構僅適用於普通類型。

常問問題

為什麼我要在託管電腦上使用它而不是鎖定資料結構？

您希望在託管環境中使用無鎖定資料結構的最大原因是避免與鎖定有關的問題，例如死鎖、優先反轉和不確定性存取延遲。如果使用得當，無鎖資料結構在某些場景下還可以提高效能。

此外， lockfree提供了一種建立應用程式和函式庫的方法，這些應用程式和函式庫可以編譯為在 POSIX 和非 POSIX 環境中工作，而無需#ifdef或多態性。

為什麼在嵌入式系統上使用 RTOS 提供的 IPC 機制？

雖然鎖定在微控制器等嵌入式系統上通常並不昂貴，但 RTOS 種類繁多，並且沒有用於鎖定的標準化 API。事實上，從 8051 到 RISC-V 存在多種架構，這意味著中斷管理方法也沒有標準化。

lockfree提供了一種建立可移植嵌入式程式碼的方法，與鎖定相比，效能成本可以忽略不計，使用lockfree程式碼可以編譯為在任何支援 C++11 的嵌入式平台上運行。此外，程式碼可以輕鬆地在主機上進行測試，而無需進行模擬。

與 C 相比，使用 C++ 為函式庫提供了哪些優勢？

• 類型安全，因為資料結構是類型和大小模板化的
• 實例化更簡單且不易出錯
• 由於編譯時已知大小和僅標頭實現，性能更高
• 封裝，資料緩衝區是類別成員而不是透過指標傳遞

lockfree中資料結構的正式分類是什麼？

lockfree中的所有結構都是有界的、基於陣列且無鎖的，spsc 資料結構也是waitfree和終止安全的。

理論與參考文獻

若想更深入了解無鎖編程，請查看：

• 赫伯·薩特 (Herb Sutter) 的精彩演講系列
• Fedor Pikus 的即時無鎖或死鎖談話系列
• 德米特里·維尤科夫 (Dmitry Vyukov) 的精彩博客