Electrical computers and digital processing systems: support – Clock – pulse – or timing signal generation or analysis – Counting – scheduling – or event timing
Reexamination Certificate
2000-06-23
2003-11-11
Lee, Thomas (Department: 2185)
Electrical computers and digital processing systems: support
Clock, pulse, or timing signal generation or analysis
Counting, scheduling, or event timing
C710S054000, C370S412000
Reexamination Certificate
active
06647505
ABSTRACT:
FIELD OF THE INVENTION
The present system describes methods for use in the deletion of transient timer entries from their positional locations in a circular queue of fixed timer entries.
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 event to be inserted at a particular point in a large sequence of items 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 insertion 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 of must traverse through the queue in order to find the right new entrance point.
Likewise, the same sort of difficulties arise when an inserted temporary timer entry is now desired to be deleted and removed.
Traditionally, time 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 temporary transient timer event 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 Event (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 temporary New Timer Event (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
) - - - TE(
4
) - - - NTE(
6
) - - - TE(
1
)
Thus, the New Timer Event insertion which is TE(
6
) 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 Event (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 invention involves a method for managing timer events which 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 FTE (fixed time entries) that one would like to configure into the queue. Also, the number “N” then determines the maximum number of timer events that can be handled by this type of configuration.
In the co-pending companion case, U.S. apllication 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.
The present disclosure now relates to handling the problem of removing and deleting such a new timer entry (NTE) when it is no longer needed or useful.
The system here contemplates a circular queue of “N” fixed timer event (FTE's) which have been modified with one or more temporary new timer entries (NTEs) and which are now desired to be removed. A specialized program is provided to locate and delete a particular temporary new timer entry (NTE) without the time-consuming problem of linear sequencing through a series of timer events in order to locate and remove a particular new timer event (NTE).
For example, if the timer “tick” or “period” between events is 100 milliseconds, and “N” is 9,000, then this queue will then be capable of handling any timer event over a period of 15 minutes. Now, since 100 milliseconds is {fraction (1/10)}th of a second, and 9,000 would equate to 900 seconds, then with 60 seconds to the minute, it is seen that 900 seconds would be equivalent to 15 minutes.
SUMMARY OF THE INVENTION
The present method provides for the utilization of a timer queue as a circular queue which has “N” permanent entries which are design
Dangi Salil
Jones Roger Andrew
Cass Nathan
Kozak Alfred W.
Lee Thomas
Rode Lise A.
Unisys Corporation
LandOfFree
Deletion system and method for removing temporary timer... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Deletion system and method for removing temporary timer..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Deletion system and method for removing temporary timer... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3125667