Selection of the working set window size

Abstract

A function is developed which describes the cost of executing a program when using demand paging. The function includes the cost of paging operations and memory usage. Several theorems are proven which determine, in a single scan of a program's reference string, the memory state sequence generated by an optimal page replacement policy. The VMIN policy, developed by Prieve and Fabry, is the optimal policy used in the research. The cost of using the working set policy with different window sizes is investigated. If β is the ratio of the cost of a paging operation to the cost of keeping a page in memory per unit of time, then using the working set policy with a window size of βis more likely to be 1.2 times the cost of using VMIN. An algorithm for finding the optimal (minimum cost) window size is given. The simulations suggest that the cost savings associated with using the optimal window size or an estimate of the optimal window size may not justify the required effort. A better alternative to solving for the optimal window size may be to use a value of β.