Article

Free access

Implementation and performance of application-controlled file caching

Authors:

Edward W. Felten,

Kai LiAuthors Info & Claims

OSDI '94: Proceedings of the 1st USENIX conference on Operating Systems Design and Implementation

Pages 13 - es

Published: 14 November 1994 Publication History

PDF eReader Publisher Site

Abstract

Traditional file system implementations do not allow applications to control file caching replacement decisions. We have implemented two-level replacement, a scheme that allows applications to control their own cache replacement, while letting the kernel control the allocation of cache space among processes. We designed an interface to let applications exert control on replacement via a set of directives to the kernel. This is effective and requires low overhead.

We demonstrate that for applications that do not perform well under traditional caching policies, the combination of good application-chosen replacement strategies, and our kernel allocation policy LRU-SP, can reduce the number of block I/Os by up to 80%, and can reduce the elapsed time by up to 45%. We also show that LRU-SP is crucial to the performance improvement for multiple concurrent applications: LRU-SP fairly distributes cache blocks and offers protection against foolish applications.

References

[1]

{1} 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

[2]

{2} Brian N. Bershad, Craig Chambers, Susan Eggers, Chris Maeda, Dylan MaNamee, Przemystaw Pardyak, Stefan Savage, and Emin Gun Sirer. SPIN -- an extensible microkernel for applicatoin-specific operating system services. Technical Report TR 94-03-03, Dept. of Computer Science and Engineering, University of Washington, 1994.]]

[3]

{3} Pei Cao, Edward W. Felten, and Kai Li. Application-controlled file caching policies. In Conference Proceedings of the USENIX Summer 1994 Technical Conference , pages 171-182, June 1994.]]

Digital Library

[4]

{4} David Cheriton. Effective use of large RAM diskless workstations with the V virtual memory system. Technical report, Dept. of Computer Science, Stanford University, 1987.]]

[5]

{5} 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

[6]

{6} 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.]]

[7]

{7} 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

[8]

{8} Edward G. Coffman, Jr. and Peter J. Denning. Operating Systems Theory. Prentice-Hall, Inc., 1973.]]

Digital Library

[9]

{9} Gregory R. Ganger and Yale N. Patt. The process-flow model: Examing I/O performance from the system's point of view. In Proceedings of SIGMETRICS 1993, pages 86-97, May 1993.]]

Digital Library

[10]

{10} Jim Gray. The Benchmark Handbook. Morgen-Kaufman, San Mateo, Ca., 1991.]]

[11]

{11} Jim Griffioen and Randy Appleton. Reducing file system latency using a predictive approach. In Conference Proceedings of the USENIX Summer 1994 Technical Conference, pages 197-208, June 1994.]]

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 L. Hennessy and David A. Patterson. Computer Organization & Design: The Hardware/Software Interface . Morgan Kaufmann Publishers, Inc., 1994.]]

Digital Library

[14]

{14} 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

[15]

{15} 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

[16]

{16} 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

[17]

{17} Udi Manber and Sun Wu. GLIMPSE: A tool to search through entire file systems. In Conference Proceedings of the USENIX Winter 1994 Technical Conference, pages 23-32, January 1994.]]

Digital Library

[18]

{18} M. McKusick, W. Joy, S. Leffler, and R. Fabry. A fast file system for UNIX. ACM Transactions on Computer Systems, August 1984.]]

Digital Library

[19]

{19} 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.]]

[20]

{20} L. W. McVoy and S. R. Kleiman. Extent-like performance from a UNIX file system. In 1991 Winter USENIX, pages 33-43, 1991.]]

[21]

{21} Jeffrey C. Mogul. A better update policy. In Proceedings of 1994 Summer USENIX, pages 99-111, June 1994.]]

Digital Library

[22]

{22} 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

[23]

{23} 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

[24]

{24} J. K. Ousterhout, H. Da Costa, D. Harrison, J.A. Kunze, M. Kupfer, and J. G. Tompson. A trace-driven analysis of the UNIX 4.2 BSD file system. In Proceedings of the Tenth Symposium on Operating Systems Principles, pages 15-24, December 1985.]]

Digital Library

[25]

{25} Hugo Patterson, Garth Gibson, and M. Satyanarayanan. Transparent informed prefetching. ACM Operating Systems Review, pages 21-34, April 1993.]]

Digital Library

[26]

{26} 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.]]

[27]

{27} 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

[28]

{28} Stuart Sechrest and Yoonho Park. User-level physical memory management for Mach. In Proceedings of the USENIX Mach Symposium, pages 189-199, 1991.]]

[29]

{29} Margo Seltzer, Keith Bostic, Marshall Kirk McKusick, and Carl Staelin. An implementation of a log-structured file system for UNIX. In Proceedings of 1993 Winter USENIX, January 1993.]]

Digital Library

[30]

{30} Alan Jay Smith. Cache memories. ACM Computing Surveys, 14(3):473-530, September 1982.]]

Digital Library

[31]

{31} Michael Stonebraker. Operating system support for database management. Communications of the ACM, v. 24, no. 7, pages 412-418, July 1981.]]

Digital Library

Cited By

Al Maruf HChowdhury MGavrilovska AZadok E(2020)Effectively prefetching remote memory with leapProceedings of the 2020 USENIX Conference on Usenix Annual Technical Conference10.5555/3489146.3489204(843-857)Online publication date: 15-Jul-2020
https://dl.acm.org/doi/10.5555/3489146.3489204
Fedorov VKim JQin MGratz PReddy AJacob B(2017)Speculative paging for future NVM storageProceedings of the International Symposium on Memory Systems10.1145/3132402.3132409(399-410)Online publication date: 2-Oct-2017
https://dl.acm.org/doi/10.1145/3132402.3132409
Cui HTumanov AWei JXu LDai WHaber-Kucharsky JHo QGanger GGibbons PGibson GXing ELazowska ETerry DArpaci-Dusseau RGehrke J(2014)Exploiting iterative-ness for parallel ML computationsProceedings of the ACM Symposium on Cloud Computing10.1145/2670979.2670984(1-14)Online publication date: 3-Nov-2014
https://dl.acm.org/doi/10.1145/2670979.2670984
Show More Cited By

Index Terms

Implementation and performance of application-controlled file caching
1. Software and its engineering
  1. Software organization and properties
    1. Contextual software domains
      1. Operating systems
        File systems management
        Memory management
        Allocation / deallocation strategies
2. Theory of computation
  1. Models of computation
    1. Concurrency
      1. Parallel computing models

Recommendations

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 ...
Application-controlled file caching and prefetching
Application-controlled file caching policies
USTC'94: Proceedings of the USENIX Summer 1994 Technical Conference on USENIX Summer 1994 Technical Conference - Volume 1

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 ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

OSDI '94: Proceedings of the 1st USENIX conference on Operating Systems Design and Implementation

November 1994

228 pages

Sponsors

SIGOPS: ACM Special Interest Group on Operating Systems
USENIX Assoc: USENIX Assoc
IEEE Technical Committee on Operating Systems (TCOS)

Publisher

USENIX Association

United States

Publication History

Published: 14 November 1994

Check for updates

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

50
Total Citations
View Citations
242
Total Downloads

Downloads (Last 12 months)43
Downloads (Last 6 weeks)7

Reflects downloads up to 25 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Al Maruf HChowdhury MGavrilovska AZadok E(2020)Effectively prefetching remote memory with leapProceedings of the 2020 USENIX Conference on Usenix Annual Technical Conference10.5555/3489146.3489204(843-857)Online publication date: 15-Jul-2020
https://dl.acm.org/doi/10.5555/3489146.3489204
Fedorov VKim JQin MGratz PReddy AJacob B(2017)Speculative paging for future NVM storageProceedings of the International Symposium on Memory Systems10.1145/3132402.3132409(399-410)Online publication date: 2-Oct-2017
https://dl.acm.org/doi/10.1145/3132402.3132409
Cui HTumanov AWei JXu LDai WHaber-Kucharsky JHo QGanger GGibbons PGibson GXing ELazowska ETerry DArpaci-Dusseau RGehrke J(2014)Exploiting iterative-ness for parallel ML computationsProceedings of the ACM Symposium on Cloud Computing10.1145/2670979.2670984(1-14)Online publication date: 3-Nov-2014
https://dl.acm.org/doi/10.1145/2670979.2670984
Ding WZhang YKandemir MSon S(2013)Compiler-directed file layout optimization for hierarchical storage systemsScientific Programming10.1155/2013/16758121:3-4(65-78)Online publication date: 1-Jul-2013
https://dl.acm.org/doi/10.1155/2013/167581
Ding WZhang YKandemir MSon SHollingsworth J(2012)Compiler-directed file layout optimization for hierarchical storage systemsProceedings of the International Conference on High Performance Computing, Networking, Storage and Analysis10.5555/2388996.2389052(1-11)Online publication date: 10-Nov-2012
https://dl.acm.org/doi/10.5555/2388996.2389052
Kandemir MMuralidhara SKarakoy MSon SHariri SKeahey K(2010)Computation mapping for multi-level storage cache hierarchiesProceedings of the 19th ACM International Symposium on High Performance Distributed Computing10.1145/1851476.1851498(179-190)Online publication date: 21-Jun-2010
https://dl.acm.org/doi/10.1145/1851476.1851498
Rafique MButt ANikolopoulos DRamirez ABiliardi GGschwind M(2008)Dma-based prefetching for i/o-intensive workloads on the cell architectureProceedings of the 5th conference on Computing frontiers10.1145/1366230.1366236(23-32)Online publication date: 5-May-2008
https://dl.acm.org/doi/10.1145/1366230.1366236
Li CShen KPapathanasiou A(2007)Competitive prefetching for concurrent sequential I/OACM SIGOPS Operating Systems Review10.1145/1272998.127301741:3(189-202)Online publication date: 21-Mar-2007
https://dl.acm.org/doi/10.1145/1272998.1273017
Li CShen KPapathanasiou A(2007)Competitive prefetching for concurrent sequential I/OProceedings of the 2nd ACM SIGOPS/EuroSys European Conference on Computer Systems 200710.1145/1272996.1273017(189-202)Online publication date: 21-Mar-2007
https://dl.acm.org/doi/10.1145/1272996.1273017
Li CShen K(2005)Managing prefetch memory for data-intensive online serversProceedings of the 4th conference on USENIX Conference on File and Storage Technologies - Volume 410.5555/1251028.1251047(19-19)Online publication date: 13-Dec-2005
https://dl.acm.org/doi/10.5555/1251028.1251047
Show More Cited By

View Options

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Login options

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

Full Access

Get this Publication

Media

Figures

Other

Tables

View Table of Contents