Page table optimizations in Linux and FreeBSD

[Jeff Garzik]

Forwarded without no comment other than it's a good read:

http://www.daemonnews.org/200001/freebsd_vm.html
Design Elements of the FreeBSD VM System
By Matthew Dillon

-----SNIP-----
The page table optimizations make up the most contentious part of the
FreeBSD VM design and they have shown some strain with the advent of
serious use of mmap(). I think this is actually a feature of most BSDs
though I am not sure when it was first introduced. There are two major
optimizations. The first is that hardware page tables do not contain
persistent state but instead can be thrown away at any time with only a
minor amount of management overhead. The second is that every active
page table entry in the system has a governing pv_entry structure which
is tied into the vm_page structure. FreeBSD can simply iterate through
those mappings that are known to exist while Linux must check all page
tables that *might* contain a specific mapping to see if it does, which
can achieve O(n^2) overhead in certain situations. It is because of this
that FreeBSD tends to make better choices on which pages to reuse or
swap when memory is stressed, giving it better performance under load.
However, FreeBSD requires kernel tuning to accommodate
large-shared-address-space situations such as those that can occur in a
news system because it may run out of pv_entry structures. 

Both Linux and FreeBSD need work in this area. FreeBSD is trying to
maximize the advantage of a potentially sparse active-mapping model (not
all processes need to map all pages of a shared library, for example),
whereas Linux is trying to simplify its algorithms. FreeBSD generally
has the performance advantage here at the cost of wasting a little extra
memory, but FreeBSD breaks down in the case where a large file is
massively shared across hundreds of processes. Linux, on the other hand,
breaks down in the case where many processes are sparsely-mapping the
same shared library and also runs non-optimally when trying to determine
whether a page can be reused or not. 
-----SNIP-----

-- 
Jeff Garzik         | Andre the Giant has a posse.
Building 1024       |
MandrakeSoft, Inc.  |

-
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo en vger.rutgers.edu
Please read the FAQ at http://www.tux.org/lkml/