web123456

Optimistic locks and pessimistic locks that must be found in interviews

This article has been included in the Java project of Github 130k+ Star:/Snailclimb/JavaGuide. Learn Java/prepare for Java interviews, JavaGuide is preferred. If you think it's good, click a star!

If you correspond to pessimistic locks (PessimisticLock) and optimistic locks (PessimisticLock or OptimisticLock) in real life. Pessimistic Lock is a bit like a more pessimistic (or maybe a rainy day) person who always assumes the worst case and avoids problems. Optimistic Lock is a bit like a more optimistic person who always assumes the best situation and quickly solves the problem before it comes.

In the program world, the ultimate purpose of optimistic locks and pessimistic locks is to ensure thread safety and avoid resource competition in concurrent scenarios. However, compared to optimistic locks, pessimistic locks have a greater impact on performance!

What is pessimistic lock?

Pessimistic locks always assume the worst case, believing that a shared resource will have problems every time it is accessed (such as the shared data is modified), so it will be locked every time it acquires the resource operation, so that other threads will block until the lock is released by the previous holder if they want to get the resource. That is to say,Shared resources are only used by one thread at a time, and other threads are blocked. After use, the resources are transferred to other threads.。

Like in JavasynchronizedandReentrantLockThe exclusive lock is the realization of the pessimistic lock idea.

public void performSynchronisedTask() {
    synchronized (this) {
        // Requires synchronization operations
    }
}

private Lock lock = new ReentrantLock();
lock.lock();
try {
   // Requires synchronization operations
} finally {
    lock.unlock();
}

In high concurrency scenarios, fierce lock competition will cause thread blockage, and a large number of blocking threads will lead to system context switching, increasing system performance overhead. In addition, pessimistic locks may also have deadlock problems, affecting the normal operation of the code.

What is optimistic lock?

Optimistic locks always assume the best situation, believing that there will be no problem every time a shared resource is accessed, and the thread can be executed continuously without locking or waiting. It just verifies whether the corresponding resource (that is, data) has been modified by other threads when submitting the modification (specific methods can be used by the version number mechanism or the CAS algorithm).

Like in JavaThe atomic variable class below the package (for exampleAtomicInteger、LongAdder) is an implementation method that uses optimistic locksCASAchieved.

[External link image transfer failed, the source site may have an anti-theft link mechanism. It is recommended to save the image and upload it directly (img-TLbHeM08-1680962691948)(/2019-6/JUC atomic class overview.png)]

// LongAdder will perform better than AtomicInteger and AtomicLong in high concurrency scenarios
// The price is to consume more memory space (space for time)
LongAdder longAdder = new LongAdder();
// Self-increase
longAdder.increment();
// Get results
longAdder.sum();

In high concurrency scenarios, optimistic locks are not blocked due to pessimistic locks, and there is no problem of thread blocking due to lock competition, and there is no problem of deadlocks. They are often better in performance. However, if conflicts occur frequently (there are a lot of writes), they will fail frequently and retry (the overhead of pessimistic locks is fixed), which will also greatly affect performance and cause the CPU to soar.

However, a large number of failed retry problems can also be solved, like what we mentioned earlierLongAdderThis problem is solved by exchanging space for time.

In theory:

  • Pessimistic locks are usually used in situations where there are more writing (more writing scenarios, fierce competition), which can avoid frequent failures and retry affecting performance. The overhead of pessimistic locks is fixed. However, if the optimistic lock solves the problem of frequent failure and retry (e.g.LongAdder), you can also consider using optimistic locks, depending on the actual situation.
  • Optimistic locks are usually more than those with less writing (read more scenes, less competition), which can avoid frequent locking and affecting performance. However, optimism locks mainly target individual shared variables (referencepackage the atomic variable class below).

How to achieve optimistic locks?

Optimistic locks are generally implemented using the version number mechanism or CAS algorithm. The CAS algorithm is relatively more, so special attention needs to be paid to this.

Version number mechanism

Generally, add a data version number to the data tableversionField, indicating the number of times the data has been modified. When the data is modified,versionThe value will be added by one. When thread A wants to update the data value, it will also be read while reading the dataversionValue, when submitting an update, if the version value just read is in the current databaseversionUpdate only when the values ​​are equal, otherwise try the update operation again until the update is successful.

Give a simple example: Suppose there is a version field in the account information table in the database, the current value is 1; and the current account balance field (balance) is $100.

  1. Operator A reads it out at this time (version=1 ) and deduct $50 ($100-$50) from its account balance.
  2. During operation by Operator A, Operator B also reads this user information (version=1 ) and deduct $20 ($100-$20) from its account balance.
  3. Operator A completed the modification work and adjusted the data version number (version=1 ), together with the balance after deduction of the account (balance=$50 ), submitted to the database update. At this time, since the submitted data version is equal to the current version of the database record, the data is updated and the database record isversionUpdated to 2 .
  4. Operator B has completed the operation and also set the version number (version=1 ) Attempt to submit data to the database (balance=$80 ), but when comparing the database record version, it was found that the data version number submitted by operator B was 1, and the current version of the database record was 2, which did not meet the optimistic locking strategy of "the submission version must be equal to the current version to perform the update". Therefore, operator B's submission was rejected.

This avoids operators using BversionThe result of the old data modification of =1 covers the possibility of operator A's operational results.

CAS Algorithm

The full name of CAS isCompare And Swap (Compare & Exchange), used to achieve optimistic locking, has been widely used in major frameworks. The idea of ​​CAS is very simple, it is to compare an expected value with the value of the variable to be updated, and only when the two values ​​are equal will it be updated.

CAS is an atomic operation, and the underlying layer depends on a CPU's atomic instruction.

Atomic operationThat is, the minimum non-detachable operation, that is, once the operation starts, it cannot be interrupted until the operation is completed.

CAS involves three operands:

  • V: The value of the variable to be updated (Var)
  • E: Expected value
  • N: New value to be written (New)

If and only if the value of V is equal to E, CAS updates the value of V atomically with the new value N. If there is no waiting, it means that other threads have updated V, and the current thread will give up the update.

Give a simple example: Thread A To modify the value of the variable i to be 6, the original value of i is 1 (V = 1, E=1, N=6, assuming there is no ABA problem).

  1. i is compared with 1. If it is equal, it means that it has not been modified by other threads and can be set to 6.
  2. i and 1 are compared. If it is not equal, it means it is modified by other threads, the current thread abandons the update, and the CAS operation fails.

When multiple threads operate a variable using CAS at the same time, only one will win and update successfully, and the rest will fail, but the failed thread will not be suspended. It is only told that the failure is and allows another attempt. Of course, the failed thread will also be allowed to give up the operation.

The Java language does not directly implement CAS, and CAS-related implementations are implemented through C++ inline assembly (JNI calls). Therefore, the specific implementation of CAS is related to the operating system and CPU.

PackedUnsafeClass providedcompareAndSwapObject、compareAndSwapInt、compareAndSwapLongMethods to achieve the rightObject、int、longType of CAS operation

/**
	 * CAS
   * @param o Contains the object to modify the field
   * @param offset The offset of a field in the object
   * @param expected expected value
   * @param update Update value
   * @return true | false
   */
public final native boolean compareAndSwapObject(Object o, long offset,  Object expected, Object update);

public final native boolean compareAndSwapInt(Object o, long offset, int expected,int update);

public final native boolean compareAndSwapLong(Object o, long offset, long expected, long update);

aboutUnsafeFor a detailed introduction to the class, you can read this article:Java Magic Unsafe Detailed explanation - JavaGuide - 2022 。

What are the problems with optimistic locking?

ABA problem is the most common problem with optimistic locks.

ABA Questions

If a variable V is the value A when it is first read, and when it is ready to be assigned, it is still the value A, can we say that its value has not been modified by other threads? It is obviously not possible, because during this time its value may be changed to another value and then changed back to A, and the CAS operation will mistakenly believe that it has never been modified. This problem is called CAS operation"ABA" problem.

The solution to the ABA problem is to follow the variables beforeVersion number or timestamp. JDK 1.5 afterAtomicStampedReferenceClasses are used to solve ABA problems, among whichcompareAndSet()The method is to first check whether the current reference is equal to the expected reference and whether the current flag is equal to the expected flag. If all are equal, the reference and the value of the flag are set to the given updated value in atomic manner.

public boolean compareAndSet(V   expectedReference,
                             V   newReference,
                             int expectedStamp,
                             int newStamp) {
    Pair<V> current = pair;
    return
        expectedReference == current.reference &&
        expectedStamp == current.stamp &&
        ((newReference == current.reference &&
          newStamp == current.stamp) ||
         casPair(current, Pair.of(newReference, newStamp)));
}

Long cycle time and high overhead

CAS often uses spin operations to retry, that is, if it fails, it will be executed cycled until it succeeds. If it fails for a long time, it will bring great execution overhead to the CPU.

If the JVM can support the pause instructions provided by the processor, the efficiency will be improved to a certain extent. The pause instructions have two functions:

  1. Pipeline execution instructions can be delayed so that the CPU does not consume too much execution resources. The delay time depends on the specific implementation version, and the delay time is zero on some processors.
  2. It can avoid the CPU pipeline being cleared due to memory sequential fluctuation when exiting the loop, thereby improving the execution efficiency of the CPU.

Only atomic operations of a shared variable can be guaranteed

CAS is only valid for a single shared variable, and CAS is invalid when an operation involves spanning multiple shared variables. But starting from JDK 1.5, it providesAtomicReferenceClasses to ensure the atomicity between referenced objects. You can put multiple variables in one object to perform CAS operations. So we can use locks or useAtomicReferenceThe class combines multiple shared variables into one shared variable to operate.

Summarize

  • In high concurrency scenarios, fierce lock competition will cause thread blockage, and a large number of blocking threads will lead to system context switching, increasing system performance overhead. In addition, pessimistic locks may also have deadlock problems, affecting the normal operation of the code. Compared with pessimistic locks, there is no lock competition that causes thread blockage, and there will be no problem of deadlocking, and it is often better in performance. However, if conflicts occur frequently (there are a lot of writes), they will fail frequently and retry, which will also greatly affect performance and cause the CPU to soar.
  • Optimistic locks are generally implemented using the version number mechanism or CAS algorithm. The CAS algorithm is relatively more, so special attention needs to be paid to this.
  • The full name of CAS isCompare And Swap (Compare & Exchange), used to achieve optimistic locking, has been widely used in major frameworks. The idea of ​​CAS is very simple, it is to compare an expected value with the value of the variable to be updated, and only when the two values ​​are equal will it be updated.
  • Problems of optimistic locking: ABA problem, long cycle time and high overhead, and can only ensure atomic operations of a shared variable.

refer to

  • "Java Concurrent Programming Core 78 Lectures"
  • Easy to understand: pessimistic lock, optimistic lock, reentry lock, spin lock, biased lock, lightweight/heavyweight lock, read and write lock, various locks and their Java implementation! :/p/71156910
  • Completely understand the principles of CAS implementation in one article & go deep into CPU instructions: /p/94976168