wilson@carcoar.Stanford.EDU (Paul Wilson) (08/31/89)
I've been thinking about the inclusion property of replacement algorithms,
and I was wondering if anybody has talked about a similar *spatial*
inclusion property.
(The normal inclusion property means that, given a "stack" replacement algo-
rithm like LRU, the pages in memory for a given number of page frames is
always a subset of the pages in memory for any larger number of page frames.)
Now suppose you have N pages of a given *size* and 2N pages twice that
size. The page faults in the smaller memory will be a superset of the
page faults in the larger one with the larger pages. Even if accesses
are pessimally distributed (e.g., only referring to one half of each
page, so that half-sized pages would halve the memory requirements),
any page fault in the larger memory will be reflected by a page
fault in the larger one.
I haven't figured this out formally or mathematically (or figured out
how general it is). But it seems useful both for simulating replacement
policies _and_for_gathering_traces_.
This principle should allow you some economies when simulating multiple
memory and page sizes, I think, allowing you to eliminate a lot of
redundant effort when simulating several things in one pass through
a reference trace.
More interesting to me is the possibility of using an actual small
memory with actual small pages to gather reference traces just by
instrumenting the page fault handler. The actual page replacement
policy would in effect act as a filter and give you a fairly small
trace.
Of course, this entails keeping memory smaller than the simulated
memory, so you'll get a lot of page faults and may thrash. But
this might not be so bad because you don't have to actually
do the paging to disk -- you just set up a RAM disk and do
everything in RAM. Or if you can actually instrument the
page replacement algorithm, you can simply monitor what
passes through the first part of the LRU queue.
If your policy is not true LRU, as most aren't, it seems like it should
be easy to show that a close approximation of LRU gives a trace with
a "close" approximation of the true reference behavior. (In some
useful sense.)
Has anybody heard of anybody exploiting (or even describing)
such a spatial inclusion principle?
(I wouldn't be surprised if this idea is well-known -- I'm not an
OS person. But I need to do some locality measurements and simulations,
so pointers to the relevant info would be very useful. In particular,
I'm thinking of gathering traces on a VAX, with its little 512-byte
pages, using Mach's VM facilities. Any advice on that would be helpful,
too.)
Thanks,
Paul
Paul R. Wilson
Software Systems Laboratory lab ph.: (312) 996-9216
U. of Illin. at C. EECS Dept. (M/C 154) wilson@bert.eecs.edu
Box 4348 Chicago,IL 60680