In article <1992Aug5.023248.1639@uniwa.uwa.edu.au> oreillym@tartarus.uwa.edu.au (Michael O'Reilly) writes:
quoted text
>davidsen@ariel.crd.GE.COM (william E Davidsen) writes:
>: In article <1992Aug4.035247.5999@uniwa.uwa.edu.au>, oreillym@tartarus.uwa.edu.au (Michael O'Reilly) writes:
>: 
>: | One thing that would improve things as well is doing pageing before it
>: | is needed.
>: | 
>: | i.e. if the buffer drops below Y buffers, and there is less than Z free
>: | pages, it starts useing a standard clock algorithm to page least
>: | recently used pages to disk.
>: | This would fit in very nicely in the idle process. (which
>: | currently just busy waits)
>: 
>:   I believe that there might be a good case for having an additional
>: state for pages instead of two. Currently pages are in use, or free, or
>: i/o buffers. One method which seems to offer room for a lot of
>: improvement is to have a additional state for pages near the end of the
>: LRU list. By unmapping those pages from all processes but not freeing
>: them immediately, you get the chance to see if they are really in use,
>: by getting a page fault and remapping them, and putting them back at
>: the top of the LRU list.
>
>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. 

Beyond that, you also have a two-tiered set of page tables, with the 
outer page directory having a 4M granularity, each table consisting of 1K
entries with a 4K (page size granularity).  Both tables exist
on a per address space basis.  This lets you look at a 4M range,
and then if there are dirty / accessed pages in that, go and 
look at the page table for that directory entry.

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.

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.

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.