First goal is to find for given load pattern of system the best possible page allocation scheme. Then we can say for example that current AA VM is only 20% slower than best case and that we are comfortable with it. If we find that the best case is either always or for some load scenarios 3 times faster (see what I mean be speed below) then
Second goal is to find cheap algorithm which would approximate the best behaviour.
VM action is one from: memory read, memory write, process wakeup, process wait and process sleep.
VM fingerprint of system is defined as paralel run of sequences. Each sequence represents one running process. The sequence elements are VM actions of the process.
# this script is names sortls ls -lR / | sort -uWhen you run the script using ./sortls command the fingerprint captured during execution might read:
Seq. name Actions sortls U(sortls) U(ls) S(10) W(0x343) R(0x432) U(sort) D(ls,sort) ls D(sortls) W(0x123) D(sort) R(0x34) sort D(sortls) R(0x234) U(ls) Key: D(x) - wait for sequence(s) x W/R(addr) - write/read memory U(x) - wakeup sequence x S(ns) - sleep some time (simulate CPU work)"ls" and "sort" sequences waits as start to be awakened by sortls script. "sortls" starts by waking itself immediately (it is "root" of all tasks here) and it forks ls (U action). Then it computes something for 10ns, makes memory read and writes and spawns sort. Then it waits for their completion.
Note that there would as many sequences as high was number of created processes
Of sourse we would need event E as exit so say that process is released and its VM pages can be used again.
The D and U (sleep & wakeup) are generated by process forking
and by waitpid (and similar). The are also generated in case where
one process is waiting on other (pipe or unix sock blocking write/read).
Only problem I see here are related to polling. If process A polls on pipe to B with timeout, it can be hard to express because we can't see what process would do after timeout.
S (sleep) is generated in just before R|W|D|U to say how much user time the process needed since last non S action till now. It allows us later to account CPU work (only relative values are important).
After some time we could have library of such fingerprints for various loads (Oracle,kernel compile,mozilla ..) and developers can use them to create and tune VM models in userspace.
io = (is_dirty + 1)/time_to_nearest_future_hitand we use frame with minimal io. I didn't attempt to prove this condition as valid predicate for dynamic programing but it seems that it should be ok.
As we go thru fingerprint we simulate behaviour of system by selecting process with smallest S value if all are in S state and we have to handle sleeps and wakeups.
Hence for each fingerprint we can compute cheapest possible paging strategy.
Just now I can think about least squares method to find set of parameters whose affect the frame selection and how. Then look at resulting function and try to create conforming algorithm.
This part should be easy.
It would be nice if someone experienced in process synchronization could bring more light into it.
Thanks for reading and if someone has something to say about it, drop me email.