On the existence of a spectrum of policies that subsumes the least recently used (LRU) and least frequently used (LFU) policies

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

On the existence of a spectrum of policies that subsumes the least recently used (LRU) and least frequently used (LFU) policies

Full text

Pdf (1.24 MB)

Source

Joint International Conference on Measurement and Modeling of Computer Systems archive
Proceedings of the 1999 ACM SIGMETRICS international conference on Measurement and modeling of computer systems table of contents

Atlanta, Georgia, United States

Pages: 134 - 143

Year of Publication: 1999

ISBN:1-58113-083-X

Also published in ...

Authors

Donghee Lee	Dept. of Information Engineering, Cheju National University, Korea and Department of Computer Engineering, Seoul National University, Seoul 151-742, Korea
Jongmoo Choi	Department of Computer Engineering, Seoul National University, Seoul 151-742, Korea
Jong-Hun Kim	Department of Computer Engineering, Seoul National University, Seoul 151-742, Korea
Sam H. Noh
Sang Lyul Min
Yookun Cho
Chong Sang Kim

Sponsor

SIGMETRICS: ACM Special Interest Group on Measurement and Evaluation

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 13, Downloads (12 Months): 65, Citation Count: 38

Additional Information:

references cited by index terms collaborative colleagues

Tools and Actions:	Request Permissions Review this Article Save this Article to a Binder Display Formats: BibTeX EndNote ACM Ref

DOI Bookmark:	Use this link to bookmark this Article: http://doi.acm.org/10.1145/301453.301487 What is a DOI?

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	1	Elizabeth J. O'Neil , Patrick E. O'Neil , Gerhard Weikum, The LRU-K page replacement algorithm for database disk buffering, Proceedings of the 1993 ACM SIGMOD international conference on Management of data, p.297-306, May 25-28, 1993, Washington, D.C., United States
	2	John T. Robinson , Murthy V. Devarakonda, Data cache management using frequency-based replacement, Proceedings of the 1990 ACM SIGMETRICS conference on Measurement and modeling of computer systems, p.134-142, April 1990, Univ. of Colorado, Boulder, Colorado, United States
	3	Theodore Johnson , Dennis Shasha, 2Q: A Low Overhead High Performance Buffer Management Replacement Algorithm, Proceedings of the 20th International Conference on Very Large Data Bases, p.439-450, September 12-15, 1994
	4	Wolfgang Effelsberg , Theo Haerder, Principles of database buffer management, ACM Transactions on Database Systems (TODS), v.9 n.4, p.560-595, Dec. 1984 [doi>10.1145/1994.2022]
	5	Raymond Ng , Christos Faloutsos , Timos Sellis, Flexible and Adaptable Buffer Management Techniques for Database Management Systems, IEEE Transactions on Computers, v.44 n.4, p.546-560, April 1995 [doi>10.1109/12.376169]
	6	P. Cao, E. W. Felten, and K. Li, "Application- Controlled File Caching Policies," in Proceedings of the Summer 1994 USENIX Conference, pp. 171-182, 1994.
	7	Mary G. Baker , John H. Hartman , Michael D. Kupfer , Ken W. Shirriff , John K. Ousterhout, Measurements of a distributed file system, Proceedings of the thirteenth ACM symposium on Operating systems principles, p.198-212, October 13-16, 1991, Pacific Grove, California, United States
	8	SPEC, "SPEC SDM Release 1.1," Mar. 1992.
	9	Gururaj S. Rao, Performance Analysis of Cache Memories, Journal of the ACM (JACM), v.25 n.3, p.378-395, July 1978 [doi>10.1145/322077.322081]
	10	Jeffrey R. Spirn, Program Behavior: Models and Measurements, Elsevier Science Inc., New York, NY, 1977

CITED BY 38

	Michael K. Bradshaw , Bing Wang , Lixin Gao , Jim Kurose , Prashant Shenoy , Don Towsley , Subhabrata Sen, Periodic broadcast and patching services: implementation, measurement, and analysis in an internet streaming video testbed, Proceedings of the ninth ACM international conference on Multimedia, September 30-October 05, 2001, Ottawa, Canada
	Jongmoo Choi , Sam H. Noh , Sang Lyul Min , Yookun Cho, Towards application/file-level characterization of block references: a case for fine-grained buffer management, ACM SIGMETRICS Performance Evaluation Review, v.28 n.1, p.286-295, June 2000
	Jongmoo Choi , Sam H. Noh , Sang Lyul Min , Eun-Yong Ha , Yookun Cho, Design, Implementation, and Performance Evaluation of a Detection-Based Adaptive Block Replacement Scheme, IEEE Transactions on Computers, v.51 n.7, p.793-800, July 2002
	Ganesh Santhanakrishnan , Ahmed Amer , Panos K. Chrysanthis , Dan Li, GD-GhOST: a goal-oriented self-tuning caching algorithm, Proceedings of the 2004 ACM symposium on Applied computing, March 14-17, 2004, Nicosia, Cyprus
	Prabhat Jain , Srinivas Devadas , Daniel Engels , Larry Rudolph, Software-assisted cache replacement mechanisms for embedded systems, Proceedings of the 2001 IEEE/ACM international conference on Computer-aided design, November 04-08, 2001, San Jose, California
	Stefan Podlipnig , Laszlo Böszörmenyi, A survey of Web cache replacement strategies, ACM Computing Surveys (CSUR), v.35 n.4, p.374-398, December 2003
	Michael K. Bradshaw , Bing Wang , Subhabrata Sen , Lixin Gao , Jim Kurose , Prashant Shenoy , Don Towsley, Periodic broadcast and patching services - implementation, measurement and analysis in an internet streaming video testbed, Multimedia Systems, v.9 n.1, p.78-93, July 2003
	Jike Cui , Mansur. H. Samadzadeh, A new hybrid approach to exploit localities: LRFU with adaptive prefetching, ACM SIGMETRICS Performance Evaluation Review, v.31 n.3, p.37-43, December 2003
	Song Jiang , Xiaodong Zhang, LIRS: an efficient low inter-reference recency set replacement policy to improve buffer cache performance, ACM SIGMETRICS Performance Evaluation Review, v.30 n.1, June 2002
	Li Chen , Song Wang , Elke A. Rundensteiner, Replacement strategies for XQuery caching systems, Data & Knowledge Engineering, v.49 n.2, p.145-175, May 2004
	Yannis Smaragdakis, General adaptive replacement policies, Proceedings of the 4th international symposium on Memory management, October 24-25, 2004, Vancouver, BC, Canada
	Konstantinos Psounis , An Zhu , Balaji Prabhakar , Rajeev Motwani, Modeling correlations in web traces and implications for designing replacement policies, Computer Networks: The International Journal of Computer and Telecommunications Networking, v.45 n.4, p.379-398, 15 July 2004
	Yuanyuan Zhou , Zhifeng Chen , Kai Li, Second-Level Buffer Cache Management, IEEE Transactions on Parallel and Distributed Systems, v.15 n.6, p.505-519, June 2004
	Ali R. Butt , Chris Gniady , Y. Charlie Hu, The performance impact of kernel prefetching on buffer cache replacement algorithms, ACM SIGMETRICS Performance Evaluation Review, v.33 n.1, June 2005
	Song Jiang , Xiaodong Zhang, Making LRU Friendly to Weak Locality Workloads: A Novel Replacement Algorithm to Improve Buffer Cache Performance, IEEE Transactions on Computers, v.54 n.8, p.939-952, August 2005
	Ganesh Santhanakrishnan , Ahmed Amer , Panos K. Chrysanthis, Towards universal mobile caching, Proceedings of the 4th ACM international workshop on Data engineering for wireless and mobile access, June 12-12, 2005, Baltimore, MD, USA
	Li Chen , Song Wang , Elizabeth Cash , Burke Ryder , Ian Hobbs , Elke A. Rundensteiner, A fine-grained replacement strategy for XML query cache, Proceedings of the 4th international workshop on Web information and data management, November 08-08, 2002, McLean, Virginia, USA
	Michael B. Nielsen , Ola Nilsson , Andreas Söderström , Ken Museth, Out-of-core and compressed level set methods, ACM Transactions on Graphics (TOG), v.26 n.4, p.16-es, October 2007
	Yuanyuan Zhou , James Philbin , Kai Li, The Multi-Queue Replacement Algorithm for Second Level Buffer Caches, Proceedings of the General Track: 2002 USENIX Annual Technical Conference, p.91-104, June 25-30, 2001
	Chris Gniady , Ali R. Butt , Y. Charlie Hu, Program-counter-based pattern classification in buffer caching, Proceedings of the 6th conference on Symposium on Opearting Systems Design & Implementation, p.27-27, December 06-08, 2004, San Francisco, CA
	Jong Min Kim , Jongmoo Choi , Jesung Kim , Sam H. Noh , Sang Lyul Min , Yookun Cho , Chong Sang Kim, A low-overhead high-performance unified buffer management scheme that exploits sequential and looping references, Proceedings of the 4th conference on Symposium on Operating System Design & Implementation, p.9-9, October 22-25, 2000, San Diego, California
	Song Jiang , Feng Chen , Xiaodong Zhang, CLOCK-Pro: an effective improvement of the CLOCK replacement, Proceedings of the USENIX Annual Technical Conference 2005 on USENIX Annual Technical Conference, p.35-35, April 10-15, 2005, Anaheim, CA
	Nathan C. Burnett , John Bent , Andrea C. Arpaci-Dusseau , Remzi H. Arpaci-Dusseau, Exploiting Gray-Box Knowledge of Buffer-Cache Management, Proceedings of the General Track: 2002 USENIX Annual Technical Conference, p.29-44, June 10-15, 2002
	H. Seok Jeon , Sam H. Noh, Dynamic buffer cache management scheme based on simple and aggressive prefetching, Proceedings of the 4th conference on 4th Annual Linux Showcase & Conference, Atlanta, p.3-3, October 10-14, 2000, Atlanta, Georgia
	Jongmoo Choi , Sam H. Noh , Sang Lyul Min , Yookun Cho, An implementation study of a detection-based adaptive block replacement scheme, Proceedings of the Annual Technical Conference on 1999 USENIX Annual Technical Conference, p.18-18, June 06-11, 1999, Monterey, California
	André Seifert , Marc H. Scholl, A multi-version cache replacement and prefetching policy for hybrid data delivery environments, Proceedings of the 28th international conference on Very Large Data Bases, p.850-861, August 20-23, 2002, Hong Kong, China
	Nimrod Megiddo , Dharmendra S. Modha, ARC: A Self-Tuning, Low Overhead Replacement Cache, Proceedings of the 2nd USENIX Conference on File and Storage Technologies, March 31-31, 2003, San Francisco, CA
	Lakshmi N. Bairavasundaram , Muthian Sivathanu , Andrea C. Arpaci-Dusseau , Remzi H. Arpaci-Dusseau, X-RAY: A Non-Invasive Exclusive Caching Mechanism for RAIDs, ACM SIGARCH Computer Architecture News, v.32 n.2, p.176, March 2004
	Sorav Bansal , Dharmendra S. Modha, CAR: Clock with Adaptive Replacement, Proceedings of the 3rd USENIX Conference on File and Storage Technologies, March 31-31, 2004, San Francisco, CA
	Sooyong Kang , Heon Y. Yeom, Modeling the Caching Effect in Continuous Media Servers, Multimedia Tools and Applications, v.21 n.3, p.203-224, December 2003
	Weifeng Shi , Shahram Ghandeharizadeh, Controlled Buffer Sharing in Continuous Media Servers, Multimedia Tools and Applications, v.23 n.2, p.131-159, June 2004
	Ozcan Ozturk , Seung Woo Son , Mahmut Kandemir , Mustafa Karakoy, Prefetch throttling and data pinning for improving performance of shared caches, Proceedings of the 2008 ACM/IEEE conference on Supercomputing, November 15-21, 2008, Austin, Texas
	Seung Woo Son , Sai Prashanth Muralidhara , Ozcan Ozturk , Mahmut Kandemir , Ibrahim Kolcu , Mustafa Karakoy, Profiler and compiler assisted adaptive I/O prefetching for shared storage caches, Proceedings of the 17th international conference on Parallel architectures and compilation techniques, October 25-29, 2008, Toronto, Ontario, Canada
	Song Jiang , Kei Davis , Xiaodong Zhang, Coordinated Multilevel Buffer Cache Management with Consistent Access Locality Quantification, IEEE Transactions on Computers, v.56 n.1, p.95-108, January 2007
	Yifeng Zhu , Hong Jiang, RACE: A Robust Adaptive Caching Strategy for Buffer Cache, IEEE Transactions on Computers, v.57 n.1, p.25-40, January 2008
	Jiyong Park , Jaesoo Lee , Saehwa Kim , Seongsoo Hong, Quasistatic shared libraries and XIP for memory footprint reduction in MMU-less embedded systems, ACM Transactions on Embedded Computing Systems (TECS), v.8 n.1, p.1-27, December 2008
	Han-Lin Li , Chia-Lin Yang , Hung-Wei Tseng, Energy-aware flash memory management in virtual memory system, IEEE Transactions on Very Large Scale Integration (VLSI) Systems, v.16 n.8, p.952-964, August 2008
	Chuanjun Zhang , Bing Xue, Divide-and-conquer: a bubble replacement for low level caches, Proceedings of the 23rd international conference on Supercomputing, June 08-12, 2009, Yorktown Heights, NY, USA