CSE Roadmap

Core tier · about 6 hours · 7 parts

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?