Application of reconstructing techniques to the optimization of program behavior in virtual memory systems

Published as Storage Systems Research Center Technical Report UCSC-SSRC-.

Abstract

One of the most effective ways of obtaining a better performance from virtual memory systems consists of improving the behavior of programs in such environments. Program restructuring attempts to achieve this goal by rearranging the block-Lo-page mappings of programs. The best existing restructuring algorithms take into account the dynamic behavior of the program to be restructured and attempt to minimize either its page fault frequency or its mean memory occupancy, which are both partial indicators of program performance. In this thesis, we present a new class of restructuring algorithms that attempt to minimize a global index of program performance, namely its spacetime product. The primary motivation of these algorithms is to avoid situations where a significant improvement of one index of program performance would be accompanied by a comparably sized deterioration of another index. Hence the name of "Balanced Algorithms" given to our algorithms. Balanced Algorithms essentially attempt to minimize a restructuring-time estimate of the space-time product of the restructured program. Since they follow a common scheme, they can be easily tailored to a wide range of variable space memory policies, including Working Set, Sampled Working Set, Global LRU and Page Fault Frequency. We prove that BWS, the balanced algorithm tailored to Working Set environments, effectively minimizes a linear combination of the number of page faults and of the mean memory occupancy of all programs whose behavior can be described by a chain having a steady-state solution and which have at most two blocks per page. In order to evaluate the performance of balanced algorithms under various memory policies and to compare it to those of other restructuring algorithms, a series of trace-driven experiments simulating the behavior of programs before and after restructuring were conducted. These simulations show that BWS, the balanced algorithm tailored to Working Set environments, performs significantly better than the two best existing restructuring algorithms. Similar results were found with the balanced algorithm tailored to Sampled Working Set environments. BPSI, the balanced algorithm tailored to Global LRU environments, exhibited only a marginal superiority over its rivals, while no clear winner emerged for the Page Fault Frequency environments. Another consequence of our choice of a global indicator of program performance as restructuring criterion is to allow our approach to be extended to segmentation environments, or which no efficient restructuring algorithms have been proposed. Here too, we prove that BWWS, the balanced algorithm tailored to time window working Set environments, minimizes a linear combination of the number of segment faults and of the mean memory occupancy of all programs whose behavior can be described by a chain having a steady-state solution and which have at most two blocks per segment. Experimental evidence is also presented showing that BWWS can significantly improve the segment fault frequency of a program without causing any comparable increase of its memory occupancy. On the other hand, our simulations indicate that BSFF, the balanced algorithm tailored to Segment Fault Frequency environments, does not bring any improvement to either indices of program performance.

 

Publication date:
May 1981

Authors:
Jehan-François Pâris

Projects:
Archival Storage

Bibtex entry

@techreport{paris-thesis81,
  author       = {Jehan-François Pâris},
  title        = {Application of reconstructing techniques to the optimization of program behavior in virtual memory systems},
  institution  = {University of California, Santa Cruz},
  number       = {UCSC-SSRC-},
  month        = may,
  year         = {1981},
}