Enhancing the Efficiency of Memory Management in a Super-Paging Environment by AMSQM

Introduction

The paging concept is very old and well-known. Super-Paging is an augmentation for this well-known concept. Super-Pages are larger pages that are pointed to by the TLB (Khalidi et al., 1993). The internal memory of modern computers has been drastically increased during the last decades. However, the TLB coverage (i.e. the size of the memory that can be pointed to directly by the TLB) has been increased by a much lower factor during the same period (Navarro, 2004), (Navarro et al., 2002). Therefore, several new architectures like Itanium, MIPS R4x00, Alpha, SPARC and HP PA RISC support multiple page size of the frames pointed to by the TLB. In that way the memory size pointed to directly by the TLB is higher and the overhead of the page table access time is reduced. There are also some particular operating systems that support Super-Paging e.g. (Ganapathy and Schimmel, 1998), (Subramanian et al., 1998), (Winwood et al., 2002).

The Super-Paging concept brings up several questions to discuss in the operating systems community. First, when should the Operating System upgrade some base pages into a large Super-Page? This dilemma is even more complicated when the processor supports several sizes of Super-Pages; e.g. the Itanium has 10 sizes of Super-Pages. Second, where should the location of the small pages in the memory be? One possibility is placing them in a location that spares the need for relocation of the base page, once the Operating System upgrades base pages into a Super-Page (Talluri and Hill, 1994). Another policy is placing the base page in the first vacant location in the memory and relocating it when the Operating System upgrades (Romer et al., 1995). Thirdly, who handles the relocation, the hardware or the software (Fang et al., 2001)? Some processors and Operating Systems have addressed these questions as was mentioned above. More about Super-pages can be read at (Wiseman, 2005).

In this chapter a new algorithm for page replacement in a Super-Paging environment is suggested (Itshak and Wiseman, 2009). The new algorithm is based on some parameters including the page size. The results show better TLB miss rate for the benchmarks used for testing.

Multimedia applications typically have large portions of memory that are clustered in few areas. Such applications can benefit Super-Paging enormously (Abouaissa et al., 1999). Also, nowadays computers usually have large memories (Wallace et al., 2006), (Geppert, 2003); hence, larger pages can be used; however using larger pages can apparently cause a higher page fault rate. This is a well-known flaw of the Super-Paging mechanism; however the algorithm suggested in this chapter does not suffer from this flaw and even utilizes the usual behavior of the paging mechanism to reduce the page fault rate. The algorithm actually makes use of the locality principle to prefetch base-pages that are a part of heavy used Super-pages and the results show that this prefetching makes the memory hit percents better.

We also aim at developing a good technique that finds the best page to be taken out when the page fault mechanism requires this in a Super-Paging environment based on all the available parameters. Here again the locality principle that the Super-paging environment induces helps us to select the victim page better, because if page's neighbors have been accessed, it can imply that the page itself might be accessed as well and it may not be a good choice to swap the page out as the common base-page algorithms would have done.

The question of which page should be taken out also occurs in higher levels as well i.e. Which page should be in the cache and which page should be pointed to by the TLB. The algorithm suggested in this chapter can be also a good alternative for the well-known Clock algorithm in these decisions.