System and methods of a CPU-efficient cache replacement algorithm

摘要

A method of updating a cache data structure that includes first, second, and third queues includes the step of storing contents of a data item in a cache location in response to a read or write input/output operation (IO) that accesses the data item. If the data item is not tracked in any of the first, second, and third queues, the data item is added to the first queue with the cache location of the data item. On the other hand, if the data item is tracked in the second queue, the data item is added to the third queue with the cache location of the data item.