AtomicReference.compareAndSet allows multiple threads to succeed

[Peter Harvey]

Thanks all for the responses. It is an ABA problem.

I changed my code so that it creates new StackEntries if multiple threads
attempt to pop the stack at the same time. This relies on getAndSet to
obtain exclusive access to the stack contents, rather than using
compareAndSet to update the stack.

I'll look into educating myself more on lock-free programming when I can.
For now, I'll be a lot more cautious when using compareAndSet.

Thanks again.



On Tue, Feb 11, 2014 at 11:41 AM, Peter Harvey <harvey at actenum.com> 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?
>
> 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
>



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