Article directory
- Lock-free concurrency (optimistic locking)
- 1. CAS (CompareAndSet)
- 2. Atomic integer (class implemented with CAS method: AutomicInteger)
- 3. Atomic Reference (AutomicReference)
- 4. Atomic Arrays
- 5. Atomic Updater
- 6. Atomic accumulator (LongAdder)
-
- 6.1 Advantages of accumulators
- 6.2 Accumulator member variables
- 6.3 Avoid false sharing
- 6.4LongAdder operating principle
-
- Add method
- LongAccumulate method
- 7. Unsafe
-
- 7.1 Unsafe for CAS modification operation
Lock-free concurrency (optimistic lock)
I am not afraid of other threads to modify my own variables. Even if I modify them, I keep trying to modify them. There will always be a modification without being modified by other counties.
1. CAS（CompareAndSet）
i.CompareAndSet (pre, next) The original intention of this method is to change the value of a to the value of next, but in multi-threading, because other threads may operate on a, this a is not necessarily when this thread operates a The original a, so after comparing a with pre, if they are the same, it means that other threads have not manipulated a, then the modification is successful, and this method will also return a true
Realize as shown in the figure below, loop continuously to meet the situation that a has not been modified
public void withdraw(Integer amount){<!-- -->
while(true){<!-- -->
int prev = balance. get();
int next=prev-amount;
if(balance. compareAndSet(prev,next)){<!-- -->
break;
}
}
}
The variables in CompareAndSet must be modified with volatile, because it is necessary to continuously obtain the latest value from the main memory to compare with pre to check whether a has been modified by other threads.
Lock-free concurrency is best used in multi-core situations, because the most important thing about lock-free is to prevent threads from entering the block, thereby causing a large cost in context switching and improving efficiency, but there are too few CPUs, and this thread is not assigned to a time slice. It will still context switch.
2. Atomic integer (class implemented with CAS method: AutomicInteger)
The implementation logic of the above method (the parameters of the method are implemented by the FunctionalInterface interface, like the previous Runnable, you can directly use the method lambda expression to pass parameters) is equal to the implementation logic of the following codes:
while(true){<!-- -->
int prev=i. get();
int next=prev*10;
if(i.compareAndSet(prev,next)){<!-- -->
break;
}
}
The real implementation method:
public final int updateAndGet(IntUnaryOperator updateFunction){<!-- -->
int prev, next;
do{<!-- -->
prev=get();
next=updateFunction.applyAsInt(prev);
\t\t
}while(!compareAndSet(prev,next));
return next;
}
3. Atomic Reference (AutomicReference)
A reference to a class is expressed in the following way: Reference to the BigDecimal class
private AtomicReference<BigDecimal> balance;
AtomicStampedReference can check whether the variable has been modified before. Some variables have been modified and then changed back. If the AtomicReference cannot be checked, the version number can be obtained through the getStamp() method.
Initialization method:
AtomicStampedReference<String> ref=new AtomicStampedReference<>("A",0);
The CAS operation can be changed to the following code
If a CAS operation occurs, first compare whether this version (which has been saved in advance in the previous int stamp=ref.getStamp method) has been modified by others before, if not, give the version number + 1, you can see This class can be checked to have been modified several times.
And AutomicMarkableReference can only check whether it has been modified
After modification, replace initialMark with false
4. Atomic Array
5. Atomic Updater
Modify the member variable method in the corresponding object of this class:
6. Atomic accumulator (LongAdder)
6.1 Advantages of accumulators
When there are multiple threads manipulating a shared variable for accumulation, each thread will use CAS to continuously try to accumulate in a loop (as long as the optimistic lock CAS fails, it will loop back to the beginning and continue to try to operate), and the thread will stop at This cycle does not move, and the efficiency is not high.
LongAdder implements an array of cells in the class. When thread competition occurs, the array is created, and each thread accumulates an element in the array corresponding to the operation. My initial question is, since the objects operated by each thread are all It’s different, is this variable still shared? It was 1 at the beginning, and both threads add 1, so isn’t it two 2, but the result we need is 3. It turns out that in this class, only how much is added to each cell is recorded. At the end of the accumulation, a sum method will be implemented to count the total amount added, and finally added to the initial number. Let each thread wait for the CAS cycle, which improves efficiency.
6.2 Accumulator member variables
1. Cell[] cells
This is the core part, the variable is created lazily, and only when thread competition occurs will it enter the creation logic
2. base
This base refers to the initial number. If there is no competition, it will be accumulated on the base. If there is competition, it will be used as the base number in the final sum.
3. cellsBusy
This variable implements a CAS lock. A cellsBusy of 0 means that no process currently owns the lock. When the process tries to lock, it will try to use the CAS operation to set cellsBusy to 1. If the attempt fails, it will continue to loop. When you need to release the lock, you only need to set cellsBusy to 0, because no thread is eligible to operate cellsBusy at this time, and no cas operation is required to ensure atomicity. The realization principle is shown in the figure below
6.3 Avoid false sharing
Because cells are arrays, arrays are generally stored continuously in memory. In order to improve efficiency, the CPU will store the data read and written into the cache line, but the cache line is stored piece by piece, which means that a thread may only need the array. The first cell in the cache line, but the entire array is indeed stored in the cache line, so in order to ensure safety, every time the array data is modified, the corresponding data of the entire cache line in the main memory needs to be marked as invalid. Others need to operate this The thread of the array is also forced to modify the data of its own cache line, which reduces the efficiency.
Use the @sun.misc.Contented annotation to decorate a class. A padding will be added to the end of each object of this class in the main memory so that it can reach the size of a cache line, so that each CPU stores the cache line. Only the data it needs will not affect the modification of other data in the array.
6.4LongAdder operating principle
Add method
LongAccumulate method
7. Unsafe
A very low-level object that provides a method to directly manipulate memory and threads. Because it is too low-level, programmers will cause many security problems when using it, so it is named Unsafe. It is a singleton implementation and must be obtained through reflection, because it is private variable.
7.1 Unsafe for CAS modification operation
Example: Modify the value of a member variable in an object
