Sorting in a paging environment

ABSTRACT

This sorting study was part of an extensive measurement project undertaken on the M44/44X, an experimental paging system which was conceived and implemented at IBM Research in order to explore the virtual machine concept. The study was concerned with the implementation of sorting procedures in the context of the dynamic paging environment characteristic of virtual memory machines. Descriptions of the experimental sort programs and analysis of the performance measurement results obtained for them are presented. The insight gained from the experimental effort is used to arrive at a set of broad guidelines for writing sort programs for a paging environment.

REFERENCES

• 1: Comm. ACM 6, 5 (May 1963). {The entire issue is devoted to
• 2: Ivan Flores, Analysis of Internal Computer Sorting, Journal of the ACM (JACM), v.8 n.1, p.41-80, Jan. 1961 [doi>10.1145/321052.321055]
• 3: HOARE, C. A. R. Quicksort. Comput. J . 5 (April 1962-Jan. 1963), 10-15.
• 4: George U. Hubbard, Some characteristics of sorting computing systems using random access storage devices, Communications of the ACM, v.6 n.5, p.248-255, May 1963 [doi>10.1145/366552.366586]
• 5: GILSTAD R. L. POLYPHASE merge sorting-an advanced technique. Proc. Eastern Joint Comput. Conf., Vol. 18, Dec. 1960, Spartan Books, New York, pp. 143-148.
• 6: O'NEILL, R. W. Experience using a time-shared multi-programming system with dynamic address relocation hardware. Proc. AFIPS 1967 Spring Joint Comput. Conf., Vol. 30, MDI Publications, Wayne, Pa., pp. 611-621.
• 7: The M44/44X user's guide and the 44X reference manual. IBM Corp., T. J. Watson Research Center, Yorktown Heights, N. Y., Sept. 1967.
• 8: BRAWN, B., AND GUSTAVSON, F. An evaluation of program performance on the M44/44X system, Parts I, II, III. Part I: RC-2083 (May 1968) ; Part II: RC-2275 (Nov. 1968) ; Part III: RC-2276 (Jan. 1969); IBM Corp., T. J. Watson Research Center, Yorktown Heights, N. Y.
• 9: BRAWN, B., AND GUSTAVSON, F. Program behavior in a paging environment. Proc. AFIPS 1968 Fall Joint Comput. Conf., Vol. 33, Pt. 2, MDI Publications, Wayne, Pa., pp. 1019- 1032.
• 10: BRAWN, B., GUSTAVSON, F., AND MANKIN, E. Sorting performance in a paged virtual memory. RC-2435, IBM Corp., T. J. Watson Research Center, Yorktown Heights, N. Y., April 1969.

INDEX TERMS

Keywords:
dynamic storage allocation, measurement of systems program behavior, memory management, merging, paging systems, performance evaluation, sorting, virtual machines