More Web Proxy on the site http://driver.im/

Article

Application-controlled file caching policies

Authors:

Edward W. Felten,

Kai LiAuthors Info & Claims

USTC'94: Proceedings of the USENIX Summer 1994 Technical Conference on USENIX Summer 1994 Technical Conference - Volume 1

Page 11

Published: 06 June 1994 Publication History

Abstract

We consider how to improve the performance of file caching by allowing user-level control over file cache replacement decisions. We use two-level cache management: the kernel allocates physical pages to individual applications (allocation), and each application is responsible for deciding how to use its physical pages (replacement). Previous work on two-level memory management has focused on replacement, largely ignoring allocation.

The main contribution of this paper is our solution to the allocation problem. Our solution allows processes to manage their own cache blocks, while at the same time maintains the dynamic allocation of cache blocks among processes. Our solution makes sure that good user-level policies can improve the file cache hit ratios of the entire system over the existing replacement approach. We evaluate our scheme by trace-based simulation, demonstrating that it leads to significant improvements in hit ratios for a variety of applications.

References

[1]

[1] Rafael Alonso and Andrew W. Appel. An Advisor for Flexible Working Sets. In Proceedings of the 1990 ACM SIGMETRICS Conference on Measurement and Modeling of Computer Systems, pages 153-162, May 1990.

Digital Library

[2]

[2] Mary Baker, John H. Hartman, Michael D. Kupfer, Ken W. Shirriff, and John Ousterhout. Measurements of a Distributed File System. In Proceedings of the Thirteenth Symposium on Operating Systems Principles, pages 198-211, October 1991.

Digital Library

[3]

[3] Andrew Braunstein, Mark Riley, and John Wilkes. Improving the efficiency of UNIX file buffer caches. In Proceedings of the Eleventh Symposium on Operating Systems Principles, pages 71-82, 1989.

Digital Library

[4]

[4] Pei Cao. Analysis of Two-Level Block Replacement. Working Paper, January 1994.

[5]

[5] David Cheriton. Effective Use of Large RAM Diskless Workstations with the V Virtual Memory System. Technical report, Dept. of Computer Science, Stanford University, 1987.

[6]

[6] David R. Cheriton. The Unified Management of Memory in the V Distributed System. Draft, 1988.

[7]

[7] Khien-Mien Chew, A. Jyothy Reddy, Theodore H. Romer, and Avi Silberschatz. Kernel Support for Recoverable-Persistent Virtual Memory. Technical Report TR-93-06, University of Texas at Austin, Dept. of Computer Science, February 1993.

Digital Library

[8]

[8] Hong-Tai Chou and David J. DeWitt. An Evaluation of Buffer Management Strategies for Relational Database Systems. In Proceedings of the Eleventh International Conference on Very Large Databases, pages 127-141, August 1985.

[9]

[9] Eric Cooper, Scott Nettles, and Indira Subramanian. Improving the Performance of SML Garbage Collection using Application-Specific Virtual Memory Management. In Proceedings of the 1992 ACM Conference on LISP and Functional Programming, June 1992.

Digital Library

[10]

[10] Kenneth M. Curewitz, P. Krishnan, and Jeffrey Scott Vitter. Practical Prefetching via Data Compression. In Proc. 1993 ACM-SIGMOD Conference on Management of Data, pages 257-266, May 1993.

Digital Library

[11]

[11] Edward G. Coffman, Jr. and Peter J. Denning. Operating Systems Theory. Prentice-Hall, Inc., 1973.

Digital Library

[12]

[12] Kieran Harty and David R. Cheriton. Application-Controlled Physical Memory using External Page-Cache Management. In The Fifth International Conference on Architectural Support for Programming Languages and Operating Systems, pages 187-197, October 1992.

Digital Library

[13]

[13] John H. Howard, Michael Kazar, Sherri G. Menees, David A. Nichols, M. Satyanarayanan, Robert N. Sidebotham, and Michael J. West. Scale and Performance in a Distributed File System. ACM Transactions on Computer Systems, pages 6(1):51-81, February 1988.

Digital Library

[14]

[14] James J. Kistler and M. Satyanarayanan. Disconnected Operation in the Coda File System. ACM Transactions on Computer Systems, pages 6(1):1-25, February 1992.

Digital Library

[15]

[15] Keith Krueger, David Loftesness, Amin Vahdat, and Tom Anderson. Tools for the Development of Application-Specific Virtual Memory Management. In OOPSLA '93 Conference Proceedings, pages 48-64, October 1993.

Digital Library

[16]

[16] H. Levy and P. Lipman. Virtual Memory Management in the VAX/VMS Operating System. IEEE Computer, pages 35-41, March 1982.

Digital Library

[17]

[17] M. Mckusick, W. Joy, S. Leffler, and R. Fabry. A Fast File System for UNIX. ACM Transactions on Computer Systems, August 1984.

Digital Library

[18]

[18] Dylan McNamee and Katherine Armstrong. Extending The Mach External Pager Interface To Accommodate User-Level Page Replacement Policies. In Proceedings of the USENIX Association Mach Workshop, pages 17-29, 1990.

[19]

[19] L. W. McVoy and S. R. Kleiman. Extent-like Performance from a UNIX File System. In 1991 Winter USENIX, pages 33-43, 1991.

[20]

[20] Michael N. Nelson, Brent B. Welch, and John K. Ousterhout. Caching in the Sprite File System. ACM Transactions on Computer Systems, pages 6(1):134-154, February 1988.

Digital Library

[21]

[21] Elizabeth J. O'Neil, Patrick E. O'Neil, and Gerhard Weikum. The LRU-K Page Replacement Algorithm For Database Disk Buffering. In Proc. 1993 ACM-SIGMOD Conference on Management of Data, pages 297-306, May 1993.

Digital Library

[22]

[22] Hugo Patterson, Garth Gibson, and M. Satyanarayanan. Transparent Informed Prefetching. ACM Operating Systems Review, pages 21-34, April 1993.

Digital Library

[23]

[23] R. Sandberg, D. Boldberg, S. Kleiman, D. Walsh, and B. Lyon. Design and Implementation of the Sun Network Filesystem. In Summer Usenix Conference Proceedings, pages 119-130, June 1985.

[24]

[24] M. D. Schroeder, D. K. Gifford, and R. M. Needham. A caching file system for a programmer's workstation. ACM Operating Systems Review, pages 19(5):35-50, December 1985.

Digital Library

[25]

[25] Stuart Sechrest and Yoonho Park. User-Level Physical Memory Management for Mach. In Proceedings of the USENIX Mach Symposium, pages 189-199, 1991.

[26]

[26] Michael Stonebraker. Operating System Support for Database Management. Communications of the ACM, v. 24, no. 7, pages 412-418, July 1981.

Digital Library

[27]

[27] Indira Subramanian. Managing discardable pages with an external pager. In Proceedings of the USENIX Mach Symposium, pages 77-85, October 1990.

[28]

[28] The Postgres Group. POSTGRES Version 4.1 Release Notes. Technical report, Electronics Research Lab, University of California, Berkeley, February 1993.

[29]

[29] M. Young, A. Tevanian, R. Rashid, D. Golub, J. Eppinger, J. Chew, W. Bolosky, D. Black, and R. Baron. The Duality of Memory and Communication in the Implementation of a Multiprocessor Operating System. In Proceedings of the Eleventh Symposium on Operating Systems Principles , pages 63-76, November 1987.

Digital Library

Cited By

Agrawal KBender MDas RKuszmaul WPeserico EScquizzato MAgrawal KLee I(2022)Online Parallel Paging with Optimal MakespanProceedings of the 34th ACM Symposium on Parallelism in Algorithms and Architectures10.1145/3490148.3538577(205-216)Online publication date: 11-Jul-2022
https://dl.acm.org/doi/10.1145/3490148.3538577
Agrawal KBender MDas RKuszmaul WPeserico EScquizzato MMarx D(2021)Tight bounds for parallel paging and green pagingProceedings of the Thirty-Second Annual ACM-SIAM Symposium on Discrete Algorithms10.5555/3458064.3458244(3022-3041)Online publication date: 10-Jan-2021
https://dl.acm.org/doi/10.5555/3458064.3458244
Agrawal KBender MDas RKuszmaul WPeserico EScquizzato MScheideler CSpear M(2020)Green Paging and Parallel PagingProceedings of the 32nd ACM Symposium on Parallelism in Algorithms and Architectures10.1145/3350755.3400231(493-495)Online publication date: 6-Jul-2020
https://dl.acm.org/doi/10.1145/3350755.3400231
Show More Cited By

Index Terms

Application-controlled file caching policies

Recommendations

Application-controlled file caching and prefetching
Implementation and performance of integrated application-controlled file caching, prefetching, and disk scheduling

As the performance gap between disks and micropocessors continues to increase, effective utilization of the file cache becomes increasingly immportant. Application-controlled file caching and prefetching can apply application-specific knowledge to ...
Adaptive insertion policies for high performance caching
ISCA '07: Proceedings of the 34th annual international symposium on Computer architecture

The commonly used LRU replacement policy is susceptible to thrashing for memory-intensive workloads that have a working set greater than the available cache size. For such applications, the majority of lines traverse from the MRU position to the LRU ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Guide Proceedings

USTC'94: Proceedings of the USENIX Summer 1994 Technical Conference on USENIX Summer 1994 Technical Conference - Volume 1

June 1994

222 pages

Publisher

USENIX Association

United States

Publication History

Published: 06 June 1994

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

34
Total Citations
View Citations
24
Total Downloads

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

Reflects downloads up to 14 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Agrawal KBender MDas RKuszmaul WPeserico EScquizzato MAgrawal KLee I(2022)Online Parallel Paging with Optimal MakespanProceedings of the 34th ACM Symposium on Parallelism in Algorithms and Architectures10.1145/3490148.3538577(205-216)Online publication date: 11-Jul-2022
https://dl.acm.org/doi/10.1145/3490148.3538577
Agrawal KBender MDas RKuszmaul WPeserico EScquizzato MMarx D(2021)Tight bounds for parallel paging and green pagingProceedings of the Thirty-Second Annual ACM-SIAM Symposium on Discrete Algorithms10.5555/3458064.3458244(3022-3041)Online publication date: 10-Jan-2021
https://dl.acm.org/doi/10.5555/3458064.3458244
Agrawal KBender MDas RKuszmaul WPeserico EScquizzato MScheideler CSpear M(2020)Green Paging and Parallel PagingProceedings of the 32nd ACM Symposium on Parallelism in Algorithms and Architectures10.1145/3350755.3400231(493-495)Online publication date: 6-Jul-2020
https://dl.acm.org/doi/10.1145/3350755.3400231
Hou BChen F(2017)GDS-LCACM Transactions on Storage10.1145/314937413:4(1-33)Online publication date: 24-Nov-2017
https://dl.acm.org/doi/10.1145/3149374
Jiang SDing XXu YDavis K(2013)A Prefetching Scheme Exploiting both Data Layout and Access History on DiskACM Transactions on Storage10.1145/25080109:3(1-23)Online publication date: 1-Aug-2013
https://dl.acm.org/doi/10.1145/2508010
López-Ortiz ASalinger AGoldwasser S(2012)Paging for multi-core shared cachesProceedings of the 3rd Innovations in Theoretical Computer Science Conference10.1145/2090236.2090246(113-127)Online publication date: 8-Jan-2012
https://dl.acm.org/doi/10.1145/2090236.2090246
Kandemir MSon SKarakoy M(2008)Improving I/O performance of applications through compiler-directed code restructuringProceedings of the 6th USENIX Conference on File and Storage Technologies10.5555/1364813.1364824(1-16)Online publication date: 26-Feb-2008
https://dl.acm.org/doi/10.5555/1364813.1364824
Zhu YJiang H(2008)RACEIEEE Transactions on Computers10.1109/TC.2007.7078857:1(25-40)Online publication date: 1-Jan-2008
https://dl.acm.org/doi/10.1109/TC.2007.70788
Ding XJiang SChen FDavis KZhang X(2007)DiskSeen2007 USENIX Annual Technical Conference on Proceedings of the USENIX Annual Technical Conference10.5555/1364385.1364405(1-14)Online publication date: 17-Jun-2007
https://dl.acm.org/doi/10.5555/1364385.1364405
Jiang SDavis KZhang X(2007)Coordinated Multilevel Buffer Cache Management with Consistent Access Locality QuantificationIEEE Transactions on Computers10.5555/1191544.119169956:1(95-108)Online publication date: 1-Jan-2007
https://dl.acm.org/doi/10.5555/1191544.1191699
Show More Cited By

View Options

View options

Media

Figures

Other

Tables

View Table of Contents