(HttpClient逾時機制)timeout排程算法探讨後記：

繼上一篇文章： httpclient逾時機制(安全問題處理:通路超大檔案控制)

提到了一個需要管理所有request請求的timeout，原先文章的一種處理方式是起一個異步線程的方式，通過jdk的unsafe的await機制控制timeout。 

存在的問題：

1.  建立新線程的開銷不小。

2.  大量線程的排程和切換，引起不必要的context switch

和同僚在溝通的過程中，提到一種新思路，就是有一個monitor線程來管理所有request的timeout。

啟動一個monitor thread，是一個while true運作

每個請求建立之前都先注冊到monitor，比如什麼時候過期和對應的request句柄，完成後登出。 

運作的monitor，定時讀取注冊的request資訊，發現有資料過期時間到了，直接拿到request引用，執行強制關閉。

針對monitor timeout排程設計時，也想過幾種思路：

思路1： 插入o(1) + 排程o(n)+ 主動輪詢式

維護一個list隊列，monitor線程間隔固定頻周遊一次list隊列。挑出時間已經過期的資料，執行關閉。

思路2： 插入o(logn) + 排程o(1) + 主動輪詢式

維護一個有序隊列(根據距離過期時間最近做升序排序)，monitor線程間隔固定頻取出頭節點，進行關閉處理。

思路3： 插入o(logn) + 排程o(1) + 阻塞通知式

維護一個二叉樹(根據距離過期時間最近做升序排序)，monitor阻塞于二叉樹隊列，擷取頭節點，通過signal方式喚醒。

很明顯，思路3在處理上比較靠譜，性能上和處理成本比較好。

二叉樹第一直覺就是選擇priorityqueue或者treemap。 

priorityqueue是一個基于object[]數組實作的二叉樹，而treemap走的是紅黑樹，比較傳統的left,right節點的樹實作。

考慮再加上timeout時間需要進行delay處理，最後就有一個不二之選delayqueue了，其内部包含了一個priorityqueue做為其資料存儲。

delayqueue的item對象是需要實作delayed接口

 說明：getdelay主要傳回對應距離目标time還存在剩餘的delay時間。這裡插入一個request後，立馬調用該方法傳回的應該就是你想要的timeout時間。

代碼實作：

啟動thread : 

最後思考一下timeout的處理機制，就類似于一個定時器的概念，隻不過這個定時器執行一次。是以最後也查了下linux的定時器排程算法，前面3種思路也是大同小異。 

現在linux作業系統使用的應該是wheel排程算法，具體可以參看一篇ibm的文章： linux 下定時器的實作方式分析

其對應的幾種算法複雜度： 

實作方式

starttimer

stoptimer

pertickbookkeeping

基于連結清單

o(1)

o(n)

基于排序連結清單

基于最小堆

o(lgn)

基于時間輪

ps :  最後感慨一下，java的确給我們封裝了很多不錯的工具包，比較友善。java.util.*還是有許多比較不錯的算法和實作，可以深挖下。