How does a function becomes atomic?

Question

I have been reading the book called art of multiprocessor programming and came across functions such as get(), getandset(), compareandset(), getandIncrease(), getandIncrease() etc.

In the book it says that all the above function are atomic and I agree but I had my own doubts on how some function becomes a atomic function.

Why does the function with get or compare become atomic ? - because it has to wait till it gets the value or waits till some condition becomes true which creates a barrier, hence atomic.

Am I right in thinking this way? is there any thing that I have missed ?

When I do

 if (tail_index.get() == (head_index.getAndIncrement()) 

is this atomic?

Answer 1

A function is atomic if it appears to occur instantaneously.^[1]

Here, "appears to" means from the point of view of the rest of the system. For instance, consider a synchronized function that reverses a linked list. To an outside observer, the operation clearly does not occur instantaneously: it takes many reads and writes to update all the list pointers. However, as a lock is held the entire time, no other part of the system may read the list during this time, so to them, the update appears instantaneous.

Equally, CAS (compare-and-set) operations do not actually occur instantly on modern computers. It takes time for one CPU core to obtain exclusive write access to the value, and then it takes more time for another core to re-obtain read access afterwards to see the new value. During this time, the CPU is executing other instructions in parallel. To ensure the illusion of instantaneous execution is preserved, the JVM issues CPU instructions before and after the CAS operation to ensure no logically subsequent reads get pulled up and executed before the CAS finishes (which would allow you to read a part of the linked list before you had actually taken the lock, for instance), and that no logically preceding writes get delayed and executed after the CAS finishes (which would allow another thread to take the lock before the linked list was completely updated).

These CPU ordering instructions are the key difference between AtomicInteger.compareAndSet and AtomicInteger.weakCompareAndSet (the "may fail spuriously" bit is easily rectified with a loop). Without the ordering guarantees, the weak CAS operation cannot be used to implement most concurrent algorithms, and "is only rarely an appropriate alternative to compareAndSet".

If this is sounding complicated...well...it is! Which is why you can still get a PhD by designing a concurrent algorithm. To show correctness for a concurrent algorithm, you have to consider what every other thread may possibly be doing to mess you around. It may help if you think of them as adversaries, trying to break the illusion of atomicity. For instance, let's consider your example:

if (tail_index.get() == (head_index.getAndIncrement()))

I assume this is part of a method to pop an item off a stack implemented as a cyclic array with index counters, and execute the body of the "if" if the stack is now empty. As head_index and tail_index are being accessed separately, your adversary can "divide" them with as many operations as he likes. (Imagine, for instance, that your thread is interrupted by the OS between the get and the getAndIncrement.) So it would be easy for him to add dozens of items to the stack, then remove all but one, leaving head_index above tail_index; your if block will then never execute, even though you are removing the last item on the stack.

So, when your book says get(), getAndSet(), etc. are atomic, it is not making a general statement about any possible implementation of those methods. It's telling you that the Java standard guarantees that they are atomic, and does so by careful use of the available CPU instructions, in a way that would be impossible to do in plain Java (synchronized lets you emulate it, but is more costly).

Answer 2

A method is made atomic relative to some instance by adding explicit thread-safety. In many cases this is done by marking the method as synchronized. There is not magic, if you look at the source code of the thread-safe class that claims that methods are atomic, you will see the locking.

WRT to your second part, No it is not atomic. Each method call is atomic but when you put two together the combination is not atomic. get and getAndIncrement have been explicitly made atomic. Once you add other code (or a combination of the calls) it is not atomic unless you make it so.

Answer 3

No, function, using get() is not atomic. But, for example, getAndIncrement or compareAndSet are atomic themselves. That means that it guaranteed, that all the logic is made atomically. For get() there is one another assurance: when you publish atomic value into one thread, it immediately becomes visible to another threads (just like volatile fields). Non-volatile and non-atomic values dont: there are cases, where value being set to non-volatile fiels is not visible to another threads; these threads get an old value reading field's value.

But you always can write atomic function using Atomic* classes and other synchonization primitives.