Implementation principle and application of atomic package in Java

1. Proposal of synchronization problem

Suppose we use a dual core processor to execute threads a and B, core 1 executes thread a, and core 2 executes thread B. these two threads now have to add 1 to the member variable I of the object named obj. Assuming that the initial value of I is 0, theoretically, the value of I should become 2 after the two threads run, but in fact, it is likely that the result is 1.

Now let's analyze the reason. For simplicity of analysis, we don't consider the cache. In fact, having a cache will increase the possibility that the result is 1. Thread a reads the variable I in memory into the core 1 arithmetic unit, then adds 1, and then writes the calculation result back to memory, because the above operation is not an atomic operation, as long as thread B writes the value of I increased by 1 back to memory before thread a writes it back to memory, If the value of I in the memory is read (at this time, the value of I is 0), the result of I will be 1. Because the value of I read by threads a and B is 0, and the value added by the two threads is 1, the two threads write 1 to the variable I successively, that is, the value of I written twice is 1.

The most common solution is to lock the obj object with the synchronize keyword for the code that adds 1 to I in two threads. Today, we introduce a new solution, which uses the related classes in the atomic package.

2. Atomic hardware support

In uniprocessor system, any operation that can be completed in a single instruction can be regarded as "atomic operation", Because interrupts can only occur between instructions (because thread scheduling needs to be completed through interrupts). This is also the reason why some CPU instruction systems have introduced test_and_set, test_and_clear and other instructions for critical resource mutual exclusion. It is different in the symmetric multi processor structure, because there are multiple processors running independently in the system, Even operations that can be completed in a single instruction may be disturbed.

On the X86 platform, the CPU provides a means to lock the bus during instruction execution. There is a lead #hlockpin on the CPU chip. If an instruction is prefixed with "lock" in the assembly language program, the assembled machine code will cause the CPU to lower the potential of #hlockpin when executing the instruction and release it until the end of the instruction, so as to lock the bus, so that other CPUs on the same bus can not access memory through the bus temporarily, This ensures the atomicity of this instruction in a multiprocessor environment. Of course, not all instructions can be prefixed with lock. Only add, ADC, and, BTC, BTR, BTS, cmpxchg, Dec, Inc, neg, not, or, SBB, sub, XOR, xadd, and xchg instructions can be prefixed with "lock" instructions to realize atomic operation.

The core operation of atomic is CAS (compareandset, implemented by cmpxchg instruction, which is an atomic instruction). The instruction has three operands, the memory value V of the variable (abbreviation of value), the current expected value E of the variable (abbreviation of exception), and the value u of the variable to be updated (short for update). When the memory value is the same as the current expected value, the updated value of the variable will overwrite the memory value. The execution pseudo code is as follows.

Now let's use CAS operation to solve the above problem. Thread B reads the variable I in memory into a temporary variable (assuming that the value read at this time is 0), then reads the value of I into the arithmetic operation unit of core1, and then performs the operation of adding 1 to compare whether the value in the temporary variable is the same as the current value of I. if it is the same, the value of I in memory is overwritten with the value of the result (I + 1) in the operation unit (note that this part is CAS operation, which is an atomic operation and cannot be interrupted, and CAS operations in other threads cannot be executed at the same time). Otherwise, the instruction execution fails. If the instruction fails, thread a has increased the value of I by 1. Therefore, it can be seen that if the value of I read by both threads at the beginning is 0, only one thread's CAS operation can succeed, because ca S operations cannot be performed concurrently. For the thread that fails to execute CAS operation, as long as the CAS operation is executed circularly, it will succeed. You can see that there is no thread blocking, which is essentially different from the principle of synchronize.

3. Atomic package introduction and source code analysis

The basic feature of classes in atomic package is that in a multithreaded environment, When multiple threads operate on a single variable (including basic type and reference type) at the same time, it is exclusive, that is, when multiple threads update the value of the variable at the same time, only one thread can succeed, while the unsuccessful thread can continue to try like a spin lock until the execution is successful.

The core methods in the atomic family of classes call several local methods in the unsafe class. One thing we need to know first is the unsafe class, whose full name is sun misc. Unsafe, this class contains a large number of operations on C code, including many direct memory allocation and atomic operation calls. The reason why it is marked as unsafe is to tell you that a large number of method calls in this class will have security risks and need to be used carefully. Otherwise, it will lead to serious consequences. For example, when allocating memory through unsafe, If you specify some regions by yourself, it may lead to the problem that some pointers like C + + cross the boundary to other processes.

Classes in the atomic package can be divided into four groups according to the data types of operations

AtomicBoolean，AtomicInteger，AtomicLong

Thread safe basic types of atomic operations

AtomicIntegerArray，AtomicLongArray，AtomicReferenceArray

Thread safe atomic operation of array type, which operates not the whole array, but a single element in the array

AtomicLongFieldUpdater，AtomicIntegerFieldUpdater，AtomicReferenceFieldUpdater

Thread safe operations are performed based on the basic types (long, integer and reference types) in the reflection principle object

AtomicReference，AtomicMarkableReference，AtomicStampedReference

Thread safe reference type and atomic operation of reference type to prevent ABA problem

We commonly use atomicinteger, atomicreference, and atomicstampedreference. Now let's analyze the source code of atomicinteger in the atomic package. The source codes of other classes are similar in principle.

1. Parameterized constructor

As can be seen from the constructor function, the value is stored in the member variable value

The member variable value is declared as volatile, which indicates the visibility under multithreading, that is, the modification of any thread will be immediately seen in other threads

2. Compareandset method (the value of value is passed through the internal this and valueoffset)

This method is the core CAS operation

The 3.getAndSet method calls the compareAndSet method in this method.

If other threads change the value of value before executing if (compareandset (current, newvalue), the value of value must be different from the value of current. Compareandset execution fails. You can only retrieve the value of value, and then continue to compare until it succeeds.

4. I + + implementation

5. Implementation of + + I

4. Use atomicinteger example

The following program uses atomicinteger to simulate the ticket selling program. In the running results, there will be no two programs that sell the same ticket, and the ticket will not be negative

5. ABA issues

The operation results of the above example are completely correct, This is based on two (or more) threads operating on data in the same direction. In the above example, both threads are decrementing tickets. For another example, if multiple threads perform object listing operations on a shared queue, correct results can also be obtained through atomicreference class (this is the case for the queues maintained in AQS), but multiple threads can be listed or listed, that is, the data operation direction is inconsistent, so ABA may occur.

Now let's take a well understood example to explain the ABA problem. Suppose there are two threads T1 and T2, which perform out of stack and in stack operations on the same stack.

We use the tail defined by atomicreference to save the stack top position

Suppose that T1 thread is ready for stack out. For stack out operation, we only need to update the stack top position from SP to newsp through CAS operation, as shown in Figure 1. However, the T1 thread executes tail Before compareandset (SP, newsp), the system performs thread scheduling, and T2 thread starts execution. T2 performs three operations: a out of the stack, B out of the stack, and then a into the stack. At this time, the system starts scheduling again, and T1 thread continues to perform the stack out operation. However, in the view of T1 thread, the top element of the stack is still a (that is, T1 still thinks that B is still the next element of top a), but the actual situation is as shown in Figure 2. T1 will think that the stack has not changed, so the tail.compareandset (SP, newsp) is executed successfully, and the top pointer is pointed to node B. In fact, B does not exist in the stack. The result after T1 pushes a out of the stack is shown in Figure 3, which is obviously not the correct result.

6. Solutions to ABA problems

Use atomicmarkablereference, atomicstampedreference. Use the above two atomic classes to operate. When implementing the compareandset instruction, they should not only compare the previous value and expected value of the current object, but also compare the current (operated) stamp value and expected (operated) stamp value. When they are all the same, the compareandset method can succeed. Each time the update is successful, the stamp value will change, and the setting of the stamp value is controlled by the programmer.

At this time, the compareandset method requires four parameters expectedreference, newreference, expectedstamp and newstamp. When using this method, we should ensure that the expected stamp value is not the same as the stamp value to be updated. Generally, newstamp = expectedstamp + 1

Take the above example

Suppose thread T1 is before the stack: SP points to a and the stamp value is 100.

Thread T2 executes: after a is out of the stack, SP points to B, and the stamp value becomes 101,

After B is out of the stack, SP points to C, and the stamp value becomes 102,

After a enters the stack, SP points to a, and the stamp value becomes 103,

Thread T1 continues to execute the compareandset statement and finds that although SP still points to a, the expected value 100 of the stamp value is different from the current value 103. Therefore, compareandset fails. You need to obtain the value of newsp (at this time, newsp will point to c) and the expected value 103 of the stamp, and then perform the compareandset operation again. In this way, a successfully exits the stack and SP will point to C.

Note that compareandset can only change one value at a time and cannot change newreference and newstamp at the same time. Therefore, during implementation, a pair class is defined internally. The pair class turns newreference and newstamp into an object. When performing CAS operations, it is actually an operation on the pair object

For atomicmarkablereference, the stamp value is a boolean variable, while the stamp value in atomicmampedreference is an integer variable.

summary

The above is all about the implementation principle and application of atomic package in Java. I hope it will be helpful to you. Interested friends can continue to refer to other related topics on this site. If there are deficiencies, please leave a message to point out.