Shulou(Shulou.com)06/02 Report--

Today, I will talk to you about the example analysis of the spin lock Atomic class of Java CAS and its application, which may not be well understood by many people. in order to make you understand better, the editor has summarized the following content for you. I hope you can get something according to this article.

1. CAS operation

The mechanism used for optimistic locking is CAS,Compare and Swap.

CAS has three operands, the memory value V, the old expected value A, and the new value B to be modified. If and only if the expected value An is the same as the memory value V, change the memory value V to B, otherwise do nothing.

1. Non-blocking algorithm (nonblocking algorithms)

The failure or suspension of one thread should not affect the algorithm of the failure or suspension of other threads.

Modern CPU provides special instructions that automatically update shared data and detect interference from other threads, which compareAndSet () uses instead of locking.

2. Atomic example

The Atomic package is another Java package specially designed for thread safety under java.util.concurrent, which contains several atomic operation classes. This package provides a set of atomic variable classes. Its basic characteristic is that in a multithreaded environment, when multiple threads execute the methods contained in instances of these classes at the same time, it is exclusive, that is, when a thread enters the method and executes its instructions, it will not be interrupted by other threads, while other threads are like spin locks, waiting for the method to be executed until JVM selects another thread from the waiting queue to enter. This is just a logical understanding. It is actually implemented with the help of hardware-related instructions and does not block threads (or just at the hardware level). You can manipulate the basic data, the basic data in the array, the basic data in the class. The atomic variable class is equivalent to a generalized volatile variable, which can support atomic and conditional read-modify-write operations.

AtomicBoolean,AtomicInteger,AtomicLong,AtomicReference these four basic types are used to deal with Boolean, integer, long integer, object four kinds of data, its internal implementation is not simply using synchronized, but a more efficient way CAS (compare and swap) + volatile and native method, thus avoiding the high overhead of synchronized, and greatly improving the execution efficiency. Let's take a look at an example. The atomic operation corresponding to our usual iTunes + is: getAndIncrement ()

Public static void main (String [] args) {AtomicInteger ai = new AtomicInteger (); System.out.println (ai); ai.getAndIncrement (); System.out.println (ai);}

Take out AtomicInteger to study how to achieve data correctness without locks.

Private volatile int value

In the unlocked mechanism, the volatile primitive is needed to ensure that the data between threads is visible (shared).

Only in this way can it be read directly when the value of the variable is obtained.

Public final int get () {return value;}

Then let's take a look at how + I does it.

Public final int incrementAndGet () {for (;;) {int current = get (); int next = current + 1; if (compareAndSet (current, next)) return next;}}

The CAS operation is used here, each time you read the data from memory and then CAS the data and the result after + 1, and return the result if it is successful, otherwise try again until it is successful.

CompareAndSet uses JNI to complete the operation of CPU instructions.

Public final boolean compareAndSet (int expect, int update) {return unsafe.compareAndSwapInt (this, valueOffset, expect, update);}

The whole process is like this, using the CAS instruction of CPU and JNI to complete the non-blocking algorithm of Java. Other atomic operations are done using similar properties.

The whole J.U.C is based on CAS, so for synchronized blocking algorithm, J.U.C has a great improvement in performance. The article in Resources describes how to use CAS to build non-blocking counters, queues, and other data structures.

2. ABA problem

CAS looks great, but it can cause "ABA problems".

An important premise of CAS algorithm is to take out the data at a certain time in memory, and compare and replace it at the next time, then the time difference class will lead to the change of data.

For example, when a thread one fetches A from memory location V, another thread two also fetches A from memory, and two does some operations and becomes B, and then two changes the data in V position into A, then thread one performs a CAS operation to find that there is still An in memory, and then the one operation succeeds. Although the CAS operation of the thread one is successful, it does not mean that there is no problem with the process. If the head of the linked list returns to its original value after two changes, it does not mean that the linked list has not changed. So the atomic operation AtomicStampedReference/AtomicMarkableReference mentioned earlier is very useful. This allows atomic operations on a pair of changing elements.

There is a classic ABA problem in using CAS to do Lock-Free operations:

Thread 1 is going to use CAS to replace the value of the variable from A to B. before that, thread 2 replaced the value of the variable from A to C, and then C to A, and then thread 1 found that the value of the variable was still A when it executed CAS, so CAS succeeded. But in fact, the scene at this time is different from the original. Although CAS is successful, there may be hidden problems, such as the following example: there is a stack implemented with an one-way linked list, the top of the stack is A, and thread T1 already knows that A.next is B, and then wants to replace the top of the stack with B with CAS:

Head.compareAndSet (A & M B)

Before T1 executes the above instruction, thread T2 intervenes to unstack An and B, and then pushD, C, A. at this time, the stack structure is like the following figure, and object B is in a free state at this time:

At this point, it is thread T1's turn to perform the CAS operation, and the detection finds that the top of the stack is still A, so the CAS succeeds and the top of the stack becomes B, but in fact, B.next is null, so the situation becomes:

There is only one element B in the stack, and the linked list composed of C and D no longer exists in the stack, so C and D are thrown away for no reason.

These are the hidden dangers caused by the ABA problem. In the implementation of all kinds of optimistic locks, the version stamp version is usually used to mark records or objects to avoid the problems caused by concurrent operations. In Java, AtomicStampedReference also achieves this function. It marks the object version stamp stamp by wrapping the tuples of [Eter Integer], so as to avoid the ABA problem. For example, the following code updates the atomic integer variable with an initial value of 100 with AtomicInteger and AtomicStampedReference, respectively. AtomicInteger will successfully perform the CAS operation, while AtomicStampedReference with a version stamp will fail to perform CAS for ABA problems:

Package concur.lock;import java.util.concurrent.TimeUnit;import java.util.concurrent.atomic.AtomicInteger;import java.util.concurrent.atomic.AtomicStampedReference;public class ABA {private static AtomicInteger atomicInt = new AtomicInteger (100); private static AtomicStampedReference atomicStampedRef = new AtomicStampedReference (100,0) Public static void main (String [] args) throws InterruptedException {Thread intT1 = new Thread (new Runnable () {@ Override public void run () {atomicInt.compareAndSet (100,101); atomicInt.compareAndSet (101,100);}}) Thread intT2 = new Thread (new Runnable () {@ Override public void run () {try {TimeUnit.SECONDS.sleep (1);} catch (InterruptedException e) {e.printStackTrace ();} boolean c3 = atomicInt.compareAndSet (100,101) System.out.println (c3); / / true}}); intT1.start (); intT2.start (); intT1.join (); intT2.join () Thread refT1 = new Thread (new Runnable () {@ Override public void run () {try {TimeUnit.SECONDS.sleep (1);} catch (InterruptedException e) {e.printStackTrace () } atomicStampedRef.compareAndSet (100,101, atomicStampedRef.getStamp (), atomicStampedRef.getStamp () + 1); atomicStampedRef.compareAndSet (101,100, atomicStampedRef.getStamp (), atomicStampedRef.getStamp () + 1);}}) Thread refT2 = new Thread (new Runnable () {@ Override public void run () {int stamp = atomicStampedRef.getStamp (); System.out.println ("before sleep: stamp =" + stamp); / / stamp = 0 try {TimeUnit.SECONDS.sleep (2) } catch (InterruptedException e) {e.printStackTrace ();} System.out.println ("after sleep: stamp =" + atomicStampedRef.getStamp ()); / / stamp = 1 boolean c3 = atomicStampedRef.compareAndSet (100,101, stamp, stamp+1); System.out.println (c3) / / false}}); refT1.start (); refT2.start ();}}

three。 Detailed explanation of spin lock

The concept of spin lock

The first is a lock, similar to a mutex, whose basic function is for synchronization between threads (processes). Unlike an ordinary lock, after a thread An acquires a normal lock, if thread B tries to acquire the lock, then thread B will hang (block) Just imagine, if the competition for resources between two threads is not particularly fierce, and the cost of thread context switching caused by a processor blocking a thread is higher than the cost of waiting for resources (the lock holder holds the lock for a short time), then thread B can not give up the CPU time slice, but can wait "in place" until the lock holder releases the lock. This is the principle of spin locking. It can be seen that spin lock is a kind of non-blocking lock.

Problems that may be caused by spin locks:

1. Excessive occupation of CPU time: if the current holder of the lock does not release the lock for a long time, the waiters will occupy the cpu time slice for a long time, resulting in a waste of CPU resources, so you can set a time, when the lock holder does not release the lock, the waiters will abandon the CPU time slice blocking

two。 Deadlock problem: imagine that a thread tries to acquire a spin lock twice in a row (for example, in a recursive program), the first time the thread acquires the lock, and the second time it tries to add the lock, it is detected that the lock is occupied (actually occupied by itself), then the thread will wait for itself to release the lock and cannot continue to execute, resulting in a deadlock. Therefore, when a recursive program uses a spin lock, it should follow the following principle: a recursive program should never call itself when it holds a spin lock, nor should it try to acquire the same spin lock when it is called recursively.

The CAS operation AtomicReference owner = new AtomicReference () in class SpinLock {/ / java; / / the thread object private int count; public void lock () {Thread cur = Thread.currentThread () that holds the spin lock; / / the lock function sets owner to the current thread and predicts that the original value is empty. The unlock function sets owner to null and predicts the value to the current thread. / / when a second thread calls the lock operation, the loop / / is executed because the owner value is not null, until the first thread calls the unlock function to set owner to null before the second thread can enter the critical section. While (! owner.compareAndSet (null, cur)) {}} public void unLock () {Thread cur = Thread.currentThread (); owner.compareAndSet (cur, null);} after reading the above, do you have any further understanding of the sample analysis of the spin lock Atomic class of Java CAS and its application? If you want to know more knowledge or related content, please follow the industry information channel, thank you for your support.

Welcome to subscribe "Shulou Technology Information " to get latest news, interesting things and hot topics in the IT industry, and controls the hottest and latest Internet news, technology news and IT industry trends.