xenium

塞尼姆

xenium 是一個僅包含頭檔的函式庫，提供並發資料結構和記憶體回收演算法的集合。資料結構被參數化，以便它們可以與各種回收方案一起使用（類似於 STL 允許自訂分配器的方式）。

• 僅標頭
• 高度可自訂
• 無需初始化程式碼
• 支援動態執行緒數（無固定編譯時規範）

該文件提供了更多詳細資訊。

這個專案是基於我之前在 https://github.com/mpoeter/emr 的工作

使用範例

# include < xenium/ramalhete_queue.hpp >
# include < xenium/reclamation/epoch_based.hpp >

struct msg { ... };

xenium::ramalhete_queue<
  std::unique_ptr<msg>,
  xenium::policy::reclaimer<xenium::reclamation::epoch_based<>>,
  xenium::policy::entries_per_node< 2048 >
> queue;

queue.push(std::make_unique<msg>());

std::unique_ptr<msg> data;
if (queue.try_pop(data)) {
    // do something with data
}

資料結構

目前提供的資料結構數量相當小，因為到目前為止的重點是回收方案。然而，計劃在不久的將來添加更多的資料結構。

• michael_scott_queue - 由 Michael 和 Scott [MS96] 提出的無界無鎖多生產者/多消費者隊列。
• ramalhete_queue - Ramalhete [Ram16] 提出的快速無界無鎖多生產者/多消費者佇列。
• vyukov_bounded_queue - 基於 Vyukov [Vyu10] 提出的版本的有界多生產者/多消費者 FIFO 佇列。
• kirsch_kfifo_queue - Kirsch 等人提出的無邊界多生產者/多消費者 k-FIFO 佇列。 [KLP13]。
• kirsch_bounded_kfifo_queue - Kirsch 等人提出的有界多生產者/多消費者 k-FIFO 佇列。 [KLP13]。
• nikolaev_queue - Nikolaev [Nik19] 提出的無界多生產者/多消費者隊列。
• nikolaev_bounded_queue - Nikolaev [Nik19] 提出的有界多生產者/多消費者隊列。
• harris_michael_list_based_set - 包含一組排序的唯一物件的無鎖容器。此資料結構基於 Michael [Mic02] 提出的解決方案，該解決方案以 Harris [Har01] 的原始提案為基礎。
• harris_michael_hash_map - 基於 Michael [Mic02] 提出的解決方案的無鎖哈希映射，該解決方案建立在 Harris [Har01] 的原始提案的基礎上。
• chase_work_stealing_deque - 基於 Chase 和 Lev [CL05] 提案的工作竊取雙端佇列。
• vyukov_hash_map - 使用細粒度鎖定進行更新操作的並發哈希映射。該實現很大程度上受到 Vyukov [Vyu08] 提出的版本的啟發。
• left_right - Ramalhete 和 Correia [RC15] 提出的 LeftRight 演算法的通用實作。
• seqlock - 序列鎖定（通常也稱為「順序鎖」）的實作。

填海計劃

回收方案的實作是基於 Robison [Rob13] 提出的介面的改編版本。

實施以下復墾計畫：

• lock_free_ref_count [Val95，MS95]
• hazard_pointer [Mic04]
• hazard_eras [RC17]
• quiescent_state_based
• generic_epoch_based - 這是一個基於通用紀元的回收器，可以透過多種方式進行設定。為了簡單起見，為對應的配置預先定義了以下別名。
  • epoch_based [Fra04]
  • new_epoch_based [HMBW07]
  • debra [Bro15]
• stamp_it [PT18a，PT18b]

大樓

xenium 是一個僅包含頭檔的函式庫，因此為了使用它，將 xenium 資料夾包含在包含目錄清單中就足夠了。不需要其他第三方函式庫。但是，此實作使用 C++17 功能，因此需要具有足夠 C++17 支援的編譯器。 CI 建置中使用了以下編譯器，因此已知它們是受支援的：

• 海灣合作委員會9
• 鏗鏘10
• 視覺工作室 2019

單元測試需要googletest ，基準測試需要taocpp/json和taocpp/config 。這些依賴項作為子模組包含在內，因此可以按如下方式建立單元測試和/或基準測試：

 git clone https://github.com/mpoeter/xenium.git && cd xenium
git submodule update --init --recursive
mkdir build && cd build
cmake ..
make gtest
make benchmark

參考

[兄弟15]	特雷弗·亞歷山大·布朗。為無鎖資料結構回收記憶體：必須有更好的方法。 2015 年 ACM 分散式計算原理研討會 (PODC) 論文集，第 261-270 頁。美國CM，2015。
[CL05]	大衛·蔡斯和約西·列夫。動態循環工作竊取雙端佇列。第 17 屆 ACM 演算法和架構平行研討會 (SPAA) 會議記錄，第 21-28 頁。美國CM，2005。
[弗拉04]	凱爾·弗雷澤。實用的無鎖。博士論文，劍橋大學電腦實驗室，2004 年。
[哈爾01]	哈里斯 (Timothy L. Harris)非阻塞鍊錶的實用實作。第 15 屆國際分散式計算會議 (DISC) 會議記錄，第 300-314 頁。施普林格出版社，2001 年。
[HMBW07]	托馬斯·E·哈特、保羅·E·麥肯尼、安吉拉·德姆克·布朗和喬納森·沃波爾。無鎖同步的記憶體回收效能。平行與分散式計算雜誌，67(12):1270–1285，2007。
[KLP13]	克里斯托夫·基爾希、邁克爾·利波茨和漢內斯·佩爾。快速且可擴展的無鎖 k-FIFO 佇列。國際平行計算技術會議記錄 (PaCT) ，第 208-223 頁，Springer-Verlag，2013 年。
[麥克風02]	馬吉德·M·邁克爾.高效能動態無鎖哈希表和基於列表的集合。第 14 屆 ACM 平行演算法和架構年度研討會 (SPAA) 會議記錄，第 73-82 頁。美國CM，2002。
[麥克風04]	馬吉德·M·邁克爾.危險指標：無鎖物件的安全記憶體回收。 IEEE 平行與分散式系統彙刊，15(6):491–504，2004 年。
[MS95]	麥吉德·M·邁克爾和邁克爾·L·斯科特。修正無鎖資料結構的記憶體管理方法。技術報告，羅徹斯特大學，1995 年。
[MS96]	麥吉德·M·邁克爾和邁克爾·L·斯科特。簡單、快速、實用的非阻塞和阻塞並發隊列演算法。第 15 屆 ACM 分散式計算原理研討會 (PODC) 會議記錄，第 267-275 頁。美國計算機學會，1996。
[尼克19]	Ruslan Nikolaev 一個可擴展、可移植且記憶體高效的無鎖 fifo 隊列。 2019 年第 33 屆國際分散式計算研討會 (DISC) 論文集。
[PT18a]	曼努埃爾·波特和傑斯珀·拉爾森·特拉夫。簡短公告：Stamp-it，C++ 記憶體模型中線程效率更高的並發記憶體回收方案。第 30 屆 ACM 演算法和架構平行研討會 (SPAA) 會議記錄，第 355-358 頁。美國CM，2018。
[PT18b]	曼努埃爾·波特和傑斯珀·拉爾森·特拉夫。 Stamp-it，C++ 記憶體模型中線程效率更高的並發記憶體回收方案。技術報告，2018。
[拉姆16]	佩德羅·拉馬爾赫特。 FAAArrayQueue - MPMC 無鎖佇列（第 4 部分，共 4 部分）。博客，2016 年 11 月。
[RC15]	佩德羅·拉馬爾赫特和安德烈亞·科雷亞。 Left-Right - 一種具有無等待總體不經意讀取的並發控制技術。 2015年10月
[RC17]	佩德羅·拉馬爾赫特和安德烈亞·科雷亞。簡短公告：危險時代 - 非阻塞記憶體回收。第 29 屆 ACM 演算法和架構平行研討會 (SPAA) 會議記錄，第 367-369 頁。美國CM，2017。
[羅布13]	阿奇·D·羅賓遜。基於策略的設計，用於並發容器中的安全銷毀。 C++ 標準委員會論文，2013 年。
[瓦爾95]	約翰·D·瓦盧瓦.無鎖資料結構。博士論文，倫斯勒理工學院，1995 年。
[Vyu08]	德米特里·維尤科夫。可擴展的哈希圖。 Google 網路論壇發帖，2008 年。
[Vyu10]	德米特里·維尤科夫。簡單高效的有界 MPMC 隊列。 Google 網路論壇發帖，2010 年。