Article

The Multi-Queue Replacement Algorithm for Second Level Buffer Caches

Authors:

Yuanyuan Zhou,

James Philbin,

Kai LiAuthors Info & Claims

Proceedings of the General Track: 2001 USENIX Annual Technical Conference

Pages 91 - 104

Published: 25 June 2001 Publication History

Abstract

No abstract available.

References

[1]

{1} J. L. Baer and W.-H. Wang. On the Inclusion Properties for Multi-Level Cache Hierarchies. In 15th ISCA.]]

Crossref

Google Scholar

[2]

{2} L. A. Belady. A study of replacement algorithms for a virtual-storage computer. IBM Systems Journal, 5(2), 1966.]]

Google Scholar

[3]

{3} R. W. Carr and J. L. Hennessy. WSClock - A Simple and Effective Algorithm for Virtual Memory Management. In SOSP, 1981.]]

Crossref

Google Scholar

[4]

{4} H. T. Chou and D. J. DeWitt. An Evaluation of Buffer Management Strategies for Relational Database Systems. In VLDB, 1985.]]

Google Scholar

[5]

{5} Oracle Co. Oracle 8i Concepts.]]

Google Scholar

[6]

{6} E. G. Coffman and P. J. Denning. Operating Systems Theory. 1973.]]

Crossref

Google Scholar

[7]

{7} EMC Corporation. Symmetrix 3000 and 5000 Enterprise Storage Systems Product Description Guide. 1999.]]

Google Scholar

[8]

{8} IBM Corporation. White Paper: ESS-The Performance Leader. 1999.]]

Google Scholar

[9]

{9} P. J. Denning. The Working Set Model for Program Behavior. Communications of the ACM, 11(5), May 1968.]]

Crossref

Google Scholar

[10]

{10} P. J. Denning. Virtual Memory. ACM Computing Surveys, 28(1), March 1996.]]

Crossref

Google Scholar

[11]

{11} P. J. Denning and S. C. Schwartz. Properties of the working-set model. Communications of the ACM, 15(3), March 1972.]]

Crossref

Google Scholar

[12]

{12} W. Effelsberg and T. Haerder. Principles of Database Buffer Management. ACM Transactions on Database Systems, 9(4), December 1984.]]

Crossref

Google Scholar

[13]

{13} C. Lee et. al. HiPEC: High Performance External Virtual Memory Caching. In 1st OSDI, 1994.]]

Crossref

Google Scholar

[14]

{14} D. Lee et. al. On the Existence of a Spectrum of Policies that Subsumes the Least Recently used (LRU) and Least Frequently Used (LFU) Policies. In SIGMETRICS-99, pages 134-143, 1999.]]

Crossref

Google Scholar

[15]

{15} E. J. O'Neil et. al. The LRU-K Page Replacement Algorithm For Database Disk Buffering. In SIGMOD-93, 1993.]]

Crossref

Google Scholar

[16]

{16} M.D. Dahlin et. al. A Quantitative Analysis Scalability for Network File Systems. In SIGMETRICS- 94, 1994.]]

Crossref

Google Scholar

[17]

{17} R. L. Mattson et. al. Evaluation Techniques for Storage Hierarchies. IBM Systems Journal, 9(2), 1970.]]

Google Scholar

[18]

{18} V. Almeida et.al. Characterizing reference locality in the WWW. In PDIS-96, 1996.]]

Crossref

Google Scholar

[19]

{19} V. F. Nicola et. al. Analysis of the Generalized Clock Buffer Replacement Scheme for Database Transaction Processing. In SIGMETRICS-92, 1992.]]

Crossref

Google Scholar

[20]

{20} W.-H. Wang et. al. Organization and Performance of a Two-Level Virtual-Real Cache Heirarchy. In 16th ISCA, 1989.]]

Crossref

Google Scholar

[21]

{21} J. Gecsei and J. A. Lukes. A Model for the Evaluation of Storage Hierarchies. IBM Systems Journal, 13(2):163-178, 1974.]]

Google Scholar

[22]

{22} Giganet Inc. Giganet.]]

Google Scholar

[23]

{23} T. Johnson and D. Shasha. 2Q: A Low Overhead High Performance Buffer Management Replacement Algorithm. In VLDB-94, 1994.]]

Crossref

Google Scholar

[24]

{24} Norman P. Jouppi. Improving direct-mapped cache performance by the addition of a small fully-associative cache and prefetch buffers. In The 17th ISCA, 1990.]]

Crossref

Google Scholar

[25]

{25} C. Lam and S. E. Madnick. Properties of Storage Hierarchy Systems with Multiple Page Sized and Redundant Data. ACM Transactions on Database Systems, 4(3):345-367, September 1979.]]

Crossref

Google Scholar

[26]

{26} B. W. Lampson. A Scheduling Philosophy for Multiprocessing Systems. Communications of the ACM, 11(5), 1968.]]

Crossref

Google Scholar

[27]

{27} S. T. Leutenegger and D. Dias. A modeling study of the TPC-C benchmark. SIGMOD Record, 22(2), June 1993.]]

Crossref

Google Scholar

[28]

{28} D. Muntz and P. Honeyman. Multi-level Caching in Distributed File Systems -or- your cache ain't nuthin' but trash. In Proceedings of the Usenix Winter Technical Conference, 1992.]]

Google Scholar

[29]

{29} VI Architecture Organization. Virtual Interface Architecture Specification version 1.0. 1997.]]

Google Scholar

[30]

{30} V. Phalke and B. Gopinath. An Inter-Reference Gap Model for Temporal Locality in Program Behavior. In SIGMETRICS-95, 1995.]]

Crossref

Google Scholar

[31]

{31} J. Robinson and M. Devarakonda. Data Cache Management Using Frequency-Based Replacement. In SIGMETRICS-90, 1990.]]

Crossref

Google Scholar

[32]

{32} C. Ruemmler and J. Wilkes. A Trace-Driven Analysis of Disk Working Set Sizes. Technical Report HPL-OSR-93-23, Hewlett-Packard Laboratories, Palo Alto, CA, USA, April 5 1993.]]

Google Scholar

[33]

{33} C. Ruemmler and J. Wilkes. UNIX Disk Access Patterns. In USENIX-93, 1993.]]

Google Scholar

[34]

{34} G. M. Sacco and M. Schkolnick. Buffer Management in Relational Database Systems. ACM Transactions on Database Systems, 11(4), December 1986.]]

Crossref

Google Scholar

[35]

{35} R. A. Shillner and E. W. Felten. Simplifying distributed file systems using a shared logical disk. Technical Report TR-524-96, Princeton University CS Department, 1996.]]

Google Scholar

[36]

{36} A. J. Smith. Sequentiality and Prefetching in Datasbase Systems. ACM Transactions on Database Systems, 3(3), September 1978.]]

Crossref

Google Scholar

[37]

{37} A. J. Smith. Disk cache - miss ratio analysis and design considerations. TOCS, 3, 1985.]]

Crossref

Google Scholar

[38]

{38} Alan J. Smith. Cache Memories. ACM Computing Surveys, 14(3):473-530, September 1982.]]

Crossref

Google Scholar

[39]

{39} J. R. Sprin. Distance String models for program behavior. Computer, 9(11), November 1976.]]

Google Scholar

[40]

{40} M. Stonebraker. Operating System Support for Database Management. Communications of the ACM, 24(7), July 1981.]]

Crossref

Google Scholar

[41]

{41} A. S. Tanenbaum. Modern Operating Systems. 1992.]]

Crossref

Google Scholar

[42]

{42} Transaction Processing Performance Council. TPC Benchmark C. May 1991.]]

Google Scholar

[43]

{43} D. L. Willick, D. L. Eager, and R. B. Bunt. Disk Cache Replacement Policies for Network File-servers. In ICDCS, May 1993.]]

Google Scholar

[44]

{44} Yuanyuan Zhou. Memory Management for Networked Servers (Thesis). Technical report, Princeton University, Computer Science Department, November 2000.]]

Crossref

Google Scholar

Cited By

View all

Mersy GWang ZSintos SKrishnan S(2024)Optimizing Collections of Bloom Filters within a Space BudgetProceedings of the VLDB Endowment10.14778/3681954.368202017:11(3551-3564)Online publication date: 1-Jul-2024
https://dl.acm.org/doi/10.14778/3681954.3682020
Zhang TGupta ARodríguez MSpjuth OHellander AToor S(2024)Data management of scientific applications in a reinforcement learning-based hierarchical storage system▪Expert Systems with Applications: An International Journal10.1016/j.eswa.2023.121443237:PBOnline publication date: 1-Feb-2024
https://dl.acm.org/doi/10.1016/j.eswa.2023.121443
Yang JWang YWang Z(2023)An Empirical Analysis on Memcached's Replacement PoliciesProceedings of the International Symposium on Memory Systems10.1145/3631882.3631883(1-10)Online publication date: 2-Oct-2023
https://dl.acm.org/doi/10.1145/3631882.3631883
Show More Cited By

Index Terms

The Multi-Queue Replacement Algorithm for Second Level Buffer Caches
1. Information systems
  1. Data management systems
    1. Data structures
      1. Data access methods
2. Software and its engineering
  1. Software organization and properties
    1. Contextual software domains
      1. Operating systems
        Communications management
        Buffering
        Memory management
        Allocation / deallocation strategies

Recommendations

Introducing hierarchy-awareness in replacement and bypass algorithms for last-level caches
PACT '12: Proceedings of the 21st international conference on Parallel architectures and compilation techniques

The replacement policies for the last-level caches (LLCs) are usually designed based on the access information available locally at the LLC. These policies are inherently sub-optimal due to lack of information about the activities in the inner-levels of ...
MRU-Tour-based Replacement Algorithms for Last-Level Caches
SBAC-PAD '11: Proceedings of the 2011 23rd International Symposium on Computer Architecture and High Performance Computing

Memory hierarchy design is a major concern in current microprocessors. Many research work focuses on the Last-Level Cache (LLC), which is designed to hide the long miss penalty of accessing to main memory. To reduce both capacity and conflict misses, ...
Hardware prefetching strategies for second level caches

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

Proceedings of the General Track: 2001 USENIX Annual Technical Conference

June 2001

339 pages

ISBN:188044609X

Editor:
Yoonho Park

Publisher

USENIX Association

United States

Publication History

Published: 25 June 2001

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

141
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 19 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

View all

Mersy GWang ZSintos SKrishnan S(2024)Optimizing Collections of Bloom Filters within a Space BudgetProceedings of the VLDB Endowment10.14778/3681954.368202017:11(3551-3564)Online publication date: 1-Jul-2024
https://dl.acm.org/doi/10.14778/3681954.3682020
Zhang TGupta ARodríguez MSpjuth OHellander AToor S(2024)Data management of scientific applications in a reinforcement learning-based hierarchical storage system▪Expert Systems with Applications: An International Journal10.1016/j.eswa.2023.121443237:PBOnline publication date: 1-Feb-2024
https://dl.acm.org/doi/10.1016/j.eswa.2023.121443
Yang JWang YWang Z(2023)An Empirical Analysis on Memcached's Replacement PoliciesProceedings of the International Symposium on Memory Systems10.1145/3631882.3631883(1-10)Online publication date: 2-Oct-2023
https://dl.acm.org/doi/10.1145/3631882.3631883
Yang JWang YWang Z(2021)Efficient Modeling of Random Sampling-Based LRUProceedings of the 50th International Conference on Parallel Processing10.1145/3472456.3472514(1-11)Online publication date: 9-Aug-2021
https://dl.acm.org/doi/10.1145/3472456.3472514
Yang JYue YRashmi K(2021)A Large-scale Analysis of Hundreds of In-memory Key-value Cache Clusters at TwitterACM Transactions on Storage10.1145/346852117:3(1-35)Online publication date: 16-Aug-2021
https://dl.acm.org/doi/10.1145/3468521
Du XLi CZhang KGherbi AVenkatasubramanian NVeiga L(2021)SHARCProceedings of the 22nd International Middleware Conference10.1145/3464298.3493389(119-131)Online publication date: 6-Dec-2021
https://dl.acm.org/doi/10.1145/3464298.3493389
Yang JLi BLilja DWassermann BMalka MChidambaram VRaz D(2021)HeuristicDBProceedings of the 14th ACM International Conference on Systems and Storage10.1145/3456727.3463774(1-12)Online publication date: 14-Jun-2021
https://dl.acm.org/doi/10.1145/3456727.3463774
Zhong CZhao XJiang SWassermann BMalka MChidambaram VRaz D(2021)LIRS2Proceedings of the 14th ACM International Conference on Systems and Storage10.1145/3456727.3463772(1-12)Online publication date: 14-Jun-2021
https://dl.acm.org/doi/10.1145/3456727.3463772
Berg BBerger DMcAllister SGrosof IGunasekar SLu JUhlar MCarrig JBeckmann NHarchol-Balter MGanger GLu SHowell J(2020)The CacheLib caching engineProceedings of the 14th USENIX Conference on Operating Systems Design and Implementation10.5555/3488766.3488810(769-786)Online publication date: 4-Nov-2020
https://dl.acm.org/doi/10.5555/3488766.3488810
Song ZBerger DLi KLloyd WBhagwan RPorter G(2020)Learning relaxed Belady for content distribution network cachingProceedings of the 17th Usenix Conference on Networked Systems Design and Implementation10.5555/3388242.3388281(529-544)Online publication date: 25-Feb-2020
https://dl.acm.org/doi/10.5555/3388242.3388281
Show More Cited By

View Options

View options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Abstract

References

Cited By

Index Terms

Recommendations

Introducing hierarchy-awareness in replacement and bypass algorithms for last-level caches

MRU-Tour-based Replacement Algorithms for Last-Level Caches

Hardware prefetching strategies for second level caches

Comments

Information

Published In

Publisher

Publication History

Qualifiers

Contributors

Other Metrics

Bibliometrics

Article Metrics

Other Metrics

Citations

Cited By

View options

Login options

Full Access

Figures

Other

Share

Share this Publication link

Share on social media

Affiliations