比较并设置操作 Java

huangapple go评论71阅读模式
英文:

compare and set operation Java

问题

我正在学习Java中的多线程编程。

我有一个类:

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

还有一个增加方法:

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

可以简化为:

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

或者这样:

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

有人告诉我不能这样做,因为其他线程可能会改变方法内的数据。
但是,据我所知,比较并交换(CAS)是一个原子操作,如果第一个get()返回0,而第二个get()返回1,CAS操作不能改变计数器,因为如果get()返回1,意味着数据已经改变。

我的问题是,既然CAS是原子操作,为什么我不能执行上述操作,为什么不建议这样做?

英文:

I am studying multithreading in java.

I have a class

public class CASCount&lt;T&gt; {
    private final AtomicReference&lt;Integer&gt; count = new AtomicReference&lt;&gt;(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?

答案1

得分: 1

第一个重写是正确的。这个版本按照与原始版本相同的顺序执行相同的操作。由于这些代码是等价的,并且原始版本是正确的,所以重写也是正确的。

第二个重写需要更深入的分析。在以下T1、T2、T3等表示不同的线程。我忽略了装箱和拆箱的过程,因为我相当确定这对分析没有影响。

让我们从只有线程调用increment方法的情况开始;即计数器只增加。如果T1在第一个get()调用之后和compareAndSet()调用之前的increment调用之间成功增加计数器,那么compareAndSet(i1, i2)将(始终)看到i1值与当前值不同。因此,它将不执行“set”。第二个get()调用可能返回与第一个调用不同的值这个事实无关。在这种情况下,第二个重写是正确的。

但是如果还有一个像这样编码的decrement方法呢:

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

并且假设T1和T2调用increment,而T3在相同时间调用decrement,操作交错如下:

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

我们失去了T3的减少效果!

换句话说,如果我们不能假设计数器的值单调递增,第二个重写是不正确的。

我的问题是,为什么CAS是原子的情况下我不能执行上述操作?

在某些用例中,其中一个重写是不正确的,参见上文。

为什么不建议这样做?

有三个原因:

  1. 如果它没有问题,就不要修复它。
  2. 如果你重写一个众所周知的并发算法,责任真的在于你证明重写是正确的。而证明正确性通常比证明不正确性更难(就像我刚才所做的)。
  3. 在这种情况下,你调用了两倍数量的getCount()来避免使用本地变量。额外的调用会影响性能。由于(第一个)get调用和compareAndSet之间的时间间隔更长,循环的概率增加。
英文:

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() -&gt; 0
T2:  getCount() -&gt; 0, getCount() -&gt; 0, compareAndSet(0, 0 + 1) -&gt; true, 1
T1:  getCount() -&gt; 1,
T3:  getCount() -&gt; 1, getCount() -&gt; 1, compareAndSet(1, 1 - 1) -&gt; true, 0
T1:  compareAndSet(0, 1 + 1) -&gt; 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.

huangapple
  • 本文由 发表于 2020年10月16日 12:26:55
  • 转载请务必保留本文链接:https://go.coder-hub.com/64382907.html
匿名

发表评论

匿名网友

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen:

确定