Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.programming.threads > #2951

Re: Please check out my algorithm unbounded SPSC (wait free?) queue

Show all headers | View raw

On 2015-04-02, Dmitry Knyaginin <knyaginin@gmail.com> wrote:
> Please check out my algorithm unbounded SPSC (wait free?) queue.
> This implementation is wait free?
> I tested this code on os x, windows, ubuntu.
> Everywhere works!
> ThreadSanitizer detect data race.
>
> C++ code
> http://pastebin.com/fWYjhyyv

Complete junk, I'm afraid.

Your code assumes that you can just magically stick a node into the shared
data structure without worrying about what another thread is doing.

You've written an ordinary doubly-linked list and simply *called*
it "wait-free".

What if two processors execute "last->v = v" at the same time?

What if two processors execute "last->next = tmp" at around the same time?

What if two processors execute "last = tmp" at the same time?

What if you have this scenario:

    Processor A          Processor B

    last->next = tmp
                         last->next = tmp
    last = tmp
                         last = tmp


How about this one:



    Processor A          Processor B

    last->next = tmp
                         last->next = tmp
                         last = tmp
    last = tmp


It is baffling as to how you can neglect such questions in code that
is supposed to be concurrent programming.

Back to comp.programming.threads | Previous | Next — Previous in thread | Find similar | Unroll thread

Thread

Please check out my algorithm unbounded SPSC (wait free?) queue Dmitry Knyaginin <knyaginin@gmail.com> - 2015-04-01 22:36 -0700
  Re: Please check out my algorithm unbounded SPSC (wait free?) queue Kaz Kylheku <kaz@kylheku.com> - 2015-04-02 17:22 +0000

csiph-web