On Tuesday, July 5, 2016 at 12:10:12 AM UTC-7, Dmitry Vyukov wrote: > > On Tue, Jul 5, 2016 at 1:36 AM, Wink Saville <[email protected] > <javascript:>> wrote: > > Dmitry, > > > > I've been using your non-intrusive mpsc fifo > <http://www.1024cores.net/home/lock-free-algorithms/queues/non-intrusive-mpsc-node-based-queue> > > in a project and its been > > working well, but now I've reached the point where I'm stressing it with > > many threads on a multicore CPU and I'm running into at least one > problem. > > To diagnose the problem I've created another implementation for testing > here <https://github.com/winksaville/test-mpscfifo> > > and I'm still seeing a problem. The problem is even though the fifo is > NOT > > empty "rmv" infrequently returns NULL!!! > > > > See the README.md > <https://github.com/winksaville/test-mpscfifo/blob/master/README.md> file > for more information. > > > > Any help much appreciated. > > > Hello Wink, > > This algorithm is not lock-free and is not linearizable. > If a producer is preempted between XCHG and next link update, the > linked list of nodes is temporary broken and all subsequent enqueues > are not visible to consumer until the list is restored. > This condition can be detected by looking at head/tail/next, and then > consumer can spin if necessary. >
I think I now understand (see slides <https://docs.google.com/presentation/d/1t_9JiTZjN6Gqz_eTruAY_GYiUpFA99ChiRRavIkoHCk/edit?usp=sharing> ). In mpsq_push from your algorithm <http://www.1024cores.net/home/lock-free-algorithms/queues/non-intrusive-mpsc-node-based-queue> you state in the "Disadvantages" that "Push function is blocking wrt consumer". So I now see if a producer, T1, is preempted after the XCHG(&self->head, n); and before the prev->next = n (I've marked below) the consumer is blocked: void mpscq_push(mpscq_t* self, mpscq_node_t* n) > { > n->next = 0; > mpscq_node_t* prev = XCHG(&self->head, n); // serialization-point wrt > producers, acquire-release > // (*) If producer is preempted here, consumer is "blocked" > prev->next = n; // serialization-point wrt consumer, release > } But in your code consumer isn't "blocked", I think the code should be something like: mpscq_node_t* mpscq_pop(mpscq_t* self) { mpscq_node_t* tail = self->tail; mpscq_node_t* next = tail->next; // serialization-point wrt producers, acquire if (next) { // Not empty self->tail = next; tail->state = next->state; return tail; } else if (tail == self->head) { // Empty return 0; } else { // Bad luck producer was preempted while ((next = tail->next) == NULL) { sched_yield(); } self->tail = next; tail->state = next->state; return tail; } } -- --- 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 [email protected]. To view this discussion on the web visit https://groups.google.com/d/msgid/lock-free/456a739f-e52e-4ab3-abab-04177f85dca0%40googlegroups.com. For more options, visit https://groups.google.com/d/optout.
