What is a spin lock
Speaking of spin locks, we need to start with the lock mechanism under multi-threading. Since some resources in a multi-processor system environment are limited, they sometimes require mutual exclusion. At this time, a lock mechanism will be introduced. Only the process that acquires the lock can obtain resource access. That is, only one process can acquire the lock at a time to enter its own critical area. At the same time, two or more processes cannot enter the critical area. When exiting the critical area, the lock will be released.
When designing a mutex algorithm, you always face a situation where you don’t have a lock, that is, what should you do if you don’t get a lock?
There are usually 2 ways to deal with it:
One is that the caller who has not obtained the lock is looping around there to see if the holder of the spin lock has released the lock. This is the focus of this article - spin lock. He doesn't have to block the line city (NON-BLOCKING).
Another way is that the process without obtaining the lock blocks itself (BLOCKING) and continues to execute other tasks on the thread, which is the mutex (including the built-in lock Synchronized, ReentrantLock, etc.).
introduction
CAS (Compare and swap), that is, comparison and exchange, is also the core operation that implements what we usually call spin lock or optimistic lock.
Its implementation is very simple, which is to compare an expected value with a memory value. If the two values are equal, replace the memory value with the expected value and return true. Otherwise, return false.
Ensure atomic operation
Any technology emerges to solve certain specific problems. The problem that CAS needs to solve is to ensure atomic operations. What is an atomic operation? Atoms are the smallest and indecent, and atomic operation is the smallest and indecent operation. That is to say, once the operation starts, it cannot be interrupted and knows that the operation is completed. In a multi-threaded environment, atomic operations are an important means to ensure thread safety. For example, suppose there are two threads working and want to modify a certain value. Take the self-increment operation as an example. To perform self-increment operation on an integer i, three basic steps are required:
1. Read the current value of i;
2. Add 1 to the i value;
3. Write the i value back to memory;
Suppose both processes read the current value of i, assuming it is 0, at this time, thread A adds 1 to i, thread B also adds 1, and finally i is 1, not 2. This is because the autoincrement operation is not an atomic operation, and the three steps divided into can be interfered with. As in the example below, for 10 threads, each thread performs 10,000 i++ operations, the expected value is 100,000, but unfortunately, the result is always less than 100,000.
static int i = 0; public static void add(){ i++; } private static class Plus implements Runnable{ @Override public void run(){ for(int k = 0;k<10000;k++){ add(); } } } public static void main(String[] args) throws InterruptedException{ Thread[] threads = new Thread[10]; for(int i = 0;i<10;i++){ threads[i] = new Thread(new Plus()); threads[i].start(); } for(int i = 0;i<10;i++){ threads[i].join(); } System.out.println(i); }In this case, what should I do? That's right, maybe you've already thought of it, you can lock or use synchronized implementation, for example, modify the add() method to the following:
public synchronized static void add(){ i++; }Alternatively, the locking operation is implemented, for example, using ReentrantLock (reentrantlock).
private static Lock lock = new ReentrantLock(); public static void add(){ lock.lock(); i++; lock.unlock(); } CAS implements spin lock
Since atomic operations can be implemented using the lock or synchronized keyword, why use CAS? Because locking or using synchronized keywords brings a large performance loss, while using CAS can achieve optimistic locking. It actually directly utilizes CPU-level instructions, so the performance is very high.
As mentioned above, CAS is the basis for implementing spin locks. CAS uses CPU instructions to ensure the atomicity of the operation to achieve the lock effect. As for spin, it is also very clear to read the literal meaning. If you rotate it yourself, it is a loop. It is generally implemented using an infinite loop. In this way, a CAS operation is executed in an infinite loop. When the operation is successful and returns true, the loop ends; when false, the loop is executed and the CAS operation is continued until true is returned.
In fact, many places in the JDK use CAS, especially in the java.util.concurrent package, such as CountDownLatch, Semaphore, ReentrantLock, and java.util.concurrent.atomic package. I believe everyone has used Atomic*, such as AtomicBoolean, AtomicInteger, etc.
Here we take AtomicBoolean as an example, because it is simple enough.
public class AtomicBoolean implements java.io.Serializable { private static final long serialVersionUID = 4654671469794556979L; // setup to use Unsafe.compareAndSwapInt for updates private static final Unsafe unsafe = Unsafe.getUnsafe(); private static final long valueOffset; static { try { valueOffset = unsafe.objectFieldOffset (AtomicBoolean.class.getDeclaredField("value")); } catch (Exception ex) { throw new Error(ex); } } private volatile int value; public final boolean get() { return value != 0; } public final boolean compareAndSet(boolean expect, boolean update) { int e = expect ? 1 : 0; int u = update ? 1 : 0; return unsafe.compareAndSwapInt(this, valueOffset, e, u); }}This is part of the code of AtomicBoolean, and we see several key methods and properties here.
1. The sun.misc.Unsafe object is used. This class provides a series of methods to directly operate memory objects, but is only used internally by jdk, and is not recommended for developers to use;
2. value represents the actual value. You can see that the get method actually judges the boolean value based on whether the value is equal to 0. The value here is defined as volatile, because volatile can ensure memory visibility, that is, as long as the value value changes, other threads can see the changed value immediately. The next article will talk about the visibility of volatile, welcome to follow
3. valueOffset is the memory offset of the value value, obtained by using the unsafe.objectFieldOffset method and used as the subsequent compareAndSet method;
4. compareAndSet method, this is the core method of implementing CAS. When using the AtomicBoolean method, you only need to pass the expected value and the value to be updated. The unsafe.compareAndSwapInt(this, valueOffset, e, u) method is called. It is a native method, implemented in c++, and the specific code will not be posted. In short, it uses the CPU's cmmpxchg instruction to complete the comparison and replacement. Of course, depending on the specific system version, there are also differences in implementation. Those who are interested can search for the relevant articles by themselves.
Use scenarios
For example, AtomicBoolean can be used in such a scenario. The system needs to determine whether some initialization operations need to be performed based on the state properties of a Boolean variable. If it is a multi-threaded environment and avoid repeated executions, it can be implemented using AtomicBoolean. The pseudocode is as follows:
private final static AtomicBoolean flag = new AtomicBoolean(); if(flag.compareAndSet(false,true)){ init(); }For example, AtomicInteger can be used in counters and in multi-threaded environments to ensure accurate counting.
ABA Questions
There is a problem with CAS, which is that a value changes from A to B and then from B to A. In this case, CAS will think that the value has not changed, but in fact it has changed. In this regard, there is AtomicStampedReference under concurrent packets that provides an implementation based on the version number, which can solve some problems.
Summarize
The above is the entire content of this article. I hope that the content of this article has certain reference value for everyone's study or work. If you have any questions, you can leave a message to communicate. Thank you for your support to Wulin.com.