System and method for intelligent timer services

Patent metadata

Field	Value
Publication number	US-9367352-B2
Application number	US-201514691726-A
Country	US
Kind code	B2
Filing date	Apr 21, 2015
Priority date	Sep 7, 2012
Publication date	Jun 14, 2016
Grant date	Jun 14, 2016

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 system for 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, 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 the allowed variance of the expiry times of each of said timers;
calculate a set of available timer slots for each of said timers based on said timer spread value; and
adjust said expiry times of said timers so as to insert and spread said timers across said set of available timer slots, by analyzing the distribution of timer expirations in the set of available slots and selecting the slot with the least timer expirations, and adjusting the expiry time so that the timer expires during the selected slot;
wherein said system performs said spreading to reduce at least one of peaks of processing activity and overhead due to processing activity.

2. A system for efficiently scheduling timer events within a timer wheel by allocating a plurality of timers to a set of available timer slots, each of said 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 the allowed variance of the expiry times of each of said timers;
calculate a set of available timer slots for each of said timers based on said timer spread value; and
adjust said expiry times of said timers so as to insert and spread said timers across said set of available timer slots, by analyzing the distribution of timer expirations in the set of available slots and selecting the slot with the least timer expirations, and adjusting the expiry time so that the timer expires during the selected slot;
wherein said system performs said spreading to reduce at least one of peaks of processing activity and overhead due to processing activity.

3. A method for 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, the method comprising:
defining a timer spread value which is a measure of 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; and
adjusting said expiry times of said timers so as to insert and spread said timers across said set of available timer slots, by analyzing the distribution of timer expirations in the set of available slots and selecting the slot with the least timer expirations, and adjusting the expiry time so that the timer expires during the selected slot;
wherein said adjusting said expiry times are for to reducing at least one of peaks of processing activity and overhead due to processing activity.

4. A method for efficiently scheduling timer events within a timer wheel by allocating a plurality of timers to a set of available timer slots, each of said timers having an expiry time, the method comprising:
defining a timer spread value which is a measure of 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; and
adjusting said expiry times of said timers so as to insert and spread said timers across said set of available timer slots, by analyzing the distribution of timer expirations in the set of available slots and selecting the slot with the least timer expirations, and adjusting the expiry time so that the timer expires during the selected slot;
wherein said adjusting said expiry times are for to reducing at least one of peaks of processing activity and overhead due to processing activity.

Assignees

• Accedian Networks Inc

Inventors

• Dupont Andre
• Decorte Thierry

Classifications

• G06F9/4825

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

• G06F9/4831

  with variable priority · CPC title

• G06F1/14 Primary

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

• G06F9/4881 Primary

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

• G06F9/4837

  time dependent · CPC title