CAS, Synchronized principle

    • What is CAS
    • CAS application
      • Atomic class
      • spin lock
      • ABA issues with CAS
    • Synchronized principle
      • Lock upgrade optimization
      • Lock elimination optimization
      • Lock coarsening optimization

What is CAS

What is CAS? Compare and swap: Compare and swap

A CAS operation involves:
We assume that the original data V in the memory, the old expected value A, and the new value B that needs to be modified.

  1. Compares A and V for equality. (Compare)
  2. If the comparison is equal, write B to V. (exchange)
  3. Returns whether the operation was successful.

    The above process: if V and A are different; there is no problem; no operation; the special feature of CAS; the above operation is completed through a CPU instruction; the efficiency is very high; this operation is atomic. It can be considered as special instructions provided by the CPU; avoiding thread safety issues.
    It can be understood: comparison is an atomic operation; exchange is also an atomic operation. If the comparisons are equal then the entire comparison and exchange is also an atomic operation.
    When multiple threads perform CAS operations on a resource at the same time, only one thread can operate successfully, but it will not block other threads, and other threads will only receive a signal that the operation failed. It can be considered as an implementation of optimistic locking.

CAS application

Atomic class

CAS implements atomic classes; for example: the atomic class AtomicInteger provided by the Java standard library
AtomicInteger atomicInteger = new AtomicInteger(0);
atomicInteger.getAndIncrement();//Equivalent to + + operation; multi-threaded + + operation is safe

Assume this ++ operation is performed in multiple threads: pseudo code

Implementation process:
1: First read the content into your own stack memory (cpu register)

2: Assume that thread 1 performs the CAS operation first. Since the values of oldValue and value are the same, value is assigned directly. CAS directly reads and writes memory, rather than operating registers; CAS’s memory reading, comparison, and memory writing operations are a hardware instruction and are atomic.

3::The result after writing is as follows

4: Thread 2 performs the CAS operation again, and finds that the writing fails during the first CAS; because oldValue and value are not equal. Therefore, you need to enter a loop; re-read the value of value in the loop and assign it to oldValue. Repeat the above process
The above uses an atomic class. Multi-threaded auto-increment operations can be completed efficiently without using heavyweight locks.

Spin lock

pseudocode:
Check whether the current lock is held by other threads through CAS operations. If the lock is already held, the CAS operation will fail and enter the spin wait state.
If the lock is not held by another thread, the CAS operation succeeds and the current thread is set as the owner of the lock.
This is a typical spin lock implementation that will continue to loop until the lock is successfully acquired.

public class SpinLock {<!-- -->
    private Thread owner = null;

    public void lock() {<!-- -->
        // Check whether the current lock is held by a thread through CAS (Compare and Swap).
        // If this lock is already held by another thread, spin and wait.
        // If this lock is not held by other threads, set the owner to the thread currently trying to lock.
        while (!CAS(this.owner, null, Thread.currentThread())) {<!-- -->
            // Spin and wait until the lock is successfully acquired
        }
    }

    public void unlock() {<!-- -->
        // Release the lock and set owner to null
        this.owner = null;
    }
}

CAS’s ABA problem

The core of CAS during operation checks whether value and oldvalue are consistent. If they are consistent, it is considered that vaue has not been modified in the middle, so there is no problem in performing the next exchange operation.
There are two possibilities for the above consistency: If it is consistent here, it may not have been changed. It may also be that it was modified but restored (ABA problem).

The ABA problem is a special situation; but it is still fatal. Suppose there is a CAS method of deduction; determine whether the money has been deducted; you have 1,000 yuan in your bank card and you want to withdraw 500.
Now the two threads read that your balance is 1,000; then when you withdraw it, someone transfers 500 to you. At this time, the deduction for thread 1 will be completed; then thread 3 will recharge 500; thread 2 will continue to deduct.

How to solve it?
Imagine that the initial version number is 1, and every time the version number is modified, it is + 1. Then when performing CAS, it is not based on the amount, but on the version number. The version number can only be upgraded; it cannot be lowered; as long as the version number does not change, it must not have changed; we have to avoid this problem ourselves. Optimistic locking based on version number is a typical implementation method.

Synchronized principle

Under jdk1.8

  1. It starts with optimistic locking, and if lock conflicts occur frequently, it is converted to pessimistic locking.
  2. It starts with a lightweight lock implementation, and if the lock is held for a long time, it is converted to a heavyweight lock.
  3. The spin lock strategy that is most likely to be used when implementing lightweight locks
  4. It is an unfair lock
  5. is a reentrant lock
  6. Not a read-write lock
    The JVM divides synchronized locks into lock-free, biased lock, lightweight lock, and heavyweight lock states. It will be upgraded sequentially according to the situation. There are many internal optimization mechanisms to make this lock more efficient and easier to use.

Lock upgrade optimization

synchronized (locker) { } process:
1: Lock-free state; in the initial stage, the object is marked as lock-free state. When the first thread enters the synchronized code block, it will try to acquire the lock, and the mark of this object becomes a biased lock. This is done through CAS.
2: Bias lock; when locking, it will first enter the bias lock state; bias lock is not a real lock, but just takes up a position; if necessary, it will be locked again if there are no other threads to compete in the future. lock, then there is no need to perform other synchronization operations (avoiding the overhead of locking and unlocking). Same as making a mark; then clear the mark.
3: Lightweight lock status: When lock competition occurs, the biased lock will be upgraded to a lightweight lock. synchronized is equivalent to locking in a spin manner (same as the above CAS pseudo-code logic), and tries to use CAS to compete for the lock.
4: Heavyweight lock status: If someone else releases the lock soon, spin is cost-effective, but if you can’t get the lock for a long time, it is not cost-effective to keep spinning. Synchronized spin is not endless spin. After the spin reaches a certain level, it will be upgraded to a heavyweight lock again (hanging and waiting for the lock;)
It can be imagined that there is a counter to record how many times the loop loops; how long the loop lasts; and then ends the loop to a certain extent to execute the logic of the heavyweight lock; let it give up the CPU first; once the current thread is switched to the CPU, it is relatively inefficient; because even if the other party releases It’s locked; you have to wait until your dispatch; who can guarantee that it will be in the year of the monkey and the month of the horse.

Note: The lock can only be upgraded in this way; it will not be downgraded; what about reentrancy? synchronized has special handling for reentrancy; it does not lock; it just counts.

Lock elimination optimization

The compiler intelligently determines whether the current code really needs to be locked. If the scenario does not require locking and the programmer has added it, the lock will be automatically removed.
For example: StringBuffer sb = new StringBuffer(); is thread-safe; the bottom layer is guaranteed by synchronized. But with a single thread, you will not use thread safety issues; so we use StringBuffer and StringBudder usually mixed without distinction.
sb.append(“a”);
sb.append(“b”);
sb.append(“c”);
sb.append(“d”);

Lock coarsening optimization

Lock granularity: The more code synchronized contains, the coarser the granularity. The less code it contains, the finer the granularity. Sometimes the finer the lock granularity, the better.
Generally speaking, it is better to have a finer lock granularity; in this way, there will be more concurrent blocks; but in some cases, the gap between two locks and unlocks is very small. In this case, it is better to just lock once; because of repeated locking and unlocking will consume more resources. (The gap is extremely small; even concurrency has little effect; the time reduced by concurrency is not as large as the cost of locking.)