Long term file migration: development and evaluation of algorithms

ABSTRACT

The steady increase in the power and complexity of modern computer systems has encouraged the implementation of automatic file migration systems which move files dynamically between mass storage devices and disk in response to user reference patterns. Using information describing 13 months of user disk data set file references, we develop and evaluate (replacement) algorithms for the selection of files to be moved from disk to mass storage. Our approach is general and demonstrates a general methodology for this type of problem. We find that algorithms based on both the file size and the time since the file was last used work well. The best realizable algorithms tested condition on the empirical distribution of the times between file references. Acceptable results are also obtained by selecting for replacement that file whose size times time to most recent reference is maximal. Comparisons are made with a number of standard algorithms developed for paging, such as Working Set, VMIN, and GOPT. Sufficient information (parameter values, fitted equations) is provided so that our algorithms may be easily implemented on other systems.

REFERENCES

• 1: Boyd, D.L. Implementing mass storage facilities in operating systems. Computr 11, 2 (Feb. 1978), 40--45.
• 2: Chaffee, R.B., Challenger, M.A., and Russell, E.S. File migration task force study. Stanford Linear Accelerator Center, June 1977.
• 3: Chu, W., and Opderbeck, H. Program behavior and the page fault frequency replacement algorithm. IEEE Computr (Nov. 1976), 29-38.
• 4: Edward G. Coffman, Jr. , Peter J. Denning, Operating Systems Theory, Prentice Hall Professional Technical Reference, 1973
• 5: Considine, J.P., and Myers, J.J., MARC: MVS archival storage and recovery program. 1BM Syst. J. 16, 4 (1977), 378-397.
• 6: 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]
• 7: Peter J. Denning , Bruce A. Eisenstein, Statistical methods in performance evaluation, Proceedings of the SIGOPS workshop on System performance evaluation, p.284-307, January 1971 [doi>10.1145/800024.808363]
• 8: Peter J. Denning , Donald R. Slutz, Generalized working sets for segment reference strings, Communications of the ACM, v.21 n.9, p.750-759, Sept. 1978 [doi>10.1145/359588.359598]
• 9: Proc. DOE/NCAR mass storage workshop, Dec. 1977, National Center for Atmospheric Research, Boulder, Colo., published May, 1978.
• 10: Roger Fajman , John Borgelt, WYLBUR: an interactive text editing and remote job entry system, Communications of the ACM, v.16 n.5, p.314-322, May 1973 [doi>10.1145/362041.362234]
• 11: IBM. MVS hierarchical storage manager release I is available. DPD Program Product Announcement, IBM Corp., Armonk, N.Y., April, 1978.
• 12: Klorer, C.J. MSS/DASD space/dataset management system. Proc. Share 51 Conf., Boston, Mass., Aug. 1978, 1090-1096.
• 13: Knight, J. CASHEW--A proposed permanent data storage system. Computer Center Rept., Lawrence Berkeley Laboratory, May 1976.
• 14: LeHeiget, J.P., and Reich, D.L. MSSCOM, A conversational MSS command processor. IBM Res. Rept. RC 7167, Dec. 4, 1978.
• 15: V. Y. Lum , M. E. Senko , C. P. Wang , H. Ling, A cost oriented algorithm for data set allocation in storage hierarchies, Communications of the ACM, v.18 n.6, p.318-322, June 1975 [doi>10.1145/360825.360843]
• 16: Mattson, R.L., Gecsei, J., Slutz, D.R., and Traiger, I. Evaluation techniques for storage hierarchies. 1BM Syst. J. 9, 2 (1970), 78-117.
• 17: Michael, G.A. MASS archival storage: Some trends, needs and plans at DOE Laboratories. Lawrence Livermore Lab. Rept. UCRL 82354, May 21, 1979.
• 18: Howard L. Morgan , K. Dan Levin, Optimal program and data locations in computer networks, Communications of the ACM, v.20 n.5, p.315-322, May 1977 [doi>10.1145/359581.359591]
• 19: Barton G. Prieve , R. S. Fabry, MIN—an optimal variable-space page replacement algorithm, Communications of the ACM, v.19 n.5, p.295-297, May 1976 [doi>10.1145/360051.360231]
• 20: Reich, D.L. Page fault model of staging for mass storage volumes. IBM Res. Rept. RC 7430, Nov. 30, 1978.
• 21: Revelle, R. An empirical study of t'de reference patterns. IBM Res. Rept. RJ 1557, April 1975.
• 22: Smith, A.J. Analysis of the optimal look-ahead, demand paging algorithms. SIAM J. Computing 5, 4 (Dec. 1976), 743-757.
• 23: Alan Jay Smith, Bibliography on paging and related topics, ACM SIGOPS Operating Systems Review, v.12 n.4, p.39-56, October 1978 [doi>10.1145/775406.775409]
• 24: Smith, A.J. Long term file reference patterns and their application to file migration algorithms. IEEE TSE (in press).
• 25: Alan Jay Smith, Sequentiality and prefetching in database systems, ACM Transactions on Database Systems (TODS), v.3 n.3, p.223-247, Sept. 1978 [doi>10.1145/320263.320276]
• 26: Smith, A.J. Bibliography on file and I/O system optimization and related topics. Oper. Syst. Rev., 1981.
• 27: Edward Preble Stritter, File migration., 1977
• 28: Zehab, D., and Boies, S. J. The SFS migration system. IBM Res. Rept. RC 6944, Jan. 1978.

INDEX TERMS

Primary Classification:
  D. Software
  D.4 OPERATING SYSTEMS

Additional Classification:
  D. Software
  D.4 OPERATING SYSTEMS

General Terms:
Documentation, Management, Theory

Keywords:
file migration, mass storage, memory hierarchies, paging, replacement algorithm