问题标签 [lock-free]

我正在设计一个连接到一个或多个数据馈送流的系统，并对数据进行一些分析，而不是根据结果触发事件。在典型的多线程生产者/消费者设置中，我将有多个生产者线程将数据放入队列，多个消费者线程读取数据，消费者只对最新的数据点加上 n 个点感兴趣。如果慢的消费者跟不上生产者线程将不得不阻塞，当然当没有未处理的更新时消费者线程将阻塞。使用带有读/写锁的典型并发队列会很好地工作，但数据进入的速度可能会很大，所以我想减少我的锁定开销，尤其是生产者的写锁。我认为我需要一个循环无锁缓冲区。

现在有两个问题：

1. 循环无锁缓冲区是答案吗？

2. 如果是这样，在我推出自己的产品之前，你知道任何符合我需要的公共实施吗？

任何实现循环无锁缓冲区的指针总是受欢迎的。

顺便说一句，在 Linux 上用 C++ 执行此操作。

一些附加信息：

响应时间对我的系统至关重要。理想情况下，消费者线程将希望尽快看到任何更新，因为额外的 1 毫秒延迟可能会使系统一文不值，或者价值大大降低。

我倾向于的设计思想是一个半无锁循环缓冲区，其中生产者线程尽可能快地将数据放入缓冲区中，让我们调用缓冲区 A 的头部，除非缓冲区已满，否则不会阻塞，当A 与缓冲区 Z 的末端相遇。消费者线程将分别持有两个指向循环缓冲区的指针 P 和 P _n，其中 P 是线程的本地缓冲区头，P _n是 P 之后的第 n 项。每个消费者线程将推进其 P和 P _n一旦它完成处理当前 P 并且缓冲区指针 Z 的末尾以最慢的 P _n前进. 当 P 赶上 A 时，这意味着不再需要处理新的更新，消费者旋转并忙于等待 A 再次前进。如果消费者线程旋转时间过长，它可以进入睡眠状态并等待条件变量，但我可以接受消费者占用 CPU 周期等待更新，因为这不会增加我的延迟（我将拥有更多的 CPU 内核比线程）。想象一下你有一个环形轨道，生产者跑在一堆消费者前面，关键是调系统，让生产者通常跑在消费者前面几步，而这些操作大部分都可以使用无锁技术完成。我知道要正确执行实施的细节并不容易……好吧，非常难，这就是为什么我想在自己犯一些错误之前从别人的错误中吸取教训。

我有一个内存数据结构，由多个线程读取并由一个线程写入。目前我正在使用一个关键部分来使这个访问线程安全。不幸的是，即使只有另一个读者正在访问它，这也会阻止读者。

有两种方法可以解决此问题：

1. 使用 TMultiReadExclusiveWriteSynchronizer
2. 通过使用无锁方法消除任何阻塞

对于 2. 到目前为止，我得到了以下内容（任何无关紧要的代码都被省略了）：

不幸的是，在旧数据实例被替换后，它存在一个小问题。如果 Read 方法中当前没有其他线程（ReaderCount=0），则可以安全地处理它，仅此而已。但如果不是这样，我该怎么办？我可以将它存储到下一次调用并在那里处理它，但是 Windows 调度理论上可以让读取器线程在 Read 方法中休眠并且仍然具有对 OldData 的引用。

如果您发现上述代码有任何其他问题，请告诉我。这将在具有多核的计算机上运行，​​并且上述方法将被非常频繁地调用。

万一这很重要：我正在使用带有内置内存管理器的 Delphi 2007。我知道内存管理器在创建新类时可能会强制执行一些锁定，但我暂时想忽略它。

编辑：从上面可能不清楚：对于 TDataManager 对象的整个生命周期，只有一个线程写入数据，而不是几个可能竞争写访问的线程。所以这是 MREW 的一个特例。

我正在尝试编写用于消息传递的调用队列的无锁版本。这不是什么严肃的事情，只是为了了解线程。

我相对确定我的代码是正确的，除非指令被重新排序或在寄存器中完成。我知道我可以使用内存屏障来停止重新排序，但是如何确保立即将值写入内存？

我正在使用原子（双）比较和交换指令实现无锁机制，例如 cmpxchg16b

我目前正在汇编中编写它，然后将其链接。但是，我想知道是否有办法让编译器自动为我执行此操作？例如，用“原子”包围代码块并让它弄清楚如何在底层处理器架构中将代码实现为原子指令（或者如果底层架构不支持它，则在编译时生成错误）？

PS我知道gcc有一些内置的（至少对于CAS）

http://gcc.gnu.org/onlinedocs/gcc-4.4.0/gcc/Atomic-Builtins.html#Atomic-Builtins

我正在编写一个带有消费者线程和生产者线程的程序，现在看来队列同步在程序中是一个很大的开销，我寻找了一些无锁队列实现，但只找到了 Lamport 的版本和 PPoPP 上的改进版本08:

两个版本都需要为数据预先分配数组，我的问题是是否有任何使用 malloc() 动态分配空间的单消费者单生产者无锁队列实现？

另一个相关的问题是，我如何测量队列同步中的确切开销？比如pthread_mutex_lock()需要多少时间等等。

Herlihy 和 Shavit 的书（多处理器编程艺术）内存回收解决方案使用 Java 的AtomicStampedReference<T>;.

要在 C++ 中为 x86_64 编写一个，我想至少需要一个 12 字节的交换操作 - 8 个用于 64 位指针，4 个用于 int。

是否有对此的 x86 硬件支持，如果没有，是否有任何关于如何在没有它的情况下进行无等待内存回收的指针？

我已经找到了针对单个生产者-单个消费者的几种实现，但没有针对多个生产者-单个消费者的实现。

Delphi 是否存在“多个生产者-单个消费者”的无锁队列？

我刚发现这个：

http://www.emadar.com/fpc/lockfree.htm

乍一看，它看起来不错。有人在用吗？或者也许有人已经看过它并发现它无法使用？

我发现了以下文章：使用 GCC 提供的原子锁操作来替换 pthread_mutex_lock 函数

它指的是GCC Atomic Builtins。

这篇文章的建议是使用 GCC atomic builtins 而不是 pthread 同步工具。

这是一个好主意吗？

PS。mysql 帖子显然具有误导性。Atomic Builtins 不能替代所有 pthread 工具。例如，锁定要求，如果无法获得锁定，则线程必须等待。换句话说，它要求操作系统等待，因此等待是被动的。简单的 GCC 内置不能做到这一点。

是否有任何小型库，将各种处理器的类似 CAS 的操作包装成宏或函数，可以跨多个编译器移植？

PS。atomic.hpp库位于 boost::interprocess::detail 命名空间内。作者拒绝让它成为一个公共的、维护良好的图书馆。

让我们重新打开这个问题，看看是否还有其他选择？