AtomicReference.compareAndSet allows multiple threads to succeed

[Peter Harvey]

If multiple threads call AtomicReference.compareAndSet with the same pair
of values, it appears that multiple threads may succeed. For example, if
multiple threads call compareAndSet("Alpha", "Beta") then they may all
succeed. Is this the correct behaviour?

The documentation maybe should make this clear, as most developers and
tutorials seem to assume that the compareAndSet methods of the Atomic
classes guarantee that at most one thread will succeed.

I've included full demonstration code at the very bottom of this email. In
this demo, multiple threads are popping items from a stack and then pushing
items back on to the stack. I discovered that it was possible for two
threads to pop the same item from the stack, despite using compareAndSet to
modify the head of the stack. Specifically, this code did not work as
intended:

AtomicReference<StackEntry> stack = new AtomicReference<StackEntry>();

...

// Pop an entry from the top of the queue
StackEntry entry;
while (true) {
 entry = stack.get();
if (entry == null)
break;

// Atomic, right? Only one thread can succeed...
if (stack.compareAndSet(entry, entry.next))
break;
}

Peter.

Full demo code below:
--------------------------------------

public class AtomicReferenceTest {
private static final class StackEntry {
volatile Thread owner;

volatile StackEntry next;
}

private static final AtomicReference<StackEntry> stack = new
AtomicReference<StackEntry>();

private static class MyThread extends Thread {
@Override
public void run() {
while (true) {

/*
 * Pop an entry off the top of the stack. The only way to exit
 * this loop is to have found an empty stack, or to have
 * ATOMICALLY replaced the head of the stack with the next item
 * on the stack. In theory, no two threads should be able to
 * exit this loop with the SAME entry...
 */
StackEntry entry;
while (true) {
entry = stack.get();
if (entry == null)
break;

// Atomic, right? Only one thread can succeed...
if (stack.compareAndSet(entry, entry.next))
break;
}

/*
 * If there was nothing on the stack, make a new entry.
 * Otherwise, just set the 'next' to null. This isn't required
 * but is good practice.
 */
if (entry == null)
entry = new StackEntry();
else
entry.next = null;

/*
 * Check if the entry really was exclusively claimed. In theory,
 * no two threads should ever have a reference to the same
 * entry...
 */
Thread owner = entry.owner;
if (owner != null)
System.err.println("ALREADY CLAIMED BY " + owner);
entry.owner = Thread.currentThread();

/* Push the entry back on to the queue. */
entry.owner = null;
while (true) {
entry.next = stack.get();

// Atomic, right? Only one thread can succeed...
if (stack.compareAndSet(entry.next, entry))
break;
}
}
}
};

public static void main(String[] args) {
Thread[] threads = new Thread[8];
for (int i = 0; i < threads.length; i++)
threads[i] = new MyThread();
for (int i = 0; i < threads.length; i++)
threads[i].start();
}
}

-- 
*Actenum Corporation*
Peter Harvey  |  Cell: 780.729.8192  |  harvey at actenum.com  |
www.actenum.com