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

该【时间轮定时器的原理和实现 】是由【huanmouyo】上传分享，文档一共【11】页，该文档可以免费在线阅读，需要了解更多关于【时间轮定时器的原理和实现 】的内容，可以使用淘豆网的站内搜索功能，选择自己适合的文档，以下文字是截取该文章内的部分文字，如需要获得完整电子版，请下载此文档到您的设备，方便您编辑和打印。Hashed and Hierarchical Timing Wheels
单击此处添加副标题
A paper by
George Varghese and Tony Lauck
CLICK HERE TO ADD A TITLE
Motivation
Timers are important for
Failure recovery, rate based flow control, scheduling algorithms, controlling packet lifetime in networks
Timer maintenance high if
Processor interrupted every clock tick
Fine granularity timers are used
# outstanding timers is high
Efficient timer algorithms are required to reduce the overall interrupt overhead
Model & Performance Measure
Routines in the model
Client Invoked :
START_TIMER(Interval, Request_ID, Expiry_Action)
STOP_TIMER(Request_ID)
Timer tick invoked :
PER_TICK_BOOKKEEPING
EXPIRY_PROCESSING
Performance Measure
Space : Memory used by the data structures
Latency : Time required to begin and end any of the routines mentioned above
Currently Used Timer Schemes
a
b
c
d
e
Can maintain absolute expiry
time or the timer interval
START_TIMER = O(1)
STOP_TIMER = O(1)
PER_TICK_BOOKKEEPING = O(n)
a
b
c
d
e
f
maintain absolute expiry time
START_TIMER = O(n)
STOP_TIMER = O(1)
PER_TICK_BOOKKEEPING = O(1)
Tree based timers
a
b
c
d
a
b
c
d
maintain 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 equal
Interval timers
START_TIMER = O(n)
STOP_TIMER = O(1)
PER_TICK_BOOKKEEPING = O(1)
Simple Timing Wheel
Keep a large timing wheel
A curser in the timing wheel moves one location every time unit (just like a seconds hand in the clock)
If the timer interval is within a rotation from the current curser position then put the timer in the corresponding location
Requires exponential amount of memory
START_TIMER = O(1)
STOP_TIMER = O(1)
PER_TICK_BOOKKEEPING = O(1)
1
2
3
4
5
6
7
0
Hashed Timing Wheel
1
2
3
4
5
6
7
0
2
4
1
2
2
1
1
2
# of rounds remaining
Say wheel has 8 ticks
Timer value = 17
Make 2 rounds of wheel + 1 more tick
Schedule the timer in the bucket “1”
Keep the # rounds with the timer
At the expiry processing if the # rounds > 0 then reinsert the timer
Hashed Timing Wheel
Sorted Lists in each bucket
The list in each bucket can be insertion sorted
Hence START_TIMER takes O(n) time in the worst case
If n < WheelSize then average O(1)
Unsorted list in each bucket
List can be kept unsorted to avoid worst case O(n) latency for START_TIMER
However worst case PER_TICK_BOOKKEEPING = O(n)
Again, if n < WheelSize then average O(1)
Hierarchical Timing Wheel
1
2
3
4
5
6
7
0
3
5
7
5
2
1
1
Hours wheel
1
2
3
4
5
6
7
0
1
2
3
4
5
6
7
0
Minutes wheel
Seconds wheel
1
3
3
5
3
7
1
5
Hierarchical Timing Wheels
START_TIMER = O(m) where m is the number of wheels
The bucket value on each wheel needs to be calculated
STOP_TIMER = O(1)
PER_TICK_BOOKKEEPING = O(1) on avg.