Muli Ben-Yehuda's journal

July 31, 2003

Rik van Riel O(1) VM

Filed under: Uncategorized — Muli Ben-Yehuda @ 4:10 PM

Fri, 15:00

Rik van Riel, previously of connectiva, now working for redhat, talking about toward an O(1) VM.

Machines get faster, but many operations get slower

page_launder: cleaning up pages (writing them to disk) in order to evict them from memory.

Split the inactive list in order to avoid scanning the entire list: – inactive dirty – pages might be clean or dirty – inactive laundry – ? – inactive clean – clean, just get rid of it

page aging: which pages from the active list to remove? 2.4-rmap uses LFRU approximation.

page aging: sort the active list based on level of activity of pages. many lists of pages, pageout moves each list one level down (toward inactivity), page_referenced bit moves a page up one list.

reverse mapping fundamentals:

regular reverse mapping (per page) simple, no corner cases set it up on fork, tear it down on exec – overhead!

object based rmap: rmaps non-existing ptes as well (because it’s per vma) needs to be searched in pageout path only works for linearly mapped file backed objects nasty interactions with truncate, remap_file_pages

conclusions: bottlenecks keep moving access patterns keep changing computers, processes keep growing

VM needs to be adjusted: more intelligent writeout of dirty pages better replacement algorithms beter search algorithms more scalable locking

O(1) VM is probably impossible, due to the problem space

Research required for a VM design that fits modern machines and workloads [maybe something I could work on…!]

Leave a Comment »

No comments yet.

RSS feed for comments on this post. TrackBack URI

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

Blog at

%d bloggers like this: