Page Tables

Kenton Lam

This is from a CSSE2310 lecture on 29/08/2019. Page tables are complicated (not really).

Multi-level example

Given a multi-level page table struct, how much memory is needed for the page table if
512MiB of contiguous memory is in use?

Assume:

• 32-bit virtual address space
• 4 KiB page size
• 4 byte page table entry
• Memory addresses starts at 0 (normally 0 is invalid because of the NULL pointer)

First, we compute the number of pages. This is equal to the number of entries we need to store because one page has exactly one page table entry.
$\begin{array}{rl}{\displaystyle \text{number of entries}=\text{number of pages}}& {\displaystyle =\frac{\text{memory in use}}{\text{page size}}}\\ {\displaystyle }& {\displaystyle =512\text{ MiB}\mathrm{/}4\text{ KiB}}\\ {\displaystyle }& {\displaystyle =2^{29}\mathrm{/}{2}^{12}=2^{17}}\end{array}$
\begin{aligned}
\text{number of entries} = \text{number of pages} &= \frac {\text{memory in use}} {\text{page size}} \
&= 512\text{ MiB} / 4 \text{ KiB} \
&= 2^{29} / 2^{12} = 2^{17}
\end{aligned}

However, the page table itself is stored in pages. We compute how many page table entries can be stored per page.
$\begin{array}{rl}{\displaystyle \text{entries in one page}}& {\displaystyle =\frac{\text{size of page}}{\text{size of entry}}}\\ {\displaystyle }& {\displaystyle =2^{12}\mathrm{/}{2}^2=2^{10}}\end{array}$
\begin{aligned}
\text{entries in one page} &= \frac {\text{size of page}} {\text{size of entry}} \
&= 2^{12} / 2^{2} = 2^{10}
\end{aligned}

Now, we work out how many pages are used to store the page table.
$\begin{array}{rl}{\displaystyle \text{pages in page table}}& {\displaystyle =\frac{\text{number of entries}}{\text{entries per page}}}\\ {\displaystyle }& {\displaystyle =2^{17}\mathrm{/}{2}^{10}=2^7}\end{array}$
\begin{aligned}
\text{pages in page table} &= \frac{\text{number of entries}} {\text{entries per page}} \
&= 2^{17} / 2^{10} = 2^7
\end{aligned}

At this point, this is the number of pages in the second level of the page table. We need one extra page for the top level table. Therefore, the final answer is
$(2^7+1)\times 4\text{ KiB}=516\text{ KiB}\mathrm{.}$
(2^{7} + 1) \times 4 \text{ KiB} = 516 \text{ KiB}.

Another case

As above, but how much memory is used if only 1 MiB is used (contiguous)?

Again, we compute the number of pages.
$\begin{array}{rl}{\displaystyle \text{number of entries}=\text{number of pages}}& {\displaystyle =1\text{ MiB}\mathrm{/}4\text{ KiB}}\\ {\displaystyle }& {\displaystyle =2^{20}\mathrm{/}{2}^{12}=2^8}\end{array}$
\begin{aligned}
\text{number of entries} = \text{number of pages} &= 1\text{ MiB} / 4 \text{ KiB} \
&= 2^{20} / 2^{12} = 2^{8}
\end{aligned}

We compute how many page table entries can be stored per page.
$\begin{array}{rl}{\displaystyle \text{entries in one page}}& {\displaystyle =\frac{\text{size of page}}{\text{size of entry}}}\\ {\displaystyle }& {\displaystyle =2^{12}\mathrm{/}{2}^2=2^{10}}\end{array}$
\begin{aligned}
\text{entries in one page} &= \frac {\text{size of page}} {\text{size of entry}} \
&= 2^{12} / 2^{2} = 2^{10}
\end{aligned}

Now, we work out how many pages are used to store the page table.
$\begin{array}{rl}{\displaystyle \text{pages in page table}}& {\displaystyle =\frac{\text{number of entries}}{\text{entries per page}}}\\ {\displaystyle }& {\displaystyle =\lceil 2^8\mathrm{/}{2}^{10}\rceil =1}\end{array}$
\begin{aligned}
\text{pages in page table} &= \frac{\text{number of entries}} {\text{entries per page}} \
&=\left\lceil 2^{8} / 2^{10}\right\rceil = 1
\end{aligned}

Note that above, we rounded up because we can't use part of a page. This is the number in the second level of the page table. We need one extra page for the top level table. Therefore, the final answer is
$\text{page table size}=(1+1)\times 4\text{ KiB}=8\text{ KiB}\mathrm{.}$
\text{page table size} = (1 + 1) \times 4 \text{ KiB} = 8 \text{ KiB}.

Exercise

Consider a system with 36-bit physical addresses and 32-bit virtual addresses. Pages are 8 KiB each and page table entries are 4 bytes each.

• In a system with single-level page tables, how much memory is used by the page table for the process?
• If multi-level page tables are used, how much memory is used by the page table if the process uses 1 GiB contiguous?

Remark: Single-level page tables will always use a fixed amount of memory. Multi-level tables will adapt to the amount of memory being used.

Single-level

In a single-level page table, the page table must be big enough to hold an entry for every virtual address. Thus,
$\begin{array}{rl}{\displaystyle \text{number of entries}}& {\displaystyle =\frac{\text{possible virtual addresses}}{\text{page size}}}\\ {\displaystyle }& {\displaystyle =2^{32}\mathrm{/}{2}^{13}=2^{19}}\end{array}$
\begin{aligned}
\text{number of entries} &= \frac {\text{possible virtual addresses}} {\text{page size}} \
&= 2^{32} / 2^{13} = 2^{19}
\end{aligned}

As in the previous case, how many entries can we fit into one page?
$\begin{array}{rl}{\displaystyle \text{entries per page}}& {\displaystyle =\frac{\text{page size}}{\text{entry size}}}\\ {\displaystyle }& {\displaystyle =2^{13}\mathrm{/}{2}^2=2^{11}}\end{array}$
\begin{aligned}
\text{entries per page} &= \frac{\text{page size}} {\text{entry size}} \
&= 2^{13} / 2^2 = 2^{11}
\end{aligned}

Next, we work out how many pages the page table is
$\begin{array}{rl}{\displaystyle \text{number of pages in page table}}& {\displaystyle =\frac{\text{number of entries}}{\text{entries per page}}}\\ {\displaystyle }& {\displaystyle =2^{19}\mathrm{/}{2}^{11}=2^8}\end{array}$
\begin{aligned}
\text{number of pages in page table} &= \frac{\text{number of entries}} {\text{entries per page}} \
&=2^{19} / 2^{11} = 2^8
\end{aligned}

Thus,
$\begin{array}{r}{\displaystyle \text{page table size}=2^8\times 2^3=2^{11}=2048\text{ KiB}\mathrm{.}}\end{array}$
\begin{aligned}
\text{page table size} = 2^8 \times 2^3 = 2^{11} = 2048 \text{ KiB}.
\end{aligned}

Multi-level

Note that $2^{10}$ bytes is one KiB. Because GiB is 3 orders of magnitude larger than KiB, 1 GiB is $2^{30}$ bytes. Now we're going to skip a few steps. Some numbers are reused from calculations above.
$\begin{array}{rl}{\displaystyle \text{number of pages}}& {\displaystyle =\text{number of entries}=2^{30}\mathrm{/}{2}^{13}=2^{17}}\\ {\displaystyle \text{pages in table}}& {\displaystyle =2^{17}\mathrm{/}{2}^{11}=2^6}\\ {\displaystyle \text{size of table}}& {\displaystyle =(2^6+1)\times 2^3\text{ KiB}=520\text{ KiB}}\end{array}$
\begin{aligned}
\text{number of pages} &= \text{number of entries} = 2^{30} / 2^{13} = 2^{17} \
\text{pages in table} &= 2^{17} / 2^{11} = 2^6 \
\text{size of table} &= (2^6+1) \times 2^{3} \text{ KiB} = 520 \text{ KiB}
\end{aligned}