如何实现"Front"?无锁并发队列中的方法? [英] How to implement "Front" method in a lock-free concurrent queue?

问题描述

我正在尝试实现并发无锁队列.我正在密切关注本文: https://www.cs.rochester .edu/u/scott/papers/1996_PODC_queues.pdf 但是本文没有提供暴露Front()或Back()方法的安全方法.有Enqueue()和Dequeue()方法. (本文详细介绍了无锁版本以及带锁的版本，我对前者感兴趣).现在让我直接解决这个问题.在进行所有安全检查(类似于入队)之后，Front()函数的紧缩归结为:

I am trying to implement a concurrent lock-free queue. I am closely following this paper : https://www.cs.rochester.edu/u/scott/papers/1996_PODC_queues.pdf But this paper doesn't provide a safe way to expose Front() or Back() method. Enqueue() and Dequeue() methods are there. ( The paper elaborates a lock-free version and also a version with locks, I am interested in the former). Let me get the question straight now. After all the safety checks (analogous to Enqueue), the crunch of the Front() function boils down to this:

1. if(local_copy_of_head == curr_shared_head) {  // Let's say I read this atomically. The equality means the head didn't move since the time I copied.
2.   return local_copy_of_head;
3. }

我想说明的是，尽管这是有关如何实现Front()函数的问题，但是我主要对如何将上述代码段重构为没有任何锁的原子块感兴趣. 我担心的是，如果Thread1在执行第1行后被中断(我已经读到了原子的意思)，那么第二个线程清空了队列，Thread1被重新安排并返回了陈旧的结果.

I want to make it clear that although this is a question about how to implement Front() function, but I am mainly interested in how to refactor the above snippet into an atomic block without any lock. My concern is , if Thread1 gets interrupted after executing line no 1 ( I read this atomically let's say), then a second thread empties the queue, Thread1 gets rescheduled and returns a stale result.

推荐答案

您不能.您可以制作一个糟糕的版本，该版本可以工作很多次，但总的来说是失败的.要消除无锁的奥秘，请用上一个术语繁忙等待"来代替它.更加恰当地等待忙碌可以捕获消耗CPU资源的选择，希望可以正确检测到您的比赛结束状况，从而使结果保持一致.

You can't. You can make a crappy version that works a bunch of times, but in general is a fail. To peel the mystique of lock-free, replace it by its previous term busy-waiting. Busy-waiting more appropriately captures the choice of consuming cpu resources in the hope that your race end condition can be appropriately detected, so the results are consistent.

通过放弃队列的头(Front)，您不知道该客户端在承诺吸收它之前可以使用多长时间(Dequeue，sic:这不是dequeue的意思).这样，您的Front函数就只能是设计欠佳的队列实现的前端.

By giving away the head of the queue (Front), you have no idea how long the client of this might use it before committing to absorbing it (Dequeue, sic: that is not what dequeue means). As such, your Front function can never be anything but a front for a poorly devised queue implementation.

从来没有很长一段时间.好的，不是永远，但是，它需要一个伴随函数(Absorb)，该函数可以告诉我们，由于调用了相应的Front，因此队列头的这种吸收是队列头上的唯一操作.因此队列处于相同状态.如果不是，则必须向调用方退回故障，在此过程中，它必须回滚进行中的任何操作以反映此故障.

Never is a pretty long time. Ok, not never, but, it needs a companion function (Absorb) which can tell that this absorption of the head of the queue is the only operation on the head of the queue since the corresponding Front was called; thus the queue is in the same state. If it was not, the caller has to be handed back a failure, in which it has to roll back whatever operation was in progress to reflect this failure.

好吧，不是永远不会，但是已经完成的一切只是将事务语义上移了一个层次，向设计者暗示也许设计有点欠缺.因此，您有一个无事务的队列.我们中有些人称其为增量.

Ok, so not never, but all that has been accomplished is to move the transaction semantics up a level, a hint to the designer that maybe the design is a bit lacking. So you have a transactionless queue. Some of us used to call that increment.

这篇关于如何实现"Front"?无锁并发队列中的方法?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！