Compare and Swap (CAS)
is a technique used to obtain synchronization during multiple writes
where each write value depends upon the current state of the shared
basically means that a variable will first be compared with a value
to see if it has changed.
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
it has not changed, then it means that its value has not been
modified by any other thread and so it can be swapped.
it can be implemented as follows:
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).
a thread is able to successfully swap, it proceeds, else it has to
above suffers from ABA
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
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.
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.
example, a lock-free counter can be implemented as follows:
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)
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
single benefit has shown to increase throughput of multithreaded
programs by a significant amount.
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).
all the classes in the java.util.concurrent
package use atomic variables instead of synchronization, either
directly or indirectly