AtomicStampedReference

Creating an AtomicStampedReference
- Creating a Typed AtomicStampedReference
Getting the AtomicStampedReference Reference
Getting the AtomicStampedReference Stamp
Getting Reference and Stamp Atomically
Setting the AtomicStampedReference Reference
Comparing and Setting the AtomicStampedReference Reference
AtomicStampedReference and the A-B-A Problem

Jakob Jenkov
Last update: 2021-09-28

The AtomicStampedReference class provides an object reference variable which can be read and written atomically. By atomic is meant that multiple threads attempting to change the same AtomicStampedReference will not make the AtomicStampedReference end up in an inconsistent state.

The AtomicStampedReference is different from the AtomicReference in that the AtomicStampedReference keeps both an object reference and a stamp internally. The reference and stamp can be swapped using a single atomic compare-and-swap operation, via the compareAndSet() method.

The AtomicStampedReference is designed to be able to solve the A-B-A problem which is not possible to solve with an AtomicReference alone. The A-B-A problem is explained later in this text.

Creating an AtomicStampedReference

You can create an AtomicStampedReference instance like this:

Object initialRef   = null;
int    initialStamp = 0;

AtomicStampedReference atomicStampedReference =
    new AtomicStampedReference(intialRef, initialStamp);

Creating a Typed AtomicStampedReference

You can use Java generics to create a typed AtomicStampedReference. Here is a typed AtomicStampedReference example:

String initialRef   = null;
int    initialStamp = 0;

AtomicStampedReference<String> atomicStampedReference =
    new AtomicStampedReference<String>(
        initialRef, initialStamp
    );

The Java AtomicStampedReference created in this example will only accept references to String instances. It is recommended to always use a generic type with an AtomicStampedReference, if you know the type of the reference you will keep in it.

Getting the AtomicStampedReference Reference

You can get the reference stored in an AtomicStampedReference using the AtomicStampedReference's getReference() method. If you have an untyped AtomicStampedReference then the getReference() method returns an Object reference. If you have a typed AtomicStampedReference then getReference() returns a reference to the type you declared on the AtomicStampedReference variable when you created it.

Here is first an untyped AtomicStampedReference getReference() example:

String initialRef = "first text";

AtomicStampedReference atomicStampedReference = 
    
    new AtomicStampedReference(initialRef, 0);

String reference = (String) 
    atomicStampedReference.getReference();

Notice how it is necessary to cast the reference returned by getReference() to a String because getReference() returns an Object reference when the AtomicStampedReference is untyped.

Here is a typed AtomicStampedReference example:

String initialRef = "first text";

AtomicStampedReference<String> atomicStampedReference =
    new AtomicStampedReference<String>(
        initialRef, 0
    );

String reference = 
    atomicStampedReference.getReference();

Notice how it is no longer necessary to cast the referenced returned by getReference() because the compiler knows it will return a String reference.

Getting the AtomicStampedReference Stamp

The AtomicStampedReference also contains a getStamp() method which can be used to obtain the internally stored stamp. Here is a getStamp() example:

String initialRef = "first text";

AtomicStampedReference<String> atomicStampedReference =
    new AtomicStampedReference<>(initialRef, 0);

int stamp = atomicStampedReference.getStamp();

Getting Reference and Stamp Atomically

You can obtain both reference and stamp from an AtomicStampedReference in a single, atomic operation using the get() method. The get() method returns the reference as return value from the method. The stamp is inserted into an int[] array that is passed as parameter to the get() method. Here is a get() example:

String initialRef   = "text";
String initialStamp = 0;

AtomicStampedReference<String> atomicStampedReference =
    new AtomicStampedReference<>(
        initialRef, initialStamp
    );

int[] stampHolder = new int[1];
String ref = atomicStampedReference.get(stampHolder);

System.out.println("ref = " + ref);
System.out.println("stamp = " + stampHolder[0]);

Being able to obtain both reference and stamp as a single atomic operation is important for some types of concurrent algorithms.

Setting the AtomicStampedReference Reference

You can set the reference stored in an AtomicStampedReference instance using its set() method. In an untyped AtomicStampedReference instance the set() method takes an Object reference as first parameter. In a typed AtomicStampedReference the set() method takes whatever type as parameter you declared as its type when you declared the AtomicStampedReference.

Here is an AtomicStampedReference set() example:

AtomicStampedReference<String> atomicStampedReference =
     new AtomicStampedReference<>(null, 0);


String newRef = "New object referenced";
int    newStamp = 1;

atomicStampedReference.set(newRef, newStamp);

There is no difference to see in the use of the set() method for an untyped or typed reference. The only real difference you will experience is that the compiler will restrict the types you can set on a typed AtomicStampedReference.

Comparing and Setting the AtomicStampedReference Reference

The AtomicStampedReference class contains a useful method named compareAndSet(). The compareAndSet() method can compare the reference stored in the AtomicStampedReference instance with an expected reference, and the stored stamp with an expected stamp, and if they two references and stamps are the same (not equal as in equals() but same as in ==), then a new reference can be set on the AtomicStampedReference instance.

If compareAndSet() sets a new reference in the AtomicStampedReference the compareAndSet() method returns true. Otherwise compareAndSet() returns false.

Here is an AtomicStampedReference compareAndSet() example:

String initialRef   = "initial value referenced";
int    initialStamp = 0;

AtomicStampedReference<String> atomicStringReference =
    new AtomicStampedReference<String>(
        initialRef, initialStamp
    );

String newRef   = "new value referenced";
int    newStamp = initialStamp + 1;

boolean exchanged = atomicStringReference
    .compareAndSet(
        initialRef, newRef, 
        initialStamp, newStamp);
System.out.println("exchanged: " + exchanged);  //true

exchanged = atomicStringReference
    .compareAndSet(
        initialRef, "new string", 
        newStamp, newStamp + 1);
System.out.println("exchanged: " + exchanged);  //false

exchanged = atomicStringReference
    .compareAndSet(
        newRef, "new string", 
        initialStamp, newStamp + 1);
System.out.println("exchanged: " + exchanged);  //false

exchanged = atomicStringReference
    .compareAndSet(
        newRef, "new string", 
        newStamp, newStamp + 1);
System.out.println("exchanged: " + exchanged);  //true

This example first creates an AtomicStampedReference and then uses compareAndSet() to swap the reference and stamp.

After the first compareAndSet() call the example attempts to swap the reference and stamp two times without success. The first time the initialRef is passed as expected reference, but the internally stored reference is newRef at this time, so the compareAndSet() call fails. The second time the initialStamp is passed as the expected stamp, but the internally stored stamp is newStamp at this time, so the compareAndSet() call fails.

The final compareAndSet() call will succeed, because the expected reference is newRef and the expected stamp is newStamp.

AtomicStampedReference and the A-B-A Problem

The AtomicStampedReference is designed to solve the A-B-A problem. The A-B-A problem is when a reference is changed from pointing to A, then to B and then back to A.

When using compare-and-swap operations to change a reference atomically, and making sure that only one thread can change the reference from an old reference to a new, detecting the A-B-A situation is impossible.

The A-B-A problem can occur in non-blocking algorithms. Non-blocking algorithms often use a reference to an ongoing modification to the guarded data structure, to signal to other threads that a modification is currently ongoing. If thread 1 sees that there is no ongoing modification (reference points to null), another thread may submit a modification (reference is now non-null), complete the modification and swap the reference back to null without thread 1 detecting it. Exactly how the A-B-A problem occurs in non-blocking algorithms is explained in more detail in my tutorial about non-blocking algorithms.

By using an AtomicStampedReference instead of an AtomicReference it is possible to detect the A-B-A situation. Thread 1 can copy the reference and stamp out of the AtomicStampedReference atomically using get(). If another thread changes the reference from A to B and then back to A, then the stamp will have changed (provided threads update the stamp sensibly - e.g increment it).

The code below shows how to detect the A-B-A situation using the AtomicStampedReference:

int[] stampHolder = new int[1];
Object ref = atomicStampedReference.get(stampHolder);

if(ref == null){
    //prepare optimistic modification
}

//if another thread changes the
//reference and stamp here,
//it can be detected

int[] stampHolder2 = new int[1];
Object ref2 = atomicStampedReference.get(stampHolder);

if(ref == ref2 && stampHolder[0] == stampHolder2[0]){
    //no modification since 
    //optimistic modification was prepared

} else {
    //retry from scratch.
}

Next: AtomicIntegerArray

Tweet
	Jakob Jenkov