compare and set operation Java

user_11945151 0
Viewed 271

I am studying multithreading in java.

I have a class

public class CASCount<T> {
    private final AtomicReference<Integer> count = new AtomicReference<>(0);
    
    public int get() {
        return count.get();
    }
}

and there is a increment method :

    public void increment() {
        int t;
        do {
            t = count.get();
        }
        while (!count.compareAndSet(t, t + 1));
    }

which could be simplified like this:

    public void increment() {
        int t;
        while (!count.compareAndSet(t = count.get(), t + 1));
    }

or like this:

public void increment() {
        while (!count.compareAndSet(count.get(), count.get() +1));
    }

I have been told that I couldn't because other threads could change the data inside the method. But, as I know, Compare and Set(CAS) is an atomic operation, and if the first get() returns 0 and the second get() returns 1, the CAS operation cannot change the counter, because if get() returns 1, it means the data has already changed.

My question is why I can not do the above operations if CAS is atomic, and why it is not advisable to do so?

thread-safety multithreading java
1 Answers

The first rewrite is correct. This version performs the same operations in the same order as in the original one. Since the codes are equivalent, and the original is correct, so is the rewrite.

The second rewrite requires deeper analysis. In the following T1, T2, T3 and so on denote distinct threads. (I am ignoring the boxing and unboxing that goes on, because I am pretty sure that it makes no difference to the analysis.)

Let us start with the case where threads only call the increment method; i.e. the counter only increases. If a T1 manages to increment the counter while T1 is calling increment between the first get() call and before the compareAndSet() call, then compareAndSet(i1, i2) will (always) see that the i1 value is different to current value. It will therefore NOT perform the "set". The fact that the second get() call may return a different value to the first one is moot. The 2nd rewrite is correct in this case.

But what if there is also a decrement method coded like this:

public void decrement() {
    int t;
    while (!count.compareAndSet(count.get(), count.get() - 1));
}

And suppose that T1 and T2 call increment and T3 calls decrement at the same time with the following interleaving of operations

T1:  getCount() -> 0
T2:  getCount() -> 0, getCount() -> 0, compareAndSet(0, 0 + 1) -> true, 1
T1:  getCount() -> 1,
T3:  getCount() -> 1, getCount() -> 1, compareAndSet(1, 1 - 1) -> true, 0
T1:  compareAndSet(0, 1 + 1) -> true, 2

and we have lost the effect of T3's decrement!

In other words, the second rewrite is incorrect if we cannot assume that the value counter is monotonically increasing.

My question is why I can not do the above operations if CAS is atomic.

One of the rewrites is incorrect in some use-cases; see above

and why it is not advisable to do so?

Three reasons:

  1. If it isn't broken, don't fix it.
  2. If you rewrite a well-known concurrent algorithm, the onus is really on you to prove that the rewrite is correct. And proving correctness is typically harder than proving incorrectness (like I just did above).
  3. In this case, you call getCount() twice as many times to save a local variable. The extra calls are a performance hit. And since the time interval between the (first) get call and the compareAndSet is larger, the probability of looping increases.
user_1399850
Related