Multilevel paging

1. Page tables are too big for memory

Let's say a particular processor has a 32-bit virtual address space (which is common), and a 4K (212) page size. In this case, the page number occupies the top 20 bits. In principle, this means that a process's address space may contain up to 220, or over a million pages. If each page table entry were 4 bytes (say, 20 bits for the frame number, plus 12 bits left over for housekeeping purposes), this means that each process may need up to 4MB of physical memory for its page table alone.

If the page table uses large areas of physical memory, it succumbs to the problems we faced in allocating memory for processes in the first place---memory fragmentation and the need to resize.

In actual fact, few processes use all of their virtual address space, but some may use large portions of it; some may use areas scattered around the virtual memory. With several processes running on a machine, we must find a way of reducing the size of page tables.

One way is to break the one, big page table into several smaller parts. The virtual addresses are now split into three parts, a table 1 index, a table 2 index, and an offset into the page (as before).

For example, let us take that 20 bit page number, and split it into two 10-bit indices.

We look up the first page table to find the second table, then look up the second table to find the frame in which the page is stored.

Each page table, including the top one, has only 1024 entries, few enough to fit comfortably within a 4K page.

This scheme has several advantages:

last updated 6 March 1998