Anomalies with variable partition paging algorithms

ABSTRACT

Five types of anomalous behaviour which may occur in paged virtual memory operating systems are defined. One type of anomaly, for example, concerns the fact that, with certain reference strings and paging algorithms, an increase in mean memory allocation may result in an increase in fault rate. Two paging algorithms, the page fault frequency and working set algorithms, are examined in terms of their anomaly potential, and reference string examples of various anomalies are presented. Two paging algorithm properties, the inclusion property and the generalized inclusion property, are discussed and the anomaly implications of these properties presented.

REFERENCES

• 1: 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]
• 2: Belady, L.A. A study of replacement algorithms for a virtual computer. IBM Syst. J. 5, 2 (1966), 78-101.
• 3: Chu, W.W., and Opderbeck, H. The page fault frequency replacement algorithm. AFIPS 1972 FJCC, Vol. 41, AFIPS Press, Montvale, N.J., pp. 597-609.
• 4: E. G. Coffman, Jr. , Thomas A. Ryan, Jr., A study of storage partitioning using a mathematical model of locality, Communications of the ACM, v.15 n.3, p.185-190, March 1972 [doi>10.1145/361268.361280]
• 5: Peter J. Denning, Virtual Memory, ACM Computing Surveys (CSUR), v.2 n.3, p.153-189, Sept. 1970 [doi>10.1145/356571.356573]
• 6: Denning, P.J., and Graham, G.S. Multiprogrammed memory management. Proc. IEEE 63, 6 (June 1975), 924-934.
• 7: 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]
• 8: Peter J. Denning , Stuart C. Schwartz, Properties of the working-set model, Communications of the ACM, v.15 n.3, p.191-198, March 1972 [doi>10.1145/361268.361281]
• 9: Denning, P.J., and Slutz, D.R. Generalized working set and optimal measures for segment reference strings. Tech. Rep. CSD-TR-178, Comptr. Sci. Dept., Purdue U., Lafayette, Ind., March 1976.
• 10: Gordon Scott Graham, A study of program and memory policy behaviour., 1976
• 11: Ram Kumar Gupta, Program reference behavior and dynamic memory management., 1974
• 12: Mattson, R.L., Gecsei, J., Slutz, D.R., and Traiger, I.L., Evaluation techniques for storage hierarchies. IBM Syst. J. 9, 2 (1970), 78-117.
• 13: D. R. Slutz , I. L. Traiger, A note on the calculation of average working set size, Communications of the ACM, v.17 n.10, p.563-565, Oct. 1974 [doi>10.1145/355620.361167]

INDEX TERMS

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

General Terms:
Algorithms, Design, Performance, Theory

Keywords:
anomaly, memory management, page fault frequency, paging algorithms, program behavior, stack algorithms, virtual memory, working set