65 Relationship Between CAS and Optimistic Lock When Will CAS Be Used #
In this lesson, I will explain the application scenarios of CAS and when to use CAS.
Concurrent Containers #
Doug Lea, the creator of the JUC package, extensively uses CAS technology, which ensures safety without the need for mutex locks and greatly improves the performance of utility classes. Let me show you the usage of CAS in concurrent containers through two examples.
Case 1: ConcurrentHashMap #
Let’s start with an example of the concurrent container ConcurrentHashMap. We’ll look at a snippet of code from the putVal method:
final V putVal(K key, V value, boolean onlyIfAbsent) {
if (key == null || value == null) throw new NullPointerException();
int hash = spread(key.hashCode());
int binCount = 0;
for (Node<K,V>[] tab = table;;) {
Node<K,V> f; int n, i, fh;
if (tab == null || (n = tab.length) == 0)
tab = initTable();
else if ((f = tabAt(tab, i = (n - 1) & hash)) == null) {
if (casTabAt(tab, i, null,
new Node<K,V>(hash, key, value, null)))
break; // no lock when adding to empty bin
}
// omitted parts
...
}
At line 10, there is a method call that stands out, which is “casTabAt”. The method name contains “CAS,” so we can guess that it must be closely related to CAS. Here is the code implementation of the casTabAt method:
static final <K,V> boolean casTabAt(Node<K,V>[] tab, int i,
Node<K,V> c, Node<K,V> v) {
return U.compareAndSwapObject(tab, ((long)i << ASHIFT) + ABASE, c, v);
}
This method contains only one line of code, which calls the compareAndSwapObject method of the U variable. So, what type of variable is U? U is defined as:
private static final sun.misc.Unsafe U
We can see that U is of type Unsafe, which includes native-level methods closely related to CAS, such as compareAndSwapInt, compareAndSwapLong, and compareAndSwapObject. The underlying implementation of these methods utilizes the CPU’s support for CAS instructions.
The casTabAt method mentioned above is not only used in the putVal method of ConcurrentHashMap but also used in important methods such as merge, compute, computeIfAbsent, and transfer. Therefore, the application of CAS in ConcurrentHashMap is quite extensive.
Case 2: ConcurrentLinkedQueue #
Next, let’s look at the second example of concurrent containers. The offer method of the non-blocking concurrent queue ConcurrentLinkedQueue also involves CAS. Here is the code of the offer method:
public boolean offer(E e) {
checkNotNull(e);
final Node<E> newNode = new Node<E>(e);
for (Node<E> t = tail, p = t;;) {
Node<E> q = p.next;
if (q == null) {
if (p.casNext(null, newNode)) {
if (p != t)
casTail(t, newNode);
return true;
}
}
else if (p == q)
p = (t != (t = tail)) ? t : head;
else
p = (p != t && t != (t = tail)) ? t : q;
}
}
It can be seen that in the offer method, there is a for loop, which is an infinite loop. There is a method related to CAS in line 8, which is the casNext method used to update the node. If the casNext method of p fails, casNext returns false, and the code continues to try in the for loop. So it is obvious that the offer method of ConcurrentLinkedQueue uses CAS.
These are two examples of the application of CAS in concurrent containers. Now let's take a look at the applications of CAS in databases.
### Database
In our database, there is also the application of optimistic locking and the CAS concept. When updating data, we can use the version field in the database to implement optimistic locking and CAS operations, without the need to add pessimistic locks when obtaining and modifying data.
The specific idea is as follows: When we retrieve the data, finish the calculation, and are ready to update the data, we check whether the current version number is consistent with the version number when the data was retrieved. If they are consistent, it means that the data has not been updated during the calculation, and we can directly update the current data. If the version number is not consistent, it means that another thread has modified the data during the calculation. In this case, we can choose to re-retrieve the data, recalculate, and then try to update the data again.
Suppose the version number when retrieving the data is 1, and the corresponding SQL statement is as follows:
UPDATE student
SET
name = '小王',
version = 2
WHERE
id = 10
AND version = 1
In this way, we can use the CAS concept to implement this update operation. It will first compare whether the version is the same as the initial value, 1. If it is the same, it will try to modify the name field and increment the value of version by 1.
### Atomic Classes
In atomic classes such as AtomicInteger, CAS is also used. We have analyzed the content of atomic classes in Lesson 39. Now let's review the key content related to CAS, which is the getAndAdd method of AtomicInteger. The code for this method is as follows:
```java
public final int getAndAdd(int delta) {
return unsafe.getAndAddInt(this, valueOffset, delta);
}
From the above three lines of code, we can see that the return value is the result of executing the getAndAddInt method of Unsafe. Next, let’s take a look at the implementation of the getAndAddInt method. The code is as follows:
public final int getAndAddInt(Object var1, long var2, int var4) {
int var5;
do {
var5 = this.getIntVolatile(var1, var2);
} while(!this.compareAndSwapInt(var1, var2, var5, var5 + var4));
return var5;
}
Here, we see the assignment to var5 in the above method, which calls the getIntVolatile(var1, var2) method of unsafe. This is a native method that gets the value at offset var2 in variable var1. In this case, var1 is the reference to the AtomicInteger object, and var2 is the offset of the value stored in the AtomicInteger (that is, valueOffset). Thus, var5 obtained here represents the value stored in the atomic class at the current moment.
Next, we see a compareAndSwapInt method, which passes in multiple parameters, namely var1, var2, var5, and var5 + var4. In fact, they represent object, offset, expectedValue, and newValue, respectively.
- The first parameter object is the object to be modified, passed in as this, which is the atomicInteger object itself.
- The second parameter is offset, which is the offset to obtain the value.
- The third parameter expectedValue represents the “expected value” and is passed in as the previously obtained var5.
- The last parameter newValue is the new value to be modified, which is equal to the previously obtained value var5 plus var4. var4 is the delta we passed in earlier. Delta is the value we hope to change in the atomic class, such as +1 or -1.
Therefore, the compareAndSwapInt method is used to check whether the current value of the atomic class’s value is equal to the previously obtained var5. If they are equal, it updates the calculated value var5 + var4. This is the process of CAS.
Once the CAS operation is successful, it exits the while loop. But it can also fail. If it fails, it means that the value of the value variable has changed between obtaining var5 and the CAS operation, indicating that another thread has modified this variable.
In this case, the code inside the loop will be executed again, re-obtaining the value of var5, which is the latest value of the atomic variable, and then using CAS to try to update it until it succeeds. It’s an infinite loop.
To summarize, the getAndAddInt method of Unsafe implements looping + CAS to obtain the value. During this process, it tries to update the value by using the compareAndSwapInt method. If the update fails, it re-obtains the value and tries to update it again until it succeeds.
Summary #
In this lesson, we explained the application scenarios of CAS. CAS is used in many code sections related to concurrent containers, databases, and atomic classes, so CAS has a wide range of application scenarios. You need to have a clear understanding of when to use CAS.