title: Writing a thread safe modular counter in Java
body: <p><em>Full disclaimer:</em> this is not really a homework, but I tagged it as such because it is mostly a self-learning exercise rather than actually "for work".</p>
  
  <p>Let's say I want to write a simple thread safe modular counter in Java. That is, if the modulo <code>M</code> is 3, then the counter should cycle through <code>0, 1, 2, 0, 1, 2, …</code>  ad infinitum.</p>
  
  <p>Here's one attempt:</p>
  
  <pre><code>import java.util.concurrent.atomic.AtomicInteger;
  
  public class AtomicModularCounter {
      private final AtomicInteger tick = new AtomicInteger();
      private final int M;
  
      public AtomicModularCounter(int M) {
          this.M = M;
      }
      public int next() {
          return modulo(tick.getAndIncrement(), M);
      }
      private final static int modulo(int v, int M) {
          return ((v % M) + M) % M;
      }
  }
  </code></pre>
  
  <p>My analysis (which may be faulty) of this code is that since it uses <a href="http://download.oracle.com/javase/6/docs/api/java/util/concurrent/atomic/AtomicInteger.html" rel="noreferrer"><code>AtomicInteger</code></a>, it's quite thread safe even without any explicit <code>synchronized</code> method/block.</p>
  
  <p>Unfortunately the "algorithm" itself doesn't quite "work", because when <code>tick</code> wraps around <code>Integer.MAX_VALUE</code>, <code>next()</code> may return the wrong value depending on the modulo <code>M</code>. That is:</p>
  
  <pre><code>System.out.println(Integer.MAX_VALUE + 1 == Integer.MIN_VALUE); // true
  System.out.println(modulo(Integer.MAX_VALUE, 3)); // 1
  System.out.println(modulo(Integer.MIN_VALUE, 3)); // 1
  </code></pre>
  
  <p>That is, two calls to <code>next()</code> will return <code>1, 1</code> when the modulo is 3 and <code>tick</code> wraps around.</p>
  
  <p>There may also be an issue with <code>next()</code> getting out-of-order values, e.g.:</p>
  
  <ol>
  <li><em>Thread1</em> calls <code>next()</code></li>
  <li><em>Thread2</em> calls <code>next()</code></li>
  <li><em>Thread2</em> completes <code>tick.getAndIncrement()</code>, returns <em>x</em></li>
  <li><em>Thread1</em> completes <code>tick.getAndIncrement()</code>, returns <em>y = x+1 (mod M)</em></li>
  </ol>
  
  <p>Here, barring the forementioned wrapping problem, <em>x</em> and <em>y</em> are indeed the two correct values to return for these two <code>next()</code> calls, but depending on how the counter behavior is specified, it can be argued that they're out of order. That is, we now have <em>(Thread1, y)</em> and <em>(Thread2, x)</em>, but maybe it should really be specified that <em>(Thread1, x)</em> and <em>(Thread2, y)</em> is the "proper" behavior.</p>
  
  <p>So by some definition of the words, <code>AtomicModularCounter</code> is <em>thread-safe</em>, but not actually <em>atomic</em>.</p>
  
  <p>So the questions are:</p>
  
  <ul>
  <li>Is my analysis correct? If not, then please point out any errors.</li>
  <li>Is my last statement above using the correct terminology? If not, what is the correct statement?</li>
  <li>If the problems mentioned above are real, then how would you fix it?</li>
  <li>Can you fix it without using <code>synchronized</code>, by harnessing the atomicity of <code>AtomicInteger</code>?</li>
  <li>How would you write it such that <code>tick</code> itself is range-controlled by the modulo and never even gets a chance to wraps over <code>Integer.MAX_VALUE</code>?
  
  <ul>
  <li>We can assume <code>M</code> is at least an order smaller than <code>Integer.MAX_VALUE</code> if necessary</li>
  </ul></li>
  </ul>
  
  <hr>
  
  <h3>Appendix</h3>
  
  <p>Here's a <code>List</code> analogy of the out-of-order "problem".</p>
  
  <ul>
  <li><em>Thread1</em> calls <code>add(first)</code></li>
  <li><em>Thread2</em> calls <code>add(second)</code></li>
  </ul>
  
  <p>Now, if we have the list updated succesfully with two elements added, but <code>second</code> comes before <code>first</code>, which is at the end, is that "thread safe"?</p>
  
  <p>If that is "thread safe", then what is it not? That is, if we specify that in the above scenario, <code>first</code> should always come before <code>second</code>, what is that concurrency property called? (I called it "atomicity" but I'm not sure if this is the correct terminology).</p>
  
  <p>For what it's worth, what is the <code>Collections.synchronizedList</code> behavior with regards to this out-of-order aspect?</p>