Compare and Swap (CAS)
CAS
is a technique used to obtain synchronization during multiple writes
where each write value depends upon the current state of the shared
variable.
It
basically means that a variable will first be compared with a value
to see if it has changed.
If
it has changed, then it means its value has been updated by some
other thread and hence swap is not possible. In such a case, current
value of the shared variable is obtained and new value is calculated
from it.
If
it has not changed, then it means that its value has not been
modified by any other thread and so it can be swapped.
Coding-wise,
it can be implemented as follows:
The
whole compare and swap operation is an atomic one (that’s why
synchronized keyword is used) guaranteeing that swap by one thread
does not concurrently happen during swap by another thread (if both
discovered that the variable’s value had not changed and both
try to update).
If
a thread is able to successfully swap, it proceeds, else it has to
retry.
The
above suffers from ABA
problem (means
value becomes A again after becoming B for a short while, hence the
name ABA). If value becomes A again after becoming B, then the thread
has no means of knowing that the value was indeed changed between.
For some threads it may not be an issue but for others it may be. To
break this, double-length
CAS is
used. DL-CAS uses a counter which is incremented with each swap and
compares both counter and the variable to check for change. Hence
even if the value becomes same after several changes, the counter
value would have increased and the compare would fail.
CAS
based algorithms are called lock-free,
because threads do not ever have to wait for a lock (sometimes called
a mutex or critical section, depending on the terminology of your
threading platform). Either the CAS operation succeeds or it doesn't,
but in either case, it completes in a predictable amount of time. If
the CAS fails, the caller can retry the CAS operation or take other
action as it sees fit.
For
example, a lock-free counter can be implemented as follows:
(This
approach guarantees that every call to increment will increment the
counter and not fall prey to two threads reading same value,
incrementing to same value and then writing the same value resulting
in a total increment of 1 even though increment() was called twice)

So,
in summary, CAS has one benefit - “It
avoids thread locking thus eliminating the whole OS infrastructure of
waiting and notification. This also avoids deadlock situations.
Downside is that the CAS function has to be called several times to
complete the operation but that is very lightweight as compared to
thread waiting/notification.”
This
single benefit has shown to increase throughput of multithreaded
programs by a significant amount.
The
atomic
variable classes
in Java 5 all expose a compare-and-set primitive (similar to
compare-and-swap), which is implemented using the fastest native
construct available on the platform (compare-and-swap, load
linked/store conditional, or, in the worst case, spin locks). Nine
flavors of atomic variables are provided in the
java.util.concurrent.atomic package (AtomicInteger; AtomicLong;
AtomicReference; AtomicBoolean; array forms of atomic integer; long;
reference; and atomic marked reference and stamped reference classes,
which atomically update a pair of values).
Nearly
all the classes in the java.util.concurrent
package use atomic variables instead of synchronization, either
directly or indirectly
|