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

This article focuses on "how to understand optimistic locks under Java concurrency". Interested friends may wish to take a look. The method introduced in this paper is simple, fast and practical. Let's let the editor take you to learn how to understand the optimistic lock under Java concurrency.

Before we talk about Letters, let's review a concept: atomic operation:

What is atomic operation?

We know that atoms (atom) refer to basic particles that can no longer be separated by chemical reactions. In Java multithreaded programming, the so-called atomic operation is that even if the command involves multiple operations, these operations are executed in turn and will not be interrupted by other threads.

Atomic operation

After talking about atomic operations, let's get down to business.

As we all know, generally speaking, because multithreading concurrency can lead to security problems, locking mechanisms are used for read and write operations of variables. Locks are generally divided into optimistic locks and pessimistic locks.

Pessimistic lock

For pessimistic locks, developers believe that there is a high probability of concurrency conflicts when data is sent, so they are locked before each read operation.

Optimistic lock

For optimistic locks, developers believe that there is little chance of concurrency conflicts when data is sent, so they are not locked before the read operation.

It is not until the write operation that it is determined whether the data has been modified by other threads during this period. If a modification occurs, a write failure is returned; if it is not modified, the modification operation is performed and the modification is successful.

Optimistic locks are generally implemented by Compare And Swap (CAS) algorithm. As the name implies, the algorithm involves two operations, Compare and Swap.

CAS algorithm flow

The idea of CAS algorithm is as follows:

The algorithm considers that there is less competition between different threads in the operation of variables.

The core of the algorithm is to compare the current read variable value E with the old value V of the variable in memory.

If equal, it means that the variable is not modified by another thread, and the variable value is updated to the new value N.

If it is not equal, it is considered that during the read value E to the comparison phase, other threads have modified the variable without doing anything.

When a thread runs the CAS algorithm, the running process is atomic, that is to say, the Compare And Swap process involves a lot of logic, but the specific operation is done in one fell swoop.

The underlying layer of CAS in Java

To implement the Unsafe class in Java, let me ask you a question:

What is a pointer?

Students who have learned C and C++ languages must be no strangers. To put it bluntly, the pointer is the memory address, and the pointer variable is the variable used to store the memory address.

But for the use of pointers, there are advantages and disadvantages. The advantage is that if we have the offset of memory, in other words, the coordinates of the location where the data is stored in memory, we can operate directly on variables in memory.

The disadvantage is that the pointer is a powerful component in the language. if a novice does not consider the security of the pointer when programming, the wrong operation pointer modifies a block of memory value that should not be modified, which can easily lead to the collapse of the whole program.

Incorrect use of pointer

For the Java language, there is no direct pointer component, and generally it is not possible to use offsets to manipulate a block of memory. These operations are relatively safe.

But in fact, Java has a class called Unsafe class, which makes Java have the ability to manipulate memory space like C language pointers, but also brings pointer problems. This class can be said to be the basis of Java concurrent development.

CAS in the Unsafe class

Generally speaking, the CAS functions you come into contact with are wrappers provided by the Unsafe class. Here are some CAS functions.

Public final native boolean compareAndSwapObject (Object paramObject1, long paramLong, Object paramObject2, Object paramObject3); public final native boolean compareAndSwapInt (Object paramObject, long paramLong, int paramInt1, int paramInt2); public final native boolean compareAndSwapLong (Object paramObject, long paramLong1, long paramLong2, long paramLong3)

These are the three functions provided under the Unsafe package: the CAS update object, the CAS update int variable, and the CAS update long variable.

Let's take the best understood compareAndSwapInt as an example, let's take a look:

Public final native boolean compareAndSwapInt (Object paramObject, long paramLong, int paramInt1, int paramInt2)

As you can see, this function takes four parameters:

The first one is the target.

The second parameter is used to represent the pointer we mentioned earlier, where it is a value of type long that represents the offset of the member variable on its corresponding object property. In other words, the function can use this parameter to find the specific location of the variable in memory and perform the CAS operation.

The third parameter is the expected old value, which is V in the example.

The fourth parameter is the modified new value, which is N in the example.

Some students will ask, is there only integer CAS function in Java? Is there a CAS function for double and boolean?

Unfortunately, the CAS operation and the UnSafe class in Java do not provide methods for manipulating double and boolean data. However, we can use the existing methods to package and self-make the operation methods of double and boolean data.

For the boolean type, we can change the boolean type to the int type when entering the parameter and the int type to the boolean type when the value is returned.

For double types, it depends on the long type, which provides a function for converting double types to long types.

Public static native double longBitsToDouble (long bits); public static native long doubleToRawLongBits (double value)

As we all know, the underlying storage of basic data types is the bit type. Therefore, both long type and double type are bits in the underlying storage mode of the computer. So it's easy to understand these two functions:

The longBitsToDouble function forcibly translates the actual binary stored data at the bottom of the long type with the double type.

The doubleToRawLongBits function forcibly translates the actual binary stored data at the bottom of the double type with the long type.

The use of CAS in Java

A more common operation, using the variable I to count for the program, can be self-incremented to achieve.

Int iTunes 0; iTunes +

But students with a little experience know that this way of writing is not thread-safe.

If 500 threads execute iCompletes at the same time, the result of getting I may not be 500, but may be less than 500.

This is because iTunes + is not just an one-line command, it involves the following operations: (the following code is the compiled bytecode of the Java code)

Getfield # get the value of variable I from memory iadd # add count to 1 putfield # assign the result of adding 1 to variable I

As you can see, a simple self-increment operation involves these three commands, and these commands are not done in one fell swoop, and are easily interrupted by other threads in the case of multithreading.

Self-increasing operation

Although both threads perform the operation inotify +, the value of I should have been 2, but according to the flow in the figure above, the value of I becomes 1.

If you need to do what we want, the code can be rewritten like this.

Int iTunes 0; synchronized {iTunes;}

We know that it is very expensive to modify through the synchronized keyword. Java provides an atomic class. If the variable I is declared as an atomic class and performs the corresponding operation, there will be no problem mentioned before, and it will be less expensive than synchronized.

AtomicInteger I = new AtomicInteger (0); i.getAndIncrement ()

Java's Atomic basic data type class also provides

AtomicInteger atomic operations for int types

AtomicLong atomic operations for long types

AtomicBoolean atomic operations for boolean types

The methods supported by the Atomic basic data type are shown in the following figure:

Atomic basic data type

GetCurrentValue: gets the current value of the underlying data type.

SetValue: sets the value of the current underlying data type to the target value.

GetAndSet: gets the current value of the underlying data type and sets the value of the current underlying data type to the target value.

GetAndIncrement: gets the current value of the underlying data type and increments it by 1, similar to iTunes +.

GetAndDecrement: gets the current value of the underlying data type and subtracts 1 from it, similar to iMel -.

GetAndAdd: gets the current value of the underlying data type and increments the value of the given parameter.

IncrementAndGet: increments 1 and gets the value of this base data type after increment, similar to + + I.

DecrementAndGet: minus 1 and get the increased value of the underlying data type, similar to-I.

AddAndGet: increments the value of a given parameter and gets the value of the underlying data type since it is incremented.

The underlying implementations of these basic data types all have the shadow of CAS.

Let's take the simplest getAndIncrement function of AtomicInteger as an example: (source JDK 7)

Volatile int value; public final int getAndIncrement () {for (;;) {int current = get (); int next= current + 1; if (compareAndSet (current, next)) return current;}}

This is similar to the previous iTunes + self-increment operation, where compareAndSet is actually a native function that encapsulates the Unsafe class:

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

This brings us back to the compareAndSwapInt function under the unsafe package we just talked about.

Spin

In addition to CAS, the Atomic class takes a way to optimize the process of getting the lock.

We know that when a thread cannot get the corresponding lock, there are two strategies:

Strategy 1: abandon the acquisition of CPU, put the thread in a blocking state, and wait for it to be woken up and scheduled by the operating system.

Of course, the disadvantage of doing this is obvious. The switching of this state involves switching from user state to kernel state, which is generally expensive, and it is obviously not cost-effective if the thread releases the occupied lock quickly.

Strategy 2: do not give up CPU, keep retrying, this operation is also known as spin.

Of course, this has its drawbacks. If one thread holds the lock for too long, it will cause other threads waiting to acquire the lock to consume CPU resources meaninglessly. Improper use will result in extremely high CPU utilization. In this case, strategy 1 is more reasonable.

The AtomicInteger,AtomicLong we mentioned earlier adopts strategy 2 when performing the relevant operations. This strategy is also known as spin locking.

You can see that in AtomicInteger's getAndIncrement function, the function outsourced a

For (;;)

In fact, it is an endless cycle of retry, which is what we call spin here.

However, most of the strategies adopted now are for developers to set a threshold and spin constantly within the threshold.

If the number of spin failures exceeds the threshold, enter the blocking state.

Spin

ABA problem and AtomicMarkable

The CAS algorithm itself has a big flaw, that is the ABA problem.

We can see that the CAS algorithm is compared based on the value. If there are currently two threads, one thread changes the variable value from A to B, and then from B to A, when the current thread starts to execute the CAS algorithm, it is easy to think that the value has not changed, mistakenly thinking that no thread has modified the data during the period from reading the data to executing the CAS algorithm.

ABA problem

At first glance, it seems that this defect will not cause any problems, but in fact, it is not. Let me give you an example.

Suppose that the bank card has a balance of 100RMB, and that the bank transfer operation is a simple CAS command, comparing whether the old value of the balance is the same as the current value, and if it is the same, then deduction / increase occurs, we will use CAS (origin,expect) to express this instruction. So let's take a look at what happens next:

Bank transfer

Hongmeng official Strategic Cooperation to build HarmonyOS Technology Community

Xiao Ming owes 100 yuan to Xiao Ai, and Xiao Ai owes 100 yuan to Mavericks

Xiao Ai is going to transfer 100 yuan to the Mavericks on ATM 1; assume that the bottom layer of bank transfer is realized by CAS algorithm. Due to the sudden jam of ATM 1, Xiao Ai ran to the nearby ATM 2 to transfer money again.

ATM 2 executes CAS (100jue 0) and completes the transfer smoothly. At this time, Xiao Ai's account balance is 0.

At this time, Xiao Ming transferred 100 more to Xiao Ai's account, and at this time the balance on Xiao Ai's account was 100.

At this time, the ATM 1 network resumed and continued to execute CAS (10010). Unexpectedly, the execution was successful, and the balance on Xiao Ai's account became 0 again.

Poor Ai, he lost 100 yuan because of the defect of CAS algorithm.

The solution to the ABA problem is not complicated. For this kind of CAS function, you need to compare not only the value of the variable, but also the version number.

Public boolean compareAndSet (V expectedReference, V newReference, int expectedStamp, int newStamp)

The previous CAS has only two parameters, but CAS with a version number comparison has four parameters, where expectedReference refers to the expected old value of the variable, newReference refers to the new value that the variable needs to be changed to, expectedStamp refers to the old value of the version number, and newStamp refers to the new value of the version number.

The execution process of the modified CAS algorithm is shown below:

Modified CAS algorithm

AtomicStampedReference

So how can you smoothly use the CAS function with version number comparison in Java?

Java developers have figured it out for us. They provide a class called Java AtomicStampedReference, which encapsulates the CAS function with version number comparison. Let's take a look.

AtomicStampedReference is defined under the java.util.concurrent.atomic package.

The following figure describes several common methods for this class:

AtomicStampedReference

AttemptStamp: if the expectReference is consistent with the current value, set the version number of the current object to newStamp

CompareAndSet: this method is the CAS method with a version number described earlier.

Get: this method returns the current object value and the version stamp of the current object

GetReference: this method returns the current object value

GetStamp: this method returns the version stamp of the current object

Set: directly sets the current object value and the version stamp of the object

At this point, I believe you have a deeper understanding of "how to understand optimistic locks under Java concurrency". You might as well do it in practice. Here is the website, more related content can enter the relevant channels to inquire, follow us, continue to learn!

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.