PROGRAM RESTRUCTURING FOR VIRTUAL SYSTEMS
J H Johnson · 1975
The problem area addressed in this report is program restructuring, a method of reordering the relocatable sectors of a program in its address space to increase the locality of the programs reference behavior, thereby reducing the number of page fetches required for its execution in a virtual memory system. Theoretical upper and lower (optimum) bounds are derived for the paging performance of programs over all partitions of relocatable sectors into pages. Program restructuring techniques are developed which use intersector reference models based on sector working sets and sector stack distances. These intersectors reference models identify the local reference behavior, and clustering procedures are developed that use this local reference behavior to rearrange sectors into pages such that significant improvement in paging performance is obtained. Results of measurements of paging performance obtained in the computer laboratory are discussed. The relationship between the paging performance of a program restructured by the practical restructuring algorithms and the theoretical bounds on paging performance are compared.