Guide to AtomicStampedReference in Java

1. Overview

In a previous article, we learned that AtomicStampedReference can prevent the ABA problem.

In this tutorial, we’ll get a closer look at how to best use it.

2. Why Do We Need AtomicStampedReference?

First, AtomicStampedReference provides us with both an object reference variable and a stamp that we can read and write atomically. We can think of the stamp a bit like a timestamp or a version number.

Simply put, adding a stamp allows us to detect when another thread has changed the shared reference from the original reference A, to a new reference B, and back to the original reference A.

Let’s see how it behaves in practice.

3. Bank Account Example

Consider a bank account that has two pieces of data: a balance and a last modified date. The last modified date is updated any time the balance is altered. By observing this last modified date, we can know the account has been updated.

3.1. Reading a Value and Its Stamp

First, let’s imagine that our reference is holding onto an account balance:

AtomicStampedReference<Integer> account = new AtomicStampedReference<>(100, 0);

Note that we’ve supplied the balance, 100, and a stamp, 0.

To access the balance, we can use the AtomicStampedReference.getReference() method on our account member variable.

Similarly, we can obtain the stamp via AtomicStampedReference.getStamp().

3.2. Changing a Value and Its Stamp

Now, let’s review how to set the value of an AtomicStampedReference atomically.

If we want to change the account’s balance, we need to change both the balance and the stamp:

if (!account.compareAndSet(balance, balance + 100, stamp, stamp + 1)) {
    // retry
}

The compareAndSet method returns a boolean indicating success or failure. A failure means that either the balance or the stamp has changed since we last read it.

As we can see, it’s easy to retrieve the reference and the stamp using their getters.

But, as mentioned above, we need the latest version of them when we want to update their values using the CAS. To retrieve those two pieces of information atomically, we need to fetch them at the same time.

Luckily, AtomicStampedReference provides us an array-based API to achieve this. Let’s demonstrate its usage by implementing the withdrawal() method for our Account class:

public boolean withdrawal(int funds) {
    int[] stamps = new int[1];
    int current = this.account.get(stamps);
    int newStamp = this.stamp.incrementAndGet();
    return this.account.compareAndSet(current, current - funds, stamps[0], newStamp);
}

Similarly, we can add the deposit() method:

public boolean deposit(int funds) {
    int[] stamps = new int[1];
    int current = this.account.get(stamps);
    int newStamp = this.stamp.incrementAndGet();
    return this.account.compareAndSet(current, current + funds, stamps[0], newStamp);
}

The nice thing about what we’ve just written is we can know before withdrawing or depositing that no other thread has altered the balance, even back to what it was since our last read.

For example, consider the following thread interleaving:

The balance is set to $100. Thread 1 runs deposit(100) up to the following point:

int[] stamps = new int[1];
int current = this.account.get(stamps);
int newStamp = this.stamp.incrementAndGet(); 
// Thread 1 is paused here

meaning the deposit has not yet completed.

Then, Thread 2 runs deposit(100) and withdraw(100), bringing the balance to $200 and then back to $100.

Finally, Thread 1 runs:

return this.account.compareAndSet(current, current + 100, stamps[0], newStamp);

Thread 1 will successfully detect that some other thread has altered the account balance since its last read, even though the balance itself is the same as it was when Thread 1 read it.

3.3. Testing

It’s tricky to test since this depends on a very specific thread interleaving. But, let’s at least write a simple unit test to verify that deposits and withdrawals work:

public class ThreadStampedAccountUnitTest {

    @Test
    public void givenMultiThread_whenStampedAccount_thenSetBalance() throws InterruptedException {
        StampedAccount account = new StampedAccount();

        Thread t = new Thread(() -> {
            while (!account.deposit(100)) {
                Thread.yield();
            }
        });
        t.start();

        Thread t2 = new Thread(() -> {
            while (!account.withdrawal(100)) {
                Thread.yield();
            }
        });
        t2.start();

        t.join(10_000);
        t2.join(10_000);

        assertFalse(t.isAlive());
        assertFalse(t2.isAlive());

        assertEquals(0, account.getBalance());
        assertTrue(account.getStamp() > 0);
    }
}

3.4. Choosing the Next Stamp

Semantically, the stamp is like a timestamp or a version number, so it’s typically always increasing. It’s also possible to use a random number generator.

The reason for this is that, if the stamp can be changed to something it was previously, this could defeat the purpose of AtomicStampedReference. AtomicStampedReference itself doesn’t enforce this constraint, so it’s up to us to follow this practice.

4. Conclusion

In conclusion, AtomicStampedReference is a powerful concurrency utility that provides both a reference and a stamp that can be read and updated atomically. It was designed for A-B-A detection and should be preferred to other concurrency classes such as AtomicReference where the A-B-A problem is a concern.