When AQS wakes up the thread, I understand why it traverses from the back to the front

First, get familiar with the code , Hang and wake up

1. Tail traversal source code

   private void unparkSuccessor(Node node) {
         
       // obtain wait state 
       int ws = node.waitStatus;
       if (ws < 0)
           compareAndSetWaitStatus(node, ws, 0);//  Will wait for status waitStatus Set to initial value 0
       /** *  If the subsequent node is empty , Or the status is CANCEL（ Has lapsed ）, Then from the tail forward traversal to find the first node in the normal blocking state  *  Wake up  */
       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);// Wake up the thread 
   }
   
   

   Be careful for Logic in the loop ： From the tail forward , Find the first node in the normal blocking state , Until the nodes coincide （ That is, it is equal to the current node ）

2. High and send the logic of joining the team
   Since the logic of traversal from the tail is adopted , Then it must be to solve the possible problems . And the problem is enq(…) In the method

   private Node enq(final Node node) {
         
       for (;;) {
         
           Node t = tail;
           if (t == null) {
          // Must initialize
               // The queue is empty and needs to be initialized , Create an empty header node 
               if (compareAndSetHead(new Node()))
                   tail = head;
           } else {
         
               node.prev = t;
               //set The tail node 
               if (compareAndSetTail(t, node)) {
         // The current node is set to the tail 
                   t.next = node; // Of a precursor node next Pointer to current node 
                   return t;
               }
           }
       }
   }
   
   

3. Atomic question
   In this method , Putting the current node at the end uses CAS To ensure thread safety , But notice ： stay if The code in the statement block does not use any means to ensure thread safety ！

   in other words , In high concurrency , That may be the case ：

   Threads A adopt CAS Get into if After the statement block , A context switch has occurred , The thread B The method is also implemented , And it's done . Then the thread C Called unparkSuccessor Method .

   Suppose it is a form of traversal from beginning to end , Threads A Of next The pointer is still null！ in other words , Subsequent nodes will be missed .

4. Diagram flow
   Threads A perform CAS Set the current node as the tail ：
   

   Original thread A To execute t.next = node; take node2 Of next Set to node3, however , A context switch occurs , The time slice is handed over to the thread B, in other words , here node2 Of next still null

   Threads B perform enq Logic , Final CLH The queue is shown in the figure ：
   

   A context switch occurs , The time slice is handed over to the thread C, Threads C Called unparkSuccessor Method , Suppose it is a form of traversal from beginning to end , stay node2 You will find ,next Pointer for null, It seems that there are no subsequent nodes .

   A context switch occurs , The time slice is handed over to the thread A,A take node2 Of next=node3. Something strange happened ： For threads C Come on , No follow-up node3 and node4, But for other threads , But these two nodes appear

5. ending
   From the head traversal, we found the reason for this problem , Finally, let's talk about why there is no such problem when traversing from the tail ？

   The most fundamental reason is ：
   node.prev = t; Precede CAS perform , in other words , You have assigned a value to the predecessor node before setting the current node as the tail , Of course it won't happen prev=null The situation of