0

I have read about ABA problem in computer science(in concurrent environment)

Also I have read that this issue is not actual for languages with GC.

Now I am thinking about java atomics and I want to know if this problem prevented but I think this problem can occur.

lets research AtomicInteger for example and java 6 implementation

each method looks approximately like this:

private volatile int value;

public int incrementAndGet(){ 
    while(true){
        int old = value; //1
        int newValue = value+1;
        if(compareAndSet(old, newValue)){ //2
            return newValue;
        }
    }
}

looks like between //1 and //2 other threads can execute increment and decrement and this check will be added but accoring my inderstanding it is wrong and it is exhibition of ABA problem. Or for example between //1 and //2 occured Integer.MAX_VALUE increments or ecrements, value overflowed but old value equally new value

Lets research scenario(Thred 1 and Thread 2 make increment, but Thread 3 - decrement):

Thread 1 calls get and gets the value 1.
Thread 1 calculates next to be 2.
Thread 2 calls get and gets the value 1.
Thread 2 calculates next to be 2.
Thread 2 invoke compareAndSet and get success
Thread 3(decrement thread) calls get and gets the value 2.
Thread 3 invoke compareAndSet and get success
Thread 1 invoke compareAndSet and get success

P.S.

from: http://www.ibm.com/developerworks/library/j-jtp11234/

The ABA problem Because CAS basically asks "is the value of V still A" before changing V, it is possible for a CAS-based algorithm to be confused by the value changing from A to B and back to A between the time V was first read and the time the CAS on V is performed. In such a case, the CAS operation would succeed, but in some situations the result might not be what is desired. (Note that the counter and mutex examples from Listing 1 and Listing 2 are immune to this problem, but not all algorithms are.) This problem is called the ABA problem, and is generally dealt with by associating a tag, or version number, with each value to be CASed, and atomically updating both the value and the tag. The AtomicStampedReference class provides support for this approach.

Please, share your thoughts.

Mark Rotteveel
  • 100,966
  • 191
  • 140
  • 197
gstackoverflow
  • 36,709
  • 117
  • 359
  • 710
  • You need to read up on what `compareAndSet` does. It will only update when the current value is equal to old, and then will set it to new; this is done atomically. If the value has changed in the mean time, then it returns `false`, and it will loop for another attempt. – Mark Rotteveel Feb 07 '17 at 08:07
  • @Mark Rotteveel, I understand thiis, but as I wrote **between //1 and //2 other threads can execute increment and decrement** and thus value looks not changed but it wrong – gstackoverflow Feb 07 '17 at 08:08
  • 1
    You would be wrong, because the implementation of `compareAndSet` prevents exactly that problem. – Mark Rotteveel Feb 07 '17 at 08:09
  • @Mark Rotteveel, from your link: **to guarantee that the value was as specified and is now at the new value.** – gstackoverflow Feb 07 '17 at 08:13
  • Also if an interleaved operation changes the value so it is still exactly the same as old, did it actually change? From the perspective of the end result of the operation that is irrelevant. – Mark Rotteveel Feb 07 '17 at 08:13
  • Seriously, the CAS operation does "if value == old, set to new and return true, otherwise return false", and it does so atomically. So your imagined problem does not exist. – Mark Rotteveel Feb 07 '17 at 08:14
  • @Mark Rotteveel Did you here about ABA problem? looks like you still have not caught my thought – gstackoverflow Feb 07 '17 at 08:14
  • @Mark Rottevee atomics use the trick to check if value was not touched from everywhere, but this trick has weakness if value changed and returned to initial before compareAndSet – gstackoverflow Feb 07 '17 at 08:17
  • The ABA problem is not really relevant here, because the end result of the operation would be the same if another thread had not modified and set the value back, or if the increment operation had started after the other thread and modified and then set it back. Maybe you should study the ABA problem a little bit closer to understand its nuances. – Mark Rotteveel Feb 07 '17 at 08:20
  • @Mark Rotteveel, I updated topic, please read, I added concrete scenario which broke atomis accordinfg my understaning – gstackoverflow Feb 07 '17 at 08:23
  • Except it doesn't break anything: the observable effect would be the same if thread1 had started **after** thread3 had completed. The relevant part of the ABA problem you are forgetting is the _"it is possible that the behavior will not be correct due to the "hidden" modification in shared memory."_ So if you want to make this an ABA problem, you need a more complex scenario that does not only involve a single `AtomicInteger` (see some of the example on wikipedia). – Mark Rotteveel Feb 07 '17 at 08:33
  • @Mark Rotteveel I don't agree with your opinion and topic is not duplicate – gstackoverflow Feb 07 '17 at 08:36
  • I have reopened because it is indeed a different question, however I still don't think that in the simple example presented, the ABA problem is relevant at all. – Mark Rotteveel Feb 07 '17 at 08:42
  • "looks like between //1 and //2 other threads can execute increment and decrement" - not a problem. The results are exactly as if read 1 had instead executed after the intervening writes. – user2357112 Feb 07 '17 at 08:45
  • @Mark Rotteveel you can present relevant ABA problem in answer – gstackoverflow Feb 07 '17 at 08:48
  • @user2357112 but it breaks "untouch" concept. I can rely that state of related objects was not changed. For example modCount – gstackoverflow Feb 07 '17 at 09:07
  • @gstackoverflow: The results are indistinguishable from an execution where nothing else executed between the read and the write. – user2357112 Feb 07 '17 at 15:53

1 Answers1

0

In the case of the integer increment routine, it's possible that other threads might increment and decrement a value between the initial fetch and the compare-and-set, but if the combined effect of the other threads's actions is to leave the object holding the same value that was initially fetched, then writing out a value one larger than the original value will be the correct behavior. The combined effect of three increments and a decrement, for example, should be to leave an object holding a value two larger than its original value. If the third increment and the decrement happened between the load and compare-and-set performed by the second, the value written would be one larger than the value which was observed before that increment and decrement, but the net effect of writing that value after both the increment and decrement had occurred would be the same as that of writing it before either had occurred. If only the increment were to occur between the fetch and the compare-and-set, that would cause the compare-and-set to fail and the loop to be re-executed.

In languages without scanning garbage collectors, ABA issues primarily arise when using pointers because it would be possible that between the time a CompareAndSet loop performs the first fetch of a pointer's old value and the operation of the CompareAndSet, the pointer might be freed and replaced with a pointer to a different object that happens to have the same address. Java's scanning GC would make such issues impossible, however, since the reference to the object within the CompareAndSet loop would prevent it from being garbage collected. The only objects that can ever be garbage collected in Java are those to which no reference will ever exist (the JVM may prepare an object for garbage collection in cases where strong references could come into existence e.g. by examining weak references, or as a result of finalize(), but wouldn't be able to actually collect the object until all possibilities of references coming into existence were exhausted).

supercat
  • 77,689
  • 9
  • 166
  • 211