Is it safe to use test_and_set stream?

Question

I was thinking about how to implement an unsecured personal list. And frankly, I don’t see many bulletproof ways to do this. Even more reliable ways to use CAS end up with some degree of problem.

Answer 1

You're right. In C ++, function arguments are evaluated in any order, but of course, your compiler does not know that root->next is an atomic operation in your sequence.

Consider two threads calling pop() : One thread evaluates root->next , and the other evaluates root->next , and both calls test_and_set() . Now you just pulled out one node.

Answer 2

Two things: (1) test & set only has a consensus number of 2; for such a weak synchronization primitive, it is enough to simply use read / write memory barriers without requiring the overhead of specialized instructions; (2) the ABA problem is a real problem with very few solutions; however, with CAS (cmpxchg8b on 32-bit systems and cmpxchg16b on 64-bit systems for x86 / -64), there is enough space at the top of the register to store such a large time stamp that ABA never happens in practice (it took even quite far-fetched settings so that one thread is delayed for several days or weeks, and then wakes up at exactly the right moment).

I think that you are trying to implement an unblocked queue (not a list). Queues are much easier to implement than lists. The papers “Optimistic Approach to FIFO Messy Queues” by Edi Lazan-Moses and Nir Shawit and “Simple, Fast and Practical Non-Blocking and Blocking Parallel Queue Algorithms” Maged M. Michael and Michael L. Scott are both very informative and simple approaches for implementing a queue without blocking .

However, if you insist on a blocked linked list, consider implementing Michael Fomichev and Eric Rupert in Lock-Free Linked Lists and Skip Lists. You can also look into a dynamic array without blocking Damian Dechev (there is a link to Wikipedia).

Answer 3

In both versions of pop :

 T *pop() { T *p = root; root = root->next; return p; } 

and

 T *pop() { return __sync_lock_test_and_set(&root, root->next); } 

You already have an error, which is that you are not checking that your list / stack is not empty before reading from the supposed root of the node.

This binds the issue you mentioned about the need to dereference root in order to move on to the next before test_and_set even happens. It essentially becomes a test_and_then_test_and_set test, where and_then means more than one step is required.

Your first version of pop should be:

 T *pop() { T *p = root; if (root) { root = root->next; } return p; } 

and, as I am sure, you can see that this adds even more steps to the mix.