问题标签 [lockless]

我今天花了很多时间研究无锁队列。我有多个生产者，多个消费者的情况。为了测试，我实现了一个在 Win32 下使用 Interlocked SList 的系统，它使我基于重线程任务的代码的性能提高了一倍。但不幸的是，我希望支持多个平台。在多个平台上互锁本身不是问题，我可以放心地假设我可以毫无问题地互锁。然而，实际的实施让我失望了。

最大的问题似乎是您需要保证列表推送/弹出将仅使用一个互锁调用。否则，您将留出空间让另一个线程咬入并将事情搞砸。我不确定微软的实现是如何在幕后工作的，并且很想知道更多。

谁能指出我有用的信息（平台和语言无关紧要）？

除此之外，我很想知道是否可以实现无锁向量。这对我有很大的用处:) 干杯！

编辑：阅读herb 的DDJ 文章后，我可以看到一个减少的锁定队列，与我已经拥有的非常相似。但是我注意到最后有一些论文可以使用双重比较和交换（DCAS）操作进行真正的无锁队列。有没有人使用 cmpxchg8b （或 cmpxchg16b ）实现队列？

我现在只是在沉思（还没有阅读论文），但是您可以使用这个系统同时更新头部和尾部指针，从而避免另一个线程在两个原子操作之间跳转的任何问题。但是，您仍然需要获取下一个头指针以针对尾指针进行测试，以查看您是否刚刚修改了尾。当另一个线程准备自己这样做时，如何避免另一个线程更改此信息？这究竟是如何以无锁方式实现的？还是我最好阅读研究论文的不可解读性？;)

我对无锁数据结构很陌生，所以对于我编写的练习（我希望用作）一个有界无锁双端队列（还没有调整大小，只是想让基本案例工作）。我只是想从知道他们在做什么的人那里得到一些确认，以确认我是否有正确的想法和/或如何改进这一点。

我有以 C 语言编写的无锁队列，以链表的形式包含来自多个线程的请求，这些请求发布到单个线程并在单个线程中处理。经过几个小时的压力，我最终让最后一个请求的下一个指针指向自身，这会创建一个无限循环并锁定处理线程。

该应用程序在 Linux 和 Windows 上都运行（并且失败）。我在 Windows 上调试，我COMPARE_EXCHANGE_PTR映射到InterlockedCompareExchangePointer。

这是将请求推送到列表头部的代码，并从多个线程调用：

这是从列表末尾获取请求的代码，仅由处理它们的单个线程调用：

请注意，我没有使用尾指针，因为我想避免在push_request. 但是我怀疑问题可能出在我找到列表末尾的方式上。

有几个地方将请求推送到队列中，但它们通常看起来像这样：

处理请求的代码不仅如此，但本质上是在循环中执行此操作：

我还刚刚添加了一个在每次操作之前和之后检查重复列表的功能，但我担心这个检查会改变时间，所以我永远不会遇到它失败的地方。（我正在等待它在我写这篇文章时打破。）

当我中断挂起程序时，处理程序线程在pop_request标记位置循环。我有一个或多个请求的有效列表，最后一个的 next 指针指向它自己。请求队列通常很短，我从未见过超过 10 个，只有 1 和 3 次我可以在调试器中查看此故障。

我尽可能多地考虑了这一点，得出的结论是，除非我两次推送相同的请求，否则我永远无法在列表中出现循环。我很确定这永远不会发生。我也相当确定（尽管不完全）这不是ABA 问题。

我知道我可能会同时弹出多个请求，但我相信这在这里无关紧要，而且我从未见过这种情况发生。（我也会解决这个问题）

我对如何破坏我的功能进行了长期而艰苦的思考，但我没有看到以循环结束的方法。

所以问题是：有人能找到一种方法来破坏它吗？有人可以证明这不能吗？

最终我会解决这个问题（也许通过使用尾指针或其他解决方案 - 锁定将是一个问题，因为发布的线程不应该被锁定，但我手头确实有一个 RW 锁）但我想确保更改列表实际上解决了我的问题（而不是因为时间不同而不太可能）。

我在想，当多个线程正在读取或写入时，是否可以有一个无锁队列？我见过一个带有无锁队列的实现，它与一个读取和一个写入线程一起工作，但任何一个线程都不会超过一个。是否可以？我不认为它是。可以/有人想证明吗？

我有一些由多个线程读取和更新的数据。读取和写入都必须是原子的。我正在考虑这样做：

通过在每次读取和写入时窃取指向它的指针来保护数据，这应该使其成为线程安全的，但每次访问都需要两条互锁指令。将会有大量的读取和写入，我无法提前判断是否会有更多的读取或更多的写入。

能做到比这更有效吗？这在读取时也会锁定，但由于很可能有更多的写入然后读取，因此优化读取没有意义，除非它不会对写入造成惩罚。

我正在考虑在没有互锁指令（以及序列号）的情况下读取指针，复制数据，然后有一种方法来判断序列号是否已更改，在这种情况下它应该重试。不过，这需要一些内存屏障，我不知道它是否可以提高速度。

- - - 编辑 - - -

谢谢大家，很棒的评论！我实际上并没有运行此代码，但我会在今天晚些时候尝试将当前方法与关键部分进行比较（如果我有时间的话）。我仍在寻找最佳解决方案，因此稍后我将返回更高级的评论。再次感谢！

Say we have a single-producer-thread single-consumer-thread lockless queue, and that the producer may go long periods without producing any data. It would be beneficial to let the consumer thread sleep when there is nothing in the queue (for the power savings and freeing up the CPU for other processes/threads). If the queue were not lockless, the straightforward way to solve this problem is to have the producing thread lock a mutex, do its work, signal a condition variable and unlock, and for the reading thread to lock the mutex, wait on the condition variable, do its reading, then unlock. But if we're using a lockless queue, using a mutex the exact same way would eliminate the performance we gain from using a lockless queue in the first place.

The naive solution is to have the producer after each insertion into the queue lock the mutex, signal the condition variable, then unlock the mutex, keeping the actual work (the insertion into the queue) completely outside the lock, and to have the consumer do the same, locking the mutex, waiting on the condition variable, unlocking it, pulling everything off the queue, then repeat, keeping the reading of the queue outside the lock. There's a race condition here though: between the reader pulling off the queue and going to sleep, the producer may have inserted an item into the queue. Now the reader will go to sleep, and may stay so indefinitely until the producer inserts another item and signals the condition variable again. This means you can occasionally end up with particular items seeming to take a very long time to travel through the queue. If your queue is always constantly active this may not be a problem, but if it were always active you could probably forget the condition variable entirely.

AFAICT the solution is for the producer to behave the same as if it were working with a regular needs-locking queue. It should lock the mutex, insert into the lockless queue, signal the condition variable, unlock. However, the consumer should behave differently. When it wakes, it should unlock the mutex immediately instead of waiting until it's read the queue. Then it should pull as much of the queue as it can and process it. Finally, only when the consumer is thinking of going to sleep, should it lock the mutex, check if there's any data, then if so unlock and process it or if not then wait on the condition variable. This way the mutex is contended less often than it would be with a lockfull queue, but there's no risk of going to sleep with data still left on the queue.

Is this the best way to do it? Are there alternatives?

Note: By 'fastest' I really mean 'fastest without dedicating a core to checking the queue over and over,' but that wouldn't fit in the title ;p

One alternative: Go with the naive solution, but have the consumer wait on the condition variable with a timeout corresponding to the maximum latency you are willing to tolerate for an item traveling through the queue. If the desired timeout is fairly short though, it may be below the minimum wait time for your OS or still consume too much CPU.

我想在两个 pthread 之间实现一个无锁的单生产者、单消费者循环队列；在 C 语言中，在 ARM Linux 上。

队列将保存字节，生产者将 memcpy() 放入，消费者将写入() 到文件中。

认为我可以将头部和尾部偏移量存储在整数中并且一切都会正常工作，这是天真的吗？我想知道诸如编译器优化之类的事情，这意味着我的头/尾写入位于寄存器中并且对其他线程不可见，或者在某处需要内存屏障。

是否有原子|=或和原子或之类的东西？如果没有，在需要线程安全的变量中设置位的推荐技术是什么？（我正在避免锁定）

我根据下面 msdn 文章中概述的原则以及下面的 DXUT 无锁管道代码编写了一个简单的无锁队列：

• http://msdn.microsoft.com/en-us/library/ee418650(v=vs.85).aspx

• http://code.google.com/p/bullet/source/browse/trunk/Demos/DX11ClothDemo/DXUT/Optional/DXUTLockFreePipe.h?r=2127

所以，我有一个生产者/消费者模型设置，我的主线程提供渲染指令，渲染线程使用可用消息并发出相应的 opengl 调用。如果我在每个循环/迭代中让主线程睡眠足够长的时间，一切都会正常工作，但如果我睡眠时间不够长（或根本没有），我会收到访问冲突异常：

我的调用堆栈是：

我不太清楚可能是什么问题。我的无锁队列的代码如下：

我很难调试它，因为从监视窗口看读/写偏移量和缓冲区指针看起来很好。不幸的是，当应用程序中断时，我无法从 BeginRead 函数中查看自动/局部变量。如果有人有使用无锁编程的经验，那么对于这个问题的任何帮助或一般的建议都会非常感激。

我想等待我的应用程序中应该立即发生的事件，所以我不想让我的线程等待并稍后唤醒它。Sleep(0)我想知道使用和硬件暂停指令有什么区别。

我看不到以下程序的 cpu 利用率有任何差异。我的问题不是关于省电的考虑。