title: Multiprocessor programming: lock-free stacks
body: <p>In preperation for my upcoming Concurrent Systems exam, I am trying to complete some questions from the text book "The Art of Multiprocessor Programming". One question is bugging me:</p>
  
  <blockquote>
    <p><em>Exercise 129:</em> Does it make sense to use the same shared BackOff object for both pushes and pop in our LockFreeStack object? How else could we structure the backoff in space and time in the EliminationBackOffStack?.</p>
  </blockquote>
  
  <p>This question bugs me because the first thing that comes to my mind is that it does not make sense because all a backoff object does is make a process wait, so why not share it? The second part of the question totally eludes me and any help is most welcome.</p>
  
  <p>The code for the LockFreeStack:</p>
  
  <pre><code>public class LockFreeStack&lt;T&gt; {
  
      AtomicReference&lt;Node&gt; top = new AtomicReference&lt;Node&gt;(null);
  
      static final int MIN_DELAY = ...;
      static final int MAX_DELAY = ...;
      Backoff backoff = new Backoff(MIN_DELAY, MAX_DELAY);
  
      protected boolean tryPush(Node node) {
          Node oldTop = top.get();
          node.next = oldTop;
          return(top.compareAndSet(oldTop, node));
      }
  
      public void push(T value) {
          Node node = new Node(value);
          while (true) {
              if (tryPush(node)) {
                  return;
              } else {
                  backoff.backoff();
              }
          }
      }
  </code></pre>