Relay-Version: version B 2.10 5/3/83; site utzoo.UUCP
Path: utzoo!mnetor!seismo!umcp-cs!chris
From: chris@umcp-cs.UUCP (Chris Torek)
Newsgroups: net.arch
Subject: Re: VERY LARGE main memories: crypt
Message-ID: <3585@umcp-cs.UUCP>
Date: Thu, 25-Sep-86 16:32:52 EDT
Article-I.D.: umcp-cs.3585
Posted: Thu Sep 25 16:32:52 1986
Date-Received: Fri, 26-Sep-86 02:01:42 EDT
References: <1276@bu-cs.bu-cs.BU.EDU> <7537@lanl.ARPA> <1819@mmintl.UUCP> <7847@lanl.ARPA>
Reply-To: chris@umcp-cs.UUCP (Chris Torek)
Organization: University of Maryland, Dept. of Computer Sci.
Lines: 35
Summary: a look at MRU replacement

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