Avoiding a lost update in Java without directly using synchronization

Question

I am wondering if it is possible to avoid the lost update problem, where multiple threads are updating the same date, while avoiding using synchronized(x) { }.

I will be doing numerous adds and increments:

val++;
ary[x] += y;
ary[z]++;

I do not know how Java will compile these into byte code and if a thread could be interrupted in the middle of one of these statements blocks of byte code. In other words are those statements thread safe?

Also, I know that the Vector class is synchronized, but I am not sure what that means. Will the following code be thread safe in that the value at position i will not change between the vec.get(i) and vec.set(...).

class myClass {
  Vector<Integer> vec = new Vector<>(Integer);

  public void someMethod() {
    for (int i=0; i < vec.size(); i++)
      vec.set(i, vec.get(i) + value);
  }
}

Thanks in advance.

Answer 1

For the purposes of threading, ++ and += are treated as two operations (four for double and long). So updates can clobber one another. Not just be one, but a scheduler acting at the wrong moment could wipe out milliseconds of updates.

java.util.concurrent.atomic is your friend.

Your code can be made safe, assuming you don't mind each element updating individually and you don't change the size(!), as:

for (int i=0; i < vec.size(); i++) {
    synchronized (vec) {
        vec.set(i, vec.get(i) + value);
    }
}

If you want to add resizing to the Vector you'll need to move the synchronized statement outside of the for loop, and you might as well just use plain new ArrayList. There isn't actually a great deal of use for a synchronised list.

But you could use AtomicIntegerArray:

private final AtomicIntegerArray ints = new AtomicIntegerArray(KNOWN_SIZE);
[...]
    int len = ints.length();
    for (int i=0; i<len; ++i) {
        ints.addAndGet(i, value);
    }
}

That has the advantage of no locks(!) and no boxing. The implementation is quite fun too, and you would need to understand it do more complex update (random number generators, for instance).

Answer 2

vec.set() and vec.get() are thread safe in that they will not set and retrieve values in such a way as to lose sets and gets in other threads. It does not mean that your set and your get will happen without an interruption.

If you're really going to be writing code like in the examples above, you should probably lock on something. And synchronized(vec) { } is as good as any. You're asking here for two operations to happen in sync, not just one thread safe operation.

Even java.util.concurrent.atomic will only ensure one operation (a get or set) will happen safely. You need to get-and-increment in one operation.