Virtual Memory Management

This thesis studies methods of scheduling, memory management, and load control in a virtual memory computer system. It also studies the problem of modeling virtual memory systems. The work contributes new ideas and techniques in each of these areas. Finally, the thesis compares the two alternative classes--local and global--of virtual memory management policies. In the area of scheduling, a multi-level, load-balancing queue is described; this mechanism is useful for maintaining good response time in interactive systems and for managing a central server in a distributed computer system. In the area of memory management, a new policy, WSCLOCK, is developed; this policy combines the natural load control of the WS (working set) policy and the simplicity and low cost of the CLOCK (approximate global LRU) policy. Two contributions are made in the area of load control. First, a general loading-task/running-task (LT/RT) control alleviates congestion when multiple tasks are newly-activated at the same time. Second, a load control for the global policy CLOCK is presented; this adaptive feedback control uses information collected during the page replacement process to estimate the overall level of main memory commitment and, then, adjusts the multiprogramming level for best performance. This control employs exponentially-smoothed confidence intervals--a statistic that is also developed in the thesis. Models to compare local and gobal memory management policies that are both accurate and efficient have been difficult to construct. The thesis (1) develops a trace-driven model of program behavior that greatly reduces the cost of simulation with a negligible loss of accuracy and (2) constructs a detailed simulation model of multiprogrammed virtual memory systems. The program behavior model is parameterized by measurements of real programs; it reflects the behavior of those programs at a very precise level. The system model is driven by a heterogeneous collection of program models that are typical of many computer systems. The thesis uses the model to make a direct comparison of the WS, CLOCK, and WSCLOCK policies. The study indicates that neither of the classes of memory management policies are inherently superior. Disregarding the time spent executing the algorithms themselves (i.e., operating system overhead) no significant differences in system performance could be detected. On a practical level, CLOCK has considerably less overhead than either WS or WSCLOCK and, thus, represents the best alternative.