JUC concurrent programming 07 -- is fair lock really fair (source code analysis)

Let's review the of fair lock tryAcquire Code .

    protected final boolean tryAcquire(int acquires) {
    
            final Thread current = Thread.currentThread();
            int c = getState();
            if (c == 0) {
    
                if (!hasQueuedPredecessors() && // Note that there , At the beginning, it will check whether there are nodes waiting 
                    compareAndSetState(0, acquires)) {
    
                    setExclusiveOwnerThread(current);
                    return true;
                }
            }
            else if (current == getExclusiveOwnerThread()) {
    
                int nextc = c + acquires;
                if (nextc < 0)
                    throw new Error("Maximum lock count exceeded");
                setState(nextc);
                return true;
            }
            return false;
        }
    }

Focus on the comment code , If hasQueuedPredecessors What happens if there is a miscarriage of justice ？ Is fair lock unfair . Let's study hasQueuedPredecessors, Is there really a secret situation .

If a thread 1 Already holding the lock . This is the time 2 To get the lock , Go to the hasQueuedPredecessors（） return false, Then go back CAS, The execution must have failed , Because now the lock is locked by the thread 1 occupy , return aquire Method .

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

Then walk to addWaiter Of enq Method . Threads 2 Enter the waiting queue .

    private Node enq(final Node node) {
    
        for (;;) {
    
            Node t = tail;
            if (t == null) {
     //  At this time, etc head、tail It's empty , Satisfy `t==null` Conditions .
                if (compareAndSetHead(new Node())) // There are no other threads competing here , success 
                    tail = head; //  Set up the success 
            } else {
    
                node.prev = t;
                if (compareAndSetTail(t, node)) {
    
                    t.next = node;
                    return t;
                }
            }
        }
    }

Assuming that thread 2 Go to the end of the note , Now there is a thread 3 Come grab the lock . When it judges the waiting queue hasQueuedPredecessors Returns the false, because h==t.

    public final boolean hasQueuedPredecessors() {
    
        Node t = tail; 
        Node h = head;
        Node s;
        return h != t && // Not meeting the conditions 
            ((s = h.next) == null || s.thread != Thread.currentThread());
    }

So here comes the question , In fact, there should be threads in the waiting queue 2, Now we have come to the judgment that the waiting queue is empty , Threads 3 No, just go CAS Do you , In case the thread 1 Just released the lock , Threads 3 Just cut in line . thus it can be seen , Fair lock is not fair .

     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;
                }
            }
            else if (current == getExclusiveOwnerThread()) {
    
                int nextc = c + acquires;
                if (nextc < 0)
                    throw new Error("Maximum lock count exceeded");
                setState(nextc);
                return true;
            }
            return false;
        }
    }

Use a chart to summarize the above process .

The key to fairness and unfairness lies in hasQueuedPredecessors Whether there will be misjudgment .