System and method for intelligent timer services
A method is provided for efficiently scheduling timer events within an operating system by allocating a plurality of timers, each of which has an expiry time, to a set of available timer slots. The method defines a timer spread value that denotes the allowed variance of the expiry times of each of the timers, calculates a set of available timer slots for each of the timers based on the timer spread value, and adjusts the expiry times of the timers so as to insert and evenly spread the timers across the set of available timer slots. In one implementation, the set of available timer slots is located in a timer wheel existing within the operating system, and the timer wheel uses a plurality of timer vectors arranged into successively increasing levels, beginning with level zero.
1. A method of efficiently scheduling timer events within an operating system by allocating a plurality of timers to a set of available timer slots, each of said timers having an expiry time, comprising
wherein said set of available timer slots is located in a timer wheel existing within said operating system, said timer wheel using a plurality of timer vectors arranged into successively increasing levels, beginning with level zero;
defining a timer spread value which denotes the allowed variance of the expiry times of each of said timers,
calculating a set of available timer slots for each of said timers based on said timer spread value, said calculating comprising
applying a maximum positive spread and a maximum negative spread, and
wherein the maximum positive spread and the maximum negative spread are equal to each other; and
adjusting said expiry times of said timers so as to insert and spread said timers across said set of available timer slots.
2. The method of claim 1 wherein each timer vector contains a plurality of timer slots defined by a slot size based on the level of said timer vector, said timer slots being evenly spaced by a number of timer ticks corresponding with said slot size.
3. The method of claim 2 wherein the slot size for the lowest level timer vector is set to one, and the slot size for each successive higher level timer vector is based on the slot size of the level of the preceding timer vector.
4. The method of claim 1 , wherein the plurality of timers includes at least one periodic timer.
5. The method of claim 4 further comprising restarting said periodic timer at the unadjusted expiry time.
6. The method of claim 1 wherein adjusting said expiry times further comprises selecting from said set of available timer slots a slot containing the fewest number of existing timers.
7. The method of claim 1 further comprising upper bounding said set of available slots, or lower bounding said set of available slots, or both.
8. The method of claim 1 wherein adjusting the expiry times further comprises selecting a timer slot randomly from said set of available slots.
9. A method of efficiently scheduling timer events within an operating system by allocating a plurality of timers to a set of available timer slots,
wherein said set of available timer slots is located in a timer wheel existing within said operating system, said timer wheel using a plurality of timer vectors arranged into successively increasing levels, beginning with level zero, and
each of said plurality timers having an expiry time;
said method comprising
defining a timer spread value which denotes the allowed variance of the expiry times of each of said timers;
calculating a set of available timer slots for each of said timers based on said timer spread value, said calculating comprising
applying a maximum positive spread and a maximum negative spread, and
wherein the sum of the maximum positive spread and the maximum negative spread is equal to the defined timer spread value; and
adjusting said expiry times of said timers so as to insert and spread said timers across said set of available timer slots.
10. The method of claim 9 wherein each timer vector contains a plurality of timer slots defined by a slot size based on the level of said timer vector, said timer slots being evenly spaced by a number of timer ticks corresponding with said slot size.
11. The method of claim 10 wherein the slot size for the lowest level timer vector is set to one, and the slot size for each successive higher level timer vector is based on the slot size of the level of the preceding timer vector.
12. The method of claim 9 , wherein the plurality of timers includes at least one periodic timer.
13. The method of claim 9 wherein adjusting said expiry times further comprises selecting from said set of available timer slots a slot containing the fewest number of existing timers.
14. The method of claim 9 further comprising selecting a timer slot randomly from said set of available slots.
15. A method of efficiently scheduling timer events within an operating system by allocating a plurality of timers to a set of available timer slots,
wherein said set of available timer slots is located in a timer wheel existing within said operating system, said timer wheel using a plurality of timer vectors arranged into successively increasing levels, beginning with level zero,
each of said plurality of timers having a corresponding original unadjusted expiry time, and
wherein the plurality of timers includes at least one periodic timer;
said method comprising
defining a timer spread value which denotes the allowed variance of the expiry times of each of said timers;
calculating a set of available timer slots for each of said timers based on said timer spread value, comprising
applying a maximum positive spread and a maximum negative spread, where the maximum negative spread is zero, and
upper bounding said set of available slots; and
adjusting said original unadjusted expiry times of said timers so as to insert and spread said timers across said set of available timer slots, and
wherein said at least one periodic timer must not elapse earlier than the original unadjusted expiry time corresponding to said at least one periodic timer.
16. The method of claim 15 wherein each timer vector contains a plurality of timer slots defined by a slot size based on the level of said timer vector, said timer slots being evenly spaced by a number of timer ticks corresponding with said slot size.
17. The method of claim 16 wherein the slot size for the lowest level timer vector is set to one, and the slot size for each successive higher level timer vector is based on the slot size of the level of the preceding timer vector.
18. The method of claim 15 wherein adjusting said expiry times further comprises selecting from said set of available timer slots a slot containing the fewest number of existing timers.
19. The method of claim 15 further comprising lower bounding said set of available slots.
20. The method of claim 15 further comprising selecting a timer slot randomly from said set of available slots.