Electrical computers and digital processing systems: support – Clock – pulse – or timing signal generation or analysis – Counting – scheduling – or event timing
Reexamination Certificate
1998-09-30
2002-05-14
Butler, Dennis M. (Department: 2182)
Electrical computers and digital processing systems: support
Clock, pulse, or timing signal generation or analysis
Counting, scheduling, or event timing
C709S238000
Reexamination Certificate
active
06389549
ABSTRACT:
BACKGROUND OF THE INVENTION
The present invention relates to a list management system, a list management method, and a recording medium wherein a computer program for realizing the list management system is recorded, and particularly to those which enable substantially equivalent list rearrangement to that performed according to an LRU (Least-Recently-Used) method with smaller overhead of a CPU (Central Processor Unit) than the LRU method.
The present invention also relates to a packet exchange which can retrieve next destination of packets with high-speed.
When there are numbers of demands to use limited resources, such as a high-speed memory of a computer, there is a method for improving usage efficiency of the resources by assigning the limited resources to the demands according to usage frequency of each unit (hereinafter called a process, and usage of a resource by a process being called a reference), such as a data set obtained from a database, to use the resources.
As an algorithm for tracing the above usage frequency, the LRU method is well known.
In the LRU method, a list is used for managing the reference frequency of each process. Every time when a process is referred to, the referred process is ranged at the top of the list. Suppose ten processes, a first to a tenth process, are ranged in the order such as 1→2→3→4→5→6→7→8→9→10, in the list. When the fifth process is referred to in the case, the order of the list is rearranged as 5→1→2→3→4→6→7→8→9→10. When a new eleventh process is referred to, the tenth process, which has been ranged at the end of the list as it has not been referred to for a longest interval, is expelled from the list.
As above described, every time when a process is referred to, a list management program is started for rearranging the list, in the LRU method. The list management program searches a position of the referred process in the list, connects a preceding process of the referred process to a following process of the referred process, and ranges the referred process at the top of the list. Therefore, the list management program may take considerable overhead, resulting in degradation of operational speed for performing the processes themselves.
This is a problem.
In a packet transmission network, data are transmitted being divided in units of packets having a fixed length, for example. Each packet has its final destination. The packet exchange in the packet transmission network retrieves a next destination whereto a received packet is to be forwarded according to the final destination.
Usually, length of transmission data is longer than a packet length, and the data are divided into numbers of packets to be transmitted in succession having the same final destination, which means that a packet exchange has high possibility to receive packets having the same final destination with a packet previously received. Therefore, how to retrieve the next destination of successive packets including packets having the same final destination, with high speed, is very important for improving performance of the packet exchange.
SUMMARY OF THE INVENTION
Therefore, a primary object of the present invention is to provide a list management system and a list management method which enable substantially the same effectiveness with the LRU method and take but smaller overhead of the CPU than the LRU method.
Another object is to provide a recording medium wherein a computer program for realizing the above list management system is recorded.
Still another object is to provide a packet exchange which can retrieve next destinations of the received packets with high speed and an economical configuration as well.
In order to achieve the objects, a list management system of the invention comprises:
a trigger generating means for generating a trigger signal every time when a time interval is passed;
counters each corresponding to each of a plurality of processes and counting a reference frequency of each of the processes;
a list of elements each corresponding to each of the processes and connected with each other by way of pointer data; and
a list maintenance means for rearranging order of the elements according to count values of the counters, when the trigger signal is generated.
Each of the elements is rearranged by the list management means in descending order of the reference frequency counted by corresponding one of the counters. The time interval is so determined that sufficient numbers of process references are performed in the time interval for evaluating substantial differences of reference frequencies between the processes. The operational time for counting up the counters is far shorter than that needed for rearranging the list. Therefore, by rearranging the list at appropriate timings, average overhead taken for the list management can be considerably reduced compared to the conventional LRU method, providing substantially the same effectiveness of the list management with the LRU method.
The time interval may be controlled according to the reference frequency counted by each of the counters.
The trigger generating means may generate a first trigger signal every time when a first time interval is passed and a second trigger signal every time when a second time interval is passed; and the list maintenance means may rearrange the elements and clears the count values when the first trigger signal is generated, and rearrange the elements without clearing the count values when the second trigger is generated.
In this case, the list maintenance means may control either or both of the first time interval and the second time interval according to the reference frequency counted by each of the counters, and further, the list maintenance means may disable generation of the second trigger signal, when the first time interval becomes longer than the second time interval.
The elements which correspond to the counters showing the same count values may be ranged according to previous order of the elements, or ranged-in the same order making use of horizontal pointers.
Instead of the trigger generating means above described, an operation monitor may be provided for generating the trigger signal when an operational load of a CPU is discriminated to be light, when the reference of the processes and the list management is performed by the CPU.
A packet exchange according to the invention, for forwarding each of received packets to a next destination determined according to a final destination described in said each of the received packets, comprises:
a trigger generating means for generating a trigger signal;
a first memory for storing a plurality of first data sets each including information of a next destination corresponding to each of final destinations which are possible to be described in the received packets;
a second memory for storing each of second data sets in each of addresses of the second memory, the second data sets being a part of the first data sets and the second memory being accessed with higher speed than the first memory;
counters each corresponding to each of the addresses of the second memory;
a first retrieving means for retrieving data of a next destination corresponding to a final destination described in a received packet from the second data sets stored in the second memory;
a memory management means for incrementing a count value of one of the counters when the first retrieving means successes to retrieve the data of the next destination from an address of the second memory corresponding to said one of the counters;
a second retrieving means for retrieving data of the next destination corresponding to the final destination described in the received packet from the first data sets stored in the first memory when the first retrieving means can not retrieve the data of the next destination from any address of the second memory; and
a memory maintenance means for revising a necessary number of the second data sets stored in the second memory into data sets each
Butler Dennis M.
NEC Corporation
Sughrue & Mion, PLLC
LandOfFree
LIST MANAGEMENT SYSTEM, A LIST MANAGEMENT METHOD, A... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with LIST MANAGEMENT SYSTEM, A LIST MANAGEMENT METHOD, A..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and LIST MANAGEMENT SYSTEM, A LIST MANAGEMENT METHOD, A... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2863600