On Thu, May 18, 2017 at 6:48 AM, Jay Miller <jay.mil...@gmail.com> wrote:
> Also it turns out I can consistently pass my test is I only replace the
> second // HERE with the spin_pop (the one after pushing _stub).
>
>
> On Wednesday, May 17, 2017 at 8:31:59 PM UTC-5, Jay Miller wrote:
>>
>> I have an C++ implementation of the MPSC queue. Under normal
>> circumstances it works correctly, but under heavy load it skips nodes when
>> releasing. That is, in a test of many writers and a single reader, nodes
>> are popped in the same order each thread wrote them, but sometimes a node
>> does not get returned at all. If anyone can see what is wrong with this I
>> would appreciate it very much.
>>
>> class Node
>> {
>> public:
>> // Atomic here as a shortcut for placing
>> // memory fences. Assignment is an atomic
>> // store with an acquire and release fence
>> std::atomic<Node*> next;
>> };
>>
>> template <typename T>
>> class MpscQueue
>> {
>> public:
>> MpscQueue()
>> : _head(&_stub)
>> , _tail(&_stub)
>> {
>> _stub.next = nullptr;
>> }
>>
>> void push(T* obj)
>> {
>> _push(obj);
>> }
>>
>> T* pop()
>> {
>> auto tail = _tail;
>> Node* next = tail->next;
>>
>> if (tail == &_stub)
>> {
>> if (!next)
>> {
>> return nullptr;
>> }
>> tail = next;
>> next = next->next;
>> }
>>
>> if (next)
>> {
>> _tail = next;
>> return static_cast<T*>(tail);
>> }
>>
>> if (tail != _head)
>> {
>> return nullptr; // HERE
>> }
>>
>> _push(&_stub);
>>
>> next = tail->next;
>> if (next)
>> {
>> _tail = next;
>> return static_cast<T*>(tail);
>> }
>>
>> return nullptr; // HERE
>> }
>>
>> private:
>> void _push(Node* node)
>> {
>> node->next = nullptr;
>> auto prev = _head.exchange(node);
>> prev->next = node;
>> }
>> std::atomic<Node*> _head;
>>
>> Node* _tail;
>> Node _stub;
>> };
>>
>>
>> As a clue, if I replace the lines above marked HERE with a call to this
>> function my tests always pass, except one time in one configuration where it
>> entered a continuous loop.
>>
>> T* spin_pop(Node* tail)
>> {
>> do
>> {
>> _tail = tail->next;
>> } while (!_tail);
>>
>>
>> return static_cast<T*>(tail);
>> }
>
Hi Jay,
This algorithm is not linearizable. If push operation is preempted
between exchange and update of the next link, the linked list of nodes
is broken and there is no way pop can reach any of the subsequent
nodes (even if their push'es are completely finished). I guess that's
what you see.
--
---
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/CAEeQi3tXuUuii5XZXoK2ZruRuBxFmHEmtGnmj7LQkZ%2Bmf76%3DEQ%40mail.gmail.com.
For more options, visit https://groups.google.com/d/optout.
