C#中的一种无锁优先级队列
我最近一直在搜索有关如何在C#中构造无锁优先级队列的信息。我甚至还没有找到任何语言的实现，或者关于这个问题的一篇像样的论文。我发现了几篇论文，它们看起来像是副本，或者至少引用了一篇特定的论文，这篇论文实际上并不是一篇关于锁自由优先级队列的论文，尽管它的名字是这样的；它实际上是一篇关于使用细粒度锁的优先级队列的论文。
我从其他地方收到的回应包括“使用单线程”、“你不需要它是无锁的”和“这是不可能的”。这三种回答都是不正确的。
如果有人有关于这方面的信息，我将非常感谢。
回答 2
Stack Overflow用户
发布于 2011-05-15 09:44:17
一般来说，它是一个bad idea to write this kind of code yourself。
但是，如果你真的想写这样的代码，我说从Eric Lippert's book (or blog, as it were) (web archive link)中拿出一个页面，基本上，你可以实现队列，但不是让所有在队列上进行修改的函数修改你调用方法的实例，这些方法返回队列的全新实例。
这在语义上类似于System.String用来维护不变性的模式；所有操作都返回一个新的System.String，原始的不会被修改。
这样做的结果是强制您重新分配每次调用时返回的引用。因为引用的赋值是原子操作，所以不用担心线程安全；您可以保证读/写将是原子的。
但是，这将导致最后获胜的情况；有可能对队列进行了多次修改，但只有最后一个赋值有效，从而丢失了队列中的其他插入。
这可能是可以接受的；否则，您必须围绕引用的赋值和读取使用同步。您仍将拥有一个无锁优先级队列，但是如果您担心线程安全和维护操作的完整性，那么除了将同步问题转移到数据结构之外(这几乎在所有情况下都是一件好事，因为它为您提供了细粒度的显式控制)之外，您什么也没有做。
Stack Overflow用户
发布于 2011-05-15 09:42:47
The Art of Multiprocessor Programming。请参阅第15章-优先级队列。Book是用Java语言编写的，但是可以很容易地转换为C#，因为它们都有GC (这对于书中的大多数实现都很重要)。
https://stackoverflow.com/questions/6005935
复制相似问题
腾讯云开发者
