In article <1992Aug5.102706.15668@colorado.edu> drew@ophelia.cs.colorado.edu (Drew Eckhardt) writes:
quoted text
>In article <1992Aug5.023248.1639@uniwa.uwa.edu.au> oreillym@tartarus.uwa.edu.au (Michael O'Reilly) writes:
>>
>>The 386 chip has a feature that lets you acomplish the same idea without
>>any fancy schemes like that. The basic idea is that when a page is
>>accessed for the first time, a bit is set in the page tables. WHen it is
>>written, a different bit is set. 

The accessed bit will be used in the soon-to-be-made (I didn't get them
together yesterday, but I'll try again today) first patch to 0.97. It's
very practical, and didn't need any additional state information. While
the current routine isn't a real LRU (Least Recently Used) which needs
some actual calculations, it's NRU (Not Recently Used) which is a simple
approximation that can do with just the one bit that is already provided
by the hardware.

A closer approximation to LRU would be some aging mechanism (the 386
page tables even have room for a 3-bit wide aging or somthing like that
in the unused bits), and it might be worth implementing eventually.

quoted text
>>So the way to do this is to clear all the bits, and then cycle through
>>doing.
>>      is bit set?
>>      yes -> clear it and go to next
>>      no -> it can be swapped, swap it and move on.

This is similar to what the 0.97+patch1 algorithm does - it's simple,
and while it's not perfect it works relatively well.  Or at least that's
the early indications from my tests.  I won't be able to do exhaustive
tuning of the algorithms, so the patch1 algorithm might not be perfect. 
We'll see. 

quoted text
>Yes and no.  When determining what pages you want out, you want to 
>deal with the hits for each incore page.  There isn't a 1:1 
>correspondance between a page in the page table, and a physical 
>page.  Instead, two or more processes may have the same page mapped,
>making the effect cumulative.

It's a bit more work to actually go through the pages and take this into
account, so I currently don't. But you are right: this is how it should
(and will) be done.

quoted text
>Some one should see what times are for 
>looking at every page in every dirty 4M range in every address
>space compared to what it takes to look at every page in physical
>memory, ie using a reverse hash function.

Actually, it's not a very time-critical check: it's done by the idle
task anyway (which is the reason I originally made task[0] special: it
just hasn't been used up till now).  That way the machine does something
useful even when waiting for disk accesses etc.  In patch1 the algorithm
just searches for non-accessed pages so that the system doesn't have to
do those calculations every time it wants to swap something out.  It
should be relatively easy to enhance to do aging and check on the same
page being used by several different processes. 

                Linus