Writing a thread safe modular counter in Java

Question

Full disclaimer: 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".

Let's say I want to write a simple thread safe modular counter in Java. That is, if the modulo M is 3, then the counter should cycle through 0, 1, 2, 0, 1, 2, … ad infinitum.

Here's one attempt:

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

My analysis (which may be faulty) of this code is that since it uses AtomicInteger, it's quite thread safe even without any explicit synchronized method/block.

Unfortunately the "algorithm" itself doesn't quite "work", because when tick wraps around Integer.MAX_VALUE, next() may return the wrong value depending on the modulo M. That is:

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

That is, two calls to next() will return 1, 1 when the modulo is 3 and tick wraps around.

There may also be an issue with next() getting out-of-order values, e.g.:

1. Thread1 calls next()
2. Thread2 calls next()
3. Thread2 completes tick.getAndIncrement(), returns x
4. Thread1 completes tick.getAndIncrement(), returns y = x+1 (mod M)

Here, barring the forementioned wrapping problem, x and y are indeed the two correct values to return for these two next() 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 (Thread1, y) and (Thread2, x), but maybe it should really be specified that (Thread1, x) and (Thread2, y) is the "proper" behavior.

So by some definition of the words, AtomicModularCounter is thread-safe, but not actually atomic.

So the questions are:

• Is my analysis correct? If not, then please point out any errors.
• Is my last statement above using the correct terminology? If not, what is the correct statement?
• If the problems mentioned above are real, then how would you fix it?
• Can you fix it without using synchronized, by harnessing the atomicity of AtomicInteger?
• How would you write it such that tick itself is range-controlled by the modulo and never even gets a chance to wraps over Integer.MAX_VALUE?
  • We can assume M is at least an order smaller than Integer.MAX_VALUE if necessary

---

Appendix

Here's a List analogy of the out-of-order "problem".

• Thread1 calls add(first)
• Thread2 calls add(second)

Now, if we have the list updated succesfully with two elements added, but second comes before first, which is at the end, is that "thread safe"?

If that is "thread safe", then what is it not? That is, if we specify that in the above scenario, first should always come before second, what is that concurrency property called? (I called it "atomicity" but I'm not sure if this is the correct terminology).

For what it's worth, what is the Collections.synchronizedList behavior with regards to this out-of-order aspect?

Answer 1

As far as I can see you just need a variation of the getAndIncrement() method

public final int getAndIncrement(int modulo) {
    for (;;) {
        int current = atomicInteger.get();
        int next = (current + 1) % modulo;
        if (atomicInteger.compareAndSet(current, next))
            return current;
    }
}