Boots – shoes – and leggings
Patent
1992-08-03
1993-06-29
Lee, Thomas C.
Boots, shoes, and leggings
3642430, 3642432, 36424341, 364DIG1, 395800, G06F 1200
Patent
active
052242170
DESCRIPTION:
BRIEF SUMMARY
FIELD OF THE INVENTION The invention is related to cache memories,
apparatuses and methods for increasing the efficiency of cache memories and more specifically to a method and apparatus for implementing a least-recently-used replacement algorithm in a cache memory for a mass storage controller.
CROSS REFERENCE TO RELATED APPLICATIONS
This application is related to but in no way dependent on "Method and Apparatus for Positioning Head of Disk Drive Using Zone-Bit-Recording," Ser. No. 07/641,264, filed Sep. 15, 1991, "Two Stage Cache Memory System and Method," Ser. No. 07/918,892, filed Jul. 16, 1992, which is a continuation of Ser. No. 07/657,969, filed Feb. 20, 1991 and now abandoned, which is a continuation of Ser. No. 07/292,189, filed Dec. 30, 1988 and now abandoned, and "Dynamic Prefetching for a Cache Memory," filed originally as Ser. No. 07/345,915 on May 1, 1989, abandoned, and now U.S. Pat. No. 5,146,578, all of common ownership and inventorship herewith.
BACKGROUND OF THE INVENTION
Information or data can be stored relatively inexpensively in various magnetic or optical mass-storage devices such as tapes, disks or drums. These devices are slow, non-volatile, and only provide for access to large blocks of data. Silicon-based random access memory (RAM) is significantly faster, provides for random byte-by-byte access to data, but is volatile, and more expensive. The difference in speed is often several orders of magnitude.
It is therefore common practice in the computer industry to mass-store data in magnetic or optical mass-storage devices, transfer the data to RAM for use or modification, and then transfer the data back to mass-storage devices.
Due to the speed difference between RAM and mass-storage devices, a computer process is significantly delayed when more data is needed from a mass-storage device. Several methods are used to minimize such delays.
One common approach is the use of a cache memory. Such a memory is usually silicon based and part of the mass-storage controller. When the computer requests data from the mass-storage device, the requested data is fetched from the mass-storage device alone with a prefetch of more data than requested. The prefetched data is loaded into the cache memory (located in the mass-storage controller) in hopes that the data that is subsequently requested will already be in the cache memory. The requested data is also retained assuming that it is likely to be used again. Each subsequent request for data is checked first against the cache memory before it is fetched from the mass-storage device. Data that is already in the cache memory can be supplied to the computer much faster than data that must be fetched from a mass-storage device.
Dynamic RAM memory can only accept data (write) or give data (read) at a given time. It is therefore important that the cache memory be able to read and write as quickly as possible so it is available for other requests. The cache memory spends a majority of its time in communication with mass-storage devices because mass-storage devices are so much slower than RAM.
The hit ratio is the number of requests found in the cache memory divided by the total number of requests. The hit ratio is a common measure of the success in fetching and retaining the right data.
It is assumed that data that has been requested before is likely to be requested again. Therefore, the cache retains data as long as it can. However, data must be replaced when the cache is full and additional data is requested.
There are several methods of determining which data in a cache to replace. The most common is "first-in first-out" (FIFO). This is like a queue or a line. The first data to be put into the cache memory is the first data to be removed from the cache memory. Another common method is "least-recently-used" (LRU). In this method the data that has not been used for the longest time is replaced. LRU is usually implemented with complicated timers or counters that determine the amount of time since the last request.
Prior art: U.S. Pat. No. 3,806,883
REFERENCES:
patent: 3737881 (1973-06-01), Cordi et al.
patent: 3806883 (1974-04-01), Weisbecker
patent: 3949369 (1976-04-01), Churchill, Jr.
patent: 4008460 (1977-02-01), Bryant et al.
patent: 4168541 (1979-09-01), DeKarske
patent: 4322795 (1982-03-01), Lange et al.
patent: 4334289 (1982-06-01), Lange et al.
patent: 4458310 (1984-07-01), Chang
patent: 4459662 (1984-07-01), Skelton et al.
patent: 4489378 (1984-12-01), Dixon et al.
patent: 4530054 (1985-07-01), Hamstra et al.
patent: 4607331 (1986-08-01), Goodrich, Jr. et al.
patent: 4636946 (1987-01-01), Hartung et al.
patent: 4672536 (1987-06-01), Giroir et al.
patent: 4680729 (1987-07-01), Steinhart
patent: 4755968 (1988-07-01), Yoshida et al.
patent: 4783785 (1988-11-01), Miu et al.
patent: 4785395 (1988-11-01), Keeley
patent: 4785398 (1988-11-01), Joyce et al.
patent: 4802086 (1989-01-01), Gay et al.
patent: 4835686 (1989-05-01), Furuya et al.
patent: 4962451 (1990-10-01), Case et al.
Lee Thomas C.
Treat William M.
LandOfFree
Computer system which uses a least-recently-used algorithm for m does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Computer system which uses a least-recently-used algorithm for m, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Computer system which uses a least-recently-used algorithm for m will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-1762720