On Tue, Jul 5, 2016 at 9:50 PM, Wink Saville <[email protected]> wrote:
>
>
> 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]> wrote:
>> > Dmitry,
>> >
>> > I've been using your non-intrusive mpsc fifo 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
>> > 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 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).
>
> In mpsq_push from your algorithm 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:
It may be that way, but it does not always need to be. If caller has
nothing else to do then it will probably spin himself, if he has
something else to do then he better do that something else rather than
spin in the queue.
> 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.
--
Dmitry Vyukov
All about lockfree/waitfree algorithms, multicore, scalability,
parallel computing and related topics:
http://www.1024cores.net
--
---
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/CAEeQi3vM8%2Bs42HmRqW%2BhawUvpVcWTuWaGt77Y97YyJ47fgdZ%3Dw%40mail.gmail.com.
For more options, visit https://groups.google.com/d/optout.
