问题标签 [lockless]

我想从原子 uint32 拼凑一个 uint64 原子计数器。计数器有一个写入器和多个读取器。writer 是一个信号处理程序，因此它不能阻塞。

我的想法是使用低位的生成计数作为读锁。读取器重试，直到整个读取过程中生成计数稳定，并且低位未设置。

以下代码在设计和使用内存排序方面是否正确？有没有更好的办法？

编辑：哎呀，已修复auto acquire = memory_order_release;

我正在开发一个程序，其中 2+ (gstreamer) boost::线程和相同数量的boost::虚拟应用程序的线程同时使用queue。现在这个队列用于gstreamer 线程的任务与其对应的虚拟应用程序线程之间的同步。

该队列是一个 EVENT 队列：其中 EVENT 是一个结构

谷歌搜索后，我发现了队列的这两个选项：lockfree::queue和lockfree::spsc_queue，这表明lockfree::queues它们用于多线程应用程序。

困惑：为什么叫 lockFREE？是否暗示不能（互斥）锁定？

另见这个例子，它说“boost::lockfree::queue is not lockfree”

头脑=吹...

好吧，然后我尝试按照示例（以上链接）并实现此队列

其定义为：

这样就编译成功了。但我在这里完全是在黑暗中奔跑。

问题：

• 为什么该示例将队列声明为

  boost::lockfree::queue<int> queue(128);

那128是干什么用的？是说队列大小是 128（字节/项）吗？是否queue<int>声明队列中的数据类型？

• 为什么它对我的程序不起作用

  boost::lockfree::queue<EVENT> mqSttEventQueue(128);

如果我这样声明它，它会得到编译错误

PS：-我真的不确定在这里放什么标题...如果可以的话，请编辑它。

I have a consumer thread that must never lock nor allocate memory, and a producer thread that can. I want to implement a two place circular buffer to be able to provide data to the consumer thread from the producer, with the bound that whenever no new data is available to consume, the consumer just re-uses the already available data.

This is what I've come up with for now:

Is this naive implementation ok? I know reading and writing to variables can be non-atomic, so I should use an atomic storage, but those can cause locks. Is the use of atomic storage needed here? Also, I'd like to eliminate the active wait in the producer, and I thought I could use a std::condition_variable, but they require the use of mutexes and I cannot afford them.

根据英特尔的手册（第 112 页）：

无效_mm_pause（无效）

下一条指令的执行延迟了实现特定的时间量。该指令不会修改架构状态。这种内在提供了特别显着的性能增益。

也就是说：

while (!acquire_spin_lock()) _mm_pause(); // code snippet 1

速度更快，功耗比

while (!acquire_spin_lock()) continue; // code snippet 2

我可以理解为什么代码片段 1的功耗比代码片段 2低。

我无法理解的是：

为什么代码片段 1比代码片段 2快？

我遇到了这个旧的（4.8.3 之前的 GCC - bug 60272）错误报告https://gcc.gnu.org/ml/gcc-bugs/2014-02/msg01951.html。现在已修复。但我对此有一个疑问。我编译了以下代码片段

和 ：

生成的程序集有以下内容（我只放了相关部分）：

这是我的问题。假设这段代码与 2 个线程同时运行。对于 T1，第 5 行被执行，然后 T1 被中断，T2 做了一些可能使队列弹出完成的事情。当操作系统重新安排 T1 时，它将从第 6 行恢复，在执行jne之前，有人应该**重新评估**条件。但是，如果不重新评估它，那么这可能会导致内存损坏。我在思考正确的方向吗？

我知道它std::atomic_flag保证是无锁的，而其他原子的东西，例如std::atomic<int>，std::atomic<bool>不是，这意味着它们可能是用锁生成的。

我的问题是为什么只有一件事std::atomic_flag是无锁的，而其他的可能不是？为什么我们不强制使用无锁来生成类似的东西std::atomic<bool>？有什么技术原因吗？

我觉得这可能是一种非常普遍和常见的情况，其中存在众所周知的无锁解决方案。

简而言之，我希望有像读者/作者锁这样的方法，但这并不要求读者获得锁，因此可以获得更好的平均性能。

相反，读者会使用一些原子操作（128 位 CAS），而编写者会使用互斥锁。我将拥有数据结构的两个副本，一个用于正常成功查询的只读副本，以及一个在互斥锁保护下更新的相同副本。将数据插入可写副本后，我们将其设为新的可读副本。旧的可读副本然后依次插入，一旦所有待处理的读者都读完它，写者旋转剩余的读者数量直到其为零，然后依次修改它，最后释放互斥体。

或类似的东西。

沿着这些思路存在吗？

在我的 C++ 游戏引擎中，我有一个利用工作线程来执行各种任务的作业系统。线程关联到每个可用的核心。最近，我一直在尝试通过最大化 CPU 利用率来优化我的一些系统管道。这是一些示例伪代码。它不是一个精确的复制品，但情况相似。

然后，我有 5 个作业同时在此列表上运行，没有Mutexes或Critical Sections。每个工作职能都通过基于标准的二分搜索访问数组，例如 guid，或者只是线性搜索。这是问题所在。没有任何工作职能修改 entityStateList 中entityState ptrs 的相同成员数据。但是，由于二分搜索与线性搜索存在冲突，它们可以遵循相同的 entityState ptr。但是，我再说一遍，他们从不同时修改相同的成员数据。没有成员数据ptrs 在每个线程上同时被取消引用。

我已经用单元测试运行了这个模拟并且没有遇到任何问题。但是，我有一些程序员朋友说，当取消引用同一个 entityStatePtr 时，这将导致线程暂停和恢复的未定义行为的可能性非常小。

我听说的另一点是此设置起作用的原因是 entityState 结构大小不适合缓存行并最终划分数据获取，由于结构本身，它本身充当数据保护数据被分成不同的缓存行。澄清一下，假设上半部分适合一个缓存行，下半部分适合另一个缓存行，并且作业函数仅对 entityState ptr 的一个数据成员进行操作，并且大部分时间它恰好位于不同的缓存行上。我不对成员数据使用任何原子修饰符或操作，因为没有作业涉及相同的成员数据。

最后，我也有一些程序员朋友说这是完全线程安全的。

尽管如此，我有三种不同的陈述，而且我对多线程的低级知识缺乏足够的知识来确定哪个是正确的。

问题是......是否有可能在“x”次中发生一次超低崩溃？即使是 1/100 万也是不可接受的。这是一种安全、无锁的线程机制，可以在列表上并行执行多个操作吗？尝试忽略示例数据的琐碎性。在我的引擎示例中，它要复杂得多。此代码可以在多个操作系统上运行，例如 PC、Linux 和控制台。它还没有崩溃，但曝光和测试是有限的。我承认我不是低级专家，但这节省了宝贵的表演时间。那么，我是在等着撞上地雷还是这样安全？编译器是 gcc 版本 C++11。另外，请避免局部性的性能话题，除非它与线程和/或线程安全有关。我知道缓存未命中很糟糕。

问题- 线程是否安全？如果是或否，请尽可能详细解释原因。我想加强我的低级知识。

似乎我应该能够实现一个可以同时插入和读取的向量类型对象，如下所示：

1. 如果向量中有空间，我可以插入东西；这不应该干扰阅读。
2. 如果我必须重新分配，我可以分配，然后复制，然后更新指向数据的指针，然后释放。
3. 如果我想从向量中读取，我只需要确保获取指向数据的指针并从中读取是原子完成的。

这样，如果我在重新分配时从向量读取，我只是从旧位置读取，这仍然有效。（当然删除不会是线程安全的，但这很好；如果你想删除东西，你只需要考虑到这一点，这无论如何不会比你std::vector现在拥有的更糟糕。）

反过来，我应该能够毫不费力地将其调整为哈希表——只需将这些向量之一用于存储桶，并使用其中一个向量支持每个存储桶。（我意识到您应该使用某种自平衡二叉树来支持存储桶以获得最佳的渐近复杂度，但是向量对于我的应用程序来说很好，我不想在这里偏离轨道。）

两个问题：

1. 这有意义还是我错过了什么？（我不相信我对线程安全的直觉。）
2. 如果是这样，是否可以使用 C++ 标准库中的一些容器作为原语来构建它或类似的东西，或者我唯一的做法是从头开始编写整个东西？（当然，我想我会std::atomic在几个地方使用，但是有什么方法可以使用类似std::vector或std::unordered_map这里的东西吗？）

或者，有没有关于这个主题的书或我可以阅读的东西？

在 x86 上，像这样的原子 RMW 指令lock add dword [rdi], 1是使用现代 CPU 上的缓存锁定来实现的。因此，高速缓存行在指令期间被锁定。这是通过在读取值时获取行 EXCLUSIVE/MODIFIED 状态来完成的，并且 CPU 在指令完成之前不会响应来自其他 CPU 的 MESI 请求。

有两种并发进度条件，阻塞和非阻塞。原子 RMW 指令是非阻塞的。CPU 硬件在持有缓存锁时永远不会休眠或做其他事情（中断发生在原子 RMW 之前或之后，而不是期间），释放缓存行之前的步数有一个有限（且很小）的上限.

非阻塞算法在理论计算机科学中可以分为 3 种风格：

1. 等待免费：所有线程将在有限的步骤中取得进展。

2. 无锁：至少一个线程将在有限的步骤中取得进展

3. 无阻塞：如果没有争用，线程将在有限的步数内取得进展

x86 提供什么样的保证？

我想它至少是无锁的；如果存在争用，至少有一个 CPU 会取得进展。

但是 x86 是否可以免费等待原子指令？是否每个 CPU 都能保证在有限数量的步骤中取得进展，或者可能是一个或多个 CPU 处于饥饿状态并可能无限期延迟？

那么当多个内核在同一个缓存行上进行原子操作时会发生什么？