Part 5 of 7 · 2 min read
Page size
In plain words: A page table has one entry for each page of the address space. Take a 32-bit address space with 4 KiB pages. There are 2^32 / 2^12 = 2^20 = 1,048,576 pages. With 4 bytes per entry, one flat table takes 4 MiB. That is large, but it is for each process: with 100 processes, 400 MiB of memory would go to page tables alone. Page 4 shows how to cut this cost.
The page size changes two things in opposite directions. The table shows a 32-bit space with 4-byte entries:
| Page size | Pages in the space | Flat table size | Average internal waste per region |
|---|---|---|---|
| 1 KiB | 4,194,304 | 16 MiB | 512 bytes |
| 4 KiB | 1,048,576 | 4 MiB | 2,048 bytes |
| 64 KiB | 65,536 | 256 KiB | 32,768 bytes |
Smaller pages waste less memory inside the last page, and follow the program's needs more closely. They also need a bigger table, and more entries to load into the TLB. Larger pages do the opposite. A test with random sizes between 1 and 100,000 bytes measured an average waste of 2,067 bytes with 4 KiB pages, close to the 2,048 bytes in the table.
There is also a cost in transfers. Reading a page from disk takes a seek and a rotation (Level 8), and then a transfer. Because the seek is paid once per page, a very small page wastes it on little data. For this reason, 4 KiB has been the common choice for decades, and many systems support larger pages (2 MiB or 1 GiB on x86-64) for programs that need big, steady regions. Level 7 returns to them.
An example with a full calculation: a process of 10,000 bytes, with 4 KiB pages, needs ceil(10,000 / 4,096) = 3 pages. They take 12,288 bytes of frames, and the waste is 12,288 − 10,000 = 2,288 bytes, all inside the last page.
Page size
The page size is the number of bytes in one page, and in one frame; it is a power of two, set by the hardware, and it decides both the number of table entries needed and the average internal waste.
Example: with 4 KiB pages, a 10,000-byte process needs 3 pages and wastes 2,288 bytes in the last one.
Check yourself: 1. How many pages does a 32-bit address space have with 64 KiB pages? 2. Why does a smaller page size need a larger page table? 3. What is the internal waste for a 5,000-byte process with 4 KiB pages?