Google Groups no longer supports new Usenet posts or subscriptions. Historical content remains viewable.
Dismiss
Please check out my algorithm unbounded SPSC (wait free?) queue
28 views
Skip to first unread message
Dmitry Knyaginin
Apr 2, 2015, 1:36:38 AM4/2/15
to
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
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
Kaz Kylheku
Apr 2, 2015, 1:22:28 PM4/2/15
to
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.
0 new messages