On Thu, Nov 3, 2016 at 8:36 PM, Miral Mirality <uec...@gmail.com> wrote: > Hi Dmitry, > > Pondering the bounded MPMC queue at > http://www.1024cores.net/home/lock-free-algorithms/queues/bounded-mpmc-queue > (very clever design, by the way, as I've said before). > > In the case where enqueue has made it all the way down to the copying of > data_ (ie. found and reserved a cell, but not yet filled it or bumped the > cell's next-sequence). If this copy throws an exception, as currently > implemented it leaves the queue permanently broken (enqueue will skip past > the cell and fill in later cells until the queue fills, and dequeue will > halt and return "no more items" once it reaches that cell). > > Is there a multi-producer-safe way to "undo" the cell reservation made in > the first part, to unblock the consumers without actually dequeuing an > invalid item? > > The best I've come up with thus far is to add an extra "invalid" bool flag > to cell_t, which is set true if the copy throws before still updating > sequence_; if dequeue finds a cell with the flag set then it resets it and > continues searching. I can't help wonder if there's a better way, though. > > (Using a reserved bit in sequence_ would also work, without the extra bool > storage, but halves the max queue size and complicates the wraparound. It > might technically be safer that way since it puts it under atomic > protection; but I'm assuming a non-atomic bool field is safe due to rarity > of use, x86 arch, and being stored prior to a nearby memory_order_release > store and loaded after a corresponding nearby memory_order_acquire load.)
Hi Miral, The best solution would be to require copying of elements to not throw. One way to achieve that is to create a copy of the element beforehand and then use moving constructor to move it to the queue. Move constructors should not allocate. Otherwise, I don't see any better solution than what you come up with -- add a flag that an element is broken and should be skipped during consumption. Whether this flag is a separate bool or a bit in sequence number looks irrelevant from algorithmic point of view. Accesses to the bool variable should be properly synchronized by acquire/release on the sequence variable, we can simply consider the bool to be part of user data. I don't see a better way to "undo" enqueue. You may also check concurrent_queue in Intel Threading Building Blocks (TBB) library. As far as I remember they also handle exceptions in some way. -- --- You received this message because you are subscribed to the Google Groups "Scalable Synchronization Algorithms" group. To unsubscribe from this group and stop receiving emails from it, send an email to lock-free+unsubscr...@googlegroups.com. To view this discussion on the web visit https://groups.google.com/d/msgid/lock-free/CAEeQi3sBL1m-wB7TX%2BDDed1%3Dx%2B210BY4BrWB0rXwp3p%3DabXmow%40mail.gmail.com. For more options, visit https://groups.google.com/d/optout.
