User:Yhuai/sandbox

From Wikipedia, the free encyclopedia
Jump to: navigation, search

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.

Summary[edit]

Quantifying the locality[edit]

While all page replacement algorithms rely on existence of reference locality to function, a major difference among different replacement algorithms is on how it is qualified. LIRS uses reuse distance of a page, or the number of distinctive pages accessed between two consecutive references of this page, to quantify locality. Specifically, LIRS uses last and second-to-last references (if any) for this purpose. If the 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 this 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 latency 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 reduce distance and recency can be visualized as below, in which T1 and T2 are page B’s second-to-last and last references, and T3 is the current time.

 . . . B . . . B . . . . . . . . . . B . . . . . 
               ^----Reuse Distance---^--Recency--^
               T1                    T2          T3

Selecting the replacement victim[edit]

LIRS organizes metadata of cached pages and some uncached pages and conducts its replacement operations described as below and illustrated with an example [2] in the graph.

  1. The cache is divided into the LIR and HIR partitions. The LIR partition is to store the most highly ranked pages (LIR pages) and the HIR partition is to store some of the other pages (HIR pages).
  2. The LIR partition holds the majority of the cache, and all LIR pages are resident in the cache.
  3. All recently accessed pages are placed in a FIFO queue called the LIRS stack (stack S in the graph), and all resident HIR pages are also placed in another FIFO queue (stack Q in the graph).
  4. An accessed page is moved to the top of Stack S and any HIR pages at the stack’s bottom are removed. For example, Graph (b) is produced after page B is accessed on Graph (a).
  5. When a HIR page in Stack S is accessed, it turns into a LIR page and accordingly the LIR page currently at Stack S’s bottom turns into a HIR page and moves to the top of Stack Q. For example, Graph (c) is produced after page E is accessed on Graph (a).
  6. When there is a miss and a resident page has to be replaced, the resident HIR page at the bottom of Stack S is selected as the victim for replacement. For example, Graphs (d) and (c) are produced after pages D and C are accessed on Graph (a), respectively.

Deployment[edit]

LIRS has been deployed in the 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 NetBSD [6].

References[edit]

  1. ^ 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. http://www.cse.ohio-state.edu/hpcs/WWW/HTML/publications/abs02-6.html
  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. http://www.cse.ohio-state.edu/hpcs/WWW/HTML/publications/abs05-11.html
  3. ^ http://lists.mysql.com/commits/28601
  4. ^ http://planet.jboss.org/post/infinispan_eviction_batching_updates_and_lirs%3bjsessionid=B7BFCED50D1F9C2731E00E3AD5B4C025
  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. http://www.cse.ohio-state.edu/hpcs/WWW/HTML/publications/abs05-3.html
  6. ^ http://fxr.watson.org/fxr/source/uvm/uvm_pdpolicy_clockpro.c?v=NETBSD

External links[edit]

  • Towards an O(1) VM by Rik van Riel about the possible use of LIRS for balancing cache and program memory in Linux.
  • A report on the implementation of the CLOCK-Pro page replacement.
  • Advanced Page Replacement Projects established by the Linux Memory Management Development Team.
  • CLOCK-Pro patch developed by Rik van Riel.
  • CLOCK-Pro patch developed by Peter Zijlstra.
  • CLOCK-Pro is referred as an example in the section of Linux and Academia in Book Professional Linux Kernel Architecture by Wolfgan Mauerer.
  • A paper detailing performance differences of LIRS and other algorithms “The Performance Impact of Kernel Prefetching on Buffer Cache Replacement Algorithms” by Ali R. Butt, Chris Gniady, and Y. Charlie Hu.

See also[edit]

Page replacement algorithm