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) 的精彩博客