问题标签 [lockless]

我正在使用 Linux 内核的无锁列表，如llist.h. llist_add添加到列表中，但它在头部之后添加新节点。如何在恒定时间内添加到列表的尾部？

我正在实现一个基于这个算法的无锁队列，它使用一个计数器来解决 ABA 问题。但我不知道如何用 c++11 CAS 实现这个计数器。例如，从算法：

这是一个原子操作，意思是 iftail.ptr->next等于next， lettail.ptr->next指向node并同时（原子地） make next.count+1。但是，使用 C++11 CAS，我只能实现：

这不能next.count+1同时发生。

我正在创建一个非常快速的多线程离散事件模拟框架。该框架的核心使用原子和无锁编程技术来实现跨多个线程的非常快速的执行。这需要我将一些变量与缓存行对齐并填充剩余的缓存行空间，这样我就不会发生缓存行争用。这是我的做法：

这对我很有用，但是我今天在将这种方法用于新对象类型时偶然发现了一个问题。CLPAD() 函数返回将输入类型填充到下一个缓存行所需的字符数。但是，如果我输入的类型的大小恰好是缓存行数的倍数，则 CLPAD 将返回 0。如果您尝试创建大小为零的数组，则会收到以下警告/错误：

我知道在这种情况下我可以修改 CLPAD() 以返回 CACHELINE_SIZE，但是我会无缘无故地烧掉一个缓存行的空间。

如果 CLPAD 返回 0，如何使“填充”声明消失？

有什么方法可以检测函数或线程是否阻塞？我想构建一个测试用例，我可以在其中测试一个函数是否是硬实时安全的。

有一种无锁环形缓冲区使用比较和交换原子操作来解决锁定问题。据说这种无锁环形缓冲区提高了性能。但是查看无锁算法的实现，你会发现每个用户其实还需要保持一个while循环等待“比较和设置”的条件为真才能继续。我理解这本质上仍然是一种锁。但是为什么这项技术会取代传统的锁定方式呢？

我正在尝试根据此https://software.intel.com/en-us/blogs/2008/07/24/tbbconcurrent_vector-secrets-of-实现类似于 std::vector 的线程安全无锁容器记忆组织

据我了解，为了防止重新分配并使所有线程上的所有迭代器无效，而不是单个连续数组，它们添加了新的连续块。
他们添加的每个块的大小都是 2 的递增幂，因此他们可以使用 log(index) 来找到应该在 [index] 处的项目的正确段。

据我所知，他们有一个指向段的静态指针数组，所以他们可以快速访问它们，但是他们不知道用户想要多少段，所以他们做了一个小的初始段，如果段的数量超过当前计数，他们分配了一个巨大的并切换到使用那个。

问题是，添加新段不能以无锁线程安全的方式完成，或者至少我还没有弄清楚如何。我可以原子地增加当前大小，但仅此而已。
而且从小段指针数组切换到大段指针数组还涉及大量分配和内存副本，所以我无法理解他们是如何做到的。

他们在网上发布了一些代码，但是所有重要的功能都没有可用的源代码，它们在他们的线程构建块 DLL 中。这是一些演示该问题的代码：

我在 C 中实现了一个无锁链表，类似于 linux 内核 llist.h 中可用的内容。我正在使用“__sync_bool_compare_and_swap”的原子操作。

这是代码片段：

我有一个小型多线程测试程序，只有 1 个生产者线程将节点插入尾部列表，两个消费者线程从列表头部删除节点。插入/删除功能如下所示：

测试显示一致的失败，例如生产者插入了 10 个节点，但消费者只弹出了 1/2 或 3 个节点，我得到的典型输出之一如下所示：

可以看出，生产者线程首先退出，并切换到消费者线程，但是，这一行： llist_remove_head: tid=7f4d469e8700 first=0x7f4d400008c0 next=(nil) first->next=(nil) 表明一个消费者线程正在尝试删除第一个节点，但它的下一个指针指向NULL，这不应该是case 因为到目前为止，列表已完全填充（有 10 个节点）。因此存在竞争条件，由于这是无锁列表，因此假设会发生这种情况，但是我挠头，无法弄清楚哪种竞争条件会导致此输出。此实现类似于https://github.com/darkautism/lfqueue 但我无法弄清楚为什么我的版本不起作用。

我想出了一个想法，我正在尝试实现一个不依赖引用计数来解决 ABA 问题的无锁堆栈，并且还可以正确处理内存回收。它在概念上类似于 RCU，并且依赖于两个功能：将列表条目标记为已删除，以及跟踪遍历列表的读者。前者很简单，它只是使用指针的 LSB。后者是我在实现无限制无锁堆栈的方法上的“聪明”尝试。

基本上，当任何线程尝试遍历列表时，一个原子计数器 (list.entries) 会递增。当遍历完成时，第二个计数器 (list.exits) 会增加。

节点分配由 push 处理，释放由 pop 处理。

push 和 pop 操作与朴素的无锁堆栈实现非常相似，但必须遍历标记为要删除的节点才能到达未标记的条目。因此，推送基本上很像链表插入。

pop 操作类似地遍历列表，但它使用 atomic_fetch_or 在遍历时将节点标记为已删除，直到到达未标记的节点。

在遍历 0 个或多个标记节点的列表后，正在弹出的线程将尝试对堆栈的头部进行 CAS。至少有一个线程并发弹出会成功，在此之后所有进入堆栈的读取器将不再看到以前标记的节点。

成功更新列表的线程然后加载原子 list.entries，并且基本上自旋加载 atomic.exits，直到该计数器最终超过 list.entries。这应该意味着列表的“旧”版本的所有读者都已完成。然后线程简单地释放它从列表顶部交换的标记节点列表。

所以 pop 操作的含义应该是（我认为）不存在 ABA 问题，因为在所有使用它们的并发读者完成之前，被释放的节点不会返回到可用的指针池中，显然内存回收问题出于同样的原因，也会被处理。

所以无论如何，这是理论上的，但我仍然对实现摸不着头脑，因为它目前不起作用（在多线程情况下）。似乎我在免费问题之后得到了一些写作，但我在发现问题时遇到了麻烦，或者我的假设可能有缺陷并且它不起作用。

任何关于概念和调试代码方法的见解都将不胜感激。

这是我当前的（损坏的）代码（使用 gcc -D_GNU_SOURCE -std=c11 -Wall -O0 -g -pthread -o list list.c 编译）：

我正在尝试在 C 中实现一个无锁链表并拥有它，以便您可以使用 create 实例化无锁链表的多个实例

代码如下：

问题是，当我尝试使用入队然后出队时，它会出现分段错误。因此，如果您能指出问题，那将有很大帮助。

任何帮助，将不胜感激。

我一直在尝试用谷歌搜索我的问题，但老实说，我不知道如何简洁地陈述这个问题。

假设我在多核 Intel 系统中有两个线程。这些线程在同一个 NUMA 节点上运行。假设线程 1 向 X 写入一次，然后只是偶尔向前读取它。进一步假设，除其他外，线程 2 连续读取 X。如果我不使用内存栅栏，线程 1 写入 X 和线程 2 看到更新值之间可能需要多长时间？

我知道 X 的写入将进入存储缓冲区并从那里进入缓存，此时 MESIF 将启动，线程 2 将通过 QPI 看到更新的值。（或者至少这是我收集到的）。我假设存储缓冲区将被写入存储围栏上的缓存，或者是否需要重用该存储缓冲区条目，但我不知道存储缓冲区被分配给写入。

最终，我试图为自己回答的问题是，线程 2 是否有可能在一个相当复杂的应用程序中在几秒钟内看不到线程 1 的写入，该应用程序正在执行其他工作。