Method and apparatus for computer disk cache management
US5778430A · kind A · utility
Assignee
Inventors
Key dates
| Filing date | Apr 19, 1996 |
| Grant date | Jul 7, 1998 |
| Priority date | — |
| Expiry date | Apr 19, 2016 |
Classification
- Technology area (CPC G)Physics
- CPC primaryG06F12/0866
- WIPO fieldComputer technology
- WIPO sectorElectrical engineering
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.
Source: USPTO / EPO open patent data. Objective bibliographic and citation counts.