Memory management is one of the most fundamental issues of modern computer systems. Typically, a computer system will include a hierarchy of memory that ranges from a small, fast cache of main memory that is placed in front of a larger, but slower, auxiliary memory. The cache is generally implemented using a physical memory, such as RAM, while the auxiliary memory is implemented using a storage device, such as a disk drive or hard disk. Both memories are usually managed in uniformly sized units known as pages. Because of their impact on performance, caching algorithms that manage the contents of the main memory are of tremendous importance to virtually any type of computer system, server, storage system, and operating system.
In order to improve performance, many computers and operating systems today implement a virtual memory. Virtual memory is where the computer system emulates that it has more memory than the computer system actually physically possesses. For example, most computer systems utilize 32-bit processors. Hence, a computer system is theoretically capable of providing a virtual memory of approximately 232 bits or approximately 4 Gigabytes, even though the physical memory is usually much smaller.
In order to provide a virtual memory of this size, the computer system runs the application or process in a memory address space that is virtual, i.e., not tied to the physical memory. The computer system will then swap pages in and out of a cache in its physical memory in order to emulate the virtual memory. During operation, an application or process will continually request pages using virtual memory addresses. In response, the computer system will translate the virtual memory address into a physical memory address and determine if the page is present in the cache (i.e., the page is resident). When a requested page is not present in the cache, it is called a cache “miss” (or page fault), and the requested page must be retrieved from storage.
However, when the cache is full, before a new page can be brought into the cache, another page (known as the victim page) must be evicted. The victim page is selected by what is known as a replacement algorithm. Several replacement algorithms are well known to those skilled in the art including Least Recently Used (LRU), 2Q, Adaptive Replace Cache (ARC), Clock with Adaptive Replacement (CAR/CART), Low Inter-reference Recency Set (LIRS), CLOCK, and CLOCK-PRO.
Unfortunately, the known cache replacement algorithms have difficulty with different types of workloads. In particular, the known cache replacement algorithms have difficulty balancing the different “recency” and “frequency” characteristics of various workloads. For example, one of the most popular algorithms is LRU. LRU replaces the page that was least recently accessed or used. LRU assumes that a page that was recently accessed will likely be accessed again, and thus, it works well with workloads having high recency characteristics. However, LRU does not perform well with workloads that exhibit certain frequency characteristics to their page access, such as scanning or looping. As a result, a computer system that uses LRU will often prematurely evict pages and be forced to retrieve the page again from storage.
Other algorithms, such as CLOCK and CLOCK-PRO, attempt to overcome the deficiencies of LRU by tracking pages that have been recently evicted. By tracking recently evicted pages, these algorithms attempt to recognize workloads that exhibit certain frequencies of page access. However, these algorithms also have several deficiencies.
For example, algorithms other than LRU tend to be difficult to tune or implement. In addition, algorithms that track recently evicted pages require a full page data structure in main memory. This results in a performance overhead that consumes a relatively large amount of space in main memory.
Accordingly, it would be desirable to provide cache replacement algorithms and systems that can maximize their hit rate or maintain a relatively low miss rate. In addition, it would be desirable to provide cache replacement algorithms and systems that can handle a variety of different workloads with a minimal amount of overhead. Furthermore, it would be desirable to provide cache replacement algorithms and systems that are relatively simple to implement.