lockfree_buffer.md

Initial configuration:

• queue with capacity for 3 elements
• two producers p1, p2 and one consumer c1
• queue contains one element "x" at the first position
• Thread p1 wants to insert an element "Y"

Pointers and queue content at initial configuration:

 front
 |
[x, ., .]
 |
 back

1. p1 checks whether the queue is full (if (rear == front-1){...})

---> Result is that the queue is not full. p1 continues trying to insert an element

2. p2 inserts elements "a" and "b"

 front
 |
[x, a, b]
       |
       back

3. c1 pops element "x"

    front
    |
[., a, b]
       |
       back

4. p2 inserts element "c"

    front
    |
[c, a, b]
 |
 back

5. p1 tries to manually test&set "back" from 0 to 1

---> Succeeds, because back (again) contains the value 0

    front
    |
[c, a, b]
    |
    back

ERROR: The queue pointers now show that the list only contains one element "a"

Analysis

In order to prevent this kind of ABA-Problem, it would be required to test&set both "front" and "back" simultaineously. Since this isn't possible using C++ Atomics, I think that the task has no correct solution.