基於Linux內核的時間輪演算法設計實現【附程式碼】

2019 年 12 月 12 日
筆記

首先聲明，本文內容參考了以下部落格文章，向這三篇文章的作者表示感謝。

https://www.cnblogs.com/arnoldlu/p/7078262.html
https://blog.csdn.net/HELPLEE601276804/article/details/36717979
https://www.cnblogs.com/lsgxeva/p/8072468.html

1. 時間輪演算法基本思想

對於一個複雜的軟體系統，定時器的對任務的管理和調度至關重要，通常定時器的管理已成為一個複雜系統的重要基礎設施。

定時器有很多種（一文完全理解定時器實現技術），基於升序的定時器時間鏈表是一種最直接的實現方式：即按照定時器時間到的時間順序依次存放在一個鏈表中進行管理。但是這種鏈表存在效率的不足，就是當插入定時器的時候時間複雜度是O(n). 因此需要一種更高效地管理定時器的數據結構和演算法，這裡結合Linux內核中基於時間輪的定時器管理器的具體實現，介紹一種基於時間輪的定時器管理演算法。圖1為時間輪的基本結構：

圖1 定時器基本結構

圖1所示的是一個時間輪的基本結構。時間輪分為N個（例如8個）時間槽slot，每時間槽指向一個定時器鏈表，這個鏈表裡包含多個定時器，這個鏈表的定時器Timeout時間相同，因此鏈表裡的定時器無須排序。

時間輪每一個滴答時間轉動一格，會指向下一個時間槽。這裡的滴答時間取決於時間輪的具體實現，可以是系統的一個時鐘時間，也可以是一個毫秒，一秒鐘等。

如果記時間輪的一個滴答時間為si（slot interval），即時間輪每轉動一個槽的時間為si，如果有N個槽，那麼時間輪轉動一圈的時間為N * si。

如果時間輪開始轉動的起始時間為ts，那麼當有個定時器Timeout時間為t的定時器要加入到時間輪，那麼應該將這個定時器放到哪個時間槽對應的鏈表呢？可以用下面的公式計算：

((t – ts）/ si) % N

以圖1為例，如果時間輪一個滴答時間為1秒，假設時間輪開始轉動時間為0，那麼一個定時器Timeout=6s的定時器應該加到6號時間槽對應的鏈表裡，一個定時器Timeout=7s的定時器應該加到7號槽對應的鏈表裡。

那麼時間輪該如何檢查定時器是否時間到呢？同樣地，如果時間輪開始轉動的起始時間為ts，當前時間為tc，則計算

((tc – ts）/ si) % N

計算結果則為定時器時間到的那個時間槽對應編號，這個時間槽對應的鏈表裡的定時器全部時間到。

聰明的讀者馬上會想到一個問題：那麼一個定時器Timout=8s的定時器會加到0號槽，豈不是和定時器Timeout=0s(馬上時間到)的定時器放到一個槽里了？這是因為圖1所示的時間輪刻度只要8個（即只能管理8種不同Timout的定時器），因此為了解決這種問題，需要增加N的值。

增加N的值更聰明的辦法是採用多級時間輪，即在圖1所示的時間輪外面再環繞一個時間輪，假設外面時間輪的刻度為8，即外輪的時間槽也是8個，每個時間槽也對應一個鏈表。同時定義時間輪的轉動規則：當裡面的時間輪轉動1圈（8格），外面的時間輪轉動1格。可以看到，採用這種方式，二級時間輪可以管理（8*8=64）種不同Timeout的定時器。

在二級時間輪的結構下，一個定時器Timeout=t的定時器怎麼加入時間輪呢？還是假設二級時間輪都有8個槽，假設時間輪的起始時間為ts，則採用如下演算法將Timeout=t的定時器加入時間輪：

1）計算t-ts/si；

2）如果t-ts/si < 8，則以t-ts/si的低3位作為索引加入內輪；

3）如果t-ts/si>= 8（當然要小於64，否則又溢出），則以t-ts/si的高3位作為索引加入外輪；

二級時間輪檢查時間到的演算法與單機時間輪類似，不同的地方就是當內輪的所有時間槽都時間到後，要把外輪的時間槽鏈表遷移到內輪。

綜上所述：基於排序鏈表的定時器使用唯一的鏈表來管理所有定時器，所以插入定時器的數目越多，效率就會越低，而時間輪則是利用哈希表的思想，將定時器散列到不同的鏈表中，這樣每條鏈表上的數據就會顯著少於原來排序鏈表的數目。插入操作的效率基本不受定時器數目的影響(不需要排序，直接散列到一個鏈表上)。因此插入定時器的時間複雜度和定時器數量n無關，為O(1)。

顯然要提高時間輪的精度，就要使si(slot interval)足夠小，要提高其執行效率則要N要足夠大。如果最裡面一級時間輪的槽採用n1為二進位編碼，外面一級時間輪採用n2位二進位編碼，則總共可以管理的時間範圍為0 ~ 2(n1+n2) – 1。以上面的例子為例，如果二級時間輪都是3位二進位編碼（8個時間槽），那麼總共可以管理的時間範圍為0 ~ 63，即64種Timeout的定時器。

Linux內核採用多級時間輪。定義了5個鏈表數組（每個數組裡面包含多個定時器鏈表）：tv1-tv5都是一個鏈表數組，其中tv1的數組大小為TVR_SIZE（256，8位編碼）， tv2、tv3、tv4、tv5的數組大小為TVN_SIZE（64，6位編碼）。可以看到一共是32位編碼，總共可以管理的時間範圍為0 ~ 232 – 1。

這5個數組就好比是5個齒輪，它們隨著滴答時間的增長而不停地轉動，每次只需處理第一個齒輪的某一個齒節，低一級的齒輪轉動一圈，高一級的齒輪轉動一個齒，同時自動把即將到期的定時器遷移到上一個齒輪中，所以低解析度定時器通常又被叫做時間輪：time wheel。事實上，它的實現是一個很好的空間換時間軟體演算法。參考Linux的實現，具體程式碼如下：

首先定義如下宏:

2. 定時器的添加

要加入一個新的定時器，按以下步驟進行處理：

1）計算定時器到期時間和當前cpu定時器所經歷過的毫秒數的差值，記為idx

2）根據idx的值，選擇該定時器應該被放到tv1–tv5中的哪一個鏈表數組中，可以認為tv1-tv5分別佔據一個32位數的不同比特位，tv1佔據最低的8位，tv2佔據緊接著的6位，然後tv3再佔位，以此類推，最高的6位分配給tv5。最終的選擇規則如下表所示：

確定鏈表數組後，接著要確定把該定時器放入數組中的哪一個鏈表中，如果時間差idx小於256，按規則要放入tv1中，因為tv1包含了256個鏈表，所以可以簡單地使定時器的expires的低8位作為數組的索引下標，把定時器鏈接到tv1中相應的鏈表中即可。如果時間差idx的值在256–18383之間，則需要把定時器放入tv2中，同樣的，使用定時器的expires的8–14位作為數組的索引下標，把定時器鏈接到tv2中相應的鏈表中,。定時器要加入tv3tv4 tv5使用同樣的原理。經過這樣分組後的定時器，在後續的tick事件中，系統可以很方便地定位並取出相應的到期定時器進行處理。程式碼如下：

3. 定時器到期處理

系統中的定時器按到期時間有規律地放置在tv1–tv5各個鏈表數組中，其中tv1中放置著在接下來的256個滴答時間（如毫秒）即將到期的定時器列表。系統滴答值一直在隨著系統的運行而動態地增加，原則上是每個tick事件會加1，定時器加入tv1中使用的下標索引是定時器到期時間expires的低8位，所以假設當前的滴答值是0x34567826，則馬上到期的定時器是在tv1.vec[0x26]中，如果這時候系統加入一個在滴答值0x34567828到期的定時器，他將會加入到tv1.vec[0x28]中，運行兩個tick後，系統滴答的值會變為0x34567828，很顯然，在每次tick事件中，定時器系統只要以當前滴答值的低8位作為索引，取出tv1中相應的鏈表，裡面正好包含了所有在該滴答值到期的定時器列表。

那什麼時候處理tv2–tv5中的定時器？每噹噹前系統滴答值的低8位為0值時，這表明當前系統滴答值的第8-13位有進位發生，這6位正好代表著tv2，這時只要按當前系統滴答值的第8-13位的值作為下標，移出tv2中對應的定時器鏈表，然後用第2節的步驟把它們重新加入到定時器系統中來，因為這些定時器一定會在接下來的256個tick期間到期，所以它們肯定會被加入到tv1數組中，這樣就完成了tv2往tv1遷移的過程。同樣地，噹噹前系統滴答值的第8-13位為0時，這表明當前系統滴答值的第14-19位有進位發生，這6位正好代表著tv3，按當前系統滴答值的第14-19位的值作為下標，移出tv3中對應的定時器鏈表，然後用第2節的步驟把它們從新加入到定時器系統中來，顯然它們會被加入到tv2中，從而完成tv3到tv2的遷移，tv4，tv5的處理可以以此作類推。具體地，定時器時間到需要實現下面二個函數：check和cascade，其中cascade完成時間輪的從外輪向里輪的進位。

基於Linux內核的時間輪實現程式碼，可以在應用程式層面實現一個基於時間輪的管理器。部分程式碼如下所示：