当前位置：网站首页>[multithreading] lock strategy

Always assume the worst , Every time I go to get the data, I think others will modify it , So every time I get the data, I lock it , So people who want to take this data will block it until it gets the lock

for example , Even if the next epidemic comes , And don't worry about it , Life can work normally , A lot of food and supplies can be bought , No special preparation is required .（ Optimism lock ）

2） Pessimistic locking , That is, the probability of expected lock conflicts is very high

It is assumed that data generally does not produce concurrency conflicts , So when the data is submitted for update , Will formally determine whether the data is generated and Send conflict detection , If concurrency conflicts are found , Returns the user's error message , Let the user decide how to do it .

for example , If the next epidemic comes , You may not be able to buy food , Just stock up a lot . （ Pessimistic locking ）

3）Synchronized Initial use of optimistic locking strategy . When lock competition is found to be frequent , It will automatically switch to pessimistic lock strategy .

Just like classmates C Begin to think " The teacher is relatively idle ", Ask questions directly to the teacher （ Optimism lock ）

But after coming directly to the teacher twice , I found that the teachers were very busy , So next time I'll ask questions , Just send a message to ask the teacher if he is busy

busy , Then decide whether to ask questions （ Pessimistic locking ）.

2. Read / write locks and ordinary mutex locks

1） For ordinary mutexes , There are only two operations ： Lock and unlock

Two threads lock the same object , There will be mutual exclusion

2） For a read-write lock , There are three operations

Add read lock ： If the code just reads , Just add a read lock
Add write lock ： If a modification is made in the code , Just add a write lock
Unlock

Between threads , There is no thread safety problem between data readers , But the writers of the data need to communicate with each other and with the readers To be mutually exclusive . If the same lock is used in both scenarios , There will be great performance loss . Therefore, read-write locks are generated .

Read write lock is to distinguish between read operation and write operation ..Java The standard library provides ReentrantReadWriteLock class , Realize the read-write lock .

ReentrantReadWriteLock.ReadLock Class represents a read lock . This object provides lock / unlock Method to lock and unlock .
ReentrantReadWriteLock.WriteLock Class represents a write lock . This object also provides lock / unlock The method is to enter into Row lock unlock

among

Between read lock and read lock , There is no mutual exclusion （ Multiple threads read a variable at the same time , There will be no thread safety issues ）
Between read lock and write lock , Between write lock and write lock , To be mutually exclusive

Be careful ：

As long as it involves " Mutually exclusive ", It will cause the thread to hang and wait . Once the thread hangs , When you wake up again, you don't know how far apart

For a long time . So reduce as much as possible " Mutually exclusive " The opportunity of , Is an important way to improve efficiency .

The read-write lock is especially suitable for " Frequent reading , Write less frequently " In the scene .

Synchronized Not a read-write lock

3. Heavyweight locks and lightweight locks

1） The core feature of locks " Atomicity ", The origin of such a mechanism is CPU Such hardware devices provide .

CPU Provides " Atomic operation instructions ".
The operating system is based on CPU Atomic instructions for , Realized mutex The mutex .
JVM Based on the mutex provided by the operating system , Realized synchronized and ReentrantLock Keywords and classes .

Be careful , synchronized Not just for mutex encapsulate , stay synchronized A lot of other work has been done internally

synchronized It starts with a lightweight lock . If the lock conflict is serious , Will become a heavyweight lock

2） Heavyweight lock

The locking mechanism is heavily dependent on OS Provides mutex

A large number of kernel mode user mode switching
It's easy to trigger thread scheduling

3） Lightweight lock

The locking mechanism should not be used as much as possible mutex, Instead, try to complete it in user status code . I'm really not sure , Reuse mutex.

A small number of kernel mode user mode switching .
It is not easy to cause thread scheduling .

4） Understand user behavior vs Kernel mode

Imagine going to the bank to do business

Outside the window , Do it yourself , This is user mode . The time cost of user mode is relatively controllable .

In the window , The staff do , This is the kernel state . The time cost of kernel state is not controllable .

If you repeatedly communicate with the staff when doing business , You need to queue up again , At this time, the efficiency is very low .

4. Hang wait lock and spin lock

The pending lock is Heavyweight lock How to implement

Spin lock is a typical Lightweight lock How to implement .

advantage : Didn't give up CPU, Thread blocking and scheduling are not involved , Once the lock is released , You can get the lock at the first time .
shortcoming : If the lock is held by other threads for a long time , Then it will continue to consume CPU resources . ( And the time to hang up waiting is
Don't consume CPU Of

Understand the pending lock and spin lock ：

Go to a rich friend's house to borrow rice , People don't want to open the door

Hang wait lock ： Always thinking about others' rice , Just wait at the door , Waited for ten days and a half months , People finally opened the door （ In the process of waiting , Maybe the rice has been used up ）

spinlocks ： A shameless knock on the door every twoorthree minutes , Once someone gets impatient, open the door , Then rush in , People couldn't stand it, so they lent him rice .

4. Fair lock and unfair lock

Suppose three threads A, B, C. A Try to get the lock first , To be successful . then B Try to get the lock again , Acquisition failure , Block waiting ; then

C Also try to get the lock , C Also get failure , Also blocked waiting

Fair lock : comply with " first come , first served ". B Than C First come . When A After releasing the lock , B Before C Get lock .

Not fair lock : Non compliance " first come , first served ". Everyone has equal opportunities ,B and C It's possible to get the lock .

Be careful ：

Thread scheduling within the operating system can be regarded as random . If you don't make any additional restrictions , A lock is an unfair lock .

If you want to Want to achieve a fair lock , You need to rely on Additional data structures , To record the order of threads .

There is no difference between fair lock and unfair lock , The key is to look at the applicable scenarios .

synchronized Fair lock .

For the operating system , The scheduling between threads is random ( Equal opportunity ) . Operating system provided mutex This lock , It belongs to unfair lock .

5. Reentrant lock and Do not reenter the lock

One thread , Lock the same lock for two consecutive times , If it will deadlock, it is a non reentrant lock , If it doesn't deadlock , It's a re-entry lock .synchronized It's a reentrant lock

6. synchronized Lock summary

1） Both an optimistic lock , It is also a pessimistic lock . ( Adaptive according to the intensity of lock competition )
2） It's not a read-write lock, it's just an ordinary mutex .
3） It's both a lightweight lock , It's also a heavyweight lock ( According to the intensity of lock competition , The adaptive )
4） The part of lightweight lock is based on spin lock . The heavyweight part is based on the pending lock
5） Not fair lock
6） Reentrant lock .

7. CAS

CAS: Full name Compare and swap, Literally :” Compare and exchange “, One CAS The following operations are involved ：

Let's assume that the raw data in memory V, Old expectations A, New values that need to be modified B.
1. Compare A And V Whether it is equal or not .（ Compare ）
2. If it's equal , take B write in V.（ In exchange for ）
3. Whether the return operation is successful .

7.1 CAS Pseudo code

The code written below is not atomic , Actual CAS It is completed by an atomic hardware instruction . This pseudo code is just an aid to understanding

CAS workflow

boolean CAS(address, expectValue, swapValue) {
 if (&address == expectedValue) {
   &address = swapValue;
        return true;
   }
    return false; 
}

When multiple threads are working on a resource at the same time CAS operation , Only one thread can operate successfully , But it doesn't block other threads , Other threads will only receive a signal that the operation has failed .

CAS It can be regarded as an optimistic lock . ( Or it can be understood as CAS It's an implementation of optimistic lock ）

7.2 CAS How did it happen

For different operating systems ,JVM Different CAS Realization principle , simply

java Of CAS Take advantage of unsafe This class provides CAS operation ;
unsafe Of CAS Rely on jvm For different operating systems Atomic::cmpxchg;
Atomic::cmpxchg The implementation of using the assembly of CAS operation , And use cpu Hardware provided lock The mechanism guarantees its atomicity

7.3 CAS Implement atomic classes

The standard library provides java.util.concurrent.atomic package , The classes inside are implemented in this way .

Typical is AtomicInteger class . Among them getAndIncrement amount to i++ operation .

Code implementation

public class Demo5 {
    public static void main(String[] args) throws InterruptedException {
        AtomicInteger num = new AtomicInteger(0);

        Thread t1 = new Thread(() ->{
            for (int i = 0; i < 5000; i++) {
                // This method is equivalent to num++
                num.getAndIncrement();
            }
        });

        Thread t2 = new Thread(() ->{
           for (int i = 0; i < 5000; i++) {
               // This method is equivalent to num++
               num.getAndIncrement();
           }
        });

        t1.start();
        t2.start();
        t1.join();
        t2.join();
        System.out.println(num.get());
    }
}

There is no thread safety problem in the above code .
be based on CAS Realized ++ operation .
This can ensure thread safety , And can compare with synchronized Efficient .
synchronized Will involve lock competition , Two threads have to wait for each other .
CAS Thread blocking and waiting are not involved

7.4 Spin lock

be based on CAS Achieve more flexible locks , Gain more control .

Spin lock pseudocode

public class SpinLock {
    private Thread owner = null;
    public void lock(){
        //  adopt  CAS  See if the current lock is held by a thread . 
        //  If the lock is already held by another thread ,  Then wait . 
        //  If the lock is not held by another thread ,  Then put  owner  Set to the thread currently trying to lock . 
        while(!CAS(this.owner, null, Thread.currentThread())){
       }
   }
    public void unlock (){
        this.owner = null;
   }
}

Similar to the atomic class above , It is also realized through a loop .

Call... In the loop CAS.CAS Will compare current owner Is the value null,
If it is null Change to the current thread . It means that the current thread has got the lock .
If not null Just go back to false, Into the next loop .
The next cycle is still going on CAS operation
If the current lock is one Directly held by others , The thread currently trying to lock will be in this while Where fast
Repeat the cycle ~~~ => The spin ~~ ( Busy etc. )
Spin lock is a lightweight lock, which can also be regarded as an optimistic lock .

8. CAS Of ABA problem

ABA The problem of :

Suppose there are two threads t1 and t2. There's a shared variable num, The initial value is A.

Next , Threads t1 Want to use CAS hold num Value changed to Z, So you need

Read first num Value , It was recorded that oldNum variable .

Use CAS Determine current num Is the value of A, If A, Just change it to Z.

however , stay t1 Between performing these two operations , t2 Threads may put num From A Changed to B, Again from B Changed to A.A It's not the same anymore A 了

ABA The problem led to BUG

Most of the time , t2 Thread such a repeated horizontal jump change , about t1 Whether to modify num It doesn't matter . But don't rule out one Some special circumstances

hypothesis A Yes 100 deposit .,A Want to ATM take 50 Yuan . The ATM creates two threads , Execute concurrently -50 operation .
We expect a thread to execute -50 success , Another thread -50 Failure .（ Another thread is stuck when the machine breaks down , Press one more withdrawal , The thread is enabled , Failed to use to withdraw ）

If you use CAS To complete this deduction process, there may be problems

Normal process ：

1) deposit 100. Threads 1 The current deposit value obtained is 100, Expect to update to 50; Threads 2 The current deposit value obtained is 100, Expect to update to 50.
2) Threads 1 Deduction successfully executed , The deposit was changed to 50. Threads 2 Blocking waiting .
3) It's the thread's turn 2 Yes , It is found that the current deposit is 50, And what I read before 100 inequality , Execution failure .
Finally take it out 50

Abnormal process ：

1) deposit 100. Threads 1 The current deposit value obtained is 100, Expect to update to 50; Threads 2 The current deposit value obtained is 100, Expect to update to 50.
2) Threads 1 Deduction successfully executed , The deposit was changed to 50. Threads 2 Blocking waiting .
3) In a thread 2 Perform before , A My friend just gave me A Transfer accounts 50, The account balance becomes 100
4) It's the thread's turn 2 Yes , It is found that the current deposit is 100, And what I read before 100 identical , Perform the deduction operation again
Finally take it out 100

This is the time , The deduction operation was performed twice , Namely ABA Caused by the

8.1 Solution

Give the value to be modified , Introduce version number .. stay CAS Compare the current value of the data with the old value , Also compare whether the version number meets the expectation .

CAS The operation reads the old value while , Also read the version number .
When it's really revised ,
If the current version number is the same as the read version number , Then modify the data , And put the version number + 1.
If the current version number is higher than the read version number . The operation failed ( Think the data has been modified ).

stay Java The standard library provides AtomicStampedReference<E> class . This class can wrap a class , In-house mention It provides the version management function described above .

8.2 Relevant interview questions

1) Explain what you understand CAS Mechanism

Full name Compare and swap, namely " Compare and exchange ". Equivalent to the operation of an atom , Simultaneous completion " Read memory , Comparison is equal , Modify memory " These three steps . Essentially, we need CPU Support of instructions .

2) ABA How to solve the problem ？

Introduce the version number to the data to be modified . stay CAS Compare the current value of the data with the old value , Also compare whether the version number meets the expectation .
If the current version number is found to be consistent with the version number read before , Just really perform the modification operation , And let the version number increase ; If you find that the current version number is larger than the version number you read before , It is considered that the operation failed .