Method and system for managing data in cache using multiple data structures
US6141731A · kind A · utility
Assignee
Inventors
Key dates
| Filing date | Aug 19, 1998 |
| Grant date | Oct 31, 2000 |
| Priority date | — |
| Expiry date | Aug 19, 2018 |
Classification
- Technology area (CPC G)Physics
- CPC primaryG06F12/0804
- WIPO fieldComputer technology
- WIPO sectorElectrical engineering
Abstract
Disclosed is a cache management scheme using multiple data structure. A first and second data structures, such as linked lists, indicate data entries in a cache. Each data structure has a most recently used (MRU) entry, a least recently used (LRU) entry, and a time value associated with each data entry indicating a time the data entry was indicated as added to the MRU entry of the data structure. A processing unit receives a new data entry. In response, the processing unit processes the first and second data structures to determine a LRU data entry in each data structure and selects from the determined LRU data entries the LRU data entry that is the least recently used. The processing unit then demotes the selected LRU data entry from the cache and data structure including the selected data entry. The processing unit adds the new data entry to the cache and indicates the new data entry as located at the MRU entry of one of the first and second data structures.
Source: USPTO / EPO open patent data. Objective bibliographic and citation counts.