Question about CAS (compare and swap) method

[illidian]

CAS method can fail because of 2 reasons:
1. - the operation was failed because of other thread.
2. - the comparison was failed.

The question is: how I know the reason of failure? Because in first case I probably whould like to retry operation in loop until it succeeded, but in second case loop will be infinite.

Thanks.

[sukatoa]

CAS method can fail because of 2 reasons:
1. - the operation was failed because of other thread.
2. - the comparison was failed.

The question is: how I know the reason of failure? Because in first case I probably whould like to retry operation in loop until it succeeded, but in second case loop will be infinite.

Thanks.

Welcome to this forum...

I really don't understand about your statements and the question...

I might be wrong if i will force myself to analyze your post...

Where did you get that "CAS"?

It is new to me...

Can you post what you have read about that term?


Wondering,
Sukatoa

[JosAH]

CAS method can fail because of 2 reasons:
1. - the operation was failed because of other thread.
2. - the comparison was failed.

The question is: how I know the reason of failure? Because in first case I probably whould like to retry operation in loop until it succeeded, but in second case loop will be infinite.

Thanks.

Look what Google came up with!

kind regards,

Jos

[sukatoa]

Base on Jo's URL given, It is about Assembly language program design implementation.

Correct me if im wrong...

I wonder why you post this in Java forum...
If you mean that you are asking this for Assembly, i can share a little bit
about XCHG and CMP instructions... Tell me...

But if you mean CAS in java (Compare and Swap)...

There are many possible ways, without failure(Depends on implementation)


Sukatoa...

[illidian]

Because you asking why I posting this question on Java forum, I feel I have to clarify number of points.
First, CAS operation is atomic compare-and-set(swap) operation. If you don't know what mean "CAS" - probably you can't help me.
So how this related to Java?
I talking about "java.util.concurrent" library. Please examine AtomicMarkableReference class, compareAndSet method. It implemented as the following:

public boolean compareAndSet(V expectedReference, V newReference, boolean expectedMark, ,boolean newMark)
{
ReferenceBooleanPair current = atomicRef.get();
return expectedReference == current.reference &&
expectedMark == current.bit &&
((newReference == current.reference && newMark == current.bit) ||
atomicRef.compareAndSet(current, new ReferenceBooleanPair<V>(newReference, newMark)));
}

So my previous question is related to last line in this method. Well, if we already talking about this, I will ask the main question:

When I looking to this implementation, I see 2 possible problems:

1. I think comparison operation (==) is not atomic, even on volatile values. To do comparison, CPU have to load first value to register, then second value to register and only then return result of comparison. Could other thread enter in the middle of comparison and change one of the values? In this case comparison operation could fail (or succeed) when it not supposed to.

2. Consider following history of thread A and thread B:

Thread A: ReferenceBooleanPair current = atomicRef.get(); //thread A obtained reference to volatile pair
Thread A: expectedReference == current.reference //here thread A completed first comparison
Thread B: ReferenceBooleanPair current = atomicRef.get(); //thread B preempted thread A
Thread B: expectedReference == current.reference &&
Thread B: expectedMark == current.bit &&
Thread B: ((newReference == current.reference &&
Thread B: newMark == current.bit)
Thread B: || CAS(current, new ReferenceBooleanPair<V>(newReference, newMark))) //thread B swapping 'current' reference with new one
Thread A: && expectedMark == current.bit ... //at this point, thread A doing comparison with different object - could lead to the same result as previous case (?). In literature this problem named as "ABA" problem.

So how this method is atomic?

[sukatoa]

Because you asking why I posting this question on Java forum, I feel I have to clarify number of points.
First, CAS operation is atomic compare-and-set(swap) operation. If you don't know what mean "CAS" - probably you can't help me.
So how this related to Java?
I talking about "java.util.concurrent" library. Please examine AtomicMarkableReference class, compareAndSet method. It implemented as the following:

public boolean compareAndSet(V expectedReference, V newReference, boolean expectedMark, ,boolean newMark)
{
ReferenceBooleanPair current = atomicRef.get();
return expectedReference == current.reference &&
expectedMark == current.bit &&
((newReference == current.reference && newMark == current.bit) ||
atomicRef.compareAndSet(current, new ReferenceBooleanPair<V>(newReference, newMark)));
}

So my previous question is related to last line in this method. Well, if we already talking about this, I will ask the main question:

When I looking to this implementation, I see 2 possible problems:

1. I think comparison operation (==) is not atomic, even on volatile values. To do comparison, CPU have to load first value to register, then second value to register and only then return result of comparison. Could other thread enter in the middle of comparison and change one of the values? In this case comparison operation could fail (or succeed) when it not supposed to.

2. Consider following history of thread A and thread B:

Thread A: ReferenceBooleanPair current = atomicRef.get(); //thread A obtained reference to volatile pair
Thread A: expectedReference == current.reference //here thread A completed first comparison
Thread B: ReferenceBooleanPair current = atomicRef.get(); //thread B preempted thread A
Thread B: expectedReference == current.reference &&
Thread B: expectedMark == current.bit &&
Thread B: ((newReference == current.reference &&
Thread B: newMark == current.bit)
Thread B: || CAS(current, new ReferenceBooleanPair<V>(newReference, newMark))) //thread B swapping 'current' reference with new one
Thread A: && expectedMark == current.bit ... //at this point, thread A doing comparison with different object - could lead to the same result as previous case (?). In literature this problem named as "ABA" problem.

So how this method is atomic?

Ok, i can't help you...
Please clarify your post next time...

I talking about "java.util.concurrent" library

Did you say this at the top? ;-)

To do comparison, CPU have to load first value to register, then second value to register and only then return result of comparison.

the Flag registers will be the reference of the result...
When compare, if equal, ZEROFLAG will be one... If less than, BORROWFLAG will be one, if above, CARRYFLAG will be one...

And the return is only the representation of the event happen during comparison...

That's all i can share...
Sukatoa...