Prof. Dr. Frank Bellosa, Marc Rittinghaus

Abstract:

In this work we analyze the capability of the IA-32e architecture's page table entry format to accurately record memory access behavior of processes. Operating systems use the recorded behavior as input to their page replacement algorithms in order to select memory pages for eviction to slower external storage in case free memory gets sparse. Furthermore, we investigate the applicability of two improved page table entry formats, providing more accurate memory access information, to improve the page replacement algorithm's replacement decisions.

We find that page table entry formats reserving too few storage space for recording page reference information suffer from both temporal as well as reference counter inaccuracies as they fail to accurately reflect the timings as well as frequency of page references. The IA-32e architecture, reserving only a single bit, is particularly affected.

In order to quantify the reference counter inaccuracies we record both memory accesses as well as the operating system's interaction with the page tables of a number of benchmarks running in Linux using the Simutrace toolchain. We reconstruct the actual as well as the hypothetical accurate state of the page tables in order to learn the number of page references going unrecorded. Our evaluation shows that the IA-32e architecture's page table format fails to provide accurate page reference counts. Furthermore, it reveals that it is also unable to rank pages approximately according to their reference frequencies, potentially causing poor page replacement decisions.

As a second step, we investigate the applicability of more accurate page access information to improve page replacement decisions. To this end, we simulate paging using an adapted Mattson stack algorithm and previously recorded memory access sequences in order to learn the number of page faults that page replacement algorithms produce on given page table entry formats. However, we find that more accurate page access information does not benefit page replacement since even a single bit is sufficient to identify pages without any references, that is suitable replacement victims. These occur sufficiently often to let more accurate page reference information go without effect.

 
BibTex:

@mastersthesis{faude14pageaccess,
 author = {Julian Faude},
 title = {On the Applicability of More Accurate Page Access Information},
 type = {Master Thesis},
 school = {Operating Systems Group, Karlsruhe Institute of Technology (KIT), Germany},
 month = jul # "31",
 year = 2014,
 note = {\url{http://os.itec.kit.edu/}}
}