netty PriorityQueue源碼分析

文章目錄

• • 1 netty PriorityQueue簡介
  • 2 隊列結構
  • 3 ScheduledFutureTask比較的本質
  • 4 優先級隊列-入隊-堆中插入元素
  • 5 優先級隊列-出隊-删除堆頂元素
  • 6 本文小結

1 netty PriorityQueue簡介

netty 的多路複用器的一個典型實作是NioEventLoop,而NioEventLoop的的reactor實作是一個非常高效的模式,可以支援在單線程情況下,完成如下工作,包括:

1. 讀取對端資料發送事件到pipline;
2. 調動pipline發送資料;
3. 執行系統調用任務;
4. 執行定時任務;

這裡涉及到的定時任務執行離不開任務加入隊列和出隊列,而netty正是在AbstractScheduledEventExecutor類中聚合了自己的隊列類,本文的主要目的便是介紹一下netty自己實作的這個任務隊列,并就相關原理進行分析!

如下圖所示是netty實作的優先級隊列的繼承關系

2 隊列結構

首先看看DefaultPriorityQueue的具體結構:

如上圖可知優先級隊列含有三個關鍵要素

• 大小比較器
• 負責任務存儲的數組–

  優先級隊列實作的堆的結構

• 堆的大小

通過DefaultPriorityQueue的執行個體化,我們找到了優先級隊列的比較器具體實作,即通過ScheduledFutureTask的compareTo完成任務比較

!

3 ScheduledFutureTask比較的本質

ScheduledFutureTask進行優先級比較的本質,如下圖所示,可以推斷為目前任務的

截止時間

,

當截止時間較長者則傳回1,如果二者具有相同截止時間則由任務建立時候統一配置設定的任務id作為唯一辨別!

因為這裡的ScheduledFutureTask也是一個個人覺得很有設計感的地方,在此同樣給出其相關圖示!

4 優先級隊列-入隊-堆中插入元素

堆中插入元素的關鍵就是插入元素與其父節點比較大小,滿足條件則維持現狀,不滿足則進行交換!

下面以隊列入隊操作分析優先級隊列的入隊操作,如下所述是隊列入隊操作offer的基本邏輯,其重點方法為bubbleUp實作,其本質為堆結構的入堆操作!

這裡是入堆操作的具體執行過程,從函數分析可知幾個要點:

1. netty實作的優先級隊列是一個小頂堆!

2. 當插入節點小于父節點值的時候就停止交換.
3. 當插入節點大于父節點的值的時候就進行交換,然後疊代檢查,直到滿足步驟二;

   

5 優先級隊列-出隊-删除堆頂元素

netty的出隊過程就是堆的删除鍵堆頂元素的過程,這裡包含兩個步驟:

1. 彈出堆頂元素;

2. 取最後一個元素自上而下進行堆化操作

   ;

下圖給出的為自上而下堆化過程的完整流程:

6 本文小結

netty實作優先級隊列的

本質是利用堆,也就是數組的資料結構,實作隊列接口的入隊和出隊操作接口

,具體任務是由自己編寫的ScheduledFutureTask任務.這裡有如下幾點值得我們在以後的程式設計中借鑒和參考,再次總結如下:

1. 高效性:使用堆資料結構實作優先級隊列–以

   截止時間長短作為優先級隊列的比較憑據,實作一個定時任務執行器

   ----->

   每次取堆頂元素節點完成任務,代替了每次取整個任務清單執行任務!這樣避免了頻繁的掃描!

2. 擴充性: DefaultPriorityQueue實作中中将比較器作為構造函數,提供使用者對外定制,這裡AbstractScheduledEventExecutor這是基于此定制了自己的比較器,使得優先級隊列的複用性更強!
3. 特别注意ScheduledFutureTask的結構,其使用了queueIndex這個變量來辨別在堆中的位置,如果出隊了則該索引等于INDEX_NOT_IN_QUEUE;
4. 程式設計參考:後續實作定時任務隊列處理流程或者實作優先級隊列可以參考netty的這種實作,其較為完備的考慮堆化\擴容的相關問題,值得學習和借鑒!

通過再次詳細列出其流程主要目的是進一步複習一下堆這種資料結構!