Method and apparatus for computer disk cache management

Details Method and apparatus for computer disk cache management Method and apparatus for computer disk cache management

1996-04-19

1998-07-07

Shin, Christopher B.

Electrical computers and digital processing systems: memory

Storage accessing and control

Hierarchical memories

711 3, 711113, G06F 1210

Patent

active

057784302

ABSTRACT:
A computer disk cache management method and apparatus which employs a least-recently-used with aging method to determine a best candidate for replacement as a result of a cache miss. A hash function takes as its input a block number and outputs a hash index into a hash table of pointers. Each pointer in the hash table points to a doubly-linked list of headers, with each header having a bit map wherein the bits contained in the map identify whether a particular block of data is contained within the cache. An ordered binary tree (heap) identifies candidates for replacement such that the best candidate for replacement is located at the root of the heap. After every access to a cache line, the heap is locally reorganized based upon a frequency of use and an age of the cache line, such that the least-frequently-used and/or oldest cache line is at the root of the heap.

REFERENCES:
patent: 4835686 (1989-05-01), Furuya et al.
patent: 4920478 (1990-04-01), Furuya et al.
patent: 5133060 (1992-07-01), Weber et al.
patent: 5313585 (1994-05-01), Jeffries et al.
patent: 5353425 (1994-10-01), Malamy et al.
patent: 5369751 (1994-11-01), Kambayashi et al.
patent: 5371885 (1994-12-01), Letwin
patent: 5418921 (1995-05-01), Cortney et al.
patent: 5418929 (1995-05-01), Tsuboi et al.
patent: 5420999 (1995-05-01), Mundy
patent: 5423019 (1995-06-01), Lin
patent: 5448709 (1995-09-01), Chandler et al.
patent: 5452447 (1995-09-01), Nelson et al.
patent: 5471602 (1995-11-01), DeLano
patent: 5519846 (1996-05-01), Swenson
patent: 5526511 (1996-06-01), Swenson et al.
patent: 5530958 (1996-06-01), Agrawal et al.
patent: 5638506 (1997-06-01), Peterson et al.
patent: 5659699 (1997-08-01), Breternitz, Jr.
patent: 5687390 (1997-11-01), McMillan, Jr.
A. Hospodor, "Hit Ratio of Caching Disk Buffers", COMPCON (Spring 1992) pp. 427-432.
J.T. Robinson et al, "Data Cache Management Using Frequency-Based Replacement", Performance Evaluation Review, vol. 18, No. 1, May 1990, pp. 134-142.

Affiliated with

Also associated with

Rating

Method and apparatus for computer disk cache management 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 apparatus for computer disk cache management, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and apparatus for computer disk cache management will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-1218589