xenium下载 - xenium源码下载

xenium

C/C++

v0.0.2: Merge pull request #19 from rbalint

下载

塞尼姆

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]	蒂莫西·L·哈里斯 (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 年。