Virtual storage management in the absence of reference bits
Özalp Babaoğlu · 1981
Virtual storage management requires a policy to replace data in primary storage with incoming data from secondary storage. To be effective, such a policy must select for replacement data that is not going to be needed in the near future. Having no knowledge about future demands for data, the replacement policy must anticipate them based on past demands. In most implementations of virtual storage systems, past demand for data is recorded in a reference bit associated with that data. These bits can then be examined and/or altered by the replacement policy. This thesis extends the virtual storage concept to within each storage hierarchy level. The analysis of such hierarchical replacement policies confirm their suitability for managing storage hierarchies that lack reference bits. Our preliminary studies are concerned with results that can be used in the evaluation of virtual storage systems in general. This includes the development of a program that is capable of synthesizing certain referencing behaviors in a virtual storage. Then, a class of hybrid replacement policies that employ different algorithms for the management of data in two logical partitions of primary storage is introduced and analyzed. It is shown that under certain conditions these hybrid policies incur little additional cost and perform as if reference bits were available. Trace-driven simulations are conducted to validate the findings of the analytic studies. These indicate that the conditions under which the hybrid policies exhibit good performance are rarely satisfied in an actual system. As alternatives, the Clock and Sampled Working Set replacement policies are developed for this environment and shown to perform more robustly with respect to most variations encountered in a typical system. Based on this work the global Clock algorithm is adopted as the page replacement policy in a virtual storage extension made to the UNIX operating system. The system runs on the VAX-11/780 computer, which lacks reference bits. Formal models based on inventory control theory are finally developed to optimize certain policy parameters adopted in the implementation.