Search⌘ K
AI Features
Home
Courses
Java Multithreading for Senior Engineering Interviews

AtomicMarkableReference

Understand the role of AtomicMarkableReference in Java concurrency as it helps maintain the state of nodes in lock-free linked lists. Explore how it uses a boolean mark alongside references to track logical deletions, preventing race conditions and inconsistent data during concurrent updates.

We'll cover the following...

If you are interviewing, consider buying our number#1 course for Java Multithreading Interviews.

Overview

The AtomicMarkedReference class is similar to the AtomicStampedReference class in that it holds a reference to an object but instead of an integer stamp it takes in a boolean value, called the mark. Both these fields can be updated atomically either together or individually. One could argue that AtomicStampedReference class would behave similarly to AtomicMarkableReference class if it accepted only two possible values for the integer stamp argument.

The code widget below demonstrates some of the basic operations when working with the AtomicMarkableReference class.

Java
import java.util.concurrent.atomic.AtomicMarkableReference;
class Demonstration {
    public static void main( String args[] ) {
        Long myLong = new Long(5);
        Long anotherLong = new Long(7);
        AtomicMarkableReference<Long> atomicMarkableReference = new AtomicMarkableReference<>(myLong, false);
        // attempt to change the long value with the wrong expected mark
        boolean wasSuccess = atomicMarkableReference.compareAndSet(myLong, anotherLong, true, true);
        System.out.println("compare and set succeeded " + wasSuccess + " current value " + atomicMarkableReference.getReference());
        // attempt to change the long value with the right expected mark
        wasSuccess = atomicMarkableReference.compareAndSet(myLong, anotherLong, false, true);
        System.out.println("compare and set succeeded " + wasSuccess + " current value " + atomicMarkableReference.getReference());
    }
}

Example

AtomicMarkableReference can be put to good use when designing lock-free lists, such as a set representation backed by a linked-list. In this lesson, we’ll not go through the implementation of a lock-free list but discuss parts of the implementation where the class AtomicMarkableReference is applicable.

Consider the SimpleNode class which represents a node in the linked list. The class uses an AtomicReference for the next node in the list, so that it can be updated atomically. The goal is to keep the list lock-free and update the next of the node correctly when a node is deleted. We’ll create a set-up that creates a race condition and causes the list to reach an inconsistent state.

Say we have three nodes linked as follows:

NodeA → NodeB → NodeC → null

Say we have two threads thread1 and thread2, each one trying to delete NodeA and NodeB respectively. The following sequence of events can cause the NodeC to not be deleted:

  1. thread1 stores the next of NodeA, which points to NodeB and the next of NodeB which points to NodeC in the variables expected and newNext respectively. These variables serve as the expected and the new value for the compareAndSet() method of the AtomicReference.

  2. At this point thread1 is suspended. We simulate that by sleeping the thread.

  3. thread2 starts and attempts to delete NodeC. thread1 computes the expected value for the next of NodeB, which is NodeC itself and the new next value which should be null, since NodeC is the last node of the list.

  4. thread2 continues and successfully deletes NodeC.

  5. thread1 wakes up and proceeds to execute the compareAndSet() call, which should succeed because NodeA still points to NodeB (the expected value) but the new next points to NodeC which has been deleted.

  6. The program ends in a state where NodeC is not deleted and remains part of the list.

The above scenario is depicted in the code widget below:

Java
class Demonstration {
    public static void main( String args[] ) throws Exception {
        SimpleNode nodeC = new SimpleNode(3, null);
        SimpleNode nodeB = new SimpleNode(2, nodeC);
        SimpleNode nodeA = new SimpleNode(1, nodeB);
        // NodeA --> NodeB --> NodeC
        Thread thread1 = new Thread(new Runnable() {
            @Override
            public void run() {
                // deleting NodeB
                SimpleNode expected = nodeA.next.get();
                SimpleNode next = nodeB.next.get();
                // thread goes to sleep
                try {
                    Thread.sleep(3000);
                } catch (InterruptedException ie) {
                    // ignore
                }
                // thread wakes-up and successfully updates referece
                nodeA.next.compareAndSet(expected, next);
            }
        });
        thread1.start();
        Thread.sleep(2000);
        Thread thread2 = new Thread(new Runnable() {
            @Override
            public void run() {
                // deleting NodeC
                SimpleNode expected = nodeB.next.get();
                SimpleNode next = nodeC.next.get();
                nodeB.next.compareAndSet(expected, next);
            }
        });
        thread2.start();
        thread1.join();
        thread2.join();
        SimpleNode start = nodeA;
        while (start != null) {
            System.out.println(start.value + " ");
            start = start.next.get();
        }
    }
}

The reason we end up in an inconsistent state is because we have no way of tracking the state of a given node if it has already been deleted or not. In our example, NodeC was deleted but thread1 didn’t realize that NodeC was not part of the list anymore. One possible solution is to store a boolean alongside each node that indicates the deletion status of the node. If set to true, the node is considered deleted but may not have been removed from the list yet.

This functionality is provided by the AtomicMarkableReference class. We can use AtomicMarkableReference to store the next for each node. Whenever, updating the next field of a node using the compareAndSet() method, we’ll pass in two expected values instead of one. The first expected value will be the reference of the object and the second a boolean value. When we update the next field of a node, we provide the new reference and false for the boolean value, implying that we only update the reference, if the node itself hasn’t been marked for deletion. In case, the delete operation finds that the predecessor of the node being deleted is already marked for deletion then the current delete operation fails physically, in the sense that the reference in the next field of the predecessor isn’t updated but the node being deleted has its mark set to true to indicate a logical delete.

If we re-run the same example with our modified algorithm, thread1 will succeed to update the reference after resumption from sleep, however, thread2 will not be able to delete nodeC. The list would still comprise of NodeA and NodeC but not be in an inconsistent state because the mark for NodeC will be true, indicating that the node has been logically deleted. The operation to delete NodeC can be either re-tried immediately or lazily deleted at a later time when another operation traverses the list and removes all the nodes marked true.

Java
class Demostration {
    public static void main( String args[] ) throws Exception {
        Node nodeC = new Node(3, null);
        Node nodeB = new Node(2, nodeC);
        Node nodeA = new Node(1, nodeB);
        // nodeA --> nodeB --> nodeC
        Thread thread1 = new Thread(new Runnable() {
            @Override
            public void run() {
                // deleting NodeB
                // mark NodeB as deleted
                nodeB.next.set(nodeB.next.getReference(), true);
                Node expected = nodeA.next.getReference();
                Node next = nodeB.next.getReference();
                // thread goes to sleep
                try {
                    Thread.sleep(3000);
                } catch (InterruptedException ie) {
                    // ignore
                }
                // thread wakes-up and attempts to compareAndSet.
                nodeA.next.compareAndSet(expected, next, false, false);
            }
        });
        thread1.start();
        Thread.sleep(2000);
        Thread thread2 = new Thread(new Runnable() {
            @Override
            public void run() {
                // deleting NodeC
                nodeC.next.set(nodeC.next.getReference(), true);
                Node expected = nodeB.next.getReference();
                Node next = nodeC.next.getReference();
                // The result of deleting nodeC is false.
                nodeB.next.compareAndSet(expected, next, false, false);
            }
        });
        thread2.start();
        thread1.join();
        thread2.join();
        Node start = nodeA;
        while (start != null) {
            boolean[] mark = new boolean[1];
            start.next.get(mark);
            System.out.println(start.value + " (mark : " + mark[0] + ") ");
            start = start.next.getReference();
        }
    }
}

This example captures the gist of the utility of the AtomicMarkableReference class and demonstrates how additional state about a data structure can be maintained.