问题标签 [lock-free]

原子操作的成本是多少（比较和交换或原子加/减）？它消耗多少周期？它会暂停 SMP 或 NUMA 上的其他处理器，还是会阻止内存访问？它会在乱序 CPU 中刷新重新排序缓冲区吗？

对缓存会有什么影响？

我对现代流行的 CPU 很感兴趣：x86、x86_64、PowerPC、SPARC、Itanium。

应该传输一个字节流，并且有一个生产者线程和一个消费者线程。生产者的速度大多数时候都高于消费者，我需要足够的缓冲数据来满足我的应用程序的 QoS。我读到了我的问题，并且有共享缓冲区、PipeStream .NET 类等解决方案……这个类将在服务器上多次实例化，所以我需要优化解决方案。使用 ByteArray 的队列是个好主意吗？

如果是，我将使用优化算法来猜测队列大小和每个 ByteArray 容量，理论上它适合我的情况。

如果没有，我最好的方法是什么？

请让我知道在 C# 或 VB 中是否有良好的无锁线程安全实现 ByteArray 队列。

提前致谢

我正在寻找一种方法来实现支持单个生产者和多个消费者的无锁队列数据结构。我看过 Maged Michael 和 Michael Scott (1996) 的经典方法，但他们的版本使用链表。我想要一个使用有界循环缓冲区的实现。使用原子变量的东西？

附带说明一下，我不确定为什么这些经典方法是为需要大量动态内存管理的链表设计的。在多线程程序中，所有的内存管理例程都是序列化的。通过将无锁方法与动态数据结构结合使用，我们不是在破坏无锁方法的好处吗？

我正在尝试在英特尔 64 位架构上使用 pthread 库在 C/C++ 中对此进行编码。

谢谢你，希里什

可能重复：
C++ 中是否有生产就绪的无锁队列或哈希实现

我正在寻找一个经过良好测试、公开可用的无锁队列的 C/C++ 实现。

我至少需要多生产者/单一消费者功能。如果存在多个消费者，那就更好了。

我的目标是 VC 的_Interlocked...内在函数，尽管任何可以直接移植的东西都可以。

任何人都可以提供任何指示吗？

在本文：无锁数据结构（pdf）中，显示了以下“比较和交换”基础：

然后说

整个过程是原子的

但怎么会这样呢？其他一些参与者不可能改变和 赋值addr之间的值if吗？在这种情况下，假设所有代码都使用这个 CAS 基础，那么下一次“预期”它会以某种方式出现时会发现它，但事实并非如此。但是，这并没有改变它可能发生的事实，在这种情况下，它仍然是原子的吗？其他演员返回 true 的情况如何，即使它的更改已被该演员覆盖？如果这不可能发生，那为什么呢？

我想相信作者，所以我在这里错过了什么？我想这一定很明显。如果这看起来微不足道，我提前道歉。

我打算使用 std::ifstream 执行打开以从多个线程中读取单个文件。我担心的是 std::ifstream 是否是线程安全且无锁的？

更多细节：

1. 我在 Ubuntu 和 Windows XP 上使用 g++ 4.4，在 Leopard 上使用 4.0。
2. 每个线程创建自己的 std::ifstream 实例

提前致谢！

假设我有两个线程（T1、T2）共享的变量 A、B 和 C。
我有以下代码：

问题：
在 T1 和 T2 上调用 InterlockedExchange（隐式全围栏）是否意味着 T2 将“看到”T1 在围栏之前完成的写入？（A、B 和 C 变量），即使这些变量与Foo和Bar不在同一缓存行上？

我一直在思考如何实现一个无锁单链表。老实说，我没有看到很多防弹的方法来做到这一点。即使是使用的更强大的方法最终也存在CAS一定程度的ABA 问题。

所以我开始思考。部分无锁系统不会比总是使用锁更好吗？某些操作可以是原子的和无锁的吗？如果我能做到这一点，它应该仍然是线程安全的。

所以，直奔问题。我正在考虑一个简单的单链表。2 主要业务。 push和pop。push总是在前面插入。像这样的东西：

而 pop 总是采用第一个元素。像这样的东西：

显然，push 并不简单，简单的无锁方法可能不会发生。但流行看起来可能是可行的。使用 gcc-intrinsics 我想到了这个：

功能等同？对。无锁？对。线程安全？我不知道。我的直觉反应是否定的，这就是为什么。

我担心其中一个参数test_and_set必须取消引用内存。如果 root 在root->next和对 的调用之间发生变化怎么办__sync_lock_test_and_set？

我想这段代码等价于：

所以，就像我说的，我认为这段代码是不正确的。但是任何人都可以肯定地说我得出了正确的结论（我不想注销一些效果很好的东西）。如果它真的像我怀疑的那样坏了。有没有简单的解决方案？

Joe Duffy，给出了描述 CLR 2.0+ 内存模型的 6 条规则（它是实际实现，不是任何 ECMA 标准）按照我的逻辑，至少这里有人能够在它让我伤心之前抓住它。

• 规则 1：永远不会违反加载和存储之间的数据依赖关系。
• 规则 2：所有存储都有释放语义，即没有加载或存储可以在一个之后移动。
• 规则 3：获取所有易失性负载，即任何负载或存储都不能移动到一个之前。
• 规则 4：任何加载和存储都不能跨越全屏障（例如 Thread.MemoryBarrier、锁获取、Interlocked.Exchange、Interlocked.CompareExchange 等）。
• 规则 5：可能永远不会引入堆的加载和存储。
• 规则 6：只有在合并来自/到同一位置的相邻加载和存储时，才能删除加载和存储。

我试图理解这些规则。

看这个，似乎加载 0 可以移动到加载 y 之前，但商店可能根本不会重新排序。因此，如果一个线程看到 z == 0，那么它也会看到 x == y。

如果 y 是 volatile，则加载 0 不能在加载 y 之前移动，否则可能。不稳定的商店似乎没有任何特殊属性，没有商店可以相互重新订购（这是一个非常强的保证！）

完整的障碍就像沙中的一条线，装载和存储无法移动。

不知道第 5 条是什么意思。

我猜规则 6 意味着如果你这样做：

然后，CLR 可以删除对 y 的加载和对 x 的第一次存储。

如果 y 不稳定怎么办？我在规则中看不到任何禁止执行上述优化的内容。这并不违反双重检查锁定，因为两个相同条件之间的 lock() 可以防止负载移动到相邻位置，并且根据规则 6，这是唯一可以消除它们的时间。

所以我想我理解除了规则 5 之外的所有内容。任何人都想启发我（或纠正我或在上述任何内容中添加一些内容？）

是否有“无锁 FIFO 队列的乐观方法”算法的 C++ 实现（源代码） ？