The core difference between fairness and unfairness of reentrantlock

Look at the class diagram ,NonfairSync and FairSync Together ReentrantLock, They are ReentrantLock The inner class of

ReentrantLock Just a shell outside , The concrete implementation is completed by these two internal classes

So the common features of these two inner classes now seem to be inherited from Sync This class

1. The core difference between

Go straight to source

static final class NonfairSync extends Sync {
        private static final long serialVersionUID = 7316153563782823691L;
        final void lock() {
            if (compareAndSetState(0, 1))
                setExclusiveOwnerThread(Thread.currentThread());
            else
                acquire(1);
        }

static final class FairSync extends Sync {
        private static final long serialVersionUID = -3000897897090466540L;

        final void lock() {
            acquire(1);
        }
// The only difference is here , The rest join the team , Blocking , Wake up the , All use Sync Class 
// The fair lock will not be directly locked once , Not fair lock will rob lock , If you grab the lock, you won't join the team , Direct execution , Then it's not fair for those in the queue , But if every thread fails , Still want to join the team , For example, continuous 100 individual , this 100 None of them grabbed the lock , In fact, they are fair , So is this fairness relatively macro or micro 

2. The same operation

Lock

public final void acquire(int arg) {
        if (!tryAcquire(arg) &&
            acquireQueued(addWaiter(Node.EXCLUSIVE), arg))
            selfInterrupt();
    }

 This method is to acquire the lock , Here are a few steps :
1. tryAcquire, Can I get the lock , from AQS Subclasses of ,AQS Only abstract, not specific implementation details 
     With ReentrantLock Take the fair lock of 
   

       protected final boolean tryAcquire(int acquires) {
            final Thread current = Thread.currentThread();
            int c = getState();
            if (c == 0) {
                if (!hasQueuedPredecessors() &&
                    compareAndSetState(0, acquires)) {
                    setExclusiveOwnerThread(current);
                    return true;
                }
            }
            // If state by 0, Indicates that you can try to acquire the lock , Because fair lock , It is also necessary to judge whether there is one in front of the queue 
            // The queue has no and state by 0    Just use cas Lock and execute code for your thread 
            else if (current == getExclusiveOwnerThread()) {
                int nextc = c + acquires;
                if (nextc < 0)
                    throw new Error("Maximum lock count exceeded");
                setState(nextc);
                return true;
            }
            // Here we need to judge whether our thread repeatedly locks     Repeated locking can also be added 
            return false;
        }

2.  If you don't get the lock    

    tryAcquire = false     !tryAcquire(arg) = true  No short circuit acquireQueued(addWaiter(Node.EXCLUSIVE), arg)
     Perform team entry operations      addWaiter(Node.EXCLUSIVE)
    
      private Node addWaiter(Node mode) {
        Node node = new Node(Thread.currentThread(), mode);
        // Try the fast path of enq; backup to full enq on failure
        Node pred = tail;
        if (pred != null) {
            node.prev = pred;
            if (compareAndSetTail(pred, node)) {
                pred.next = node;
                return node;
            }
        }
        enq(node);
        return node;
     }
     //  The figure below       

3.  After joining the team successfully 

     If it is a head node , No blocking , Try to get the lock again , Reduce resource consumption 
     perform  acquireQueued()
    final boolean acquireQueued(final Node node, int arg) {
        boolean failed = true;
        try {
            boolean interrupted = false;
            for (;;) {
                final Node p = node.predecessor();
                if (p == head && tryAcquire(arg)) {
                    setHead(node);
                    p.next = null; // help GC
                    failed = false;
                    return interrupted;
                }
                if (shouldParkAfterFailedAcquire(p, node) &&
                    parkAndCheckInterrupt())
                    interrupted = true;
            }
    // Here, if the lock is obtained, it will head Pointer backward , And through setHead Method erase head The information of the node pointed to by the node , Give Way head Or point to an empty node without information 
    // Usually we may use head The next node pointed to is removed ,head The position of , But here we use the method of erasing information 
            

4.  If you succeed in joining the team 
     And if the lock is not acquired successfully, it will be blocked 
         The blocking process is a two round cycle 
        1: adopt shouldParkAfterFailedAcquire Methods will head Point to the empty node waitStatus Change to SIGNAL Indicates that the following nodes can be awakened 
        2: Carry out the real blocking flag bit setting operation , return true, Here, only the flag bit to block is set 

        private static boolean shouldParkAfterFailedAcquire(Node pred, Node node) {
        int ws = pred.waitStatus;
        if (ws == Node.SIGNAL)
            return true;
        if (ws > 0) {
            do {
                node.prev = pred = pred.prev;
            } while (pred.waitStatus > 0);
            pred.next = node;
        } else {
            compareAndSetWaitStatus(pred, ws, Node.SIGNAL);
        }
        return false;
    }
    // From the top ,head It always points to an empty node , The second node is our thread node 

5.  Team success , After getting the allowed blocking flag bit , Is the real blocking operation 

    if (shouldParkAfterFailedAcquire(p, node) &&
                    parkAndCheckInterrupt())
                    interrupted = true;
    private final boolean parkAndCheckInterrupt() {
        LockSupport.park(this);
        return Thread.interrupted();
    }

Unlock

public void unlock() {
        sync.release(1);
    }

1.  Check the unlocked code 

    public final boolean release(int arg) {
        if (tryRelease(arg)) {
            Node h = head;
            if (h != null && h.waitStatus != 0)
                unparkSuccessor(h);
            return true;
        }
        return false;
    }
​
    private void unparkSuccessor(Node node) {
        int ws = node.waitStatus;
        if (ws < 0)
            compareAndSetWaitStatus(node, ws, 0);
        Node s = node.next;
        if (s == null || s.waitStatus > 0) {
            s = null;
            for (Node t = tail; t != null && t != node; t = t.prev)
                if (t.waitStatus <= 0)
                    s = t;
        }
        if (s != null)
            LockSupport.unpark(s.thread);
    }
​

    waitestate = 0 - > -1 head Why is the node changed to -1, Because the thread holding the lock T0 When releasing the lock , To judge head Node waitestate whether !=0, If ！=0 establish , I'll put waitstate = -1->0, To wake up the first thread in the queue T1,T1 Wake up and then go through the cycle , Go grab the lock , May fail again （ In an unfair lock scenario ）, At this point, there may be threads T3 Hold the lock ！T1 May be blocked again ,head The node state of needs to go through two cycles again ：waitState = 0 -> -1
   Park Blocking thread wakes up in two ways ：
    1、 interrupt 
    2、release()
 Because the head of the queue is an empty node , Instead of the first node to get the lock , So control head Of waitestate To mark whether the node that wants to obtain the lock can be unblocked 
​
 Whether it's fair lock or unfair lock , Wake up the first one in the queue , Instead of waking up and competing again , Unfair also want to join the team , Just join the team , Then there is no competition between them  
 There was a misunderstanding about fairness and unfairness , Think that the unfair lock should wake up all threads in the queue to compete again when unlocking , It's not , At the bottom LockSupport Not all abilities are awakened , Even if it can , Wake up competition is very big , High resource consumption , So as long as you join the team, you only wake up one at a time , Because every time one must be in order as long as they join the team 

3. The efficiency of fair lock and unfair lock

Let's imagine a scene like this , Here we use Thread1   Thread2 This represents a thread
In a period of time, there are 1000 Thread access , The execution time of each thread is not particularly short , The average running time of a thread will be 10 Threads arrive at

Fair lock scenario :
Thread1 Get the lock and start execution , At this time Thread2-Thread11 arrive ,Thread2-Thread12 The team , Queue empty , The first team leader to join Thread2 Will try to grab a lock , Didn't grab the jam , Then at this time Thread2-Thread12 It's blocked , here Thread1 Release lock after execution ,Thread2 Be awakened to perform ,Thread2 During execution ,Thread12-Thread22 The team , And these are not the head of the queue , And none of them are the first threads to be added when the team is empty , Only when these two conditions are met will the lock be attempted , Get no more blocking , So it can be inferred that ,Thread2-Thread1000 in , Only Thread The attempt to acquire the lock has not been blocked , The rest are directly blocked

Not fair lock :
Thread1 Get the lock and start execution , At this time Thread2-Thread11 arrive ,Thread2-Thread12 The team , Queue empty , The first team leader to join Thread2 Will try to grab a lock , Didn't grab the jam , Then at this time Thread2-Thread12 It's blocked , here Thread1 Release lock after execution , At this time, I want to wake up Thread2 Let it do , however Thread13 When you come, grab the lock directly and execute , From here until 1000, May produce 100 Threads are not queued and blocked , If you come directly, grab the lock and execute

We know that blocking wakeup consumes resources , involves cpu State switch of , So it's the same 1000 Time , Unfair lock has 100 There is no need to block wakeup , And the fair lock once did not , The performance gap is coming , But the problem is also very big , If the running time of each thread is very accurate ,Thread2 Wait until the front 100 Every robber who comes up and grabs the lock will execute it after execution , This is less friendly
Of course, the timing of my example may not be appropriate , Execution time and arrival thread are too tight , This must be inappropriate , It is possible to starve many threads without getting the lock , Here is just an analogy of time expenditure , The specific use of fairness and unfairness depends on the running time of the thread , Concurrency , The number of queues stacked and whether it is necessary to enforce fairness to handle business decisions

Here is a picture of AQS General process of , By contrast, we can see where the fair and unfair source code is public , Where is private