C# 中的无锁优先级队列
我最近一直在寻找有关如何在 C# 中构造无锁优先级队列的信息。我什至还没有找到任何语言的实现，或者关于此事的像样的论文。我发现了几篇论文，它们看起来像是副本，或者至少引用了一篇特定的论文，尽管它的名字，但实际上并不是一篇关于无锁优先级队列的论文；它实际上是一篇关于使用细粒度锁的优先级队列的论文。
我从其他地方收到的回复包括“使用单线程”和“你不需要它是无锁的”和“这是不可能的”。这三个回答都是不正确的。
如果有人有这方面的信息，我将不胜感激。
I have been searching lately for information on how to construct a lock-free priority queue in C#. I have yet to even find an implementation in any language, or a decent paper on the matter. I have found several papers which appear to be copies or at least referencing one particular paper which is not actually a paper on lock free priority queues, despite its name; it is in fact a paper on a priority queue which uses fine grained locks.
The responses I have been receiving from elsewhere include "use a single thread" and "you do not need it to be lock free" and "it is impossible". All three of these responses are incorrect.
If someone has some information on this, I would greatly appreciate it.
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（2）
一般来说，自己编写这种代码是一个坏主意。
但是，如果您真的想编写这种代码，我建议您从Eric Lippert 的书（或博客） (web archive link)，基本上，您将实现队列，但不是让所有对队列进行修改的函数修改您调用的实例方法上，该方法返回队列的全新实例。
这在语义上类似于 System.String 用于维护不变性的模式；所有操作都返回一个新的
System.String，原来的没有修改。这样做的结果是您被迫重新分配每次调用时返回的引用。因为引用的赋值是原子操作，所以不用担心线程安全；您可以保证读/写将是原子的。
然而，这将导致最后获胜的局面；可能会对队列进行多次修改，但只有最后一个分配会保留，从而丢失队列中的其他插入。
这可能是可以接受的；如果没有，您必须在引用的分配和读取周围使用同步。您仍然会有一个无锁优先级队列，但是如果您担心线程安全和维护操作的完整性，那么您除了将同步的关注移到数据结构之外之外什么也没做（这几乎是所有情况） ，是一件好事，因为它为您提供了细粒度的显式控制）。
Generally, it's a bad idea to write this kind of code yourself.
However, if you really want to write this kind of code, I say take a page from Eric Lippert's book (or blog, as it were) (web archive link), where basically, you would implement the queue but instead of having all the functions that make modifications on the queue modify the instance you call the method on, the methods return completely new instances of the queue.
This is semantically similar to the pattern that
System.Stringuses to maintain immutability; all operations return a newSystem.String, the original is not modified.The result of this is that you are forced to reassign the reference returned on every call. Because the assignments of references are atomic operations, there is no concern about thread-safety; you are guaranteed that the reads/writes will be atomic.
However, this will result in a last-in-wins situation; it's possible that multiple modifications are being made to the queue, but only the last assignment will hold, losing the other insertions into the queue.
This might be acceptable; if not, you have to use synchronization around the assignment and reading of the reference. You will still have a lock-free-priority queue, but if you have concerns about thread-safety and maintaining the integrity of the operations, you have done nothing but move the concern about synchronization outside of the data structure (which is almost all cases, is a good thing, as it gives you fine-grained explicit control).
多处理器编程的艺术。请参阅第 15 章 - 优先级队列。本书是用 Java 编写的，但可以轻松翻译为 C#，因为它们都有 GC（这对于本书中的大多数实现都很重要）。
The Art of Multiprocessor Programming. Look at Chapter 15 - Priority Queues. Book is in Java, but can be easily translated to C# since they both have GC (which is important for most implementations in the book).