title: Non-blocking queue in Java using AtomicStampedReference
body: <p>So I'll start by saying this is for an assignment, and there are a few restrictions on the queue I need to build:</p>
  
  <ol>
  <li><p>It is unbounded.</p></li>
  <li><p>No locking mechanisms are allowed(no <code>synchronized</code>, <code>ReentrantLock</code>, etc){not even to simulate things like CompareAndSet}.</p></li>
  <li><p>It must implement <a href="http://www.research.ibm.com/people/m/michael/podc-1996.pdf" rel="nofollow">Michael and Scott's</a> algorithm.</p></li>
  <li><p>Of course, I can't rip off Java's source code for <code>ConcurrentLinkedQueue</code>.</p></li>
  </ol>
  
  <p>Here's what I have so far(dequeue is left out):</p>
  
  <pre><code>public class LockFreeQueue&lt;T&gt; implements MyQueue&lt;T&gt;
  {
      private class Node&lt;R&gt;
      {
          public final R value;
          public volatile AtomicReference&lt;Node&lt;R&gt;&gt; next;
  
          public Node()
          {
              value = null;
              next = new AtomicReference&lt;Node&lt;R&gt;&gt;(null);
          }
  
          public Node(R v)
          {
              value = v;
              next = new AtomicReference&lt;Node&lt;R&gt;&gt;(null);
          }
      }
  
      volatile AtomicStampedReference&lt;Node&lt;T&gt;&gt; head = new AtomicStampedReference&lt;Node&lt;T&gt;&gt;(new Node&lt;T&gt;(), 0);
      volatile AtomicStampedReference&lt;Node&lt;T&gt;&gt; tail = head;
      AtomicInteger count = new AtomicInteger(0);
  
      public boolean enq(T value)
      {
          Node&lt;T&gt; node = new Node&lt;T&gt;(value);
  
          while (true)
          {
              Node&lt;T&gt; tempTail = tail.getReference();
              int tailCount = tail.getStamp();
              Node&lt;T&gt; next = tempTail.next.get();
              if (tempTail == tail.getReference())
              {
                  if (null == next)
                  {
                      if(tempTail.next.compareAndSet(null, node))
                      {
                          // Problem on this line:
                          tail.compareAndSet(tempTail, node, tailCount, count.incrementAndGet());
                          return true;
                      }
                  }
                  else
                  {
                      tail.compareAndSet(tempTail, next, tailCount, count.incrementAndGet());
                  }
              }
          }
      }
  ...
  }
  </code></pre>
  
  <p>Now, for the most part, this follows the code found in <a href="http://www.ibm.com/developerworks/library/j-jtp04186/" rel="nofollow">this IBM article</a>.  Particularly, it follows the code in <code>Listing 4. Insertion in the Michael-Scott nonblocking queue algorithm</code>.  The problem, which is exhibited by both my code and the code in the article, is that when the reference for the tail is swung to the new tail, it does the same for the head. It does this of course because it's changing the <code>Node</code> being referred to, rather than the actual reference, and the reference that <code>tail</code> and <code>head</code> have are the same.</p>
  
  <p>I also found <a href="http://gee.cs.oswego.edu/dl/classes/EDU/oswego/cs/dl/util/concurrent/WaitFreeQueue.java" rel="nofollow">a different solution</a> but the main problem with this code is that it uses <code>synchronized</code>, even though it's only doing so to simulate a CAS operation.</p>
  
  <p>As far as Java's <a href="http://fuseyism.com/classpath/doc/java/util/concurrent/ConcurrentLinkedQueue-source.html" rel="nofollow"><code>ConcurrentLinkedQueue</code></a> goes, I've noticed that they utilize <a href="http://docs.oracle.com/javase/7/docs/api/java/util/concurrent/atomic/AtomicReferenceFieldUpdater.html" rel="nofollow"><code>AtomicReferenceUpdater</code></a> and that really seems to be the only way to go.  The problem here, though, is that my code starts to look surprisingly close to Java's and I don't want to be docked points for plagiarism(or worse!).</p>
  
  <p>Is <code>AtomicReferenceUpdater</code> the only way for me to move forward, or are there other things I can do?  </p>
  
  <p>A last note:</p>
  
  <ul>
  <li><code>Node</code> is a total fabrication of my own, so it can change to be anything it needs to be.</li>
  </ul>
  
  <p><strong>Edit:</strong></p>
  
  <p>Ben Manes mentioned not needing to be concerned about the ABA problem in a language with garbage collection.  For those interested in this in the future, there's <a href="http://www.hergert.me/blog/2009/12/25/intro-to-lock-free-wait-free-and-aba.html" rel="nofollow">this article</a> which is a nice read.  The important part:</p>
  
  <blockquote>
    <p>In garbage collected languages this isn't a problem. Why? Because the node's memory cannot be reclaimed for a new object until observing threads containing pointers to the structure have released them.</p>
  </blockquote>