Generalized page replacement algorithms in a relational data base

ABSTRACT

This paper describes a generalized page replacement problem in which the pages have variable sizes and the cost of a page fault is a function of the particular page referenced. In such an environment the conventional page replacement algorithms are found to perform inadequately. New algorithms are proposed for reducing the cost incurred because of page faults in response to a series of references. Simulation experiments have been run in order to compare the cost performance of these algorithms with standard techniques, and also with the minimum achievable cost. The latter is determined by means of a novel tree-pruning algorithm. One practical environment in which the general problem may arise is a relational data base having an implied relations facility, in which some relations are maintained in definition form until queried. The implied relation is analogous to a page, and the processing time for restructuring a relation from its definition varies from one relation to another. An efficient replacement algorithm is needed to manage the process as the implied relations alternate between the state of definitions and the state of explicit representation.

REFERENCES

• 1: E. F. Codd, A relational model of data for large shared data banks, Communications of the ACM, v.13 n.6, p.377-387, June 1970 [doi>10.1145/362384.362685]
• 2: Notley, M.G., "The Peterless IS/l System", IBM (UK) Scientific Centre Report, March 1972, UKSC-0018.
• 3: Hoare, C.A.R. and McKeay, R.M., "A Survey of Store Management Techniques", Operating Systems Techniques APIC Studies in Data Processing No. 9, C A R Hoare and R H Perrotteds, Academic Press, London and New York, 1972.
• 4: Gecsei, J., Mattson, R.L., Slutz, D.R., Traiger, I.L, "Evaluation Techniques for Storage Hierarchies", IBM Systems Journal 9, No. 2, 78-117 (1970).
• 5: Belady, L.A., "A Study of Replacement Algorithms for a Virtual-Storage Computer", IBM Systems Journal 5, No. 2, 78-101 (1966).
• 6: Hatfield, D.J., Parmelee, R.P., Peterson, T.I., Tillman, C.C., "virtual Storage and Virtual Machine Concepts", IBM Systems Journal 11, No. 2, 99-130 (1972).
• 7: Slutz, D.R., and Traiger, J.L., "One-Pass Techniques for the "Evaluation of Memory Hierarchies", IBM Res. Report RJ-892 (1972).

INDEX TERMS

Primary Classification:
  D. Software
  D.4 OPERATING SYSTEMS
      D.4.2 Storage Management

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

  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.4 Systems
          Subjects: Relational databases

General Terms:
Algorithms, Design, Management