Electrical computers and digital processing systems: support – Clock – pulse – or timing signal generation or analysis – Counting – scheduling – or event timing
Reexamination Certificate
2001-04-03
2004-07-13
Butler, Dennis M. (Department: 2115)
Electrical computers and digital processing systems: support
Clock, pulse, or timing signal generation or analysis
Counting, scheduling, or event timing
C713S600000
Reexamination Certificate
active
06763476
ABSTRACT:
FIELD OF THE INVENTION
The present invention generally relates to scheduling events in computers and system networks and in particular to dynamically increasing the capacity of a circular timer queue.
BACKGROUND OF THE INVENTION
In many computer networks, computerized telephone and billing systems, etc., there are intercommunication mechanisms in computers and other types of systems which handle multiple events, where such mechanisms are often presented with the problem of scheduling a certain event to happen at a particular time which is to be arranged for set-up in the system.
Many memory systems for example, have queues of items to be accessed or handled in a particular sequence. Many programs have lists of instructions which are sequenced also to be handled in a particular arrangement of time events. Sometimes, thousands of different items are placed in queues in order to be available for access in a particular sequence or order.
For example, in the compilation of a telephone directory or a directory of certain businesses in a certain location or a directory of the names of people associated with a certain group, these are all examples of data words or information which are placed in queues and which may be accessed, acquired and used or deleted at certain moments of time.
Additionally, once such a list is compiled, it is very often necessary to place insertions into the queue list, for example, new person's names may be added to a group organization list, or new telephone numbers and addresses and names may be put in a telephone book. Similarly, and often in Kerberos Security Systems, a list of authenticated users and appropriate passwords and tickets may be involved in a list of such useful items.
In each and any of the cases, when it is necessary to add to a particular list, it is sometimes a rather magnitudinous task to achieve this type of event when there is required the normal situation where the system must check through each of the items in the list step-by-step until it reaches its selected position where the insertion must be made, after which a stop operation must occur, and after which the new item is inserted into the system which performs the completion of this operation. However, in so doing, sometimes thousands and thousands of entries must be sequenced through to find the exact point where the new insertion is to be made. This is very time-consuming and exceedingly complex in terms of programming the request to be inserted at a particular point in a large sequence of other requests in a list.
The normal method for this to happen is that there be a sequential scan of each item, item-by-item, step-by-step, until there is reached or achieved the proper insertion point. The performance cost of queue searching for inserting events which need to be handled at some fixed time in the future, is quite an expensive proposition. However, the queues which must be scanned sequentially are used very often for these purposes because they are simple to implement and maintain, and can reflect the linear nature of the problem to be solved in finding the correct placement point or item into which the new event is to be inserted. Additionally, such a technique is inherently slow, and thus also becomes increasingly costly, as more entries are added to the queue, and considerable time latency factors are involved in the mechanism which must traverse through the queue in order to find the right new entrance point.
Likewise, the same sort of difficulties arise when an inserted transient timer entry is now desired to be deleted and removed.
Traditionally, timer events are maintained in a queue structure, and each timer event has a value associated with it. The value of the timer event determines when the event would or should happen after the previous timer event has happened.
As an example, if five events are to happen at t+3, then t+8, then t+45, then t+55, then t+56, (where “t” is current time), then as an example, the queue may be considered to look as follows:
TE(
3
)—TE(
5
)—TE(
37
)—TE(
10
)—TE(
1
)
Where “t” is the current time and the bracketed value (X) represents the added time, for example, in seconds, which indicates the event as occurring just after the time count that the previous event had occurred.
In this particular operation, after one tick of time has occurred (that is to say, at t+1), then the timer queue could be represented to look as follows:
TE(
2
)—TE(
5
)—TE(
37
)—TE(
10
)—TE(
1
)
The difference here, is that the first item has now changed from TE(
3
) to now be TE(
2
).
With this type of scheme being used, it is seen to be very time-consuming to insert a transient timer entry in the queue, since the fixed timer entries need to be scanned from the “start” of the queue until the correct place is found. For example, if a temporary New Timer Entry (NTE) is to be added, for example, which is to happen after 48 ticks, then the entries of the timer queue will need to be scanned until an event is found which will happen after 48 ticks, and then the transient New Timer Entry (NTE) needs to be inserted just prior to that event. Thus, in the above example, it would be necessary to scan step-by-step for each of the entries.
Thus, in the above example, the timer queue after the new event insertion (NTE) will now appear as shown below:
TE(
2
)—TE(
5
)—TE(
37
)—NTE(
4
)—TE(
6
)—TE(
1
)
Thus, the New Timer Entry insertion which is NTE(
4
) required the scanning of four previous entries.
Now, in the situation where the queue has thousands of entries, this type of operation will be seen to be very time-consuming in order to provide for a new event insertion. Likewise later when the removal of a temporary New Timer Entry (NTE) was desired, the usual and ordinary solution was to sequence through each of the fixed timer entries until the temporary NTE was found so it could then be deleted. Here much wasteful time was consumed.
The present system involves a method for managing timer events and expanding the number of pre-existing fixed timer entries, FTEs. This does not require any scan of the existing entries in the queue, and as a result, provides for an extensive speeding-up for handling the sequence of events which are desired to be utilized in a queue. The new method uses the operation of the timer queue as if it were maintained as a circular queue. Here, the circular queue would have “N” permanent entries, where “N” is a chosen number, but an arbitrary one depending on the number of permanent entries or FTEs (fixed timer entries) that one would like to configure into the queue. Also, the number “N” then determines the maximum duration in timer ticks that can be handled by this type of configuration.
In the co-pending companion case, U.S. Ser. No. 09/602,692, the major focus was to provide the “insertion” of a transient or temporary timer entry designated as an NTE or new timer entry.
Still, in the co-pending companion case, U.S. Ser. No. 09/602,693, the major focus was to handle the problem of removing and deleting such a new timer entry (NTE) when it is no longer needed or useful.
The method of the present invention relates to dynamically allowing a timer queue to process NTEs with duration in timer ticks greater than the limit of the previous existing timer queue, thus increasing capacity for a larger number of FTEs. This is achieved by inserting additional FTEs to the circular queue and increasing the value of “N” to a new “N”.
The system here contemplates a circular queue of “N” fixed timer entries (FTEs). A request to process an NTE (New Timer Entry) with a duration greater than N timer ticks is presented to the circular queue. Without the method of the present invention, the NTE could not be handled. Using the method of the present invention, however, the circular queue is expanded to a size allowing the requested duration to be handled through the dynamic insertion of new FTEs (Fixed Timer Entries).
For example, if the timer “tick” or “period” is 100 milliseconds, and “N” is 9,000, then this queue will be capable of handling
Dangi Salil
Jones Roger Andrew
Butler Dennis M.
Cass Nathan
Kozak Alfred W.
Starr Mark T.
Unisys Corporation
LandOfFree
Enhanced timer queue mechanism for dynamic capacity increase does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Enhanced timer queue mechanism for dynamic capacity increase, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Enhanced timer queue mechanism for dynamic capacity increase will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3222113