AtomicReference.compareAndSet allows multiple threads to succeed

[Doug Lea]

On 02/11/2014 01:41 PM, Peter Harvey wrote:
> 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?

Your example has an ABA problem.
See http://en.wikipedia.org/wiki/ABA_problem
(that uses a variant of this example to illustrate).
And/or try commenting out the
                 //                if (entry == null)
                 entry = new StackEntry();
                 //                else
                 //                    entry.next = null;

-Doug

>
> 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();
> }
> }
>