🚀 go-pugleaf

In article <7847@lanl.ARPA> jlg@a.UUCP (Jim Giles) writes:
>The MRU [Most Recently Used] algorithm (as far as I can see) does
>the following:
>    Assume M pages of data are to be used cyclically and only N pages
>    will fit.  Initially, the first page is loaded and the code begins
>    executing.  At the end of page 1, the next page is loaded, and so
>    on for N pages.  Now you have a choice to make, do you flush page
>    1 or page N to make room for N+1.  The MRU algorithm presumably
>    flushes page N (the most recently used).  And so you continue up
>    to page M.  Now on the second cycle through the data, the first N-
>    1 pages are already there, so no page fault occurs until page N is
>    needed.  Then a page fault occurs for every page until page M.
>
>This doesn't seem optimal to me.  Or did I get the algorithm wrong?

Yes, in two important ways: pageouts occur not when free pages are
exhausted, but when free pages are low; and pageins are performed
in advance if you have marked your process cyclic.  Let us assume
that N pages will fit, but that the OS wants to keep F pages free
and that it operates in `clusters' of C pages.  Initially, the
first C pages are loaded, then the next, and so on for N-F pages.
At this point pages N-F-2C through N-F-C+1 are flushed, with N-F
through N-F+C-1 being paged in.  The last few (V) pages are not
marked valid.  When the process touches page N-F+C-V, those V pages
are marked valid and the OS begins bringing in pages N-F+C through
N-F+2C-1, simultaneously paging out pages N-F-C through N-F-1.

To put it another way, the OS will try to keep a range of 2C pages
avialable.  If C is large enough, the only price is for the extra
faults that the O/S needs to discover that you are indeed about to
use the next group of pages.  (This is not necessarily negligible.)
-- 
In-Real-Life: Chris Torek, Univ of MD Comp Sci Dept (+1 301 454 1516)
UUCP:	seismo!umcp-cs!chris
CSNet:	chris@umcp-cs		ARPA:	chris@mimsy.umd.edu