System and method for intelligent timer services

Patent metadata

Field	Value
Publication number	US-9910703-B2
Application number	US-201615156480-A
Country	US
Kind code	B2
Filing date	May 17, 2016
Priority date	Sep 7, 2012
Publication date	Mar 6, 2018
Grant date	Mar 6, 2018

Abstract

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.

First claim

The invention claimed is:

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 located in a timer wheel existing within the operating system, the timer wheel using a plurality of timer vectors arranged into successively increasing levels, beginning with level zero, each of the plurality of timers having an expiry time, the method comprising:
defining a timer spread value for each of the plurality of timers which is a measure of an allowed variance of the expiry times of each of the plurality of timers;
specifying a timer interval for each of the plurality of timers;
calculating a set of available timer slots for each of the plurality of timers based on the timer spread value;
comparing the timer interval for each of the plurality of timers to each slot in the plurality of timer vectors; and
adjusting the expiry times of each of the plurality of timers so as to insert and spread the plurality of timers across the set of available timer slots.

2. The method of claim 1 , wherein at least one of the plurality of timers is designated as a non-periodic timer.

3. The method of claim 1 , wherein at least one of the plurality of timers is designated as a periodic timer.

4. The method of claim 1 , wherein the timer interval is specified in microseconds.

5. The method of claim 1 , wherein the timer interval is specified in nanoseconds.

6. The method of claim 1 , further comprising converting the timer interval into a number of operating system (OS) ticks as
t _tick=timer_tick/ t

wherein t_tick is the timer interval in number of OS ticks, timer_tick is the timer interval, and t is the OS time period.

7. The method of claim 1 , wherein calculating the set of available timer slots comprises applying a maximum positive spread and a maximum negative spread.

8. The system of claim 1 , wherein at least one of the plurality of timers is designated as a non-periodic timer.

9. The system of claim 1 , wherein at least one of the plurality of timers is designated as a periodic timer.

10. The system of claim 1 , wherein the timer interval is specified in microseconds.

11. The system of claim 1 , wherein the timer interval is specified in nanoseconds.

12. The system of claim 1 , further comprising converting the timer interval into a number of operating system (OS) ticks as
t _tick=timer_tick/ t

wherein t_tick is the timer interval in number of OS ticks, timer_tick is the timer interval, and t is the OS time period.

13. The system of claim 1 , wherein the calculating comprises applying a maximum positive spread and a maximum negative spread.

14. A system for efficiently scheduling timer events within an operating system by allocating a plurality of timers to a set of available timer slots located in a timer wheel existing within the operating system, the timer wheel using a plurality of timer vectors arranged into successively increasing levels, beginning with level zero, each of the timers having an expiry time, the system comprising:
one or more processors; and
one or more modules stored on a memory and executable by the one or more processors, the one or more modules configured to:
define a timer spread value which is a measure of an allowed variance of the expiry times of each of the plurality of timers;
specify a timer interval for each of the plurality of timers;
calculate a set of available timer slots for each of the timers based on the timer spread value;
compare the timer interval for each of the plurality of timers to each slot in the plurality of timer vectors; and
adjust the expiry times of the timers so as to insert and spread the timers across the set of available timer slots.

Assignees

• Accedian Networks Inc

Inventors

• Dupont Andre
• Decorte Thierry

Classifications

• G06F9/4825

  Interrupt from clock, e.g. time of day · CPC title

• G06F1/14 Primary

  Time supervision arrangements, e.g. real time clock · CPC title

• G06F9/4837

  time dependent · CPC title

• G06F9/4881 Primary

  Scheduling strategies for dispatcher, e.g. round robin, multi-level priority queues · CPC title

• G06F9/4831

  with variable priority · CPC title