词条 | LIRS caching algorithm |
释义 |
LIRS (Low Inter-reference Recency Set) is a page replacement algorithm with an improved performance over LRU (Least Recently Used) and many other newer replacement algorithms.[1] This is achieved by using reuse distance as a metric for dynamically ranking accessed pages to make a replacement decision. The algorithm was developed by Song Jiang and Xiaodong Zhang. SummaryQuantifying the localityWhile all page replacement algorithms rely on existence of reference locality to function, a major difference among different replacement algorithms is on how this locality is qualified. LIRS uses reuse distance of a page, or the number of distinct pages accessed between two consecutive references of the page, to quantify locality. Specifically, LIRS uses last and second-to-last references (if any) for this purpose. If a page is accessed for the first time, its reuse distance is infinite. In contrast, LRU uses recency of a page, which is the number of distinctive pages accessed after the reference of the page, to quantify locality. To take into account of up-to-date access history, the implementation of LIRS actually uses the larger of reuse distance and recency of a page as the metric to quantify its locality, denoted as RD-R. Assuming the cache has a capacity of C pages, the LIRS algorithm is to rank recently accessed pages according to their RD-R values and retain the C most highly ranked pages in the cache. The concepts of reuse distance and recency can be visualized as below, in which T1 and T2 are page B’s second-to-last and last reference times, respectively, and T3 is the current time. {{clear}}. . . B . . . B . . . . . . . . . . B . . . . . ^----Reuse Distance---^--Recency--^ T1 T2 T3 Selecting the replacement victimLIRS organizes metadata of cached pages and some uncached pages and conducts its replacement operations described as below, which are also illustrated with an example [2] in the graph.
DeploymentLIRS has been deployed in MySQL since version 5.1.[3] It is also adopted in Infinispan data grid platform.[4] An approximation of LIRS, CLOCK-Pro,[5] is adopted in NetBSD.[6] See also
References1. ^Song Jiang, and Xiaodong Zhang, "LIRS: An Efficient Low Inter-Reference Recency Set Replacement Policy to Improve Buffer Cache Performance", in Proceedings of the ACM SIGMETRICS Conference on Measurement and Modeling of Computer Systems (SIGMETRICS'02), Marina Del Rey, CA, June, 2002. 2. ^Song Jiang, and Xiaodong Zhang, "Making LRU Friendly to Weak Locality Workloads: A Novel Replacement Algorithm to Improve File Buffer Cache Performance", in IEEE Transactions on Computers, 54 (8): 939-952, August 2005. 3. ^svn commit - mysqldoc@docsrva: r6768 - trunk/ndbapi 4. ^Infinispan eviction, batching updates and LIRS 5. ^Song Jiang, Feng Chen, and Xiaodong Zhang, "CLOCK-Pro: An Effective Improvement of the CLOCK Replacement", in Proceedings of 2005 USENIX Annual Technical Conference (USENIX'05), Anaheim, CA, April, 2005. 6. ^FreeBSD/Linux Kernel Cross Reference sys/uvm/uvm_pdpolicy_clockpro.c External links
3 : Memory management algorithms|Virtual memory|Online algorithms |
随便看 |
|
开放百科全书收录14589846条英语、德语、日语等多语种百科知识,基本涵盖了大多数领域的百科知识,是一部内容自由、开放的电子版国际百科全书。