Cache management algorithms for flexible filesystems

ABSTRACT

Cache management in flexible filesystems deals with the problem of determining a cached file to be replaced when the local cachespace is exhausted. In analogy to virtual memory management, several different algorithms exist for managing cached files. In this paper we simulate the behavior of First-In-First-Out (FIFO), Least Recently Used (LRU), Least Frequently Used (LFU) and a variation of LFU we call the File Length Algorithm (LEN) from the viewpoint of file access times, cache hit ratios and availability. The results of several simulation runs are presented and interpreted.

REFERENCES

• 1: Alfred V. Aho , Peter J. Denning , Jeffrey D. Ullman, Principles of Optimal Page Replacement, Journal of the ACM (JACM), v.18 n.1, p.80-93, Jan. 1971 [doi>10.1145/321623.321632]
• 2: L. A. Belady , R. A. Nelson , G. S. Shedler, An anomaly in space-time characteristics of certain programs running in a paging machine, Communications of the ACM, v.12 n.6, p.349-353, June 1969 [doi>10.1145/363011.363155]
• 3: Harvey M. Deitel, An Introduction to Operating Systems, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1990
• 4: Peter J. Denning, The working set model for program behavior, Communications of the ACM, v.11 n.5, p.323-333, May 1968 [doi>10.1145/363095.363141]
• 5: James J. Kistler , M. Satyanarayanan, Disconnected operation in the Coda File System, ACM Transactions on Computer Systems (TOCS), v.10 n.1, p.3-25, Feb. 1992 [doi>10.1145/146941.146942]
• 6: Maffeis, S. Resim - A REplication SIMulator. CS Dept. University of Zurich, Internal Report, Jan. 1992.
• 7: Silvano Maffeis, File access patterns in public FTP archives and an index for locality of reference, ACM SIGMETRICS Performance Evaluation Review, v.20 n.3, p.22-35, March 1993 [doi>10.1145/155768.155771]
• 8: Silvano Maffeis , Clemens H. Cap, Replication Heuristics and Polling Algorithms for Object Replicationand a Replicating File Transfer Protocol, University of Zurich, 1992
• 9: Presotto, D., Pike, R., Thompson, K., and Trickey, H. Plan 9, A Distributed System. In <i>Proceedings of the Spring 1991 EurOpen Conference</i> (May 1991).
• 10: Sean Quinlan, A cached WORM file system, Software—Practice & Experience, v.21 n.12, p.1289-1299, Dec. 1991 [doi>10.1002/spe.4380211203]
• 11: Harjinder S. Sandhu , Songnian Zhou, Cluster-based file replication in large-scale distributed systems, ACM SIGMETRICS Performance Evaluation Review, v.20 n.1, p.91-102, June 1992
• 12: J. Howard , M. Kazar , S. Menees , D. Nichols , M. Satyanarayanan , Robert N. Sidebotham , M. West, Scale and performance in a distributed file system, ACM SIGOPS Operating Systems Review, v.21 n.5, p.1-2, Nov. 1987
• 13: Alexander Siegel, Performance in flexible distributed file systems, Cornell University, Ithaca, NY, 1992

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.6 SIMULATION AND MODELING
      I.6.8 Types of Simulation
          Subjects: Discrete event

Additional Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.1 Network Architecture and Design
          Subjects: Network topology

  D. Software
  D.4 OPERATING SYSTEMS
      D.4.2 Storage Management
          Subjects: Virtual memory

General Terms:
Algorithms, Performance