Take a look at the new version of this page: [ beta version ]. Tell us what you think.

ABSTRACT

An algorithm is proposed for the purpose of optimizing the availability of files to an operating system prior to their being required during execution by a running system. This algorithm is a first step in optimizing speed using a prefetching scheme based upon previous history of access. The technique described utilizes a mathematically based approach considering the actual occurrence of file application patterns. This technique was defined for pattern matching, and prefetching of files is indeed a pattern matching problem. We utilize the technique of Finite Inductive Sequences which is defined within the body of this paper. We also note that the formulation for the approach is defined and included, actual data for comparisons are still not completed as of the writing of this paper. However, we believe that the richness of this approach will be useful in considering how to prefetch multiple files for multiple applications under one system.

REFERENCES

• 1: J. Ousterhout, "Why aren't operating systems getting faster as fast as hardware?," Proceedings of the 1990 USENIX Summer Technical Conference, pp. 247--256, June 1990.
• 2: Hui Lei , Dan Duchamp, An analytical approach to file prefetching, Proceedings of the annual conference on USENIX Annual Technical Conference, p.21-21, January 06-10, 1997, Anaheim, California
• 3: A. Amer, and D. D. E. Long, "Noah: Low-cost file access prediction through pairs," Proceedings of the 20th International Performance, Computing, and Communications Conference, pp. 27--33, April 2001.
• 4: I-Cheng K. Chen , John T. Coffey , Trevor N. Mudge, Analysis of branch prediction via data compression, Proceedings of the seventh international conference on Architectural support for programming languages and operating systems, p.128-137, October 01-04, 1996, Cambridge, Massachusetts, United States
• 5: Kenneth M. Curewitz , P. Krishnan , Jeffrey Scott Vitter, Practical prefetching via data compression, Proceedings of the 1993 ACM SIGMOD international conference on Management of data, p.257-266, May 25-28, 1993, Washington, D.C., United States
• 6: A. Amer , D. D. E. Long , J.-F. Paris , R. C. Burns, File access prediction with adjustable accuracy, Proceedings of the Performance, Computing, and Communications Conference, 2002. on 21st IEEE International, p.131-140, April 03-05, 2002 [doi>10.1109/IPCCC.2002.995144]
• 7: H. Case, and P. S. Fisher, "Long Term Memory Modules," Bulletin of Mathematical Biology, 46(2): 295--326, Springer New York, March 1984.
• 8: Lily Mummert , Mahadev Satyanarayanan, Long Term Distributed File Reference Tracing: Implementation and Experience, Carnegie Mellon University, Pittsburgh, PA, 1994
• 9: Drew Roselli, Characteristics of File System Workloads, University of California at Berkeley, Berkeley, CA, 1998
• 10: John H. Howard , Michael L. Kazar , Sherri G. Menees , David A. Nichols , M. Satyanarayanan , Robert N. Sidebotham , Michael J. West, Scale and performance in a distributed file system, ACM Transactions on Computer Systems (TOCS), v.6 n.1, p.51-81, Feb. 1988 [doi>10.1145/35037.35059]
• 11: Udi Manber , Sun Wu, GLIMPSE: a tool to search through entire file systems, Proceedings of the USENIX Winter 1994 Technical Conference on USENIX Winter 1994 Technical Conference, p.4-4, January 17-21, 1994, San Francisco, California

INDEX TERMS

Primary Classification:
  D. Software
  D.4 OPERATING SYSTEMS
      D.4.3 File Systems Management
          Subjects: Access methods

Additional Classification:
  D. Software
  D.4 OPERATING SYSTEMS
      D.4.3 File Systems Management
          Subjects: File organization
      D.4.8 Performance
          Subjects: Operational analysis

  E. Data
  E.5 FILES
      Subjects: Organization/structure; Sorting/searching

  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Pattern matching

General Terms:
Algorithms, Design, Management, Performance

Keywords:
file access prediction, finite inductive sequences, following, ruling