Method and apparatus for providing efficient management of least recently used (LRU) algorithm insertion points corresponding to defined times-in-cache
US6842826B1 · kind B1 · utility
Assignee
Inventor
Key dates
| Filing date | Jun 7, 2000 |
| Grant date | Jan 11, 2005 |
| Priority date | — |
| Expiry date | Mar 28, 2022 |
Classification
- Technology area (CPC G)Physics
- CPC primaryG06F12/0866
- WIPO fieldComputer technology
- WIPO sectorElectrical engineering
Abstract
A method and apparatus for providing efficient management of LRU insertion points corresponding to defined times-in-cache is disclosed. Insertion points are implemented as “dummy entries” in the LRU list. As such, they undergo the standard process for aging out of cache, along with all other entries. A circular queue of insertion points is maintained. At regular intervals, a new insertion point is placed at the top of the LRU list, and at the tail of the queue. When an insertion point reaches the bottom of the LRU list (“ages out”), it is removed form the head of the queue. Since insertion points are added to the list at regular intervals, the remaining time for data at the corresponding LRU list positions to age out must increase in the same, regular steps, as we consider insertion points from the bottom to the top of the LRU list. Therefore, we can find an insertion point which exhibits any desired age-out time, by indexing into the circular queue.
Source: USPTO / EPO open patent data. Objective bibliographic and citation counts.