preface

The basic CAS principles must be understood in order to score points in an interview. Here are some of the questions that may be asked:

  • What are optimistic locks and pessimistic locks
  • What is the implementation method of optimistic lock -CAS (Compare and Swap), the implementation principle of CAS (Compare and Swap)
  • Use in JDK and package distribution
  • The defect of the CAS

1. What are optimistic locks and pessimistic locks?

Pessimistic locking

Always assume the worst-case scenario, that every time data is read, the default is that some other thread will change the data, so it needs to be locked, and when some other thread wants to access the data, it needs to block and suspend. Pessimistic lock implementation:

  • Traditional relational databases use this locking mechanism, such as row lock, table lock, read lock, write lock, etc., are locked before the operation;
  • Synchronization in JavasynchronizedKeyword implementation.

Optimistic locking

Optimistic locking, actually is a kind of thought, always think won’t produce concurrency issues, every time reading data that other threads will not modify the data, so it does not lock, but at the time of update will determine whether the other threads have modified data during this period, optimistic locking is suitable for the read operation more scenarios, which can improve the throughput of the program. Implementation method:

  • CAS implementation: in Java Java. Util. Concurrent. The atomic package this atomic variable USES the optimistic locking a CAS implementation way, CAS analysis the next day.
  • Version control: Generally, a version field is added to the data table to indicate the number of times the data has been modified. When the data has been modified, the version value will be increased by one. When thread A wants to update the data value, it also reads the version value. When submitting the update, it updates the version value only when the version value it just read is the same as the version value in the current database. Otherwise, the update operation is retried until the update succeeds

Optimistic locking is applicable to the scenario where read is excessive and write is insufficient (overread scenario), while pessimistic locking is applicable to the scenario where write is excessive and read is insufficient

2. Implementation method of optimistic lock -CAS (Compare and Swap) and implementation principle of CAS (Compare and Swap)

background

Before JDK1.5, synchronized ensured that no matter which thread held the lock on a shared variable, it would use exclusive access to these variables, resulting in these problems:

  • In the multi-thread competition, locking and releasing locks will lead to more context switching and scheduling delay, resulting in performance problems
  • If one thread holds the lock, all the other threads are suspended, waiting for the thread holding the lock to release it.
  • If a thread with a higher priority waits for a thread with a lower priority to release the lock, priority inversion can occur, causing performance risks

To optimize these problems, optimistic locks are created:

Assume that there is no concurrent conflict and the same variable is performed each time. If the operation fails due to concurrent conflict, retry until the operation succeeds.

Compare and Swap (CAS) principle

CAS stands for Compare and swap. CAS is a mechanism for synchronization in multi-threaded environments. It is also lock-free optimization, or spin, and adaptive spin.

In the JDK, CAS adds the volatile keyword as a cornerstone for implementing and sending packages. Without CAS, there will be no concurrent packets. Java.util.concurrent uses CAS instruction to realize an optimistic lock different from synchronized.

A typical implementation mechanism for optimistic locking (CAS) :

Optimistic locking consists of two main steps:

  • Collision detection
  • Data update

When multiple threads try to update the same variable using CAS at the same time, only one thread can update the value of the variable, and all the other threads will fail. The failed thread will not be suspended, but will be informed that it has lost the race and can try again.

To ensure thread safety without locking, there are three important operands in the CAS implementation mechanism:

  • Memory location to read and write (V)
  • Expected original value (A)
  • The new value (B)

First, read the memory location (V) that needs to be read and written. Then compare the memory location (V) with the expected original value (A). If the memory location matches the expected original value (A), then update the value of the memory location to the new value B. If the memory location does not match the value of the expected original value, the processor does nothing. In either case, it returns the value of that location before the CAS instruction. It can be divided into three steps:

  • Read (memory location needed to read and write (V))
  • Compare (the memory location required to read and write (V) with the expected value (A))
  • Write back (new value (B))

3. Use of CAS in JDK and package delivery

Java.util.concurrent (JUC Java Concurrency Toolkit) is implemented based on CAS algorithm in JDK1.5. CAS is a common implementation of non-blocking algorithm compared to synchronized exclusive lock and blocking algorithm. Using optimistic lock JUC provides a significant performance improvement.

How the CAS in the circumstance that does not use locking to ensure the safety of the thread, and atomic operations class AtomicInteger in contract: : getAndIncrement () method (i++ operation) :

/ / AtomicInteger
// The offset of value
private static final long valueOffset; 
/ / get the value
private volatile int value;
// Set the offset of value
static {
        try {
            valueOffset = unsafe.objectFieldOffset
                (AtomicInteger.class.getDeclaredField("value"));
        } catch (Exception ex) { throw newError(ex); }}//增加1
public final int getAndIncrement(a) {
        return unsafe.getAndAddInt(this, valueOffset, 1);
    }

Copy the code

  • First, value must be volatile, which ensures that it is visible and ordered

  • The offset of value needs to be initialized

  • Unsafe. getAndAddInt performs the CAS operation on the offset. After reading data from memory, the CAS operation is performed on the original data and the CAS operation is performed on the original data.

    / / the unsafe
public final int getAndAddInt(Object var1, long var2, int var4) {
    int var5;
    do {
        // Use the offset to get the value in memory
        var5 = this.getIntVolatile(var1, var2);
       // compare and value +1
    } while(!this.compareAndSwapInt(var1, var2, var5, var5 + var4));
    return var5;
}
Copy the code

JAVA implementation the principle of CAS, the unsafe: : compareAndSwapInt is using C to invoke the underlying CPU instructions. Below is the sun. The misc. Unsafe: : compareAndSwapInt () method of the source code:

public final native boolean compareAndSwapInt(Object o, long offset,
                                               int expected, int x);
Copy the code

4. Defects of CAS

ABA problem

In multi-threaded scenarios, ABA problems may occur in CAS. For example, two threads perform CAS operations on the same value (the initial value is A) at the same time. These three threads are as follows

Thread 1, expected value A, wants to update value B thread 2, expected value A, wants to update value B

Thread 3, expected value B, updated value A

  • Thread 1 gets the CPU slice first, thread 2 blocks for some other reason, thread 1 compares its value to the expected value of A, finds it equal and updates its value to B,
  • The value of thread 3 is compared with the expected value B, and the value is updated to A if it is found to be equal
  • At this point, thread 2 recovers from the block and gets the CPU time slice. At this point, thread 2 compares its value with the expected value A and finds it equal to the expected value A, and then updates its value to B. Although thread 2 also completes the operation, thread 2 does not know that its value has gone through the process of A->B->A.

1) Thread 1 (ATM) : get the current value of 100, expect to update to 50, thread 2 (ATM) : Get current value 100, expect update to 50, thread 1 executes successfully, thread 2 blocks for some reason, then someone sends Xiaoming 50 thread 3 (default) : Thread 3 returns from the Block with a balance of 100. Thread 2 returns from the Block with a balance of 100. Thread 2 returns from the Block with a balance of 100. At this point, you can see that the actual balance should be 100 (100-50+50), but it is actually 50 (100-50+50-50), which is the ABA problem resulting in a successful submission.

The solution

  • AtomicStampedReference an object reference with a timestamp to resolve an ABA problem. The compareAndSet method of this class first checks whether the current reference is equal to the expected reference, and whether the current flag is equal to the expected flag, and if all are equal, sets the reference and flag values to the given updated value atomically.
public boolean compareAndSet(V expectedReference,// expectedReference V newReference,// updated referenceintExpectedStamp, // Expect stampintNewStamp // Updated logo)
Copy the code
  • Add the version number to the front of the variable. Each time the variable is updated, the version number of the variable is +1. That is, A->B->A becomes 1A->2B->3A

Long cycle time and high overhead

Spin CAS (unsuccessful, loop until successful), if unsuccessful for a long period of time, can impose significant execution overhead on the CPU.

Solutions:

  • Limit the number of spins to prevent an infinite loop

  • If the JVM can support pause instructions provided by the processor, there will be some improvement in efficiency.

Atomic operations of only one shared variable are guaranteed

When operating on a shared variable, we can use a cyclic CAS to guarantee atomic operation, but when operating on multiple shared variables, the cyclic CAS cannot guarantee atomic operation

Solutions:

  • If you need to operate on multiple shared variables, you can use locking (pessimistic locking) to ensure atomicity.

  • Multiple shared variables can be combined into a single shared variable for CAS operation.

Is everyone still ok? If you like, move your hands to show 💗, point a concern!! Thanks for your support! Welcome to scan code attention, original technical articles launched at the first time

Is everyone still ok? If you like, move your hands to show 💗, point a concern!! Thanks for your support!

Welcome to scan code attention, original technical articles launched at the first time