Alan Jay Smith
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.
- 1 Boyd, D.L. Implementing mass storage facilities in operating systems. Computr 11, 2 (Feb. 1978), 40--45.Google Scholar
- 2 Chaffee, R.B., Challenger, M.A., and Russell, E.S. File migration task force study. Stanford Linear Accelerator Center, June 1977.Google Scholar
- 3 Chu, W., and Opderbeck, H. Program behavior and the page fault frequency replacement algorithm. IEEE Computr (Nov. 1976), 29-38.Google ScholarDigital Library
- 4 Coffman, E.G., and Denning, P.J. Operating Systems Theory. Prentice-Hall, Englewood Cliffs, N.J., 1973. Google ScholarDigital Library
- 5 Considine, J.P., and Myers, J.J., MARC: MVS archival storage and recovery program. 1BM Syst. J. 16, 4 (1977), 378-397.Google Scholar
- 6 Denning, P.J. The working set model for program behavior. Comm. ACM 11, 5 (May 1968) 323-333. Google ScholarDigital Library
- 7 Denning, P.J., and Eisenstein, B. Statistical methods in performance evaluation. Proc. ACM Workshop on Computer Performance Evaluation, Harvard University, Cambridge, Mass., April, 1971, 284-307. Google ScholarDigital Library
- 8 Denning, P.J., and Slutz, D.R. Generalized working sets for segment reference strings. Comm. ACM 21, 9 (Sept. 1978), 750-759. Google ScholarDigital Library
- 9 Proc. DOE/NCAR mass storage workshop, Dec. 1977, National Center for Atmospheric Research, Boulder, Colo., published May, 1978.Google Scholar
- 10 Fajman, R., and Borgelt, J. Wylbur: An interactive text editing and remote job entry system. Comm. ACM 16, 5 (May 1973), 314- 322. Google ScholarDigital Library
- 11 IBM. MVS hierarchical storage manager release I is available. DPD Program Product Announcement, IBM Corp., Armonk, N.Y., April, 1978.Google Scholar
- 12 Klorer, C.J. MSS/DASD space/dataset management system. Proc. Share 51 Conf., Boston, Mass., Aug. 1978, 1090-1096.Google Scholar
- 13 Knight, J. CASHEW--A proposed permanent data storage system. Computer Center Rept., Lawrence Berkeley Laboratory, May 1976.Google Scholar
- 14 LeHeiget, J.P., and Reich, D.L. MSSCOM, A conversational MSS command processor. IBM Res. Rept. RC 7167, Dec. 4, 1978.Google Scholar
- 15 Lum, V.Y., Senko, M.E., Wang, C.P., and Ling, H. A cost oriented algorithm for data set allocation in storage hierarchies, Comm. ACM 18, 6 (June 1975), 318-322. Google ScholarDigital Library
- 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.Google ScholarDigital Library
- 17 Michael, G.A. MASS archival storage: Some trends, needs and plans at DOE Laboratories. Lawrence Livermore Lab. Rept. UCRL 82354, May 21, 1979.Google Scholar
- 18 Morgan, H., and Dan Levin, K. Optimal program and data locations in computer networks. Comm. ACM 20, 5 (May 1977), 315- 322. Google ScholarDigital Library
- 19 Prieve, B.G., and Fabry, R.S. VMIN--An optimal variable space replacement algorithm. Comm. ACM 19, 5 (May 1976), 295-297. Google ScholarDigital Library
- 20 Reich, D.L. Page fault model of staging for mass storage volumes. IBM Res. Rept. RC 7430, Nov. 30, 1978.Google Scholar
- 21 Revelle, R. An empirical study of t'de reference patterns. IBM Res. Rept. RJ 1557, April 1975.Google Scholar
- 22 Smith, A.J. Analysis of the optimal look-ahead, demand paging algorithms. SIAM J. Computing 5, 4 (Dec. 1976), 743-757.Google ScholarCross Ref
- 23 Smith, A.J. Bibliography on paging and related topics. Oper. Syst. Rev. 12, 4 (Oct. 1978), 39-56. Google ScholarDigital Library
- 24 Smith, A.J. Long term file reference patterns and their application to file migration algorithms. IEEE TSE (in press). Google ScholarDigital Library
- 25 Smith, A.J. Sequentiality and prefetching in data base systems. IBM Res. Rept. RJ 1743, March 19, 1976, and ACM Trans. Data Base Syst. 3, 3 (Sept. 1978), 223-247. Google ScholarDigital Library
- 26 Smith, A.J. Bibliography on file and I/O system optimization and related topics. Oper. Syst. Rev., 1981.Google Scholar
- 27 Stritter, E.P. File migration. Stanford Computr Sci. Rept. STAN- CS-77-594, Ph.D. Disseration, Jan. 1977. Google ScholarDigital Library
- 28 Zehab, D., and Boies, S. J. The SFS migration system. IBM Res. Rept. RC 6944, Jan. 1978.Google Scholar
Index Terms
- Long term file migration: development and evaluation of algorithms
Recommendations
Analysis of Long Term File Reference Patterns for Application to File Migration Algorithms
In most large computer installations files are moved between on-line disk and mass storage (tape, integrated mass storage device) either automatically by the system and/or at the direction of the user. In this paper we present and analyze long term file ...
File Migration and File Replication: A Symbiotic Relationship
Much of the past research on file migration and file replication has examined these two resource management strategies in isolation or in an environment where they do not work together. We establish through simulation that these two strategies can be ...
Comments