Article

Free access

Exploiting the non-determinism and asynchrony of set iterators to reduce aggregate file I/O latency

Author:

David C. SteereAuthors Info & Claims

SOSP '97: Proceedings of the sixteenth ACM symposium on Operating systems principles

Pages 252 - 263

https://doi.org/10.1145/268998.266705

Published: 01 October 1997 Publication History

PDF eReader

References

[1]

ARNOLD, K., AND GOSLING, J. The Java Programming Language. The Java Series. Addison-Wesley, 1996, pp. 221-223.]]

Digital Library

Google Scholar

[2]

BACH, M. J. The Design of the Unix Operating System. Prentice Hall, Inc. A division of Simon & Schuster, Englewood Cliffs, New Jersey 07632,1986. Chapter 3: The Buffer Cache.]]

Digital Library

Google Scholar

[3]

BAENTSCH, M., BAUM, L., MOLTER, G., ROTHKUGEL, S., ANt) STURM, P. Enhancing the web infrastructure- from caching to replication. IEEE Internet Computing 1, 2 (Apr. 1997). Also available as http://www, computer, org/intemet/9702/baentsch9702.htm.]]

Digital Library

Google Scholar

[4]

BAKER, M. G., HARTMAN, J. H., KUPFER, M. D., SHIRRIFF, K., AND OUSTERHOUT, J. K. Measurements of a distributed file system. In Proceedings of the 13th ACM Symposium on Operating Systents Principles (October 1991).]]

Digital Library

Google Scholar

[5]

BOWMAN, M., SPASOJEVIC, M., AND SPECTER, A. File system support for search. Transarc white paper, 1994.]]

Google Scholar

[6]

CAO, P., FELTEN, E. W., KARLIN, A., AND LI, K. A study of inte. grated prefetching and caching strategies. In Proceedings of the ACM SIGMETRICS Conference on Measurement and Modeling of Com, puterSystems (May 1995).]]

Digital Library

Google Scholar

[7]

CAO, P., F~LTEN, E. W., AND LI, K. Implementation and performance of application-controlled file caching, In Proceedings of the First USENIX Symposium on Operating Systems Design and hnple, mentation (November 1994).]]

Digital Library

Google Scholar

[8]

CUREWITZ, K. M., KRISHNAN, P., AND ViTTER, J. $. Practical prefetching via data compression. In Proceedings of the 1993 ACM Conf. on Management of Data (SlGMOD) (May 1993).]]

Digital Library

Google Scholar

[9]

DUSKA, B., AND MARWOOD, D, Squid proxy analysis, Appeared in the Second Web Caching Workshop, Boulder, Colorado, Juno 1997. http:lfircache.nlanr, netlCachelWorkshop971, 1997, Also avail., able as http'd/www, cs.ubc.calspider/marwood!ProjectslSPAIReportl Report. html.]]

Google Scholar

[10]

GIFFORD, D. K., JOUVELOT, P., SHELDON, M. A., AND O'TOOLE, JR., J. W. Semantic file systems. In Proceedings of the 13th ACM Symposium on Operating Systems Principles (October 1991).]]

Digital Library

Google Scholar

[11]

GLASSMAN, $. A caching relay for the world wide web, Computer Networks and lSDN Systems 27, 2 (Nov. 1994). Special Issue: selected papers from the Fast International WWW Conference.]]

Digital Library

Google Scholar

[12]

GRIFFIOEN, J., AND APPLETON, R. The design, implementa{lon, and evaluation of a predictive caching file system. Tech. Rep, CS-264., 96, Department of Computer Science, University of Kentucky, Juno 1996.]]

Google Scholar

[13]

GRIMSHAW, A. S., AND LOYOT, E. C., J. ELFS: Object-oriented extensible file systems. Tech. Rep. TR-91-14, Computer Science De., partment, University of V'uginia, July 1991.]]

Digital Library

Google Scholar

[14]

HOWARD, J., KAZAR, M., MENEES, S., NICHOLS, D., SATYA- NARAYANAN, M., SIDE~OTHAM, R., AND WEST, M. Scale and performance in a distributed file system. ACM Trans. Compttt. Syst. 6, 1 (Feb. 1988).]]

Digital Library

Google Scholar

[15]

-JACOBSEN, V. Congestion avoidance control. In Proceedings of the SIGCOMM '88 Conference on Comuunications Archltectures and Protocols (1988).]]

Google Scholar

[16]

JOSEPH, A. D., DELESPINASSE, A. F., TAUBER, J. A., GIFFORD, D. K., AND KAASHOEK, M. F. Rover: A toolkit for mobile information access. In Proceedings of the 15th ACM Symposium on Operating Systems Principles (December 1995).]]

Digital Library

Google Scholar

[17]

JoY, W. An introduction to the C shell. In Unix User~ Manual, Sup. plementary Documents, M. J. Karels and S. J. Leffler, Eds. Computer Science Division, Department o fElectrical Engineering and Computer Science, University of California, 1980.]]

Google Scholar

[18]

KIMBREL, T., TOKMINS, A., PATTERSON, R. H., BERStlAD, B, CAO, P., FELTEN, E. W., GIBSON, G. A, KARLIN, A, R., AND LI, K. A trace-driven comparison of algorithms for parallel prefetchlng and caching. In Proceedings of the Second USENiX $ymposhttn on Operating Systems Design and Implementation (Oct. 1996).]]

Digital Library

Google Scholar

[19]

KLEIMAN, S. Vnodes: An architecture for multiple file sys{em types in Sun UNIX. In Summer USENIX Conference Proceedings (Atlanta, 1986).]]

Google Scholar

[20]

KOTZ, D. Disk-directed I/O for MiMD multiprocessors, In Proceedings of the First USENIX Symposium on Operating $ystents Destgn and implementation (November 1994).]]

Digital Library

Google Scholar

[21]

KOTZ, D., AND ELLIS, C. Practical prefetching techniques for paral, lel file systems. In Proceedings of the 1st International Conference on Parallel and Distributed Information Systems (Miami Beach, Florida, Dee. 1992).]]

Digital Library

Google Scholar

[22]

KUENNINO, G. H. The design of the SEER predictive caching system. In Proceedings of the Workshop on Mobile Computing Systems and Applications (Santa Cruz, CA, Dee. 1994).]]

Google Scholar

[23]

LISKOV, B., AND GUTTAO, J. Abstraction and Specification hi Pro, gram Development. The Mrr EECS Series. MIT Press, Cambridge, MA; McGraw-Hill, New York, 1986.]]

Digital Library

Google Scholar

[24]

MANBER, U., AND WU, S. Glimpse: A tool to search through entire file systems. In Winter USENIX Conference Proceedings (1994). Also available as The University of Arizona Department of Computer Science Technical Report TR 93-34.]]

Digital Library

Google Scholar

[25]

MOWRY, T. C., DEMKE, A. K., AND KRIEGER, O. Automatic compiler-inserted I/O prefetching for out-of-core applications. In Proceedings of the Second USENIX Symposium on Operating Systems Design and hnplementation (Oct. 1996).]]

Digital Library

Google Scholar

[26]

NELSON, M., WELCH, B., AND OUSTERHOUT, J. Caching in the Sprite Network File System. ACM Trans. Comput. Syst. 6, 1 (Feb. 19{}8).]]

Digital Library

Google Scholar

[27]

OUSTERHOUT, J. K., DA COSTA, H., HARRISON, U., KUNZE, J. A., KUPFER, M., AND THOMPSON, J. G. A trace-driven analysis of the UNIX 4.2 BSD file system. In Proceedings ofthe IOthACM Symposium on Operating Systems Principles (December 1985).]]

Digital Library

Google Scholar

[28]

PADMANABHAN, V. N., AND MOGUL, J.C. Using predictive prefetching to improve world wide web latency. ACM $IGCOMM Computer Communication Review 26, 3 (July 1996).]]

Digital Library

Google Scholar

[29]

PAXTERSON, R. H., GIBSON, O. A., GINTINa, E., STODOLSKY, D., AND ZELENKA, J. Informed prefetchingand caching. In Proceedings of the 15th ACM Symposium on Operating System Principles (Dee. 1995).]]

Digital Library

Google Scholar

[30]

Pu, C., BLACK, A., COWAN, C., WALPOLE, J., AND CONSEL, C. Microlanguages for operating system specialization. In Proceedings of the SlGPLAN Workshop on Domain Specific Languages (Paris, France, Jan. 1997).]]

Google Scholar

[31]

SANDBERO, R., GOLDBERG, D., KLEIMAN, S., WALSH, D., AND LYON, B. Design and implementation of the Sun Network File System. in Summer USENIX Conference Proceedings, Portland (1985).]]

Google Scholar

[32]

SATYANARAYANAN, M. A study of file sizes and functional lifetimes. In Proceedings of the 8th ACM Symposium on Operating Systems Principles (December 1981).]]

Digital Library

Google Scholar

[33]

SHAW, M., WULF, W. A., AND LONDON, R.L. Abstraction and verification in Alphard: Defining and specifying iteration and generators. Commun. ACM 20, 8 (Mar. 1977). Reprinted in Tutorial: Progmmnfng Language Design, text for IEEE Tutorial by Anthony I. Wasserman, 1980, pp. 145-155.]]

Digital Library

Google Scholar

[34]

SMITH, A. J. Disk cache- miss ratio analysis and design considerations. ACM Trans. Comput. $yst. 3, 3 (Aug. 1985).]]

Digital Library

Google Scholar

[35]

SPASOJEVIC, M., AND SATYANARAYANAN, M. A usage profile and evaluation of a wide-area distributed file system. In Winter Usenix Conference Proceedings (San Francisco, CA, 1994).]]

Digital Library

Google Scholar

[36]

STAEHLI, R. Quality of Service Specification for Resource Management in Multimedia Systems. Phi) thesis, Department of Computer Science and Engineering, Oregon Graduate Institute, 1996. Available as ftp:licse.ogi.edulpubltech-reports!1996196-TH-OO l .ps.gz.]]

Digital Library

Google Scholar

[37]

STEERE, D., KISTLER, J., AND SATYANARAYANAN, M. Efficient user-level file cache management on the Sun vnodeinterface. In Summer USENIX Conference Proceedings (Anaheim, CA, 1990).]]

Google Scholar

[38]

STEERE, D. C. Using Dynamic Sets to Reduce theAggregateLatency of Data Access. Phi) thesis, School of Computer Science, Carnegie Mellon University, 1997. Available as technical report CMU-CS-94- 215.]]

Digital Library

Google Scholar

[39]

TAIT, C. D., AND DUCHAMP, D. Detection and exploitation of file working sets. In Proceedings of the ll th International Conference on Distributed Corn puting Systems (Arlington, TX, 1991).]]

Crossref

Google Scholar

[40]

WEBCOMPASS 1.0. Quarterdeck, Corp. Marina del Ray, CA. (800) 683-6696. Additional information is available at http'.//www, quarterdeck.com.]]

Google Scholar

[41]

WINO, J., AND STEERE, D. Specifying weaksets. In Proceedings of the International Conference on Distn'buted Computer Systems (Van. couver, June 1995). Also available as Carnegie Mellon University School of Computer Science technical report CMU-CS-94-194.]]

Digital Library

Google Scholar

Cited By

View all

Chen MHildebrand DNelson HSaluja JSubramony AZadok EKuenning GWaldspurger C(2017)vNFSProceedings of the 15th Usenix Conference on File and Storage Technologies10.5555/3129633.3129661(301-314)Online publication date: 27-Feb-2017
https://dl.acm.org/doi/10.5555/3129633.3129661
Chen MBangera GHildebrand DJalia FKuenning GNelson HZadok E(2017)vNFSACM Transactions on Storage10.1145/311621313:3(1-24)Online publication date: 28-Sep-2017
https://dl.acm.org/doi/10.1145/3116213
Zhang XDavis KJiang S(2012)Opportunistic Data-driven Execution of Parallel Programs for Efficient I/O ServicesProceedings of the 2012 IEEE 26th International Parallel and Distributed Processing Symposium10.1109/IPDPS.2012.39(330-341)Online publication date: 21-May-2012
https://dl.acm.org/doi/10.1109/IPDPS.2012.39
Show More Cited By

Index Terms

Exploiting the non-determinism and asynchrony of set iterators to reduce aggregate file I/O latency
1. Software and its engineering
  1. Software organization and properties
    1. Contextual software domains
      1. Operating systems
        Communications management
        Input / output
    2. Software system structures
      1. Distributed systems organizing principles
2. Theory of computation
  1. Models of computation
    1. Concurrency
      1. Parallel computing models

Recommendations

Exploiting the non-determinism and asynchrony of set iterators to reduce aggregate file I/O latency
Exploiting Lustre File Joining for Effective Collective IO
CCGRID '07: Proceedings of the Seventh IEEE International Symposium on Cluster Computing and the Grid

Lustre is a parallel file system that presents high aggregated IO bandwidth by striping file extents across many storage devices. However, our experiments indicate excessively wide striping can cause performance degradation. Lustre supports an ...
A log file service exploiting write-once storage

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

SOSP '97: Proceedings of the sixteenth ACM symposium on Operating systems principles

October 1997

303 pages

ISBN:0897919165

DOI:10.1145/268998

Chairmen:
Michel Banâtre
IRISA/INRIA
,
Henry Levy
Univ. of Washington, Seattle
,
Editor:
William M. Waite
Univ. of Colorado, Boulder

ACM SIGOPS Operating Systems Review Volume 31, Issue 5
Dec. 1997
301 pages
ISSN:0163-5980
DOI:10.1145/269005
Chairmen:
Michel Banâtre
IRISA/INRIA
,
Henry Levy
Univ. of Washington, Seattle
,
Editor:
William M. Waite
Univ. of Colorado, Boulder
Issue’s Table of Contents

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 01 October 1997

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Qualifiers

Article

Conference

SOSP97

Sponsor:

SIGOPS
INRIA

SOSP97: Sixteenth ACM Symposium on Operating Systems Principles

October 5 - 8, 1997

Saint Malo, France

Acceptance Rates

Overall Acceptance Rate 174 of 961 submissions, 18%

Upcoming Conference

SOSP '25

Sponsor:
sigops

ACM SIGOPS 31st Symposium on Operating Systems Principles

October 13 - 16, 2025

Seoul , Republic of Korea

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

21
Total Citations
View Citations
495
Total Downloads

Downloads (Last 12 months)68
Downloads (Last 6 weeks)13

Reflects downloads up to 19 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

View all

Chen MHildebrand DNelson HSaluja JSubramony AZadok EKuenning GWaldspurger C(2017)vNFSProceedings of the 15th Usenix Conference on File and Storage Technologies10.5555/3129633.3129661(301-314)Online publication date: 27-Feb-2017
https://dl.acm.org/doi/10.5555/3129633.3129661
Chen MBangera GHildebrand DJalia FKuenning GNelson HZadok E(2017)vNFSACM Transactions on Storage10.1145/311621313:3(1-24)Online publication date: 28-Sep-2017
https://dl.acm.org/doi/10.1145/3116213
Zhang XDavis KJiang S(2012)Opportunistic Data-driven Execution of Parallel Programs for Efficient I/O ServicesProceedings of the 2012 IEEE 26th International Parallel and Distributed Processing Symposium10.1109/IPDPS.2012.39(330-341)Online publication date: 21-May-2012
https://dl.acm.org/doi/10.1109/IPDPS.2012.39
Anastasiadis SWickremesinghe RChase J(2009)Rethinking FTPACM Transactions on Storage10.1145/1480439.14804424:4(1-27)Online publication date: 9-Feb-2009
https://dl.acm.org/doi/10.1145/1480439.1480442
Brim MMiller B(2009)Group file operations for scalable tools and middleware2009 International Conference on High Performance Computing (HiPC)10.1109/HIPC.2009.5433223(69-78)Online publication date: Dec-2009
https://doi.org/10.1109/HIPC.2009.5433223
Petrou DGibson GGanger GKramer W(2005)Scheduling speculative tasks in a compute farmProceedings of the 2005 ACM/IEEE conference on Supercomputing10.1109/SC.2005.62Online publication date: 12-Nov-2005
https://dl.acm.org/doi/10.1109/SC.2005.62
Thereska ESchindler JBucy JSalmon BLumb CGanger G(2004)A framework for building unobtrusive disk maintenance applicationsProceedings of the 3rd USENIX conference on File and storage technologies10.5555/1973374.1973390(16-16)Online publication date: 31-Mar-2004
https://dl.acm.org/doi/10.5555/1973374.1973390
Anastasiadis SWickremesinghe RChase J(2004)CircusProceedings of the 3rd USENIX conference on File and storage technologies10.5555/1973374.1973389(15-15)Online publication date: 31-Mar-2004
https://dl.acm.org/doi/10.5555/1973374.1973389
Anastasiadis SWickremesinghe RChase J(2004)Circus: Opportunistic Block Reordering for Scalable Content ServersProceedings of the 3rd USENIX Conference on File and Storage Technologies10.5555/1096673.1096700(201-212)Online publication date: 31-Mar-2004
https://dl.acm.org/doi/10.5555/1096673.1096700
Petrou DGanger GGibson GFeautrier PGoodman JSeznec A(2004)Cluster scheduling for explicitly-speculative tasksProceedings of the 18th annual international conference on Supercomputing10.1145/1006209.1006256(336-345)Online publication date: 26-Jun-2004
https://dl.acm.org/doi/10.1145/1006209.1006256
Show More Cited By

View Options

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Login options

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

Cited By

Index Terms

Recommendations

Exploiting the non-determinism and asynchrony of set iterators to reduce aggregate file I/O latency

Exploiting Lustre File Joining for Effective Collective IO

A log file service exploiting write-once storage