问题标签 [lock-free]

是否有实现 IList 的无锁和线程安全的数据结构？

自然，无锁我的意思是一种在.NET中不使用锁定原语而是使用互锁操作/原子操作来实现线程安全的实现......显然在并发数据结构下没有一个......

有没有人看到一个漂浮在周围？

我已经看到了一个在amino-cbbs中实现的java ，称为LockFreeVector ，但到目前为止还没有用于.NET。有任何想法吗？

Herb Sutter 的关于无锁和并发队列的文章在 SO 中已经被多次提及。但是，我没有 C++0x 编译器……所以我想知道是否有人翻译了他的代码以使用一些 boost 库或任何提供一些“原子”操作的东西。

即使有人可以提供互斥锁/条件变量示例，我也不介意...

以下是我参考的文章...

http://drdobbs.com/cpp/210604448

http://drdobbs.com/cpp/211601363

http://drdobbs.com/high-performance-computing/212201163

谢谢！

以下是使用 compareAndSet（Java 中）的无锁队列中的一些代码：

（head 和 tail 是队列的成员）

在 deq 和 enq 函数中，第一次检查对我来说似乎是不必要的。（那些用“???”评论的）我怀疑它只是为了某种优化。

我在这里错过了什么吗？这些检查会影响代码的正确性吗？

（代码取自“多处理器编程艺术”，尽管我确实重构了代码样式以减少嵌套的 if 和 else，同时保持代码等效）

有人对 C/c++ 的无锁内存分配器有什么好的经验吗？

我研究过 boost 和 libcds，但我不确定要使用哪个库。

背景，我一直在研究“无锁、无等待、非阻塞、动态完美哈希、可扩展、并发哈希表” *是的，我知道这听起来很自命不凡，但这就是所谓的。

无论如何，我已经准备好开始多线程测试了，当添加新节点时，我需要找出设置内存分配的最佳方法。（当我需要分配指针数组时）

那么有人对无锁内存分配有什么好的经验吗？

最近发现了这样一个java-concurrency面试任务：

使用两种方法编写简单的无锁堆栈：push 和 pop。

我做了浓缩：

是否与预期的方法相似？或者“无锁堆栈”意味着不同的东西？请帮助一个java面试新手。

Raymond Chen一直在做大量 关于无锁算法的系列 文章。除了函数的简单案例之外，所有这些的流行模式似乎是它们实现了自己的 locks。当然，没有处理器锁，但在每个 CPU 上反复循环以确保一致性的概念非常类似于自旋锁。作为自旋锁，它们的效率将低于操作系统附带的通用锁，因为它们在等待其他线程时不会产生对它们的量子的控制。因此，每当有人来找我说“但我的算法是无锁的”时，我的一般反应是“所以”？ InterlockedXxx

我很好奇——是否有可用的基准测试显示无锁算法比全锁算法更有优势？

我正在尝试了解 x86/x64 上 CAS 的低级机制，我非常感谢一些帮助/见解。

我一直在考虑这个问题的原因是我试图对指数退避进行推理，并从原则上找出正确的退避延迟单位应该是多少。

如果我查看一个没有指数退避的无锁 freelist 基准测试，我会看到随着线程数量的增加，性能迅速趋于平缓。

正如我们所知，可能会发生活锁，每个线程都会阻止其他线程继续进行。

我最初的想法——现在我认为是错误的——认为 CAS 正在干扰 CAS。我的意思是，如果它们同时发生，CAS 指令本身将与另一个 CAS 发生破坏性冲突。两者都会失败。（Prolly，因为我在脑海中思考以太网）。

这“显然”解释了结果 - 所有这些 CAS 指令同时运行，很少有机会在被破坏性中断之前完全执行。

再想一想，我相信现在情况并非如此。CAS 指令实际上没有故障模式。它会告诉你目的地等于或不等于比较对象。就这样。它不会回来说“哦，对不起，撞到别人了”。

破坏性干扰正在发生，但它发生在更高级别，在数据结构算法本身中。当我们从/向自由列表推送或弹出时，我们实际上是在尝试交换。我们需要目标足够长的时间稳定，以便我们可以读取它，做我们需要做的任何工作，然后发现它没有改变，这样我们就可以完成我们的推送/弹出。

如果其他线程继续 CASing，destination 就不稳定——它一直在变化——我们一直不得不重试我们的操作。

但现在我很困惑。

我们看到的是，单个线程执行了大约 3000 万次 push/pop 操作。Destination 必须在其中一项操作期间保持稳定，操作才能成功，因此我们看到有 3000 万个“槽”。如果我们有两个线程，那么我们可以拥有的最大理论性能是每个线程 1500 万次操作；每个线程使用一半的插槽。

现在让我们回到 CAS。CAS 没有故障模式。那么当另一个线程已经在进行 CAS 时，当第二个线程尝试 CAS 时会发生什么？好吧，第二个线程将在数据结构级别失败，因为交换无法发生，所以它将重试交换。

但现在想象我们有很多线程。开始 CAS 的第一个线程将成功（假设每个 CAS 花费完全相同的时间 - 不正确，但该假设不会改变任何基本内容，因此可以推理）。所有其他人都会失败。

但是一旦第一个线程完成，读取新目标值的下一个线程将使其 CAS 成功（所有其他线程，仍在执行它们的 CAS 或现在开始新的 CAS，将失败）。

那么为什么我们看不到完美的缩放比例呢？因为每个“插槽”都应该被使用！

我认为因此我不正确理解CAS。

阅读英特尔的架构软件开发人员手册，我发现如果所有数据都存在于缓存中（我感兴趣的情况），缓存一致性协议会处理 CAS。

Drepper 在他的白皮书中描述了 LL/SC 以及它是如何使用 MESI 工作的。

对我来说，CAS 以类似的方式运作似乎是合理的。

让我们考虑两个线程的情况。第一个线程开始其 CAS。具有目标的缓存行在其缓存中并标记为独占。

第二个线程开始 CAS。第一个核心将其缓存线发送到第二个核心，并且两个核心都将该缓存线标记为共享。

第一个线程完成 CAS 并写入缓存行（写入总是发生在 x86/x64 上，即使比较结果为假；它只是写入原始值）。

写入动作将缓存行标记为已修改；发生 RFO，导致第二个内核将其缓存行标记为无效。

第二个线程来完成它的 CAS 并注意到它的缓存行是无效的......然后，什么？我发现很难相信指令在 CPU 内部循环，直到它成功 - 尽管我想知道，因为 ARM 上的 LL/SC 要求您在程序集中执行此循环。但是CAS指令知道destination的值发生了变化，所以它的比较结果是无效的。但是 CAS 不会出错；它总是返回 true 或 false 进行比较。但即使指令确实循环直到完成，我仍然期望完美的缩放。每个“插槽”仍应使用。

那么会发生什么？CAS 发生了什么？

我所看到的是，随着线程数的增加，完成的工作越来越少——所有可用的“插槽”肯定都没有被使用。是什么原因造成的。CAS指令之间是否存在破坏性干扰？还是大量 RFO 占用 CPU-> 北桥总线？

我非常感兴趣地注意到的是，同一物理核心上的两个线程可以完美扩展。在这种情况下会发生一些特殊和不同的事情——不同物理内核上的两个线程也可以缩放一半。但这还不足以解释这一切。

我知道阻塞队列和无锁队列，这是Scott 等人提供的这些实现的一个很好的例子。，但是有无锁阻塞队列的实现吗？

在无锁阻塞队列中，出队不需要锁定，但如果队列中没有项目，它将阻塞消费者。有没有这种野兽的实现？我更喜欢它们是 C# 实现，但任何实现在技术上都可以工作。

更新：

我想我最终在 D14.1 行出现了竞争条件：

我已经使用基于http://www.boyet.com/articles/LockfreeQueue.html的比较和交换在 C 中实现了一个无锁队列。

它工作得很好，但我正在尝试将此队列集成到我已经实现的无锁跳过列表中。我将跳过列表用作优先级队列，并希望在发生优先级冲突时使用每个节点内的无锁队列来存储多个值。但是，由于当我检测到优先级冲突时在跳过列表中管理节点的方式，我需要能够仅当队列不为空时才能将项目添加到队列中。

由于队列的无锁特性，我不确定如何实际执行此操作。

所以基本上我将如何编写一个原子 enqueue_if_not_empty 操作？

嘿伙计们，
我正在阅读这些所谓的非阻塞技术，但我几乎没有疑问：

1）使用原子操作执行无锁操作，现在这些原子操作是什么？我的意思是在一定程度上他们也需要锁，对吗？那么这种无锁方法是否只为我们提供了更细粒度的锁定？
2）他们说非阻塞列表，现在非阻塞列表应该是什么：如果多个线程同时插入，只有一个会成功，另一个会做其他工作对吗？，但是如果其他线程别无选择，只能插入一个节点，那么它为什么是非阻塞的？在前一个完成之前它不会被阻止吗？
3）在java中，它们如何进行原子操作？他们不做类似的事情吗 synchronized boolean ..... 那么它是如何无锁的，因为他们正在获取锁，即同步部分？4）CAS通常用于实现原子操作。那么 cas 是否只允许对同一对象进行一项操作，并停止（阻止）其他想要对同一对象进行操作的操作？很抱歉有这么多疑问...请澄清...

编辑 当我有一个结构要更新时会发生什么？硬件也支持吗？不对，那么语言不会在某种程度上获取锁以使这些结构操作原子化吗？
关于JAVA：有 AtomicReference 和 AtomicReferenceFieldUpdater 类提供对对象（结构或任何类型的对象）的更新，所以我们可以在性能方面比较它们，我的意思是速度吗？两者都使用 Unsafe 类，它使用 Native 类。