Browse Prior Art Database

Algorithm for Implementing Efficient Software Timers

IP.com Disclosure Number: IPCOM000117433D
Original Publication Date: 1996-Feb-01
Included in the Prior Art Database: 2005-Mar-31
Document File: 4 page(s) / 215K

Publishing Venue

IBM

Related People

Vrabel, RA: AUTHOR

Abstract

Proposed in an efficient method processing a large number of asynchronous requests in a software program for notification of timer interval expiration.

This text was extracted from an ASCII text file.
This is the abbreviated version, containing approximately 45% of the total text.

Algorithm for Implementing Efficient Software Timers

      Proposed in an efficient method processing a large number of
asynchronous requests in a software program for notification of timer
interval expiration.

      In a communications controller, gateway, or router which
supports the attachment of a large number of devices over different
line types, many CCU cycles can be used to run various timers
required for the protocols supported by the attached devices.  For
example, a single IEEE 802.2 tpe 2 connection requires running an
inactivity timer, an acknowledgement timer, and a reply timer.  A
communications controller can support thousands of these connections
simultaneously which can heavily utilize the CCU and limit the number
of devices that the controller can support.

Timers for software applications are normally run in one of two ways:
  1.  The amount of time-until-timer-expiration is passed to a
hardware
       component which signals the software with an interrupt when
the
       timer has expired; or
  2.  The software builds a chain of control blocks indicating the
       specific timers and the amount of time-until-timer-expiration
       that needs to be run.  The hardware then interrupts the
software
       at some fixed interval and the software scans the entire
chain,
       subtracting off of the current timer value the amount in the
       fixed interval that represents how often the hardware
interrupt
       occurs, looking for timers that have expired.

      The first method above requires an interface with hardware that
may not exist all machines.  The second method is a software timer
implementation that is inefficient and is the subject of this
disclosure.

      Timers can be efficiently run in software by creating a
table-based timer algorithm.  This method requires that the software
program receive an external signal on a periodic interval that will
be used to run the timers.  The main features of the algorithm is
that it only requires one external signal (mentioned above) to run
all required timers regardless of the number of devices supported and
it limits the amount of processing required for timers that are not
expiring.

The following describes the software timer algorithm:
  o  A table of fixed length must be created that will be used to
      point to control blocks that represent timers.  Each entry in
the
      table represents a timer interval that is equal to the smallest
      granularity that is required of the timers that are running.
The
      number of entries is arbitrary but will be used to determine
      where control block are placed in the table.  The table size,
      however, will affect the efficiency of the algorithm.
  o  Each entry in the table is assigned a number, starting at zero
      and increased sequentially by one, which will be used as an
index
      into the...