Browse Prior Art Database

Timer Sorting Enhancement

IP.com Disclosure Number: IPCOM000112527D
Original Publication Date: 1994-May-01
Included in the Prior Art Database: 2005-Mar-27
Document File: 4 page(s) / 112K

Publishing Venue

IBM

Related People

Butler, ND: AUTHOR [+2]

Abstract

Described is a method whereby a sorted list is ordered by a modulo type timer counter which can wrap back to zero, in place of several conventional real-time clock counters.

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

Timer Sorting Enhancement

      Described is a method whereby a sorted list is ordered by a
modulo type timer counter which can wrap back to zero, in place of
several conventional real-time clock counters.

      Communication adapters require to operate with a knowledge of
real-time and have potentially many timers running to ensure that
they perform their function synchronised with the outside world.  One
commonly used implementation of this is to use a counter running at a
fixed rate, and to represent each timer as a member of a linked list
containing a stop time and a pointer to the next entry in the list.
On each hardware timer event, the contents of the counter are
incremented and then compared with the timer stop times.  Any timers
which have expired are processed.  To make the performance of this
arrangement acceptable,  timers are sorted into order of expiry, so
that on each timer-tick, only the first item in the list need be
checked.  This invention relates to an efficient way of creating that
sorted list.

      The key which makes the problem difficult to solve is the fact
that the counter against which all the timers are being compared is
of finite length, so that after a while the counter wraps round from
large values back to zero.  The code which inserts a new timer into
the linked, sorted listed must be capable of handling this.

      Conventionally the wrapping of the counter was handled by
maintaining an extra variable as part of each timer entry which
represented the carry bit if this timer was one where the counter
would wrap between the timer being started and expiring.  This
requires much special case logic to be defined when new timers are
started to cope with the multitude of cases about inserting next to
timers with the carry bit set or clear, before and after the counter
has wrapped.

      This disclosed solution involves using the restriction that no
timer may have a duration of longer than half the cycle time of the
counter, to implement an insertion algorithm with the following
advantages:

1.  Compact code

2.  High performance

3.  Simple to prove correctness logically

      These are important because; adapter memory space is limited,
processors usually have limited processing power, and it is important
to know that the function is correct, as the type of errors
encountered may not show up until the product is tested and out in
the field.

      The key fact, based on the assumptions above, is that the most
significant bit of the counter can only change once during the
"lifetime" of all the timers in the list at any instant.  (No timer
is longer than half the duration of the counter, and all timers in
the list are currently active).  Also, integers can be treated either
as signed or unsigned numbers.  If they are treated as signed (the
most significant bit is a sign bit), there is a discontinuity in
counting between 0x7FFF and 0x8000 when the counter moves from as
posit...