Write a ReentrantLock lock

Handwritten ReentrantLock

Recently, I learned about locks in the Java language, looked at the ReentrantLock source code, and wrote a ReentrantLock by myself.

ReentrantLock is a reentrant lock, and it can be converted between fair lock and unfair lock through constructor in source code.

Reentrant lock means that the current thread can acquire the lock multiple times without releasing the lock, but the number of times to release the lock should be the same as the number of times to acquire the lock, otherwise an IllegalMonitorStateException exception will be thrown.

The difference between fair lock and unfair lock is that fair lock enables the thread that enters the waiting queue first to acquire the lock, and each thread has the opportunity to acquire the lock. Unfair lock is the probability of each thread getting lock is uncertain. The concurrency of unfair lock is better, but it is easy to cause some threads can not get lock for a long time.

Non reentrant lock, unfair

/**
 * Non reentrant lock
 */
public class WonderReentranrLock{
    //Mark the thread that obtains the lock, and the reference of atomic type ensures atomicity
    private AtomicReference<Thread> owner = new AtomicReference<>();
    //Enter the waiting queue in case of lock grabbing failure
    private Queue<Thread> waitQueue = new LinkedBlockingQueue();

    /**
     * Lock up
     */
    public void lock(){
        //Failure to grab locks
        if(!tryLock()){
            Thread current = Thread.currentThread();
            //Thread enters waiting queue
            waitQueue.offer(current);
            //Keep trying to grab the lock
            for(;;){
                //Get queue header
                Thread head = waitQueue.peek();
                //If the current thread is in the queue header
                if(current == head){
                    //Grab lock
                    if(!tryLock()){
                        //If the lock snatch fails
                        LockSupport.park();
                    }else{
                        //If the lock snatch is successful, the thread will be out of the queue
                        waitQueue.poll();
                        return;
                    }
                }else{
                    //If not in the queue header, suspend the thread
                    LockSupport.park();
                }
            }
        }
        //If you succeed, you get the lock
    }

    /**
     * Try locking
     * @return
     */
    public boolean tryLock(){
        Thread current = Thread.currentThread();
        //CAS atomic operation modification mark, i.e. lock grabbing
        return owner.compareAndSet(null,current);
    }

    /**
     * Unlock
     */
    public void unLock(){
        //The current thread released the lock successfully
        if(tryUnLock()){
            Thread head = waitQueue.peek();
            //Whether the queue header exists
            if(head!=null){
                //If it exists, wake up the queue head thread to rob the lock
                LockSupport.unpark(head);
            }
        }
    }

    /**
     * Try to unlock
     * @return
     */
    public boolean tryUnLock(){
        Thread current = Thread.currentThread();
        //Determine whether the current thread holds the lock
        if(owner.get()!=current){
            throw new IllegalMonitorStateException();
        }else{
            //Hold CAS operation release lock
            return owner.compareAndSet(current,null);
        }
    }
}

This ReentrantLock is an unfair and non reentrant lock.

There is a pit here: although it is judged whether to lock the queue head, if it is the queue head, let it rob the lock, if it is not the head, hang up, it seems to be the first in first out of the queue, like a fair lock, but in multithreading, queue head and threads not in the queue may rob the lock, and the head thread may fail to rob the lock, so it is unfair .

Then write a re entrant lock (unfair). It seems that the implementation of fair lock is more complex, so it is not considered first.

ReentrantLock, unfair

/**
 * Reentrant lock
 */
public class WonderReentrantLock2 {
    //Mark the thread that gets the lock. It's not the owner. It doesn't use the atomic type
    private Thread owner = null;
    //Record the number of re-entry, grab the lock, grab the count
    private AtomicInteger count = new AtomicInteger();
    //Enter the waiting queue in case of lock grabbing failure
    private Queue<Thread> waitQueue = new LinkedBlockingQueue();

    /**
     * Lock as non reentrant lock
     */
    public void lock(){
        //Failure to grab locks
        if(!tryLock()){
            Thread current = Thread.currentThread();
            //Thread enters waiting queue
            waitQueue.offer(current);
            //Keep trying to grab the lock
            for(;;){
                //Get queue header
                Thread head = waitQueue.peek();
                //If the current thread is in the queue header
                if(current == head){
                    //Grab lock
                    if(!tryLock()){
                        //If the lock snatch fails
                        LockSupport.park();
                    }else{
                        //If the lock snatch is successful, the thread will be out of the queue
                        waitQueue.poll();
                        return;
                    }
                }else{
                    //If not in the queue header, suspend the thread
                    LockSupport.park();
                }
            }
        }
        //If you succeed, you get the lock
    }

    /**
     * Try locking
     * @return
     */
    public boolean tryLock(){
        Thread current = Thread.currentThread();
        //Number of times the lock was seized
        int ct = count.get();
        //The number of times is not 0, which means that a thread has grabbed the lock
        if (ct!=0){
            //If the thread that grabs the lock is the current thread
            if(owner==current){
                //Reentry, times + 1
                count.set(ct+1);
                return true;
            }else{
                //Not the current thread, failed to grab lock
                return false;
            }
        }else{
            //The number of times is 0, which means there is no thread to seize the lock and CAS operation to seize the lock
            if(count.compareAndSet(ct,ct+1)){
                //Mark owner as the current thread after seizing the lock
                owner = current;
                return true;
            }else{
                //CAS lock snatch failed
                return false;
            }
        }
    }

    /**
     * Unlock
     */
    public void unLock(){
        //The current thread released the lock successfully
        if(tryUnLock()){
            Thread head = waitQueue.peek();
            //Whether the queue header exists
            if(head!=null){
                //If it exists, wake up the queue head thread to rob the lock
                LockSupport.unpark(head);
            }
        }
    }

    /**
     * Try to unlock
     * @return
     */
    public boolean tryUnLock(){
        Thread current = Thread.currentThread();
        //Determine whether the current thread holds the lock
        if(owner!=current){
            throw new IllegalMonitorStateException();
        }else{
            //Acquire lock times
            int ct = count.get();
            //count should be next after unlocking
            int next = ct - 1;
            //count.set(next); pit!
            if(next==0){
                //If the count is 0 after unlocking, all the locks are unlocked, and the owner is set to null
                owner = null;
                //Change the count value to 0 after the owner is null
                count.set(next);
                return true;
            }else{
                //If the next value is not 0, it means that there is still a re-entry lock unresolved. Just modify the count, and the owner will not change
                count.set(next);
                return false;
            }
        }
    }
}

The difference between re entrant locks and non re entrant locks is that non re entrant locks are the process in which threads compete for the owner (thread mark), and re entrant locks increase the count to record the times of a thread re entrant. Therefore, when the re-entry lock grabs the lock, first judge whether the count is 0. If the count is 0, the lock is idle. First use CAS to modify the count, and then modify the owner as the current thread. The lock grabbing is successful. If count is not 0, it means that the lock is occupied by a thread. Then judge whether the thread occupying the lock is the current thread. If it is, add 1 to count to realize reentry. If it is not the current thread, the lock grabbing failure will be suspended.

When writing the reentrant lock, a pit was encountered. In the code, the tryUnLock() method starts to unlock if the owner is the current thread. At the beginning of writing, first modify the count value to the original value minus 1, and then set the owner to null. After running, it is found that the illegal monitor state exception error has been reported all the time, that is, after the current thread is locked, the owner is not the current thread when trying to unlock. This is because the owner is modified after the count is modified. If the count value is 0 after modification, other threads will seize the lock and modify the owner. At this time, the owner is not the original thread. Here, you can fix the problem by putting the modified count after owner=null. You can also change the owner to the AtomicReference type.

Test code

public class Test {
    static WonderReentrantLock lock = new WonderReentrantLock();
    static WonderReentrantLock2 lock2 = new WonderReentrantLock2();

    volatile static int count=0;

    public static void main(String[] args) throws InterruptedException {
        for(int i=0; i<10; i++){
            new Thread(){
                @Override
                public void run() {
                    for(int j=0; j<10000; j++){
                        lock2.lock();//Reentrant
                        count++;
                    }
                    for(int j=0; j<10000; j++){
                        lock2.unLock();//How many times to lock, how many times to unlock
                    }
                    System.out.println("over...");
                }
            }.start();
        }
        Thread.sleep(4000);
        System.out.println(count);

        /*for(int i=0; i<10; i++){
            new Thread(){
                @Override
                public void run() {
                    for(int j=0; j<10000; j++){
                        lock.lock();//Non reentrant
                        count++;
                        lock.unLock();
                    }
                    System.out.println("over...");
                }
            }.start();
        }
        Thread.sleep(4000);
        System.out.println(count);*/
    }
}
Published 5 original articles, praised 0, visited 8
Private letter follow

Tags: Java

Posted on Sat, 01 Feb 2020 02:47:57 -0800 by rubadub