virtual memory 4498

Bill Todd

I found such studies, which appear to show that VMS's mechanism is within, by looking at a graph, about 0.5% of LRU.

This was a unpleasant woman to track down because there are so many different names for the same mechanisms. "Segmented FIFO" seems to be somewhat popular for the VMS mechanism, but many also call it Second Chance FIFO and just FIFO. Some erroneously claim the VMS is strict FIFO which it is not. Some documents are scanned images so they don't show up in searches.

I found references to such studies in:

Virtual Memory Management in the VAX-VMS Operating System Levy, Lipman IEEE Computer, March 1982

where it states:

"Although VAX does not have reference bits, work at the University of California, Berkeley 2 on VAX-Unix... suggests that software simulation of the reference bit consumes 0.05 percent of the processor."

"... the VAX-VMS free-list mechanism acts to reduce program fault rates. ... Results from simulation studies 3 ... show the effect effect of reducing the size of the program's resident set... the graph indicates that the addition of a free list can reduce the fault rate of strict FIFO replacement to a level arbitrarily close to LRU. This effect has been demonstrated by other analytic and simulation studies. 4"

2 Design and implementation of the Berkeley Virtual Memory Extensions to the UNIX Operating System. Babaoglu, Joy, Porcar 1979

3 Segmented FIFO Page Replacement Turner, Levy Proc. ACM Sept 1981

4 Virtual Storage Management in the Absence of Reference Bits Babaoglu PhD thesis, UofCal, Berkeley, 1981, available in ACM

It then shows a graph where the Segmented FIFO fault rate is within what looks to be about 0.5% of the LRU fault rate.

As usual, there is more info available but locked up in the ACM.

Eric