[HBZ sharing] the principle of reentrantlock realized by AQS + CAS +locksupport

according to ReentrantLock Handwritten a lock source code

Handwritten source code gitee Address : https://gitee.com/huang_bao_se/write_aqs_cas_locksupport

CAS principle

1. cas Controls the 3 It's worth , Namely 【 Memory address V】【 The original value of the expected A】【 New value after modification B】
2. When changing the memory value , Will take 【 Original memory value 】 And 【 Expected original value 】 Contrast , If memory address V The value saved in and the expected original value A equal , The processor will automatically B Replace the value of with V On
3. If V != A, Will fail to update . It can be said that someone put V Changed . Once the update fails , It's going to spin , Recapture V Value , And recalculate B The new value of , then V Continue and A Continue to compare , If equal , Just put B Update to V On
4. AtomicInteger,AtomicXXX, At the bottom of the atomic class is CAS Realization , To some extent than Synchonized good , Because the latter belongs to pessimistic lock
5. shortcoming ： When too many threads spin , It can lead to CPU Consume , This situation may be better than Synchonized The poor . That is, in many cases ,Synchonized It is quite possible that CAS good

AQS Lock principle

1. Lock for the first time , Will acquire lock ,state Add 1.
2. The thread B coming , Lock acquisition failed , He'll go into a blocking queue . Then the thread C Here we are , He will also fail , He will insert into B Line up behind .
3. The blocking queue is a two-way linked list , When a thread A Of state Reduced to 0 了 , This will traverse the blocking queue ( Be careful , Is traversal , Not a thread that goes directly to the next node ). Then obtain the thread from the nearest qualified node to lock . This note , If B The thread is still alive , Then I'll take it B node , The reason for traversing rather than removing a node , To prevent B The thread may stop or die , If it stops , Then I'll take it C. In short, it is generally first in first out , But the thread must be normal

AQS Unlock unlock

1. Unlock first state Will be reduced 1, If state Not for 0, Thread activation in the queue is still not triggered .
2. If state by 0 了 , The lock is completely released , Then traverse the blocking queue NODE, Take out the thread saved by the node closest to him that meets the requirements and lock it .

ReentrantLock principle （ Not fair lock – Default – Performance is better than fair lock ）

1. ReentrantLock When receiving a new thread , Because it is an unfair lock , So direct will directly use CAS Judge and lock
2. When the expected original value A = 0, The new value B = 1, If the lock is successful , Then return directly true that will do . And put state = 1, Record the number of reentries of this thread
3. If CAS return false, It means that a thread has already got the lock , Now judge 【 Current thread 】 And 【 Lock thread 】 Whether it is the same thread , If it is , be state++, Then return true
4. If CAS return false, also 【 Current thread 】 It's not equal to 【 Lock thread 】, Then the current thread will enter the blocking state , And will load 【 List queue 】 in
5. Multiple threads to , Will follow the order of time , Add to in turn 【 List queue 】 in
6. When the unlock , Will be able to state–, If state = 0, Indicates that the lock is released , If state-- Later not 0, It means that only one layer of re-entry lock is unlocked , The lock cannot be released at this time , The thread in the linked list queue will not wake up
7. When state = 0 when ,, Because it is an unfair lock , Will wake up all threads in the waiting queue , All threads will rob the lock , Those who don't get it continue to return to the queue , And so on until the queue is empty

ReentrantLock principle （ Fair lock ）

1. ReentrantLock When receiving a new thread , Because it's a fair lock , So judge first state = 0, Instead of directly using CAS Lock
2. If it is 0, It means that the lock is not acquired by any thread at this time , Then it will pass CAS To lock , Will lock successfully , Get the lock , then state = 1;
3. If state != 0, Will judge 【 Current thread 】 and 【 Lock thread 】 Whether it is equal or not , If equal , be state++, Otherwise enter the waiting line
4. Multiple threads to , Will follow the order of time , Add to in turn 【 List queue 】 in
5. When the unlock , Will be able to state–, If state = 0, Indicates that the lock is released , If state-- Later not 0, It means that only one layer of re-entry lock is unlocked , The lock cannot be released at this time , The thread in the linked list queue will not wake up
6. When state = 0 when ,, Because it's a fair lock , Therefore, only the first thread in the waiting queue will be awakened , At this point, the first thread gets the lock , Do the same and so on , Until the queue is empty

Handwriting ReentrantLock Source code

/**
 *  Handwriting AQS
 */
public class MysLockAQS {

    /**
     *  Whether it is locked , The lock state (0: Lock present ;1:  Lock given to thread )
     */
    private AtomicInteger lockState = new AtomicInteger(0);

    /**
     *  The object that gets the lock 
     */
    private Thread thread = null;

    /**
     *  Lock type (true:  Fair lock ;false:  Not fair lock )
     */
    private boolean lockType = false;

    /**
     *  Number of re-entry locks 
     */
    private Integer state = 0;

    /**
     *  The thread that did not acquire the lock , Save to the linked list 
     */
    private ConcurrentLinkedDeque<Thread> concurrentLinkedDeque = new ConcurrentLinkedDeque<Thread>();


    public MysLockAQS(){

    }

    public MysLockAQS(boolean lockType){
        this.lockType = lockType;
    }

    /**
     *  Lock 
     * @return
     */
    public boolean lock(){

        //  The dead cycle here refers to , After the blocked thread is awakened, it should try again and again 
        for (;;){
            //  adopt CAS Try to lock 
            if(acquire()){
                //  Locking success ,thread Give the current thread 
                thread = Thread.currentThread();
                // state assignment 1, Means to lock 1 Time 
                state = 1;
                //  Locking success , Exit the loop directly 
                return true;
            }else{
                //  Locking failed , Determine whether the current thread 
                if(thread == Thread.currentThread()){
                    //  Is the current thread , Then it will still be released , also state+1
                    state++;
                    return true;
                }
            }

            //  Locking failed , Add the thread to the linked list to save 
            concurrentLinkedDeque.add(Thread.currentThread());
            //  Block the current thread , By unPark After wake up , Continue from here , That is, enter the next cycle 
            LockSupport.park();
        }

    }

    /**
     *  Unlock 
     * @return
     */
    public boolean unLock(){
        //  Determine whether the current thread has got the lock 
        if(thread == null){
            return false;
        }
        //  Judge if it is the current thread 
        if(thread == Thread.currentThread()){
            //  Judge state Is it 1
            if(state > 1){
                //  Greater than 1, It means that there is a re-entry lock , need state - 1,  But you can't release the lock 
                state--;
                return true;
            }
            // CAS Perform unlocking 
            if(compareAndSetState(1, 0)){
                //  unlocked , Judge whether it is a fair lock or an unfair lock 
                if(lockType){
                    //  Fair lock , Wake up the first thread in the linked list 
                    Thread first = concurrentLinkedDeque.pollFirst();
                    //  Wake up the thread 
                    LockSupport.unpark(first);
                }else{
                    //  Not fair lock , Loop to wake up all threads of the linked list , Let them take it by themselves 
                    for(;;){
                        if(concurrentLinkedDeque.size() == 0){
                            System.out.println(" The queue is empty ");
                           break;
                        }
                        //  Fair lock , Wake up the first thread in the linked list 
                        Thread first = concurrentLinkedDeque.pollFirst();
                        //  Wake up the thread 
                        LockSupport.unpark(first);
                    }

                }
            }
        }

        return false;
    }

    private boolean acquire(){
        if(compareAndSetState(0, 1)){
            return true;
        }
        return false;
    }
    /**
     * CAS
     * @param expect    Expected original value 
     * @param update    Change the new value 
     * @return
     */
    private boolean compareAndSetState(int expect, int update){
        return lockState.compareAndSet(expect, update);
    }

 Call tests ：
public class Test {

    private static MysLockAQS mysLockAQS = new MysLockAQS(true);
    public static void main(String[] args) throws InterruptedException {
        mysLockAQS.lock();
        System.out.println(" The main thread is locked : " + Thread.currentThread().getName());
        for(int i = 0; i < 10; i++){
            //  Turn on 10 Sub threads , Verify fair lock and unfair lock 
            new Thread(()->{
                System.out.println("start: " + Thread.currentThread().getName());
                mysLockAQS.lock();
                System.out.println("end: " + Thread.currentThread().getName());
                try {
                    Thread.sleep(100);
                } catch (InterruptedException e) {
                    e.printStackTrace();
                }
                mysLockAQS.unLock();
            }).start();
        }

//        System.out.println(" The main thread is unlocked : " + Thread.currentThread().getName());
        test2();
        mysLockAQS.unLock();

    }

    /**
     *  Reentry lock test 
     * @throws InterruptedException
     */
    public static void test2() throws InterruptedException {

        mysLockAQS.lock();
        System.out.println(" The main thread 2 Second lock : " + Thread.currentThread().getName());
        Thread.sleep(200);

        test3();
        mysLockAQS.unLock();
    }

    /**
     *  Reentry lock test 
     * @throws InterruptedException
     */
    public static void test3() throws InterruptedException {

        mysLockAQS.lock();
        System.out.println(" The main thread 3 Second lock : " + Thread.currentThread().getName());
        Thread.sleep(300);
        mysLockAQS.unLock();
    }

}