问题标签 [lock-free]

我正在创建一个适合我的 concurrnetHashtable，与 concurrentHashMap 几乎没有什么不同，我正在使用 AtomicReferenceFieldUpdater 进行 CASNext 操作（通常支持 CAS，但我们也可以执行 CASNext），所以我走的是正确的道路吗？虽然通常我在这个 concurrentHashTable 中获得比锁定哈希表更好的性能，但有时事情并没有解决。
所以我得出以下结论：
如果可用处理器的数量大于哈希表中可用的存储桶数量，则发生锁争用的可能性更高，因此在这种情况下，concurrentHashTable 将比锁定方法工作得更好，当然，如果阅读量很大（期刊说 85- 90％的阅读操作），那么它很好用..所以请建议我，我是否走在正确的道路上，并且假设事情正确？
如果您有时间，请查看此页面上的代码代码 在此哈希表中，如果元素尚不存在，我将进行插入...所以请告诉我这是否是正确的无锁方法？

我也在做一个c实现，目前有队列的结构：

但不确定如何继续，使用队列和出队功能......

• 代码会是什么样子？

我正在为密集型网络应用程序实现一个无锁的单一生产者单一消费者队列。我有一堆工作线程在他们自己的单独队列中接收工作，然后他们将其出列并处理。

从这些队列中移除锁极大地提高了高负载下的性能，但是当队列为空时它们不再阻塞，这反过来又导致 CPU 使用率飙升。

如何有效地导致线程阻塞，直到它可以成功地使某些东西出队或被杀死/中断？

我怎样才能实现这个无锁队列伪代码C？

如何使用内置函数进行原子内存访问

我目前有

我们一直在寻找在我们的代码中使用无锁队列来减少当前实现中单个生产者和消费者之间的锁争用。那里有很多队列实现，但我还不太清楚如何最好地管理节点的内存管理。

例如，生产者看起来像这样：

消费者看起来像：

我们目前使用内存池进行分配。您会注意到生产者分配内存而消费者删除它。由于我们使用的是池，因此我们需要向内存池添加另一个锁以正确保护它。这似乎首先否定了无锁队列的性能优势。

到目前为止，我认为我们的选择是：

• 实现无锁内存池。
• 转储内存池并依赖线程安全分配器。

还有其他我们可以探索的选择吗？我们试图避免实现无锁内存池，但我们可能会走这条路。

谢谢。

我正在编写一个网络控制功能，所以算法是

1. 读取当前传输速率

2. 如果它小于所需的传输速率，则继续，否则休眠一些 x 秒并转到步骤 1：

3. x 是根据所需传输率和当前传输率计算得出的。

你能建议如何使这个算法线程安全吗

是否有实现用 C（不是 C++）编写的无锁算法（队列、链表等）的库？我看过一些像英特尔这样的库，但我想使用通用库，至少比英特尔的更通用。

为了评估 go 是否是音频/视频应用程序的可能选项，我想知道传入 go 的消息是否满足任何非阻塞进度保证（无阻塞、无锁或无等待）。特别是，以下情况是相关的：

单一生产者单一消费者：

两个线程使用共享通道进行通信。线程 A 只做异步发送，线程 B 只做异步接收。假设 OS 调度程序决定在“可能的最坏时刻”无限期地中断线程 A。线程 B 是否保证在有限数量的 cpu 周期内完成接收操作，或者线程 A 是否有（理论上）可能将通道置于线程 B 需要等待操作系统恢复线程 A 的状态？

多个生产者：

多个线程 A1、A2、A3、... 使用共享通道与一个或多个其他线程通信。线程 Ai 只进行异步发送。假设 A2、A3、... 在“最坏的可能时刻”被 OS 调度程序挂起无限时间。线程 A1 是否仍然保证在有限的 cpu 周期内完成发送操作？进一步假设每个线程只想进行一次发送。如果程序运行的时间足够长（使用“恶意”调度程序，它可能会饿死一些线程或中断并在“最糟糕的时刻”恢复线程），是否至少有一个发送保证成功？

我对这里的典型场景不太感兴趣，而是对最坏情况的保证感兴趣。有关无阻塞、无锁和无等待算法的更多详细信息，请参阅非阻塞算法（维基百科） 。

为什么英特尔线程构建模块 (TBB)parallel_for的开销如此之大？根据第 3.2.2 节Automatic ChunkingTutorial.pdf大约半毫秒。这是教程中的一个尝试：

注意：通常一个循环需要至少一百万个时钟周期才能使 parallel_for 提高其性能。例如，在 2 GHz 处理器上花费至少 500 微秒的循环可能会受益于 parallel_for。

从我目前所读到的内容来看，TBB 在内部使用线程池（工作线程池）模式，它通过最初只产生工作线程一次（花费数百微秒）来防止这种糟糕的开销。

那么什么是花时间呢？使用互斥锁的数据同步不是那么慢吗？此外，TBB 不使用无锁数据结构进行同步吗？

我写了一些无锁代码，在大多数情况下都可以很好地处理本地读取。

本地旋转内存读取是否一定意味着我必须始终在旋转读取之前插入内存屏障？

（为了验证这一点，我设法生成了一个读写器组合，这导致在某些非常特定的条件下——专用 CPU、附加到 CPU 的进程、优化器一直打开、没有其他工作，读者永远看不到写入的值在循环中完成——所以箭头确实指向那个方向，但我不完全确定旋转通过内存屏障的成本。）

如果缓存的存储缓冲区中没有要刷新的内容，那么旋转通过内存屏障的成本是多少？即，所有过程正在做（在C中）是

我是否正确地假设它是免费的并且它不会用任何流量阻碍内存总线？

另一种说法是问：内存屏障除了刷新存储缓冲区、对其应用无效以及防止编译器在其位置重新排序读取/写入之外，还有什么作用吗？

反汇编， __sync_synchronize() 似乎转化为：

来自英特尔手册（对于新手来说同样模糊）：

我的翻译：“当你说 LOCK 时，这会很昂贵，但我们只在必要时才这样做。”

@BlankXavier：

我确实测试过，如果写入器没有明确地从存储缓冲区中推出写入，并且它是该 CPU 上运行的唯一进程，那么读者可能永远看不到写入器的效果（我可以使用测试程序重现它，但是正如我上面提到的，它只发生在特定的测试中，具有特定的编译选项和专用的核心分配——我的算法工作正常，只有当我对它的工作原理感到好奇并编写了我意识到它可能具有的显式测试时一个问题在路上）。

我认为默认情况下简单的写入是 WB 写入（回写），这意味着它们不会立即被刷新，但读取将采用它们的最新值（我认为他们称之为“存储转发”）。所以我为作者使用了 CAS 指令。我在 Intel 手册中发现了所有这些不同类型的写入实现（UC、WC、WT、WB、WP），Intel vol 3A 第 11-10 章，仍在学习它们。

我的不确定性在于读者方面：我从 McKenney 的论文中了解到，还有一个失效队列，一个从总线到缓存的传入失效队列。我不确定这部分是如何工作的。特别是，您似乎暗示循环通过正常读取（即，非锁定，没有障碍，并且仅使用 volatile 以确保优化器在编译后离开读取）每次都会检查“无效队列” （如果存在这样的事情）。如果一个简单的读取不够好（即可以读取一个旧的缓存行，它仍然显示为有效等待队列失效（这对我来说也有点不连贯，但是失效队列是如何工作的呢？）），那么原子读取将是必要的，我的问题是：在这种情况下，这会对公共汽车有什么影响吗？（我认为可能不会。）

我仍在阅读英特尔手册，虽然我看到了关于存储转发的精彩讨论，但我还没有找到关于失效队列的很好讨论。我决定将我的 C 代码转换为 ASM 并进行实验，我认为这是真正了解其工作原理的最佳方式。