3

Suppose I have a list, and I want to use a test_and_set operation a parameter of which is the calculation of some pointer address l->a.next->next. This, I think, will not be atomic, and the test_and_set will be useless. Is there a way to calculate that pointer value atomically so that the TAS will work atomically?

Dervin Thunk
  • 19,515
  • 28
  • 127
  • 217
  • There are multiple differences there, so I don't think that what you want can be done without either locks or some sort of double CAS usage. – Evan Teran Feb 28 '13 at 19:54

1 Answers1

2

You probably mean CAS (more useful).

In general: yes it is often used to implement transactional or wait-free datastructures,

Buf first things first: let's separate address-calculations from atomic operations on an address, you first get the specific address at which something should be swapped, the CAS does not care how you got there.

Specifically you should first let each of your threads navigate the list until they find a place where they want to replace a next-pointer, then they can try-repeat this by using CAS. It depends on your scenario whether the thread has to re-walk the list for the retry.

The tricky part is actually at a different place in the code: where you free (or re-use) the list-nodes. In general you have to assume that you cannot re-use or free node-chains that were disconnected from your list ever. In practice there are heursitics you can use but this depends on your use-case.

Bernd Elkemann
  • 23,242
  • 4
  • 37
  • 66
  • It should be noted that While the technique you show is generally how lock free data structures are created. As described, it suffers from the ABA problem. Look into a DCAS (http://en.wikipedia.org/wiki/Double_compare-and-swap) to deal with that. – Evan Teran Feb 28 '13 at 20:58
  • @EvanTeran dCAS is not really available. Good that there are other ways to solve the problem. – Bernd Elkemann Feb 28 '13 at 21:17