replacing the page replacement algo.
If I wanted to experiment with different algorithms that chose which page to replace (say on a page fault) what functions would I have to replace? or in other words, is there any good place that explains the code path of how pages are chosen to be swapped out. For example, by scheduling, its easy to replace the scheduler because all you need to deal with is schedule() and possibly add_to/del_from runqueue, with schedule() being the important function, is there an equivalent function in 2.4 for choosing pages to swap out?
thanks,
shaya potter
Signature · 1 line
spotter@{cs.columbia.edu,yucs.org}Quoted 3 lines · Shaya Potter
If I wanted to experiment with different algorithms that chose which page to replace (say on a page fault) what functions would I have to replace?
try_to_free_pages() and all the functions it calls.
Rik
Signature · 3 lines
Shortwave goes a long way: irc.starchat.net #swl http://www.surriel.com/ http://distro.conectiva.com/
Quoted 7 lines · Rik van Riel
Quoted 3 lines · Shaya Potter
If I wanted to experiment with different algorithms that chose which page to replace (say on a page fault) what functions would I have to replace?
try_to_free_pages()and all the functions it calls.
I was looking at vmscan.c and it appears that swap_out() is what I want. If instead of having it step through the mmlist, I give it the explicit mm of the processes that I want a page swapped out from? so I could implement my algorithm either inside that func or as function calls from it and have it pass onto swap_out_mm() the mm of the processes I choose to swap out.
or am I totally misunderstanding something here? (likely, as this is my first time digging into the vm and trying to learn about it)
thanks,
shaya potter
Quoted 11 lines · Shaya Potter
Quoted 7 lines · Rik van Riel
Quoted 3 lines · Shaya Potter
If I wanted to experiment with different algorithms that chose which page to replace (say on a page fault) what functions would I have to replace?
try_to_free_pages()and all the functions it calls.I was looking at
vmscan.cand it appears thatswap_out()is what I want.
You're missing the fact here that swap_out() only unmaps pages from processes' page tables, actual reclaiming of the pages is done elsewhere.
Rik
Signature · 3 lines
Shortwave goes a long way: irc.starchat.net #swl http://www.surriel.com/ http://distro.conectiva.com/
Quoted 8 lines · Rik van Riel
Quoted 7 lines · Shaya Potter
Quoted 6 lines · Rik van Riel
Quoted 3 lines · Shaya Potter
If I wanted to experiment with different algorithms that chose which page to replace (say on a page fault) what functions would I have to replace?
Quoted 8 lines
Quoted 4 lines
Quoted 1 line
try_to_free_pages()and all the functions it calls.I was looking at
vmscan.cand it appears thatswap_out()is what I want.You're missing the fact here that
swap_out()only unmaps pages from processes' page tables, actual reclaiming of the pages is done elsewhere.
ok, but if what I'm interested in playing with right now is playing around with which pages get swapped out, and not with the actual reclamation procedure, is it ok to just play with swap_out and having it do the thing it does, and let the rest of the kernel behave as is, or will this cause problems?
thanks again,
shaya potter
Quoted 5 lines · Shaya Potter
ok, but if what I'm interested in playing with right now is playing around with which pages get swapped out, and not with the actual reclamation procedure, is it ok to just play with
swap_outand having it do the thing it does, and let the rest of the kernel behave as is, or will this cause problems?
The name of swap_out is historical. It currently does no writing to disk it just removes the page from the page tables. But the page is still in RAM. The other routines are what decide which page should actually be reused, or which pages get written.
The current code is both simple, auto-tuning and does a fairly good job so look very closely at it before trying to randomly tune it.
Eric
Quoted 5 lines · Shaya Potter
ok, but if what I'm interested in playing with right now is playing around with which pages get swapped out, and not with the actual reclamation procedure, is it ok to just play with
swap_outand having it do the thing it does, and let the rest of the kernel behave as is, or will this cause problems?
No, it's quite a bit more complex than you imagine. I'll do a *very quick* trip through it.
Swap_out and shrink_caches work together to decide which pages to evict. The interaction is quite subtle. Basically, swap_out scans through virtual memory doing one of two things to each page:
- If the page was referenced, set the reference bit in the struct page
- Otherwise unmap the page so that it can eventually be evicted
The rest of the work is done by shrink_caches. It is concerned with two
lists: an 'active' LRU list and a 'inactive' FIFO list, each of which is a list of struct page, i.e., descriptors of physical pages. It also has to worry about some caches that aren't simple, replaceable pages. All the following things are being done, more or less at the same time:
- Move referenced pages from the tail of the active list to the head of the active list (implements 'LRU' policy)
- Move unreferenced pages from the tail of the active list to the head of the inactive list (queue for eviction)
- Move referenced pages from the tail of the inactive list to the head of the inactive list
- Schedule dirty pages at the tail of the inactive list for writeout
- Recover clean pages from the tail of the inactive list
- Explicitly shrink the dcache, icache and dqcache as necessary by evicting objects from those caches in the hope of recovering pages from them.
You can think of the whole process as being roughly divided into two parts:
virtual scanning (swap_out) and physical scanning (refill_inactive, shrink_cache). The reason for dividing it this way is simple: the only way we can associate the hardware page-referenced bit with a physical page is by scanning all the page tables (the virtual scan). I.e, there is no way to find that hardware bit, starting from a struct page, and we do need the information in that bit to decide which process pages should be evicted.
Some non-scanning events can occur that affect the page replacement process:
- A page may be explicitly touched by file IO, which is another way for a page to move from the inactive to active list.
- A process page that has been unmapped may be faulted back in before shrink_caches gets around to evicting it
These are two different kinds of 'rescue'. The efficient operation of the replacement policy relies on such rescuing.
I hope you can see now that tweaking the page replacement policy is not a simple matter of playing with any single function. All the parts I described work together in a complex dance. I glossed over many important details as well, particularly the fact that you can't consider page eviction in isolation from page allocation. I didn't even touch on zone balancing.
Good luck, have fun reading the code. If you're ready to do serious work on the page replacement policy in less than 6 months you'll be doing very well. You might want to head on over to www.kernelnewbies.org and have a read through some of the excellent background material there.
--
Daniel
Quoted 9 lines · Daniel Phillips
Quoted 5 lines · Shaya Potter
ok, but if what I'm interested in playing with right now is playing around with which pages get swapped out, and not with the actual reclamation procedure, is it ok to just play with
swap_outand having it do the thing it does, and let the rest of the kernel behave as is, or will this cause problems?No, it's quite a bit more complex than you imagine. I'll do a *very quick* trip through it.
[snip complex interaction in standard kernel]
Shaya, if you want a VM where you can easily change the page replacement algorithm, you probably want to work on top of my 'rmap' patch. The VM in that patch uses reverse mappings to determine which process uses a page, so you could put normal clock, lru, ... algorithms on top of it.
Things like swap_out() are completely gone in my patch, it's just one selection based on physical page.
regards,
Rik
Signature · 3 lines
Shortwave goes a long way: irc.starchat.net #swl http://www.surriel.com/ http://distro.conectiva.com/