海量定時器的調度方法
2023-06-04 20:36:01
專利名稱：海量定時器的調度方法
技術領域：
本發明涉及定時器領域，具體來說是涉及一種海量定時器的調度方法。
一般來講，定時器調度方法包含如下基本步驟用於定時器啟動的插入步驟；用於定時器中止或超時的刪除步驟；用於作業系統監視激活的定時器的掃描步驟。其中掃描步驟是由一個周期為T的作業系統提供的定時器進行驅動，在該定時器的驅動下，在每個掃描周期對等待超時的定時器進行一次檢查，使到時的預先登記時長的定時器通過刪除步驟進入掛起狀態。定時器調度方法雖然只需使用一個或少數幾個系統級的定時器，但是卻可以對外提供多個定時器。
隨著通訊系統的容量越來越大，速度越來越快，協議越來越複雜，客戶對穩定性要求越來越高，對定時器調度的要求也越來越高。如在大話務量負載仿真測試工具開發過程中，該工具需要模擬巨大數量的用戶極其頻繁地發起長短不一的呼叫，呼叫中許多特殊狀態的定時器精度要求非常高，經常需要精確到10ms，而有些狀態(例如通話狀態等)的時長要求非常長，可能要達到數小時或更長。由於該測試工具是通用測試工具，狀態的屬性可以由用戶自由定製，每個狀態的等待時長的可能範圍非常大，幾十毫秒到幾個小時不等，需要對不同長度範圍和精度的定時器做不同的處理。
而現有的定時器調度方法主要有下面幾種1、輪詢定時器調度方法，是一種常用於少量定時器調度的輪詢方法，在每個掃描周期把所有的定時器檢查一遍，看看是否有定時器超時，並且把每個定時器的剩餘時間減一。很明顯，如果當精度要求很高，掃描周期非常短時，這種方法便不能在一個掃描周期內檢查太多的定時器。
2、差分定時器調度方法。在該方法中，定時器按照到時時刻排列成一個長鏈，每個定時器記錄自身到時時刻與上一個定時器到時時刻的時間差(即差分方案)，這種方法幾乎沒有掃描開銷，在判斷是否有定時器超時，只需判斷鍊表頭的第一個定時器即可。但是，如果要想插入一個新定時器，就必須遍歷鍊表，這樣，當處於激活狀態的定時器數量非常大時，插入過程就會很慢。
3、分類定時器調度方法，這種方法採用定時器時長分類的方式，利用了差分定時器的優點，並且針對系統的特殊性克服差分定時器插入效率低的缺點。例如，在系統所用到的定時器長度只有少數幾種的情況下，可以針對每個長度的定時器構造一個鍊表，由於每個鍊表只有一種定時時延，新登記的定時器插入該定時器所屬定時器類的鍊表尾部，每個掃描周期掃描所有定時器鍊表的頭即可，由於定時器時長的種類很少，這種定時器非常高效。但是這種定時器只能應付定時器時長的可能取值有限的情況，對於超時時長可能取值種類過多或者可變的系統是不適用的。
另外，在現有技術中還有一些系統按照定時器的精度對定時器進行分類，越高精度的定時器可定時的最大時長越短。例如提供毫秒、秒鐘、分鐘、小時的數種定時器，用戶根據精度和長度的要求選取相應的類別。這種定時器方案也可以做得非常高效，但卻存在使用相對比較麻煩，需要根據長度和精度確定類別的缺點。
以上將定時器分類的方法在許多通訊協議軟體系統中得到應用，但是這些方法使用起來需要指定類別而不能任意直接指定時長，並且修改或者增刪類別的維護工作比較煩瑣並且容易出錯。
4、時間緩衝區方法。該方法將到時時刻做成一個固定尺寸的環型區域，一個代表當前時刻的指針指向當前時刻對應的單元，該指針每過一個掃描周期便前進一個單元，並且將該單元裡面的定時器啟動。登記定時器的時候，直接登記到該定時器到時時刻所對應的位置上去。這種方案也是非常高效的通用方案，但缺點是定時的最大掃描周期數受環型區域尺寸的限制。如果要定時非常長的時間間隔，即使沒有一個處於激活狀態的定時器，也需要巨大的內存。
顯然，上述現有的定時器調度方法都存在各自的缺點，而且由於皆動態地分配和釋放內存，從而造成了內存碎片化。另外，雖然上述方法可以對不同長度範圍和精度的定時器做不同的處理，但是會增大調度程序總的複雜性，增大應用程式使用定時任務的難度，降低系統的可靠性。
為實現上述目的，本發明的海量定時器的調度方法包含如下具體步驟用於定時器啟動的插入步驟；用於定時器中止的刪除步驟；用於作業系統監視激活的定時器超時的掃描步驟。其中所述的掃描步驟包含下列步驟a、在每個掃描周期判斷定時器隊列中是否有激活的定時器，如果否，退出本步驟，如果是，繼續；b、讀取位於定時器隊列頭部的定時器；c、判斷該定時器是否到時，如果否，退出本步驟，如果是，繼續；d、將該定時器對象從定時器隊列中清除並同時調整定時器隊列順序，然後回到步驟a。
所述的插入步驟包含先將到時時刻保存到定時器對象中，然後將該定時器對象插入容納定時器對象的定時器隊列中並同時調整隊列順序。
所述的刪除步驟包含先判斷該定時器是否被激活，如果未被激活則退出本步驟，否則清空該定時器，然後將該定時器對象從定時器隊列中清除並同時調整定時器隊列順序。
另外，所述的定時器隊列是指以堆數據結構構成的定時器隊列或者是以前序完全二叉樹結構構成的定時器隊列。
本發明通過使用堆數據結構或前序完全二叉樹結構對定時器隊列進行組織，利用其中堆或者樹的優良特性達到對海量定時器的高效調度，能夠有效地降低系統的複雜度，提高系統的穩定性、可移植性和可維護性。具體來說具有下述優點1、能夠高效掃描大量處於激活狀態的定時器，執行超時的定時器任務；2、能夠高效插入、刪除定時器；3、可提供的定時時延範圍足夠大，應用程式不必對特殊長度的時延進行特殊處理；4、定時的精度足夠高，滿足精確定時的需要。
下面結合附圖
和具體實施例來詳細描述本發明。
由於堆數據結構具備一些優良的特性，這種數據結構可以在每次插入和刪除元素操作的時候迅速地進行調整，保證操作之後數據仍然被組織為一個堆。只要數據被組織成為一個堆，就可以按照先後順序將元素提取出來，並且提取操作也是非常迅速的。上述各個基本步驟的具體過程為如圖2所示，所述的插入步驟包含先將到時時刻保存到定時器對象中，然後將該定時器對象插入容納定時器對象的堆數據結構定時器隊列中並同時調整堆數據結構。
如圖3所示，所述的刪除步驟包含先判斷該定時器是否被激活，如果未被激活則退出本步驟，否則清空該定時器，然後將該定時器對象從堆數據結構定時器隊列中清除並同時調整堆數據結構。
如圖4所示，所述的掃描步驟包含下列步驟1、在每個掃描周期判斷堆數據結構定時器隊列中是否有激活的定時器，如果否，退出本步驟，如果是，繼續；2、讀取位於堆數據結構定時器隊列頭部的定時器；3、比較該定時器的定時時長和系統的計時時長，如果二者不相等，退出本步驟，如果二者相等，繼續；4、將該定時器對象從堆數據結構定時器隊列中清除並同時調整堆數據結構，然後回到步驟1。
考慮到如果系統長時間運行，系統計時記數器可能會溢出，為了使系統在溢出的前後仍然能夠正確工作，本實施例使用32位無符號整數記錄時長和系統計時記數器，這時計時時長最大合法長度可以達到10ms×(232-1)約497天，且所述的步驟c判斷定時器是否到時的比較中不使用大於或小於，而使用相等或不相等，只有在二者相等的時候才說明該定時器在隊列中超時，其他情況，無論是大於還是小於，都說明該定時器沒有在該隊列中到時。這樣就可以巧妙地避開系統計時記數器溢出後系統混亂的問題，無論系統計時記數器溢出多少次，系統都可以毫無問題地正常工作。
假設每一次掃描步驟的時間開銷是O(1)，通過本實施例所述的海量堆定時器的調度方法，每次插入步驟的時間開銷是O(log(N))，每次刪除步驟的時間開銷是O(log(N))。其中N為處於激活狀態的定時器數量。插入和刪除定時器的時間開銷都是因調整堆數據結構造成的。另外，由於實際系統的內存限制，log(N)是存在上限的，例如32位系統中，0＜＝log(N))＜32。
表1是本實施例和現有的幾種調度方法的性能比較，其中系統整數位數B定時器插入速度F(次/tick)定時器平均生存時長T(tick)系統激活狀態的定時器個數N定時器內存佔用M可直接定時時長數L(分類定時器的)定時器類別數C可以看出，現有的幾種調度方法在某些方面比本實施例所述的方法更快，但是在比較極端的情況下都存在嚴重的缺陷，導致現有的幾種調度方法在極端情況下很難使用。例如在PII300以上的機器上，每秒掃描100次，每秒插入1000個定時器，系統中有近1,000,000個定時器同時處於激活狀態，這兩項操作所佔用的CPU時間不到1/1000。也就是說，雖然這兩項比其他類型定時器的最佳值要低，但是根本不足以構成性能瓶頸。在基本內存佔用方面，本實施例在沒有激活的定時器的時候基本沒有開銷，所以完全可以應用在單板的嵌入式環境中。
表1
表2是在極端情況下本實施例和現有的幾種調度方法的性能具體數據近似值的比較，系統整數位數為32，定時器插入速度為10次/掃描周期，定時器平均生存時長為100,000掃描周期，緩衝定時器方法的可直接定時時長數為1,000,000掃描周期，分分類定時器方法中定時器類別數為100個類別，這樣，分類調度方案就只能對100種時長直接定時，遠遠少於其他類型定時器的可直接定時的時長數。
表2
權利要求
1.一種海量定時器的調度方法，其特徵在於該方法包含如下步驟用於定時器啟動的插入步驟；用於定時器中止的刪除步驟；用於作業系統監視激活的定時器超時的掃描步驟；其中，所述的掃描步驟包含下列步驟a、在每個掃描周期判斷定時器隊列中是否有激活的定時器，如果否，退出本步驟，如果是，繼續；b、讀取位於定時器隊列頭部的定時器；c、判斷該定時器是否到時，如果否，退出本步驟，如果是，繼續；d、將該定時器對象從定時器隊列中清除並同時調整定時器隊列順序，然後回到步驟a。
2.如權利要求1所述的一種海量定時器的調度方法，其特徵在於，所述插入步驟包含先將到時時刻保存到定時器對象中；然後將該定時器對象插入容納定時器對象的定時器隊列中並同時調整隊列順序。
3.如權利要求1所述的一種海量定時器的調度方法，其特徵在於，所述刪除步驟包含先判斷該定時器是否被激活，如果未被激活則退出本步驟，否則清空該定時器；然後將該定時器對象從定時器隊列中清除並同時調整定時器隊列順序。
4.如權利要求1、2或3所述的一種海量定時器的調度方法，其特徵在於，所述的定時器隊列是指以堆數據結構構成的定時器隊列或者是以前序完全二叉樹結構構成的定時器隊列。
5.如權利要求1、2或3所述的一種海量定時器的調度方法，其特徵在於，所述的定時器是用無符號整數表示的。
6.如權利要求1所述的一種海量定時器的調度方法，其特徵在於，所述步驟a中的計時是用無符號整數來計時的。
7.如權利要求1所述的一種海量定時器的調度方法，其特徵在於，所述步驟c實現過程為比較該定時器的定時時長和步驟a中的計時時長，如果二者不相等，退出本步驟，如果二者相等，繼續。
全文摘要
本發明提供了一種海量定時器的調度方法，該方法包含用於定時器啟動的插入步驟、用於定時器中止的刪除步驟、用於作業系統監視激活的定時器超時的掃描步驟；其中所述的掃描步驟包含下列步驟a.在每個周期判斷定時器隊列中是否有激活的定時器，如果否，退出本步驟，如果是，繼續；b.讀取位於定時器隊列頭部的定時器；c.判斷該定時器是否到時，如果否，退出本步驟，如果是，繼續；d.將該定時器對象從定時器隊列中清除並同時調整定時器隊列順序，然後回到步驟a。本發明通過使用堆數據結構或前序完全二叉樹結構對定時器隊列進行組織，利用其優良特性對海量定時器的高效調度，能夠有效地降低系統的複雜度，提高系統的穩定性、可移植性和可維護性。
文檔編號H04B17/00GK1474241SQ0212875
公開日2004年2月11日 申請日期2002年8月7日 優先權日2002年8月7日
發明者孫伊, 孫 伊 申請人:華為技術有限公司