NO IMAGE

l 時間輪的概念

   關於定時器有很多種,有基於升序的定時器時間連結串列,但是這種連結串列存在效率的不足,就是當插入定時器的時候時間複雜度是O(n).今天,我們來認識一下高效能定時器時間輪。

   如上圖所示,就是一個時間輪的基本輪廓。一個輪子上有很多槽slot,每一個槽指向一個定時器連結串列,這個連結串列是無序的。時間輪每轉動一步就會指向下一個槽,其實也可以理解為一個滴答時間成為時間輪的槽間隔si (slot interval)。它實際上就是心跳時間。如果該時間輪有n個槽,因此它運轉一週的時間是n*si.

   如果現在指標指向槽cs,我們此時要新增一個定時器時間為ti的定時器,則該定時器將被插入槽ts對應的連結串列

                               Ts = (cs ti/si)%N

   基於排序連結串列的定時器使用唯一的連結串列來管理所有定時器,所以插入定時器的數目越多,效率就會越低,而時間輪則是利用雜湊表的思想,將定時器雜湊到不同的連結串列中,這樣每條連結串列上的資料就會顯著少於原來排序連結串列的數目。插入操作的效率基本不受定時器數目的影響(不需要排序,直接雜湊到一個連結串列上)。

顯然要提高時間輪的精度,就要使si(slot interval)足夠小,要提高其執行效率則要N要足夠大。

轉自:http://wenku.baidu.com/link?url=q6N4azyNaZMxGyr6ScqVtpb8EWqHudQCjHshZru6d-7QLI41uiqYQYWXjWrE5-Y8CIaZmWoQQd3CdNZyEk-zhF3tiSYfH2T7n3_mmuD8bei

進階 分層時間輪模型: http://www.tuicool.com/articles/yeeua2n

時間輪實現和規範介面:http://blog.csdn.net/mindfloating/article/details/8033340

遊戲後臺之高效定時器-時間輪http://blog.csdn.net/soft2967/article/details/9274691