AtomicReference, I don't get it

I think you may be misinterpreting the purpose of the logic. From my understanding (caveat emptor) this logic is trying to do no more than to ensure that the return value is the immediate predecessor to the value you are setting. For example, if you try to set a value, which is currently 4, to 10 and it didn't have this logic it may return "4" even though between the read and the write something else set it to 7. So that would return 4 and this would return 7 and the final value would be 10, or that would return 10 and this would return 4 and the final value would be 7. I don't think the method or its intended users care about what value "wins", only that you don't have both of them return 4.

Hi Scott, I get what you're saying as that is my understanding of how is was suppose to be used. However...

getAndSet

public final V getAndSet(V newValue)

• Set to the given value and return the old value.

• Parameters:

• newValue - the new value

• Returns:

• the previous value

The javadoc doesn't suggest that having multiple threads updating this data structure will result in a race condition.

I have to agree with Scott. It seems to me that the intent is to assure that no other thread changed the value during the course of the get() and the CAS. It does that.

I am unclear what you mean by "win" in this case, or even exactly how this is a race condition. To succeed, a thread needs to execute the get() and the CAS atomically; to fail it means some other thread managed to do that *in between* the get() and CAS of the current thread. So I'm not clear on what it means to be "the loser of the race condition"; the code as written ensures that an N calls to getAndSet() will occur atomically; actually, they will behave serially, with any given call returning the value which was last set prior to the successful CAS. However, the code does not impose that the first thread to attempt the get() + CAS pair will be the first to succeed -- based on hardware vagaries it may not be or so. But that is hardly losing.

It seems to me it guarantees exactly what the javadoc says -- it will set it to the specified value, and return the old value. Nowhere does the javadoc make a claim as to the fairness of this behavior in terms of ordering. It further defines "old value" as the last value the object held prior to a successful CAS -- not the value at the time the getAndASet call was made. You can't argue that is wrong interpretation, though you might favor other interpretations more.

Ok, let me rephrase this. What value does CAS in a loop like this have over volatile?

- in java synchronization allows you to do two things - atomic compound operation and it ensures visibility of shared data

• - volatile is capable of ensuring the visibility issue, but not the atomic operations(one variable depends on the other)

• If you would like to implement a counter with volatile variable only you would not succeed. But with AtomicVariables it is as simple as calling incrementAndGet()

public final int incrementAndGet() {

• for (;;) {

• int current = get();

• int next = current + 1;

• if (compareAndSet(current, next))

• return next;

• }

• }

• - anyway the getAndSet method has the same semantic as volatile variable at least as I understand it.

Kirk,

re-read what Scott and chris are saying. It is NOT possible to perform a get AND a SET operation atomically using a volatile.

Example (I will use an int and corresponding AtomicInteger the same principle applies for AtomicReference):

volatile int count =1;

int last = count; count++; System.out.println(last);

If two threads race through this code both threads could print 1. You are guaranteed that count will be 3.

Otoh if you used AtomicInteger then you guarantee that one and only one thread in the race prints 1 and one and only one thread prints 2. The final value is still 3.

Talyor,

I'm not asking about getAndIncrement, this is about getAndSet. So while your argument is correct, its addressing a different question.

That said, with getAndSet, if one thread is trying to set the value to 6 and another 10, you don't know what state you'll end up with in the end.

Kirk,

The argument is the same for getAndSet.

Consider:

AtomicReference ref = new AtomicReference(foo);

Thread A: Object oldVal = ref.getAndSet(bar);

Thread B: Object oldVal = ref.getAndSet(woz);

If thread A and B are executing concurrently, we are not guaranteed which one will execute first (your argument). We are, however, guaranteed that A and B will each have different values for oldVal, namely one will be foo and depending on who wins the race, bar or woz. We are guaranteed here that Thread A.oldVal != Thread B.oldVal.

Compare this to the volatile version:

Object ref = foo;

Thread A: Object oldVal = ref; ref = bar;

Thread B: Object oldVal = ref; ref = woz;

Here, both threads could wind up with oldVal being foo (Thread A.oldVal != ThreadB.oldVal no longer holds). We still don't have a guarantee about who will win the race, so ref could end up being bar or woz, as in our AtomicReference example.

The point is about atomicity of the get and set operation which otherwise is two operations.

Reference assignment is always atomic and this implementation also uses volatile. CAS is there to provide a way to change a value in memory with a means of failing in the case where you'd be "corrupting" an others work.

The apparent value add in this implementation is that (as you said), successive concurrent updates *may* (this is where we differ slightly) end up with different values. What would seem to be lost is in this implementation is the ability to detect if I'm about to corrupt while remaining lockless.

Yes, a read, or a write of a volatile is atomic. But the read AND the write is not atomic.

That's what this implementation is doing for you - it is making both the read and the write atomic so you get to read what was there at the time you set it.

Hi,

I think you misuse the term 'race condition'. The fact that two threads want to read and update the same data does not necessarily mean a data race, as long as operations are properly synchronised.

Suppose you had: public class SomeClass() {

• private String myString = "initial value";

• public String replaceString(String newValue) {

• String oldValue = myString;

• myString = newValue;

• return oldValue;

• }

The main thread would create an instance of this. Two threads, t1 and t2, would each have access to the same instance of SomeClass. t1 would call System.out.println("t1 replaced " + someInstance.replaceString("t1's value")); t2 would call System.out.println("t2 replaced " + someInstance.replaceString("t2's value"));

Chances are you would sometimes see output like t1 (or t2) replaced initial value t2 (or t1) replaced initial value (or t1(t2) replaced null, as there are no visibility guarantees without any synchronisation)

This is a data race. The order of operations cannot be established, data has been lost.

Make replaceString synchronized. Now you may only see t1 (or t2) replaced initial value t2 (or t1) replaced t1(or t2)'s value You can now establish the order: initial write, followed by t1's read of that value, updating it with t1's value, t2 reading what t1 had written, t2 updating (you may swap t1 and t2, of course - there are no guarantees which one comes first, but the order can always be determined afterwards - hence no data loss).

Making the field volatile would help with visibility, but not with the data race.

getAndSet provides what the synchornized method would, but is cheaper.

Hi Kofa,

Point taken on mis use of the term race condition. So lets define one. Lets say a race condition occurs when the order in which internal variables are changed determines how a program will function. A CAS should *only* affect a memory cell IFF it can knows the value that is currently sitting in that cell. If a thread can't predict the value then the CAS should fail. What getAndSet does is completely over ride this behavior thus delegating the responsibility of constancy of view to the caller. However, the getAndSet completely ignores CAS failures and in doing so doesn't protect you from cases where two or more threads may inadvertently tromp on each other. You only get to know about the trampling after the fact. So I'm not disputing many of the technical points regarding the mechanics of how this all works, that is perfectly clear. However, the semantics are some what less than they should be IMHO.

Hi Kirk,

what a race condition is is defined in JLS section 17.4.5, p.563.

I don't know what you mean by "A CAS should *only* affect a memory cell IFF it can knows the value that is currently sitting in that cell. If a thread can't predict the value then the CAS should fail." AtomicReference.compareAndSet() does what you want: updates the value if it matches a certain value (e.g. the current thread's idea about its value), and returns true; otherwise, returns false. getAndSet() does not promise to update it based on some condition (e.g. some thread's idea about the contents).

Concurrent programs are usually non-deterministic, when it comes to timing of events. This does not mean they are not correct. Take, for example, a server where multiple threads service requests: the order in which requests will be serviced, and the thread servicing some specific request will be different every time, but as long as each request is serviced, we do not care. Or take a long-running calculation that a master splits into sub-calculations and distributes between several slaves (workers), then creates a final result based on the results of the individual sub-calculations: the order in which those results become available is not important (and is not fixed); as long as the aggregate result is correct (always the same, given the same inputs), the program is correct.

If you want to make sure things happen in a certain order, you'll have to use the synchronization utilities (e.g. Lock, Semaphore, Barrier, Latch), or types like Future and BlockingQueue to make sure you establish ordering between your threads' actions.

Maybe you misunderstand the while loop in getAndSet? Here the thread has NO idea about the old value of the variable, wants to unconditionally set its desired value, and learn what value was overwritten (what value was last set by any thread). It starts with a get() to read the current value, then calls compareAndSet(). If the value was not overwritten by some other thread, compareAndSet will return true and we leave the loop, knowing that the overwritten value was what we read (and passed to compareAndSet). If the comparison fails, we read again, and continue the loop until we get lucky (which, unless the AR is heavily contended, will happen pretty soon).

I don't think the JLS says anything much different that my simple definition. Also, I'm not interested in the overly pessimistic locking models we are current forced to use. Database vendors realized a long time ago that is you want things to scale, you can not use pessimistic locking models. But using a CAS, we should be able to loosen the model up a bit and in the process, achieve higher throughput. There is no point in giving me a data structure that forces me to use synchronization on an outer layer. In fact, Little's law tells me that would be worse than just using a fully synchronized data structure.

I'm not saying this code is incorrect, I'm just pointing out that I don't understand why the author(s) decided to over-ride the value of using CAS in that it will fail if you can't predict the current value in the memory cell. That gives me a chance to decide how I want to react to the situation. In this code, I've no choice, the value will be slammed down into the cell no matter what. The most popular use cases would or could force me to synchronize the call to getAndSet thus defeating the purpose of using such a data structure.

IMHO, this only works because locks (read shared data) are rarely accessed by more than one thread. In those rare cases where you do have many threads chasing the same bits of data, there is rarely contention. The reasons for this are numerous but one is tied to the number of cores that we've typically been testing with. That condition (as we are well aware) is fast coming to and end. So while this maybe good enough for our current situation, we must remember that it is good enough for our current situation.

I'll be posting code in the next couple of weeks so people can kill my code instead of my words ;-)

Kirk,

It seems don't get what you're not getting. ;-) Why don't you use compareAndSet() instead of getAndSet() to set the value conditionally?

Kofa

Indeed, compareAndSet is a better choice. But the question still remains, why is that method there in the first place?

why is that method there in the first place?

Well, check out the source of LinkedBlockingQueue.

Also, suppose that there is a buffer that can hold one element only. Normally, one would implement this with a bounded queue, but for the sake of the example we'll use an AtomicReference. The sets of threads could be using it, producers that put something there if empty, and consumers, which take whatever is there. We'll throttle producers by having them process the item themselves if the buffer is full (meaning all consumers are busy - normally, consumer threads will take items and process them, so the buffer should be empty); this way, producers will not create too many items that no thread can process.

Producers would do:

while (true) {

• Item i = new Item();

• if (!buffer.compareAndSet(null, i)) {

• // buffer was full, no consumer is available, we'll process the item ourselves

• processItem(i);

• }

A consumer could do something like this:

while (true) {

• // we attempt to take an item and mark the buffer as empty

• Item i = buffer.getAndSet(null);

• if (null != item) {

• // there is some work to do

• processItem(i);

• } else {

• // buffer was empty, do something else

• doSomeOtherWorkOrGoOnVacation();

• }

I know the example is contrived. Real uses would probably be synchronisation logic, like in LinkedBlockingQueue.

I wouldn't necessarily say that the example code is contrived. I would say that as much as it justifies the implementation, it also calls into question as to where to draw the line when designing a group of classes. The technical label for this is separation of concerns. The question remains; is it appropriate for this method to exist in the class? Is this slam down behavior something that should be in the client code rather than here? I'd argue yes but not to the death.