Guide to AtomicMarkableReference

1. Overview

In this tutorial, we’ll dive into the details of the AtomicMarkableReference class from the java.util.concurrent.atomic package.

Next, we’ll walk through the API methods of the class, and we’ll see how we can use the AtomicMarkableReference class in practice.

2. Purpose

AtomicMarkableReference is a generic class that encapsulates both a reference to an Object and a boolean flag. These two fields are coupled together and can be updated atomically, either together or individually.

AtomicMarkableReference could also be a possible remedy against the ABA problem. 

3. Implementation

Let’s take a more in-depth look at the AtomicMarkableReference class implementation:

public class AtomicMarkableReference<V> {

    private static class Pair<T> {
        final T reference;
        final boolean mark;
        private Pair(T reference, boolean mark) {
            this.reference = reference;
            this.mark = mark;
        }
        static <T> Pair<T> of(T reference, boolean mark) {
            return new Pair<T>(reference, mark);
        }
    }

    private volatile Pair<V> pair;

    // ...
}

Notice that AtomicMarkableReference has a static nested class Pair that holds the reference and flag.

Also, we see that both variables are final. As a result, whenever we want to modify these variables, a new instance of the Pair class is created, and the old instance is replaced.

4. Methods

First of all, to discover AtomicMarkableReference‘s usefulness, let’s start by creating an Employee POJO:

class Employee {
    private int id;
    private String name;
    
    // constructor & getters & setters
}

Now, we can create an instance of the AtomicMarkableReference class:

AtomicMarkableReference<Employee> employeeNode 
  = new AtomicMarkableReference<>(new Employee(123, "Mike"), true);

For our examples, let’s suppose that our AtomicMarkableReference instance represents a node in an organization chart. It is holding the two variables: the reference to an instance of the Employee class and a mark that indicates if the employee is active or has left the company.

AtomicMarkableReference comes with several methods to update or retrieve either one or both fields. Let’s have a look at these methods one by one:

4.1. getReference()

We use the getReference method to return the current value of the reference variable:

Employee employee = new Employee(123, "Mike");
AtomicMarkableReference<Employee> employeeNode = new AtomicMarkableReference<>(employee, true);

Assertions.assertEquals(employee, employeeNode.getReference());

4.2. isMarked()

To get the value of the mark variable, we should call the isMarked method:

Employee employee = new Employee(123, "Mike");
AtomicMarkableReference<Employee> employeeNode = new AtomicMarkableReference<>(employee, true);

Assertions.assertTrue(employeeNode.isMarked());

4.3. get()

Next, we use the get method when we want to retrieve both the current reference and the current mark. To get the mark, we should send as a parameter a boolean array of size at least one, which will store at index 0 the current value of the boolean variable. At the same time, the method will return the current value of the reference:

Employee employee = new Employee(123, "Mike");
AtomicMarkableReference<Employee> employeeNode = new AtomicMarkableReference<>(employee, true);

boolean[] markHolder = new boolean[1];
Employee currentEmployee = employeeNode.get(markHolder);

Assertions.assertEquals(employee, currentEmployee);
Assertions.assertTrue(markHolder[0]);

This way of getting both the reference and the mark fields is a little odd because the inner Pair class is not exposed to the caller.

Java doesn’t have a generic Pair<T, U> class in its public API. The main reason for this is that we may be tempted to overuse it instead of creating distinct types.

4.4. set()

In case we want to update both the reference and the mark fields unconditionally, we should use the set method. If at least one of the values sent as a parameter is different, the reference and the mark will be updated:

Employee employee = new Employee(123, "Mike");
AtomicMarkableReference<Employee> employeeNode = new AtomicMarkableReference<>(employee, true);

Employee newEmployee = new Employee(124, "John");
employeeNode.set(newEmployee, false);
        
Assertions.assertEquals(newEmployee, employeeNode.getReference());
Assertions.assertFalse(employeeNode.isMarked());

4.5. compareAndSet()

Next, the compareAndSet method updates both the reference and the mark to the given updated values if the current reference is equal to the expected reference, and the current mark is equal to the expected mark.

Now, let’s see how we can update both reference and mark fields using compareAndSet:

Employee employee = new Employee(123, "Mike");
AtomicMarkableReference<Employee> employeeNode = new AtomicMarkableReference<>(employee, true);
Employee newEmployee = new Employee(124, "John");

Assertions.assertTrue(employeeNode.compareAndSet(employee, newEmployee, true, false));
Assertions.assertEquals(newEmployee, employeeNode.getReference());
Assertions.assertFalse(employeeNode.isMarked());

Also, when calling the compareAndSet method, we get true if the fields were updated or false if the update failed.

4.6. weakCompareAndSet()

The weakCompareAndSet method should be a weaker version of the compareAndSet method. That is, it doesn’t provide strong memory ordering guarantees just like compareAndSet. Also, it may fail spuriously to get exclusive access at the hardware level.

This is the specification for the weakCompareAndSet method. However, currently, the weakCompareAndSet simply calls the compareAndSet method under-the-hood. So, they have the same strong implementation.

Even though these two methods have the same implementation right now, we should use them based on their specifications. Therefore, we should consider weakCompareAndSet as a weak atomic.

Weak atomics can be less expensive on some platforms and in some circumstances. For instance, if we’re going to perform a compareAndSet in a loop, it may be a better idea to use the weaker version. In this case, we’ll eventually update the state as we’re in a loop, so spurious failures won’t affect the program’s correctness.

The bottom line is, weak atomics can be useful in some specific use-cases and, consequently, aren’t applicable to every possible scenario. So, when in doubt, prefer the stronger compareAndSet.

4.7. attemptMark()

Finally, we have the attemptMark method. It checks whether the current reference is equal to an expected reference sent as a parameter. If they match, it sets the value of the mark atomically to the given updated value:

Employee employee = new Employee(123, "Mike");
AtomicMarkableReference<Employee> employeeNode = new AtomicMarkableReference<>(employee, true);

Assertions.assertTrue(employeeNode.attemptMark(employee, false));
Assertions.assertFalse(employeeNode.isMarked());

It’s important to note that this method may fail spuriously even if the expected and current reference are equal. As a result, we should pay attention to the boolean returned by the method execution.

The result is true if the mark was updated successfully, or false otherwise. However, repeated invocation when the current reference is equal to the expected reference will modify the mark value. As a result, it is advisable to use this method inside a while loop structure.

This failure may occur as a result of the underlying compare-and-swap (CAS) algorithm used by the attemptMark method to update the fields. If we have multiple threads that are trying to update the same value using CAS, one of them manages to change the value, and the other ones are notified that the update failed.

5. Conclusion

In this quick guide, we learned how the AtomicMarkableReference class is implemented. Moreover, we discovered how we could update its properties atomically by going through the class’s public API methods.