Java并發架構——AQS阻塞隊列管理（三）——CLH鎖改造

在CLH鎖核心思想的影響下，Java并發包的基礎架構AQS以CLH鎖作為基礎而設計，其中主要是考慮到CLH鎖更容易實作取消與逾時功能。比起原來的CLH鎖已經做了很大的改造，主要從兩方面進行了改造：節點的結構與節點等待機制。在結構上引入了頭結點和尾節點，他們分别指向隊列的頭和尾，嘗試擷取鎖、入隊列、釋放鎖等實作都與頭尾節點相關，并且每個節點都引入前驅節點和後後續節點的引用；在等待機制上由原來的自旋改成阻塞喚醒。如圖2-5-9-4，通過前驅後續節點的引用一節節連接配接起來形成一個連結清單隊列，對于頭尾節點的更新必須是原子的。下面詳細看看入隊、檢測挂起、釋放出隊、逾時、取消等操作。

圖2-5-9-4 CLH隊列

① 入隊，整塊邏輯其實是用一個無限循環進行CAS操作，即用自旋方式競争直到成功。将尾節點tail的舊值賦予新節點node的前驅節點，并嘗試CAS操作将新節點node賦予尾節點tail，原先的尾節點的後續節點指向建立節點node。完成上面步驟就建立起一條如圖2-5-9-4所示的連結清單隊列。代碼簡化如下：

for (;;) {

   Node t = tail;

   node.prev = t;

   if (compareAndSetTail(t, node)) {

      t.next = node;

      return node;

   }

}

② 檢測挂起，上面我們說到節點等待機制已經被AQS作者由自旋機制改造成阻塞機制，一個建立的節點完成入隊操作後，如果是自旋則直接進入循環檢測前驅節點是否為頭結點即可，但現在被改為阻塞機制，目前線程将首先檢測是否為頭結點且嘗試擷取鎖，如果目前節點為頭結點并成功擷取鎖則直接傳回，目前線程不進入阻塞，否則将目前線程阻塞。代碼簡化如下：

 for (;;) {

    if (node.prev == head)

if(嘗試擷取鎖成功){

         head=node;

         node.next=null;

         return;

     }

   阻塞線程

③ 釋放出隊，出隊的主要工作是負責喚醒等待隊列中後續節點，讓所有等待節點環環相接，每條線程有序地往下執行。代碼簡化如下：

Node s = node.next;

喚醒節點s包含的線程

④ 逾時，在支援逾時的模式下需要LockSupport類的parkNanos方法支援，線程在阻塞一段時間後會自動喚醒，每次循環将累加消耗時間，當總消耗時間大于等于自定義的逾時時間時就直接分返。代碼簡化如下：

   嘗試擷取鎖

   if (nanosTimeout <= 總消耗時間)

      return;

   LockSupport.parkNanos(this, nanosTimeout);

 }

⑤ 取消，隊列中等待鎖的隊列可能因為中斷或逾時而涉及到取消操作，這種情況下被取消的節點不再進行鎖競争。此過程主要完成的工作是将取消的節點移除，先将節點的。先将節點node狀态設定成取消，再将前驅節點pred的後續節點指向node的後續節點，這裡由于涉及到競争，必須通過CAS進行操作，CAS操作就算失敗也不必理會，因為已經改了節點的狀态，在嘗試擷取鎖操作中會循環對節點的狀态判斷。

node.waitStatus = Node.CANCELLED;

Node pred = node.prev;

Node predNext = pred.next;

Node next = node.next;

compareAndSetNext(pred, predNext, next);

<a target="_blank" href="https://item.jd.com/12185360.html">點選訂購作者書籍《Tomcat核心設計剖析》</a>