Peter J. Denning has referenced my MSc project on the working set in a (draft) article he has written for the CRC Handbook of Computer Science and Engineering.
Advertisements
Tag: working set
Working set heuristics and the Linux kernel: my MSc report
My MSc project was titled “Applying Working Set Heuristics to the Linux Kernel” and my aim was to test some local page replacement policies in Linux, which uses a global page replacement algorithm, based on the “2Q” principle.
There is a precedent for this: the so-called “swap token” is a local page replacement policy that has been used in the Linux kernel for some years.
My aim was to see if a local replacement policy graft could help tackle “thrashing” (when a computer spends so much time trying to manage memory resources – generally swapping pages back and forth to disk – it makes little or no progress with the task itself).
The full report (uncorrected – the typos have made me shudder all the same) is linked at the end, what follows is a relatively brief and simplified summary.
Fundamentally I tried two approaches: acting on large processes when the number of free pages fell to one of the watermark levels used in the kernel and acting on the process last run or most likely to run next.
For the first my thinking – backed by some empirical evidence – was that the largest process tended to consume much more memory than even the second largest. For the second the thought was that make the process next to run more memory efficient would make the system as a whole run faster and that, in any case the process next to run was also quite likely (and again some empirical evidence supported this) to be the biggest consumer of memory in the system.
To begin I reviewed the theory that underlies the claims for the superiority of the working set approach to memory management – particularly that it can run optimally with lower resource use than an LRU (least recently used) policy.
Peter Denning, the discoverer of the “working set” method and its chief promoter, argued that programs in execution do not smoothly and slowly change their fields of locality, but transition from region to region rapidly and frequently.
The evidence I collected – using the Valgrind program and some software I wrote to interpret its output, showed that Denning’s arguments appear valid for today’s programs.
Here, for instance is the memory access pattern of Mozilla Firefox:
Working set size can therefore vary rapidly, as this graph shows:
It can be seen that peaks of working set size often occur at the point of phase transition – as the process will be accessing memory from the two phases at the same time or in rapid succession.
Denning’s argument is that the local policy suggested by the working set method allows for this rapid change of locality – as the memory space allocated to a given program is free to go up and down (subject to the overall constraint on resources, of course).
He also argued that the working set method will – at least in theory – deliver a better space time product (a measure of overall memory use) than a local LRU policy. Again my results confirmed his earlier findings in that they showed that, for a given average size of a set of pages in memory, the working set method will ensure longer times between page faults, compared to a local LRU policy – as shown in this graph:
Here the red line marks the theoretical performance of a working set replacement policy and the blue line that of a local LRU policy. The y-axis marks the average number of instructions executed between page faults, the x-axis the average resident set size. The working set method clearly outperforms the LRU policy at low resident set values.
The ‘knee’ in either plot where 
So, if Denning’s claims for the working set method are valid, why is it that no mainstream operating system uses it? VMS and Windows NT (which share a common heritage) use a local page replacement policy, but both are closer to the page-fault-frequency replacement algorithm – which varies fixed allocations based on fault counts – than a true working set-based replacement policy.
The working set method is just too difficult to implement – pages need to be marked for the time they are used and to really secure the space-time product benefit claimed, they also need to be evicted from memory at a specified time. Doing any of that would require specialised hardware or complex software or both, so approximations must be used.
“Clock pressure”
For my experiments I concentrated on manipulating the “CLOCK” element of the page replacement algorithm: this removes or downgrades pages if they have not been accessed in the time been alternate sweeps of an imaginary second hand of an equally imaginary clock. “Clock pressure” could be increased – ie., pages made more vulnerable to eviction – by systematically marking them as unaccessed, while pages could be preserved in memory by marking them all as having been accessed.
The test environment was compiling the Linux kernel – and I showed that the time taken for this was highly dependent on the memory available in a system:
The red line suggests that, for all but the lowest memory, the compile time is proportional to 
Watermarks
The first set of patches I tried were based on waiting for free memory in the system to sink to one of the “watermarks” the kernel uses to trigger page replacement. My patches looked for the largest process then either looked to increase clock pressure – ie., make the pages from this large process more likely to be removed – or to decrease it, ie., to make it more likely these pages would be preserved in memory.
In fact the result in either case was similar – at higher memory values there seemed to be a small but noticeable decline in performance but at low memory values performance declined sharply – possibly because moving pages from one of the “queues” of cached pages involves locking (though, as later results showed also likely because the process simply is not optimal in its interaction with the existing mechanisms to keep or evict pages).
The graph below shows a typical result of an attempt to increase clock pressure – patched times are marked with a blue cross.
The second approach was to interact with the “completely fair scheduler” (CFS) and increase or decrease clock pressure on the process lease likely to run or most likely to run.
The CFS orders processes in a red-black tree (a semi-balanced tree) and the rightmost node is the process least likely to run next and the leftmost the process most likely to run next (as it has run for the shortest amount of virtual time).
As before the idea was to either free memory (increase clock pressure) or hold needed pages in memory (decrease clock pressure). The flowchart below illustrates the mechanism used for the leftmost process (and decreasing clock pressure):
But again the results were generally similar – a general decline, and a sharp decline at low memory values.
(In fact, locking in memory of the leftmost process actually had little effect – as shown below:)
But when the same approach was taken to the rightmost process – ie the process that has run for the longest time (and presumably may also run for a long time in the future), the result was a catastrophic decline in performance at small memory values:
And what is behind the slowdown? Using profiling tools the biggest reason seems to be that the wrong pages are being pushed out of the caches and need to be fetched back in. At 40MB of free memory both patched and unpatched kernels show similar profiles with most time spent scheduling and waiting for I/O requests – but the slowness of the patched kernel shows that this has to be done many more times there.
There is much more in the report itself – including an examination of Denning’s formulation of the space-time product – I conclude his is flawed (update: in fairness to Peter Denning, who has pointed this out to me, this is as regards his approximation of the space-time product: Denning’s modelling in the 70s also accounted for the additional time that was required to manage the working set) as it disregards the time required to handle page replacement – and the above is all a (necessary) simplification of what is in the report – so if you are interested please read that.
Applying working set heuristics to the Linux kernel
Related articles
- Best book on Linux kernel internals (cartesianproduct.wordpress.com)
- Is the time pages are in the working set stochastic? (cartesianproduct.wordpress.com)
- Counting soft and hard faults (cartesianproduct.wordpress.com)
- Building The Linux Kernel In 60 Seconds (phoronix.com)
- Update Your Linux Kernel Without Reboot (hackstips.wordpress.com)
The binomial distribution, part 1
I think there are now going to be a few posts here which essentially are about me rediscovering some A level maths probability theory and writing it down as an aid to memory.
All of this is related as to whether the length of time pages are part of the working set is governed by a stochastic (probabilistic) process or a deterministic process. Why does it matter? Well, if the process was stochastic then in low memory situations a first-in, first-out approach, or simple single queue LRU approach to page replacement might work well in comparison to the 2Q LRU approach currently in use. It is an idea that is worth a little exploring, anyway.
So, now the first maths aide memoire – simple random/probabilistic processes are binomial – something happens or it does not. If the probability of it happening in a unit time period is 
(In operating systems terms my thinking is that if the time pages spent in a working set were governed by similar processes then there will be a half life for every page that is read in. If we discarded pages after they were in the system after such a half life, or better yet some multiple of the half life, then we could have a simpler page replacement system – we would not need to use a CLOCK algorithm, just record the time a page entered the system and stick it in a FIFO queue and discard it when the entry time was more than a half life ago.
An even simpler case might be to just discard pages once the stored number reached above a certain ‘half life’ limit. Crude, certainly, but maybe the simplicity might compensate for the lack of sophistication.
Such a system would not work very well for a general/desktop operating system – as the graph for the MySQL daemon referred to in the previous blog shows, even one application could seem to show different distributions of working set sizes. But what if you had a specialist system where the OS only ran one application – then tuning might work: perhaps that could even apply to mass electionics devices, such as Android phones – after all the Android (Dalvik) VM is what is being run each time.)
Related articles
- What are four requirements for binomial distribution (wiki.answers.com)
- Is the time pages are in the working set stochastic? (cartesianproduct.wordpress.com)
- The foundations of Statistics: a simulation-based approach (r-bloggers.com)
- Using math symbols in wordpress pages and posts – LaTex (1) (etidhor.wordpress.com)
- Using the binomial GLM instead of the Poisson for spike data (xcorr.net)
- Diagram for a Bernoulli process (using R) (r-bloggers.com)
- LaTeX (climbinggecko.wordpress.com)
- How to understand segmented binomial heaps described in (stackoverflow.com)
Done and dusted
I submitted my MSc project report yesterday, so that is it, at least for now, as a computer science student.
The report was on “applying working set heuristics to the Linux kernel“: essentially testing to see if there were ways to overlay some elements of local page replacement to the kernel’s global page replacement policy that would speed turnaround times.
The answer to that appears to be ‘no’ – at least not in the ways I attempted, though I think there may be some ways to improve performance if some serious studies of phases of locality in programs gave us a better understanding of ways to spot the end of one phase and the beginning of another.
But, generally speaking, my work showed the global LRU policy of the kernel was pretty robust.
I find out how I did in November.
Need to find some other programming task now. Mad bit of me suggests getting engaged with GNU Hurd. Though mucking about with Android also has an appeal.
Related articles
- Linux Kernel Moves To Github (linux.slashdot.org)
- How-To Debug Linux Kernel with Xilinx FPGA (lighttomorrow.wordpress.com)
What that working set comparison graph should have looked like
The graphs look similar but the differences are important – this one (the correct one), appears to confirm that Peter Denning‘s findings about the working set model versus LRU still hold good, at least in broad terms – though this still suggests LRU has better performance characteristics than might be expected.
But it’s late now and I am going to bed – perhaps more later.
Related articles
- The graph is wrong (cartesianproduct.wordpress.com)
The graph is wrong
Once I published the graph on the previous blog entry I more or less immediately realised it was wrong – it’s not that the curves are wrong: it’s that they are plotted on different scales.
The red line plots lifetime curve using the working set of the process based on pages accessed in a certain time frame – this gives an average working set size (
The blue line is the lifetime curve with a maximum working set of a fixed size (ie it is a simple LRU type page replacement simulation). But it is not scaled correctly against the x axis. Something of a waste of 31 hours of wallclock time!
Happily my 12 core box is now online and so I should have a replot done shortly – my best guess is that it may not change too much, things will be interesting if it does.
Working sets compared
NB: This graph is wrong – read more here
This shows the ‘lifetime curve’ of Xterm using a time based
The y-axis measures the average number of instructions executed between faults.
Better algorithm found
Late last night, in a state of some despair, I pleaded for computing power help with my MSc project. Today, having thought about it long and hard I found a better algorithm and speeded the whole thing up by a factor of 50.
Like, I am sure, many people previously in my position, my inspiration was the classic Programming Pearls
This is a Birkbeck set text but it’s also one that I did not read when I should have last year – or rather I just read a small part of it. Luckily I am systematically going through it now and was yesterday reading about how much of a difference a better algorithm can make – not that I did not know this, but it helped provide the determination to find one.
So what did I do. Firstly I realised that there was a specialist implementation of the Java Map interface that, as the Javadoc file explicitly says, is good for LRU caches (essentially what I am seeking to model): LinkedHashMap.
This sets up a last-accessed order and so means that it is no longer necessary to search through the whole Map to find the out-of-date pages. Using an Iterator and an EntrySet I only need to get to the first page that is not out-of-date and stop.
When I was checking that worked I noticed that temporal locality meant that in many cases the LRU page was still inside the time frame I was seeking to check – in other words literally billions of checks for outdated pages were taking place needlessly. As pages in the cache cannot get “older” (ie there reference time cannot go backwards), at time 
The result of these two changes is a massive speed up in the code – by a factor of 40 – 50.
Related articles
- Help! Computing power or better algorithm required (cartesianproduct.wordpress.com)
- Waiter! Where is My Algorithm! (laf.ee)
- MAD ALGOrithms (geomblog.blogspot.com)
- Simple algorithms, illustrated (sathyasays.com)
- When is an algorithm not an algorithm? (jrvarma.wordpress.com)
- Sorting Algorithm Explained with a Hungarian Folk Dance (neatorama.com)
- GCSE Computing Revision – What an Algorithm is, How to write it and How to use it to plan a program (mattg99.wordpress.com)
- Finally, all my PhD code released under GPL! (louisdorard.wordpress.com)
- An Israeli algorithm sheds light on the Bible (physorg.com)
Help! Computing power or better algorithm required
I have a serious problem with my MSc project.
For the first part of this I am seeking to demonstrate/investigate the underlying assumptions about locality, phases of locality and so on that underlie the working set method of VM management.
The graphs on other blogs here are some of the output of the test cases I have been using and they seem to work well.
In addition, though, I want to show what Peter Denning refers to as a “lifetime curve” for a process – essentially showing how increasing the size of the resident set (or in my case increasing the time for which pages remain resident) changes the time between page faults.
This should not (and early results of mine show) it isn’t linear (though it is monotonic). But to calculate this seems, under the algorithm I am using, to require vast amounts of computing power.
My algorithm (in Groovy) is essentially this:
1. Set time (if we are plotting 600 points then first time would be 1/600th of the process lifetime) for page expiry
2. Reading the lackeyml file and using a groovy/java map, store the page number and the reference time -if the page wasn’t referred to in the map, increase the fault count
3. Look through the map to see if there are any pages which are older than the page expiry times, and evict them from the map
4. Move to the next record in the lackeyml file and return to 2
5. Get to the end of the file and count the total faults.
The problem with all this is (2) above – typically it is being called millions of times and iterating through a map in this way is extremely slow. I think on a dual AMD64 box here with the 48 million instruction count for xterm (pretty much a ‘toy’ application in this context) – this will take 20 days to run, even with a decent bit of parallelization in the code.
Hence I need a better algorithm or massive (and affordable) computing power. Anyone have a cluster they could lend me for a few hours?
Related articles
- Introducing the lackeyml format (cartesianproduct.wordpress.com)
- Eighteen million lines of XML! (cartesianproduct.wordpress.com)
- Patterns of locality in xterm (cartesianproduct.wordpress.com)
- Bob Morris and stream algorithms (geomblog.blogspot.com)
- When is an algorithm not an algorithm? (jrvarma.wordpress.com)
- Simple algorithms, illustrated (sathyasays.com)
- Optimizing the A* algorithm (takinginitiative.net)
Memory demands of a Linux process
The graph above shows the number of (4k) pages required by xterm when running on a 32 bit Linux system – the x axis measures the lifetime of the process (as determined by instructions executed), the y axis the number of pages.
