4.3.2. Use of Page Table
Translation of hierarchical address with lookup in page table” by Max Lütkemeyer and Jens Lechtenbörger under CC BY-SA 4.0; from GitLab
For paging, we consider virtual addresses as hierarchical objects,
where some bits enumerate pages while the remaining bits enumerate
bytes within those pages. For the sake of this
example, we suppose that virtual addresses have a size of 20 bits,
while physical addresses only have a size of 15 bits.
It is quite common that virtual address spaces are larger than the
size of physical RAM. Indeed, recall from the
that virtual address spaces also cover areas of secondary storage.
Moreover, recall that pages and frames have the
Here the size is determined by 10 bits. Thus, pages and frames share
the same size of 2 10 B = 1 KiB.
In practice, 4 KiB is a typical size for pages and frames, and addresses
are much larger than 20 bits. (E.g., with 32 bits, we can address up to
32 B = 4 GiB. Even “small” devices such as smartphones may have
more RAM than that, requiring more address bits…)
We see that the first 10 bits making up the page number are used as
index into the page table, where the frame number for the page is
found. In fact, the page table shown here is the beginning of the
table of the previous slide (but we omit valid bits for simplicity here).
The remaining 10 bits are used as stable
pages and frames as illustrated next.
4.3.3. Offset as Address Covered by Range
image/svg+xml 10 bits 10 bits Virtual page number Page offset 10 bits 5 bits Frame number Page offset Virtual page number 3 Virtual page number 2 Virtual page number 1 Virtual page number 0 Frame number 3 Frame number 2 Frame number 1 Frame number 0 1 KiB 1 KiB 1 KiB 1 KiB Address Translation 1 KiB 1 KiB 1 KiB 1 KiB Start of page 0 Offset Start of frame 1 Offset
Address translation with offset in covered address range” by Max Lütkemeyer and Jens Lechtenbörger under CC BY-SA 4.0; from GitLab
For a different view on the hierarchical nature of virtual addresses,
let us continue the previous scenario of virtual addresses of 20 bits,
to be translated to physical addresses of 15 bits, with a page size of
Out of the 2
10 = 1024 possible pages and 2 5 = 32 possible frames,
only the first four of each type are shown.
As before, suppose that page 0 is located in frame 1 as recorded in
the page table. Thus, for translation of addresses falling into page
0, the 0 encoded in the first 10 bits of the virtual address is
replaced by a 1 encoded in the first 5 bits of the physical address.
Importantly, the 10 offset bits do
not change under address
Note how each page and each frame cover a range of addresses, starting
at 0 and (given 10 bits for the offset) ending at 1023 (= 2
The offset identifies a single byte in that range.
Subsequent slides provide sample calculations for address translation.
4.5. Challenge: Page Table Sizes
E.g., 32-bit addresses with page size of 4 KiB (2
Virtual address space consists of up to 2
32 B = 4 GiB = 2 20 pages
Every page with entry in page table
If 4 bytes per entry, then
4 MiB (2 22 B) per page table
Page table itself needs 2
10 pages/frames! Per process! Much worse for 64-bit addresses
Outlook: Two approaches to reduce amount of RAM for page tables
Multilevel (or hierarchical)
page tables (2 or more levels)
Tree-like structure, efficiently representing large unused areas
Entries cover larger address space portions
While the sample pages tables shown so far may seem simple to manage,
pages tables can be huge in practice. As page tables are used to
locate data in RAM, a naïve implementation might require the page
tables themselves to be located in RAM in the first place. Let’s see
how large page tables might get.
With 32-bit addresses, you see a calculation on this slide, showing
that the page table for every process requires up to 4 MiB of RAM.
Note that those 4 MiB are pure OS overhead, unusable for applications.
So, after you booted your system half a GB of RAM may already be gone.
Although this result is already pretty bad, for 64-bit systems the
situation is much worse, even if current PC processors do not use all
64 bits for addressing. Suppose 48 bits are used for virtual
addresses, again with 4 KiB pages. Then 2
36 pages may exist per
process, now maybe with 8 B per entry in the page table, leading to
2 39 B = 2 9 GiB = 512 GiB. In words: A single page table might
occupy 512 GiB of RAM, quite likely more than you’ve got.
Solutions to reduce the amount of RAM for page tables fall into two
classes, namely multilevel page tables and inverted page tables.
The key idea of multilevel page tables is that large portions of the
theoretically possible virtual address space remain unused, and such
unused portions do not need to be represented in the page table. To
efficiently represent smaller (used) and larger (unused) portions, the
page table is represented and traversed as a tree-like structure with
multiple levels. The root of that tree-like structure is always
located in RAM and is called page directory. Each entry in that page
directory represents a large portion of the address space, in case of
32-bit addresses and two levels (as on
represents 1024 pages with a total size of 4 MiB. If such a 4 MiB
region is not used at all, no data needs to be allocated in lower
levels of the tree like structure.
The key idea of inverted page tables is that RAM is limited and
typically smaller than the virtual address space. Instead of storing
each allocated frame per page as discussed so far, with inverted page
tables one entry exists per frame of RAM, recording what page of what
process is currently located in that frame (if any). Note that only
one such inverted page table needs to be maintained, whereas page
tables exist per process. Also note that the number of entries of the
inverted table is determined by the number of frames in RAM, instead
of the (potentially much larger) number of pages of virtual address
space. You will see how address translation works with inverted page
tables on later slides. Right now, you may want to think about that
yourself. Starting again from a page number for which the
corresponding frame number is necessary, how do you locate the
appropriate entry in the inverted page table? Clearly, a linear
search is too slow.