Electrical computers and digital processing systems: memory – Storage accessing and control – Hierarchical memories
Reexamination Certificate
1999-09-30
2002-09-17
Kim, Matthew (Department: 2186)
Electrical computers and digital processing systems: memory
Storage accessing and control
Hierarchical memories
C711S136000, C711S160000
Reexamination Certificate
active
06453386
ABSTRACT:
FIELD OF THE INVENTION
The present invention relates to memory usage in a computer system and more particularly to a method and system for providing a variable aging interval for aging a memory resource.
BACKGROUND OF THE INVENTION
FIG. 1
depicts a simplified block diagram of a portion of a computer system
10
. The computer system includes a memory
12
, a processor
14
, a large capacity storage
16
, an input/output mechanism
18
, such as a keyboard, monitor or network, and a computation procedure for generating memories
20
. The memory
12
is used to temporarily store items which may be used by the processor
14
in performing various tasks. Typically, when the processor
14
requires an item, the memory
12
is searched first. If the item is found in the memory
12
, the item is provided directly to the processor
14
. When an item that is searched for is not found in the memory
12
, the item is typically found by searching the large capacity storage
16
, or other by other means. The new item is generally provided to the memory
12
and the processor
14
. Alternatively, a new memory is computed by some procedure
20
, such as generation of a forwarding table. Thus, if the processor
14
requires the item again, the memory
12
may contain the item.
Items stored in the memory
12
are desired to be rapidly and easily accessible by the processor
14
. Items stored in the memory
12
can be more rapidly retrieved than items stored in the large capacity storage
16
. Similarly, items stored in the memory
12
can be more rapidly retrieved than items recomputed by some procedure
20
, such as generation of a forwarding table. Thus, the memory
12
may be a cache. In order for the interaction between the memory
12
and the processor
14
to be efficient, the memory
12
is made relatively small. Consequently, the memory
12
is typically much smaller than the large capacity storage
16
. Memory retrieval from the memory
12
is also much faster than recomputation. The small size of the memory
12
reduces unnecessary delay in retrieving items in the memory
12
.
Furthermore, the full capacity of the memory
12
is not desired to be used. If the memory
12
becomes full it is difficult to store additional items. Thus, the occupancy of the memory
12
is desired to be below the maximum possible occupancy. In addition, when fewer items are stored in the memory
12
, the problem of finding a location to store new items is simplified. The search of the memory
12
, therefore, consumes less time. Thus, the memory
12
and processor
14
can operate more efficiently.
Furthermore, it is desirable for the hit ratio to be relatively large. The hit ratio is the ratio of the number of times a search in the memory
12
results in the desired item being found to the total number of times the memory
12
is searched. If the hit ratio is relatively high, then the memory
12
is storing those items that are repeatedly used. However, as discussed above, the occupancy of the memory
12
should still remain below the maximum occupancy in order to improve the speed of accessing to the memory
12
or adding new items to the memory
12
.
One of ordinary skill in the art will readily realize that without management, the efficiency of the memory
12
may not be maintained. As discussed above, a large hit ratio, a small size, and a relatively low occupancy are generally desired for the memory
12
. These are competing goals. A larger memory
12
having a higher occupancy stores more items, allowing for a larger hit ratio. However, a small memory
12
with a relatively low occupancy has a high speed. As the size of the memory
12
decreases, it becomes more important to store only those items which will be reused by the system
10
in order to preserve a higher hit ratio. Furthermore, items that the processor
14
cannot find in the memory
12
are stored in the memory
12
when the items are found, either being recalled from the large capacity memory
16
or generated by the computation procedure
20
. Unchecked, the memory
12
may become full, unable to store additional items, and function improperly. Items stored in the memory
12
may also become seldom used or may never be used again. These items may unnecessarily clutter the memory
12
. Thus, some mechanism for managing, or aging, the memory
12
is used to attempt to improve the efficiency of the memory
12
.
There are many conventional mechanisms for aging the memory
12
. One conventional mechanism keeps the memory
12
relatively full, discarding the least recently used item for additional space. Other conventional mechanisms use variations of purging the least recently used items or purging the memory
12
when the memory
12
is full or almost full. However, in such a case, the occupancy of the memory
12
is relatively high, making it difficult to store additional items. Thus, another mechanism is often used for managing the memory
12
.
FIG. 2A
depicts one conventional method
50
for purging the memory
12
periodically in order to age the memory
12
. A purge of the memory removes some of the items of the memory
12
, for example those items not sought since the previous purge and not added during the same time period, or epoch. A conventional aging period, which sets the time between purges of the memory
12
, is set, via step
52
. An epoch for the memory is a time equal to the conventional aging period. The time since the last purge is then set to zero, via step
54
. It is determined whether the memory is near full, via step
56
. If so, then the memory
12
is purged immediately, via step
58
. Steps
56
and
58
allow for accelerated purging of the memory
12
. Accelerated purging helps prevent the memory
12
from becoming full. Step
54
is then returned to.
If it is determined in step
56
that the memory is not nearly full, then it is determined if the current epoch is completed, via step
60
. In other words, it is determined whether a time equal to the conventional aging period has expired, via step
60
. If the time equal to the conventional aging period has not expired, then step
56
is returned to. If it is determined that the current epoch has expired, then the memory is purged, via step
62
. Step
54
is then to returned to.
Thus, the conventional method
50
periodically removes items from the memory
12
at the end of each epoch, for example those items not referenced and not added during the just completed epoch. The conventional aging period is typically set by a user, such as a network administrator. The network administrator typically sets the conventional aging period based on the network administrator's experience or knowledge of the computer system
10
. The memory
12
is purged upon expiration of each conventional aging period.
FIG. 2B
depicts a time line
70
for the conventional method
50
. The conventional aging period, A, defines the lengths of the epochs
72
and
74
. Each epoch
72
and
74
is followed by a purge
73
and
75
, respectively. Additional epochs (not shown) and purges (not shown) follow during operation of the computer system
10
using the conventional method
50
. Thus, the conventional aging period sets the time between the end of one purge and the beginning of a subsequent purge. During a purge
73
or
75
, the memory
12
is typically unavailable for other operations.
Referring to
FIGS. 2A and 2B
, the purging steps
58
and
62
are conventionally carried out in a number of ways. Some conventional systems simply delete all of the items in the memory
12
when the memory
12
is full instead of relying on the conventional aging period. Thus, steps
58
and
62
could purge all or merely some of the items in the memory
12
. In one conventional method
50
, the number of items purged in step
58
and
62
is a function of the occupancy of the memory
12
. When the memory
12
is nearly full, a larger number of items are deleted during the purging steps. When the memory
12
is closer to being empty, fewer items are deleted in the purging steps. In another conven
Jeffries Clark Debs
Patel Piyush Chunilal
Woodland Gail Irene
Elmore Stephen
Kim Matthew
Mitchell Janyce
Sawyer Law Group
LandOfFree
Method and system for performing variable aging to optimize... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Method and system for performing variable aging to optimize..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and system for performing variable aging to optimize... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2858211