Cache management system using hashing
US6567817B1 · kind B1 · utility
Assignee
Inventor
Key dates
| Filing date | Sep 8, 2000 |
| Grant date | May 20, 2003 |
| Priority date | — |
| Expiry date | May 9, 2021 |
Classification
- Technology area (CPC Y)Emerging Cross-Sectional Technologies
- CPC primaryY10S707/99943
- WIPO fieldComputer technology
- WIPO sectorElectrical engineering
Abstract
In a computer system having multiple devices, such as hard disk drives, CD ROM drives, DVD drives, and like volumes in which the data is accessible in numbered blocks, an operating system maintains, for all such devices, a device buffer cache system in which 4K RAM buffers are allocated to any 4k block of device-resident data on any device that is accessed by a program. These 4K buffers are linked to the, buckets of a hash table. Indices into the hash table are computed by exclusive-ORing together the block number of a data block with a device identifier. The device identifiers are selected in such a manner that they are relatively uniformly distributed over a permissible range of values, thereby reducing the number of hash table collisions. These identifiers may be the size of the hash table multiplied by fractions in the series: 0, ½, ¼, ¾, ⅛, ⅝, ⅜, ⅞, {fraction (1/16)}, {fraction (3/16)}, and so on.
Source: USPTO / EPO open patent data. Objective bibliographic and citation counts.