Fix ABA problem in CAS.

It is important to note that there are two common ABA problems that require specific examples.

The use of CAS can be referred to:

  • Source | concurrent a flower ConcurrentLinkedQueue “false”
  • Source | use FutureTask correct posture
  • Source | concurrent flower already and AQS (1) : the lock and unlock
  • Source | concurrent flower already and AQS (3) : Condition

1 definition

1.1 Basic ABA problems

In the CAS algorithm, data needs to be fetched from memory at one point (done by the user) and compared and replaced at the next point (done by the CPU, which is atomic). This time difference will lead to changes in the data.

Assume the following sequence of events:

  1. Thread 1 fetches A from memory location V.
  2. Thread 2 fetches A from position V.
  3. Thread 2 does something, writing B to position V.
  4. Thread 2 writes A again to position V.
  5. Thread 1 performs the CAS operation and finds that position V is still A. The operation succeeds.

Even though the CAS operation for thread 1 was successful, it doesn’t mean that the process was problem-free — for thread 1, the modification for thread 2 was lost.

1.2 ABA problems associated with memory models

In memory models without garbage collection (such as C++), programmers can free up memory at will.

Assume the following sequence of events:

  1. Thread 1 fetches A from memory location V, which points to memory location W.
  2. Thread 2 fetches A from position V.
  3. Thread 2 does something that frees the memory pointed to by A.
  4. Thread 2 reapplies for memory and stores location W into the contents of C.
  5. Thread 2 writes memory location W to location V.
  6. Thread 1 performs the CAS operation and finds that location V is still pointed to by A, that is, memory location W. The operation succeeds

This is more serious than problem 1.1, the actual content has been modified, but thread 1 is not aware of thread 2’s changes.

Even more, if thread 2 only frees the memory pointed to by A, and thread 1 has to access the contents of A before CAS, thread 1 will access A wild pointer.

2, for example,

2.1 Examples of basic ABA problems

If position V stores the head of the linked list, then in the linked list where ABA problems occurred, the original head was node1, and thread 2 changed the head twice, most likely by first changing the head to node2 and then reassigning node1 (which in C++ is also a reassigned node node3). Insert the table header to become the new header.

For thread 1, the header is still node1 (or the value of the header, because in C++ the contents might be node3 even though the address is the same), the CAS operation succeeds, but the status of the child list after the header is unpredictable.

Picture the diagram.

2.2 Examples of ABA problems related to memory models

The problem is clearly defined.

3 to solve

Java’s garbage collection mechanism has helped us solve problem 1.2; As for problem 1.1, add the version number to solve it.

3.1 AtomicStampedReference

In addition to the object value, an AtomicStampedReference maintains a state stamp inside it. The status stamp can be analogous to the time stamp, which is an integer value. Every time the object value is modified, the state stamp should also be modified to distinguish different states of the same object value. When AtomicStampedReference sets the object value, the object value and state stamp must meet the expected value. The write is successful.

Several apis for AtomicStampedReference add information about timestamps to the AtomicReference:

// The comparison setting parameters are: expected write new value expected timestamp New timestamp
public boolean compareAndSet(V expectedReference, V newReference, 
    int expectedStamp, int newStamp)
// Get the current object reference
public V getReference(a)
// Get the current timestamp
public int getStamp(a)
// Sets the current object reference and timestamp
public void set(V newReference, int newStamp)
Copy the code

3.2 AtomicMarkableReference

An AtomicMarkableReference has a similar function to an AtomicStampedReference, but an AtomicMarkableReference describes a simpler yes-or-no relationship. The definition of it is to simplify the state stamp to true | false. As follows:

public final static AtomicMarkableReference<String> ATOMIC_MARKABLE_REFERENCE 
    = new AtomicMarkableReference<>("abc" , false); 
Copy the code

Operation:

ATOMIC_MARKABLE_REFERENCE.compareAndSet("abc"."abc2".false.true);
Copy the code

This article is published under the Creative Commons Attribution – Share alike 4.0 International License. The attribution and link to this article must be reserved.