Writing a thread safe modular counter in Java

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 calle开发者_如何学编程d? (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?

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

I would say that aside from the wrapping, it's fine. When two method calls are effectively simultaneous, you can't guarantee which will happen first.

The code is still atomic, because whichever actually happens first, they can't interfere with each other at all.

Basically if you have code which tries to rely on the order of simultaneous calls, you already have a race condition. Even if in the calling code one thread gets to the start of the next() call before the other, you can imagine it coming to the end of its time-slice before it gets into the next() call - allowing the second thread to get in there.

If the next() call had any other side effect - e.g. it printed out "Starting with thread (thread id)" and then returned the next value, then it wouldn't be atomic; you'd have an observable difference in behaviour. As it is, I think you're fine.

One thing to think about regarding wrapping: you can make the counter last an awful lot longer before wrapping if you use an AtomicLong :)

EDIT: I've just thought of a neat way of avoiding the wrapping problem in all realistic scenarios:

• Define some large number M * 100000 (or whatever). This should be chosen to be large enough to not be hit too often (as it will reduce performance) but small enough that you can expect the "fixing" loop below to be effective before too many threads have added to the tick to cause it to wrap.

• When you fetch the value with getAndIncrement(), check whether it's greater than this number. If it is, go into a "reduction loop" which would look something like this:

  long tmp;
  while ((tmp = tick.get()) > SAFETY_VALUE))
  {
      long newValue = tmp - SAFETY_VALUE;
      tick.compareAndSet(tmp, newValue);
  }
  

Basically this says, "We need to get the value back into a safe range, by decrementing some multiple of the modulus" (so that it doesn't change the value mod M). It does this in a tight loop, basically working out what the new value should be, but only making a change if nothing else has changed the value in between.

It could cause a problem in pathological conditions where you had an infinite number of threads trying to increment the value, but I think it would realistically be okay.

Concerning the atomicity problem: I don't believe that it's possible for the Counter itself to provide behaviour to guarantee the semantics you're implying.

I think we have a thread doing some work

  A - get some stuff (for example receive a message)
  B - prepare to call Counter
  C - Enter Counter <=== counter code is now in control
  D - Increment
  E - return from Counter <==== just about to leave counter's control
  F - application continues

The mediation you're looking for concerns the "payload" identity ordering established at A.

For example two threads each read a message - one reads X, one reads Y. You want to ensure that X gets the first counter increment, Y gets the second, even though the two threads are running simultaneously, and may be scheduled arbitarily across 1 or more CPUs.

Hence any ordering must be imposed across all the steps A-F, and enforced by some concurrency countrol outside of the Counter. For example:

pre-A - Get a lock on Counter (or other lock)
  A - get some stuff (for example receive a message)
  B - prepare to call Counter
  C - Enter Counter <=== counter code is now in control
  D - Increment
  E - return from Counter <==== just about to leave counter's control
  F - application continues
post- F - release lock

Now we have a guarantee at the expense of some parallelism; the threads are waiting for each other. When strict ordering is a requirement this does tend to limit concurrency; it's a common problem in messaging systems.

Concerning the List question. Thread-safety should be seen in terms of interface guarantees. There is absolute minimum requriement: the List must be resilient in the face of simultaneous access from several threads. For example, we could imagine an unsafe list that could deadlock or leave the list mis-linked so that any iteration would loop for ever. The next requirement is that we should specify behaviour when two threads access at the same time. There's lots of cases, here's a few

a). Two threads attempt to add
b). One thread adds item with key "X", another attempts to delete the item with key "X"
C). One thread is iterating while a second thread is adding

Providing that the implementation has clearly defined behaviour in each case it's thread-safe. The interesting question is what behaviours are convenient.

We can simply synchronise on the list, and hence easily give well-understood behaviour for a and b. However that comes at a cost in terms of parallelism. And I'm arguing that it had no value to do this, as you still need to synchronise at some higher level to get useful semantics. So I would have an interface spec saying "Adds happen in any order".

As for iteration - that's a hard problem, have a look at what the Java collections promise: not a lot!

This article , which discusses Java collections may be interesting.

Atomic (as I understand) refers to the fact that an intermediate state is not observable from outside. atomicInteger.incrementAndGet() is atomic, while return this.intField++; is not, in the sense that in the former, you can not observe a state in which the integer has been incremented, but has not yet being returned.

As for thread-safety, authors of Java Concurrency in Practice provide one definition in their book:

A class is thread-safe if it behaves correctly when accessed from multiple threads, regardless of the scheduling or interleaving of the execution of those threads by the runtime environment, and with no additional synchronization or other coordination on the part of the calling code.

(My personal opinion follows)

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 thread1 entered the entry set of the mutex object (In case of Collections.synchronizedList() the list itself) before thread2, it is guaranteed that first is positioned ahead than second in the list after the update. This is because the synchronized keyword uses fair lock. Whoever sits ahead of the queue gets to do stuff first. Fair locks can be quite expensive and you can also have unfair locks in java (through the use of java.util.concurrent utilities). If you'd do that, then there is no such guarantee.

However, the java platform is not a real time computing platform, so you can't predict how long a piece of code requires to run. Which means, if you want first ahead of second, you need to ensure this explicitly in java. It is impossible to ensure this through "controlling the timing" of the call.

Now, what is thread safe or unsafe here? I think this simply depends on what needs to be done. If you just need to avoid the list being corrupted and it doesn't matter if first is first or second is first in the list, for the application to run correctly, then just avoiding the corruption is enough to establish thread-safety. If it doesn't, it is not.

So, I think thread-safety can not be defined in the absence of the particular functionality we are trying to achieve.

The famous String.hashCode() doesn't use any particular "synchronization mechanism" provided in java, but it is still thread safe because one can safely use it in their own app. without worrying about synchronization etc.

Famous String.hashCode() trick:

int hash = 0;

int hashCode(){
    int hash = this.hash;
    if(hash==0){
        hash = this.hash = calcHash();
    }
    return hash;
 }