wilson@carcoar.stanford.edu (Paul Wilson) (08/02/89)
A while back I posted a posting in comp.os.research that, among other
things, asked for references to work on prepaging. Maybe because the
posting had too many other things in it, I got no such replies. So I'll
try again:
Anybody know any good references to work in prepaging? Any
strategies that work better than simple demand paging?
I've been thinking of a scheme in which the unit of disk transfer
is actually about ten pages, and dynamic access information is used
to order the pages within these hunks. The idea is similar to
Bob Courts' incremental garbage collector for the TI Explorer
(CACM, December 1988), which copies objects to new pages
in the order that they are encountered by the running program.
My system would operate at a larger granularity, grouping pages
within larger "disk pages". Only a few of these large disk pages
would be kept in memory -- only those (normal) pages that are actually
referenced soon would be kept in memory.
This scheme would keep track of the order of initial page accesses (via
a little bit of code attached to the page fault handler). When
it comes time to write some pages out, they would be preferentially
written out in the same sequence as their original accesses. (Recently-
accessed pages would be excepted, and handled differently.)
This scheme might be combined with my scheme for compressing heap
data, so that more (compressed) pages would fit within the unit of
disk transfer.
Any comments or pointers to relevant information would be appreciated.
(I'm particularly interested in prefetching of normal program data, though
references about database techniques couldn't hurt.)
thanks prematurely,
Paul
P.S. If you sent me a note requesting the tech report on compression, etc.,
it should be there within a few days -- sorry about the delay. I think
I sent one out to everybody who asked (lots of people) except someone
named something like Wernher Bahnke (?) (W.B.?: you didn't include a
mailing address and I lost the note and couldn't reply via email.)
P.P.S. If you've got that tech report, you might want to know that Ralph
Johnson at U of I Urbana has a better scheme for incremental faulting
than the one I describe. It works basically the same way, except
that the unit of relocation is the page, not the object. This is
better because the mapping is simpler -- transient pages to persistent
pages (though they are of different sizes due to different repre-
sentations). My per-object copying is a holdover from the Appel-Ellis-
Li incremental gc; it is unnecessary if you're not doing garbage
collection along with your relocation.
Paul R. Wilson
Software Systems Laboratory lab ph.: (312) 996-9216
U. of Illin. at C. EECS Dept. (M/C 154) wilson@carcoar.stanford.edu
Box 4348 Chicago,IL 60680