How to solve race condition of two writers using immutable objects

Question

I was thinking about how to solve race condition between two threads which tries to write to the same variable using immutable objects and without helping any keywords such as synchronize(lock)/volatile in java.

But I couldn't figure it out, is it possible to solve this problem with such solution at all?

public class Test {
    private static IAmSoImmutable iAmSoImmutable;

    private static final Runnable increment1000Times = () -> {
        for (int i = 0; i < 1000; i++) {
            iAmSoImmutable.increment();
        }
    };

    public static void main(String... args) throws Exception {
        for (int i = 0; i < 10; i++) {
            iAmSoImmutable = new IAmSoImmutable(0);

            Thread t1 = new Thread(increment1000Times);
            Thread t2 = new Thread(increment1000Times);

            t1.start();
            t2.start();

            t1.join();
            t2.join();

            // Prints a different result every time -- why? :
            System.out.println(iAmSoImmutable.value);
        }
    }

    public static class IAmSoImmutable {
        private int value;

        public IAmSoImmutable(int value) {
            this.value = value;
        }

        public IAmSoImmutable increment() {
            return new IAmSoImmutable(++value);
        }
    }

If you run this code you'll get different answers every time, which mean a race condition is happening.

Answer 1

You can not solve race condition without using any of existence synchronisation (or volatile) techniques. That what they were designed for. If it would be possible there would be no need of them.

More particularly your code seems to be broken. This method:

public IAmSoImmutable increment() {
            return new IAmSoImmutable(++value);
}

is nonsense for two reasons:

1) It makes broken immutability of class, because it changes object's variable value.

2) Its result - new instance of class IAmSoImmutable - is never used.

Answer 2

The fundamental problem here is that you've misunderstood what "immutability" means.

"Immutability" means — no writes. Values are created, but are never modified.

Immutability ensures that there are no race conditions, because race conditions are always caused by writes: either two threads performing writes that aren't consistent with each other, or one thread performing writes and another thread performing reads that give inconsistent results, or similar.

(Caveat: even an immutable object is effectively mutable during construction — Java creates the object, then populates its fields — so in addition to being immutable in general, you need to use the final keyword appropriately and take care with what you do in the constructor. But, those are minor details.)

With that understanding, we can go back to your initial sentence:

I was thinking about how to solve race condition between two threads which tries to write to the same variable using immutable objects and without helping any keywords such as synchronize(lock)/volatile in java.

The problem here is that you actually aren't using immutable objects: your entire goal is to perform writes, and the entire concept of immutability is that no writes happen. These are not compatible.

That said, immutability certainly has its place. You can have immutable IAmSoImmutable objects, with the only writes being that you swap these objects out for each other. That helps simplify the problem, by reducing the scope of writes that you have to worry about: there's only one kind of write. But even that one kind of write will require synchronization.

The best approach here is probably to use an AtomicReference<IAmSoImmutable>. This provides a non-blocking way to swap out your IAmSoImmutable-s, while guaranteeing that no write gets silently dropped.

(In fact, in the special case that your value is just an integer, the JDK provides AtomicInteger that handles the necessary compare-and-swap loops and so on for threadsafe incrementation.)