时间轮定时器的原理和实现.ppt

Hashed and Hierarchical Timing Wheels A paper by George Varghese and Tony Lauck.MotivationnTimers are important for nFailure recovery,rate based flow control,scheduling algorithms,controlling packet lifetime in networksnTimer maintenance high if nProcessor interrupted every clock tick nFine granularity timers are usedn#outstanding timers is highnEfficient timer algorithms are required to reduce the overall interrupt overhead.Model&Performance MeasurenRoutines in the modelnClient Invoked:nSTART_TIMER(Interval,Request_ID,Expiry_Action)nSTOP_TIMER(Request_ID)nTimer tick invoked:nPER_TICK_BOOKKEEPINGnEXPIRY_PROCESSINGnPerformance MeasurenSpace:Memory used by the data structuresnLatency:Time required to begin and end any of the routines mentioned above.Currently Used Timer SchemesabcdeCan maintain absolute expiry time or the timer intervalSTART_TIMER=O(1)STOP_TIMER=O(1)PER_TICK_BOOKKEEPING=O(n)abcdefmaintain absolute expiry timeSTART_TIMER=O(n)STOP_TIMER=O(1)PER_TICK_BOOKKEEPING=O(1).Tree based timersabcdabcdmaintain absolute expiry time START_TIMER=O(log(n)STOP_TIMER=O(1)PER_TICK_BOOKKEEPING=O(1)Can degenerate to a linear list in case of equalInterval timersSTART_TIMER=O(n)STOP_TIMER=O(1)PER_TICK_BOOKKEEPING=O(1).Simple Timing WheelnKeep a large timing wheelnA curser in the timing wheel moves one location every time unit(just like a seconds hand in the clock)nIf the timer interval is within a rotation from the current curser position then put the timer in the corresponding locationnRequires exponential amount of memorySTART_TIMER=O(1)STOP_TIMER=O(1)PER_TICK_BOOKKEEPING=O(1)12345670.Hashed Timing Wheel1234567024122112#of rounds remainingnSay wheel has 8 ticksnTimer value=17nMake 2 rounds of wheel+1 more ticknSchedule the timer in the bucket“1”nKeep the#rounds with the timernAt the expiry processing if the#rounds 0 then reinsert the timer.Hashed Timing WheelnSorted Lists in each bucketnThe list in each bucket can be insertion sortednHence START_TIMER takes O(n)time in the worst casenIf n WheelSize then average O(1)nUnsorted list in each bucketnList can be kept unsorted to avoid worst case O(n)latency for START_TIMERnHowever worst case PER_TICK_BOOKKEEPING=O(n)nAgain,if n WheelSize then average O(1).Hierarchical Timing Wheel123456703575211Hours wheel1234567012345670Minutes wheelSeconds wheel1 33 53 715.Hierarchical Timing WheelsnSTART_TIMER=O(m)where m is the number of wheelsnThe bucket value on each wheel needs to be calculatednSTOP_TIMER=O(1)nPER_TICK_BOOKKEEPING=O(1)on avg.ComparisonSTART_TIMERSTOP_TIMERPER_TICKO(1)Straight FwdO(1)O(n)SequentialListO(n)O(1)O(1)Tree BasedO(log(n)O(1)O(1)SimpleWheelO(1)O(1)O(1)High memory requirementHashedWheel(sorted)Hashed Wheel(unsorted)Hierarchical WheelsO(n)worst caseO(1)avgO(1)O(m)O(1)O(1)O(1)O(1)O(n)worst caseO(1)avgO(1).