I++ is not a thread-safe operation because it is not an atomic operation.
So, what collections or utility classes should I use if I want to achieve something like i++?
Prior to JDK1.5, the synchronized keyword had to be relied on to ensure atomicity in multithreading operations on a base or reference data type, but this has changed since JDK1.5. Of course you can still use synchronized to ensure atomicity, and one thread-safe approach we’re talking about here is AtomicInteger, AtomicBoolean, etc. These atomic classes are thread-safe utility classes, and they are also lock-free. Let’s take a look at these utility classes and what lock-free is.
Understand AtomicInteger
AtomicInteger is a new utility class in JDK 1.5, so let’s first look at its inheritance
Like Integer, the wrapper for int, it inherits from Number.
The Number class is a wrapper around the basic datatype, from which all datatype related objects are inherited.
Its inheritance system is very simple, so let’s look at its basic properties and methods
The basic properties of AtomicInteger
AtomicInteger has three basic properties
Unsafe is a class under the Sun.misc package, and AtomicInteger relies on some native methods provided by Sun.misc.Unsafe to ensure atomicity of operations.
The Unsafe objectFieldOffset method obtains the offset of the memory address of a member attribute relative to the object’s memory address. In simple terms, find the memory address of the variable, so that you can use the memory address to operate directly. This value is value
We’ll talk more about that later
Value is the value of an AtomicIneger.
Constructor of AtomicInteger
Moving on, there are only two AtomicInteger constructors. One is a no-argument constructor. The default value of the no-argument constructor is 0, and the constructor with arguments can specify an initial value.
Methods in AtomicInteger
Let’s talk about the methods in AtomicInteger.
Get and Set
Let’s start with the simplest get and set methods:
Get () : Gets the current AtomicInteger value
Set () : Sets the current AtomicInteger value
Get () can read AtomicInteger atomically, and set() can set the current value atomically, because both get() and set() ultimately operate on the value variable, which is volatile. Therefore, get and set are equivalent to reading and setting memory. As shown in the figure below
We mentioned above the non-atomic operations on i++ and i++, and we said we could use the method in AtomicInteger to make the substitution.
Incremental operation
The Incremental correlation method in AtomicInteger satisfies our requirements
getAndIncrement(): atomically increments the current value and returns the result. The equivalent ofi++In the operation.
To verify that it is thread safe, let’s test with the following example
public class TAtomicTest implements Runnable{
AtomicInteger atomicInteger = new AtomicInteger();
@Override
public void run(a) {
for(int i = 0; i <10000;i++){
System.out.println(atomicInteger.getAndIncrement());
}
}
public static void main(String[] args) {
TAtomicTest tAtomicTest = new TAtomicTest();
Thread t1 = new Thread(tAtomicTest);
Thread t2 = newThread(tAtomicTest); t1.start(); t2.start(); }}Copy the codeSo if you look at the output and you see that it’s a thread-safe operation, you can change the value of I, but you still end up with i-1, because it’s evaluated first, and then + 1, and it looks like this.
incrementAndGetInstead, perform the + 1 operation first and then return the incremented result, which ensures atomicity on value. As shown in the figure below
Decremental operation
In contrast, a decrement operation like x– or x = x minus 1 is atomic. We can still use the method in AtomicInteger to replace it
getAndDecrement: returns an int of the current type and then decrement the value of value. Here is the test code
class TAtomicTestDecrement implements Runnable{
AtomicInteger atomicInteger = new AtomicInteger(20000);
@Override
public void run(a) {
for(int i = 0; i <10000 ;i++){
System.out.println(atomicInteger.getAndDecrement());
}
}
public static void main(String[] args) {
TAtomicTestDecrement tAtomicTest = new TAtomicTestDecrement();
Thread t1 = new Thread(tAtomicTest);
Thread t2 = newThread(tAtomicTest); t1.start(); t2.start(); }}Copy the codeBelow is a sketch of getAndDecrement
decrementAndGetAlso, decrementAndGet is a method that decrements and then obtains the value of a value, as shown below
LazySet method
Did you know that Volatile has memory barriers?
What is a memory barrier?
Memory barrier, also known as memory barrier, memory gate barrier, barrier instruction, etc., is a kind of synchronization barrier instruction. It is a synchronization point in the operation of random memory access by CPU or compiler, so that all read and write operations before this point can be executed before the operation after this point. It is also a technique for making the state of memory in a CPU processing unit visible to other processing units.
The CPU uses many optimizations, such as caching, instruction reordering, etc. The ultimate goal is performance. That is, when a program executes, it doesn’t matter if the instructions are reordered as long as the end result is the same. So instructions are not executed sequentially, but out of order, which causes a lot of problems, which also leads to memory barriers.
Semantically, all writes prior to the memory barrier are written to memory; Any read operation after the memory barrier can obtain the result of any write operation before the synchronous barrier. Therefore, for sensitive blocks, memory barriers can be inserted after write operations but before read operations.
The overhead of a memory barrier is very lightweight, but even a small barrier has a cost, and LazySet does just that by reading and writing variables as normal variables.
It could also be: Too lazy to put up barriers
GetAndSet method
Set atomically to the given value and return the old value.
Its source code calls the getAndSetInt method from unsafe, as shown below
GetIntVolatile (); getIntVolatile (); getIntVolatile ();
Loop until compareAndSwapInt returns false, indicating that CAS has not been updated to the new value, so var5 returns the latest memory value.
CAS method
We always say that CAS is actually the CompareAndSet method, this method just as the name, is the comparison and update meaning, of course this is a bit of a mistake, in fact, the other people’s meaning is to compare first, if satisfied then update.
If the current value is equal to expect, set the current value atomically to update the given value. This method returns a Boolean type, If true, the comparison and update succeeded; otherwise, it failed.
CAS is also a lock-free concurrency mechanism, also known as Lock Free, so do you think Lock Free is cool? Don’t.
Let’s build a CASLock that locks and unlocks
class CASLock {
AtomicInteger atomicInteger = new AtomicInteger();
Thread currentThread = null;
public void tryLock(a) throws Exception{
boolean isLock = atomicInteger.compareAndSet(0.1);
if(! isLock){throw new Exception("Locking failed");
}
currentThread = Thread.currentThread();
System.out.println(currentThread + " tryLock");
}
public void unlock(a) {
int lockValue = atomicInteger.get();
if(lockValue == 0) {return;
}
if(currentThread == Thread.currentThread()){
atomicInteger.compareAndSet(1.0);
System.out.println(currentThread + " unlock"); }}public static void main(String[] args) {
CASLock casLock = new CASLock();
for(int i = 0; i <5; i++){new Thread(() -> {
try {
casLock.tryLock();
Thread.sleep(10000);
} catch (Exception e) {
e.printStackTrace();
}finally{ casLock.unlock(); } }).start(); }}}Copy the codeIn the above code, we build a CASLock. In the tryLock method, we first update using the CAS method, throw an exception if the update is unsuccessful, and set the current thread to the locked thread. In unLock, we decide if the current value is 0, if 0 is what we want to see, and we return it. Otherwise, the value is 1, indicating that the current thread is still locked. We will check whether the current thread is locked, if so, perform unlocking operation.
So the compareAndSet we mentioned above can actually be resolved as follows
/ / pseudo code
/ / the current value
int v = 0;
int a = 0;
int b = 1;
if(compare(0.0) = =true){
set(0.1);
}
else{
// Continue down
}
Copy the codeYou can also take buying tickets in life scenes as an example. You must hold a ticket to travel in scenic spots. If you hold a fake ticket or a ticket that does not conform to the scenic spot, you can definitely be identified.
Without further ado, here is the schematic diagram of compareAndSet
weakCompareAndSetJDK1.8: compareAndSet: compareAndSet: JDK1.8: compareAndSet
But is that really the case? Not really, the JDK source code is too extensive and profound to design a repetitive method, and you think the JDK team is not going to make this low-level team, but why?
The book “Java High Concurrency In Detail” provides an answer
AddAndGet
AddAndGet and getAndIncrement, getAndAdd, incrementAndGet, etc. The while + CAS operation is equivalent to a spin lock. If CAS is modified successfully, the loop will continue, and if CAS fails, the loop will return. The schematic diagram is as follows
In-depth AtomicInteger
We have discussed the specific use of AtomicInteger above, and we know that AtomicInteger relies on volatile and CAS to ensure atomicity, so let’s analyze why CAS can guarantee atomicity and what is its underlying. What does AtomicInteger have to do with optimistic locking?
The underlying implementation principle of AtomicInteger
Let’s look at this lovely compareAndSetL(CAS) method again. Why are these two lines of code guaranteed to be atomic?
As you can see, this CAS method calls the compareAndSwapInt method from Unsafe, which we can look at in action as we dive into unsafe.
CompareAndSwapInt is a method in Sun.misc, this method is a native method, its bottom layer is C/C++ implementation, so we need to see C/C++ source code.
See what’s cool about C/C++? Using Java is to play with the application and architecture, C/C++ is to play with the server, the bottom.
CompareAndSwapInt source in jdk8u – dev/hotspot/SRC/share/vm/prims/unsafe. The app directory, its source code to achieve
That’s the Unsafe_CompareAndSwapInt method, which we found
I can’t read the C/C++ source code either, but that doesn’t stop us from finding the key code: Atomic:: CMPXCHG. CMPXCHG is an assembly instruction for x86 CPUS. Its main function is to compare and swap operands. Let’s go ahead and find the definition of this instruction.
We will find that the underlying implementation is different for different OS
We found the Windows implementation as follows
So let’s go down, it’s actually line 216, so let’s go in
At this point, assembly instructions and register related knowledge is needed.
OS :: IS-MP () above is an interface to a multiprocessing operating system, and __asm below is a C/C++ keyword for calling inline assembler programs.
The code in __asm is an assembler, which basically puts the dest, exchange_value, and compare_value values in registers. LOCK_IF_MP
In the case of multiple processors, the lock is executed and the comparison is performed. Where CMP stands for comparison, MP stands for MultiProcess, JE stands for equal jump, and L0 stands for identifier bit.
Going back to the assembly instruction above, we can see that the underlying CAS instruction is the CMPXCHG instruction.
Optimistic locking
ExpectValue: expectValue = expectValue = expectValue = expectValue = expectValue;
Because AtomicInteger is just an atomic utility class, it is not exclusive. It is not mutually exclusive like synchronized or lock. Remember that AtomicInteger has two methods get and set? They are only modified with volatile, and volatile is not atomic, so you can expect to have inconsistent expectvalues and the current values, so you can expect to have repeated modifications.
There are two solutions to the above situation. One is to use synchronized and lock and other similar locking mechanisms. This lock has exclusivity, that is to say, only one thread can modify at the same time. Another solution is to use a version number or CAS method.
The version number
The version number mechanism is implemented by adding A version field to the data table, indicating the number of times the data has been modified. When the write operation is performed and the write is successful, version = version + 1. When thread A wants to update data, the version value will be read as well as the data. If the version value read is the same as the version value in the current database, the update operation is updated until the update succeeds.
CAS method
Another option is CAS. We’ve devoted a lot of space to the CAS method, so we think you have a good understanding of how it works now, so we won’t go into how it works.
Everything has advantages and disadvantages, there is no perfect solution in the software industry only the optimal solution, so optimistic lock also has its weaknesses and defects, that is the ABA problem.
ABA problem
If A variable reads A value of A for the first time and is ready to write to A and the value is still A, can we assume that the value of A has not been changed? This could be the case with A -> B -> A, but AtomicInteger doesn’t think so, it just believes what it sees, and what it sees is what it sees. Take an example
Suppose you now have a single linked list, as shown below
A.next = B, b. next = null, there are two threads T1 and T2 respectively from the single linked list A, due to some special reasons, T2 changed A to B, then changed to A, T1 executed CAS method, found that the single linked list is still A, The CAS method is executed, and while the result is correct, this operation creates some potential problems.
At this point, it is still A single linked list. Two threads T1 and T2 fetch A from the single linked list, and T1 changes the list to ACD, as shown in the figure below
When T2 finds that the memory value is still A, it will try to replace the value of A with B, because the reference of B is null, so C and D will be in A free state
The AtomicStampedReference class after JDK 1.5 provides this capability. The compareAndSet method checks whether the value is equal to the expected value (the reference and postmark are equal to the expected reference and postmark, respectively). Is set atomically to the given update value.
Ok, so that’s the Java code flow, seeing native we know we need to polish CPP again. Open lu
UnsafeWrapper is just another name. It then goes through some JNI processing, and since compareAndSwapOject compares references, it needs to go through C++ object-oriented transformation. The primary method is atomic_compare_exchange_OOP
As you can see, the familiar term CMPXCHG reappears, meaning that compareAndSwapOject still uses the CMPXCHG atomic instruction, but it has undergone a series of transformations.
Afterword.
This raises the question, does CAS guarantee visibility between variables? Why is that?
One more question: where is the CPP source for getIntVolatile? How to find?
If you are interested in these two questions, welcome to communicate.
Cxuan, the programmer of the public account, replied to cXuan to receive high-quality materials.
I wrote six PDFS myself, very hardcore, linked below
I wrote six PDFS myself, very hardcore, linked below
I wrote six PDFS myself, very hardcore, linked below
Cxuan took pains to read four PDFS.
Cxuan read two more PDFS