Mic*_*ray 8 .net c# priority-queue
我最近一直在搜索有关如何在C#中构建无锁优先级队列的信息.我甚至还没有找到任何语言的实现,或者关于这个问题的正确论文.我发现有几篇论文似乎是复制品,或者至少引用了一篇特定的论文,这篇论文实际上并不是一篇关于无锁优先级队列的论文,尽管它的名字不同; 它实际上是一个使用细粒度锁的优先级队列上的文章.
我从其他地方收到的回复包括"使用单个帖子"和"你不需要它免费锁定"和"这是不可能的".所有这三个答案都是不正确的.
如果有人对此有一些信息,我将不胜感激.
但是,如果你真的想写这种代码,我会说从Eric Lippert的书(或博客,原来的)中取一个页面,基本上,你将实现队列,而不是拥有所有修改的函数队列修改您调用方法的实例,该方法返回队列的全新实例.
这在语义上类似于System.String用于维持不变性的模式; 所有操作都返回一个新的System.String,原来没有修改.
结果是您被迫重新分配每次调用时返回的引用.因为引用的赋值是原子操作,所以不关心线程安全性; 保证读/写将是原子的.
但是,这将导致最后的胜利局面; 可能会对队列进行多次修改,但只有最后一次分配将保留,其他插入将丢失到队列中.
这可能是可以接受的; 如果没有,则必须围绕赋值和读取引用使用同步.您仍将拥有无锁优先级队列,但如果您担心线程安全并保持操作的完整性,那么除了移动数据结构之外的同步问题之外什么都没做(几乎所有情况都是如此) ,这是一件好事,因为它为您提供了细粒度的显式控制).