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 

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.