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

Groups > comp.programming.threads > #771

Re: Lockfree_mpmc version 1.1 -

Show all headers | View raw

"aminer" <aminer68@gmail.com> wrote in message 
news:2a1bad9e-0e91-4c24-8266-5eb0a5f15fd1@z19g2000vbe.googlegroups.com...
>
> Hello,
>
>
> I have added an exponential backoff both in the push() and the pop()
> of the algorithm,
> and now it's giving a good performance under contention.
>
>
> Description
>
> Lock-free MPMC algorithm to handle queue FIFO based on a cicular
> buffer,
> proposed by Dariusz Mazur and modified and enhanced by Amine Moulay
> Ramdane,
> use only single CAS on pop and single CAS on push.

Humm... I think I see a problem with the algorithm. So you basically have 
something like this:
_______________________________________________
producer
------------------
for (;;)
{
P1:    unsigned head = ATOMIC_LOAD(head);
P2:    unsigned tail = ATOMIC_LOAD(tail);
P3:    if (queue_full(head, tail)) return false;
P4:    setobject(head, user_state);
P5:    if (ATOMIC_CAS(&head, head, head + 1)) return true;
}


consumer
------------------
for (;;)
{
C1:    unsigned head = ATOMIC_LOAD(head);
C2:    unsigned tail = ATOMIC_LOAD(tail);
C3:    if (queue_empty(head, tail)) return false;
C4:    user_state = getobject(tail);
C5:    if (ATOMIC_CAS(&tail, tail, tail + 1)) return true;
}
_______________________________________________


Imagine two producer threads PT1, PT2 and one consumer CT1 and the execution 
sequence went as follows:


Scenario:
T1 is trying to push item1 and T2 is trying to push item2 while consumer is 
trying to consume a single item.

Execution Sequence:
PT1: P1
PT1: P2
PT1: P3
PT2: P1
PT2: P2
PT2: P3
PT2: P4 - setobject to item2
PT2: P5 - CAS SUCCESS - item2 pushed!
CT1: C1
CT1: C2
CT1: C3
PT1: P4 - setobject to item1  -- OOPS!
CT1: C4 - getobject - gets item1 Yikes!
CT1: C5 - CAS SUCCESS - item1 popped instead of item2!
PT1: P5 - CAS FAULURE



Well, item2 gets lost forever! ;^(... 

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

Thread

Lockfree_mpmc version 1.1  - aminer <aminer68@gmail.com> - 2011-12-16 11:26 -0800
  Re: Lockfree_mpmc version 1.1 - aminer <aminer68@gmail.com> - 2011-12-16 13:47 -0800
  Re: Lockfree_mpmc version 1.1 - aminer <aminer68@gmail.com> - 2011-12-17 13:44 -0800
  Re: Lockfree_mpmc version 1.1  -  "Chris M. Thomasson" <cristom@charter.net> - 2011-12-21 02:00 -0800

csiph-web