Paging

Why this matters

The previous module ended with a conclusion: external fragmentation is inevitable as long as a process’s memory has to be contiguous. Paging removes that requirement.

The idea is almost trivially simple: divide both the logical and the physical space into pieces of equal size. Then any piece fits into any free slot, and the question of where to put things disappears along with fragmentation.

The price is a table that has to record which piece went where. All the complexity of paging is concentrated in that table.

Prerequisites. Logical and physical addresses, the MMU (module 10), CPU caches (module 2).

Pages and frames

A page is a piece of the logical address space; a frame is a piece of physical memory of the same size. Typically 4 KiB.

The size is always a power of two, and the reason is practical. A logical address is split into two parts by simply cutting the bits: the high bits give the page number, the low bits the offset within the page, so the hardware does no division with remainder at all.

Only the page number is translated. The offset passes through unchanged, which is why the page size has to be a power of two.

External fragmentation disappears completely, because any free page suits any need. Internal fragmentation comes back instead, but in its smallest form: what is lost is the unused tail of the process’s last page, half a page on average. With 4 KiB pages that is two kilobytes per process, which is quite livable.

A page table entry

An entry holds more than the frame number. Each one also carries bits that half of the rest of the course depends on:

Bit	Meaning	Used for
frame number	where the page is mapped	translation
valid	whether there is a mapping at all	page fault
permissions (r/w/x)	what is allowed	protection, SIGSEGV
user/kernel	whether the process can access the page	kernel isolation
accessed	whether it was accessed since the last check	replacement algorithms
dirty	whether it was written to	whether it must be saved before eviction

All of virtual memory is built on the valid-invalid bit: by clearing it, the kernel makes the hardware report any access to that page. The dirty bit saves a disk write, because an unmodified page can simply be thrown away: the copy on disk is already up to date.

The size problem

Let’s do the math for a 32-bit system with four-kilobyte pages. The offset takes 12 bits, leaving 20 for the page number, which is 2²⁰ = 1,048,576 entries. At 4 bytes per entry that makes 4 MiB of table for every process. A hundred processes eat 400 MiB on page tables alone.

Work out the 64-bit case yourself. x86-64 uses 48 significant address bits, 12 of them for the offset, so the page number takes 36 bits: 68,719,476,736 entries of 8 bytes give 512 GiB of table for every process, a table larger than the memory it describes.

One observation saves the day: the address space is almost empty. A process uses a few regions (code, heap, stack, libraries), and between them stretch gigabytes of nothing. Storing entries for emptiness is pointless.

Multi-level page tables

Instead of one huge table, you build a tree of tables. The page number is cut into several parts, and each part indexes its own level.

On x86-64 an address breaks down into four 9-bit indices plus a 12-bit offset, and each table takes exactly one page, that is, 512 entries of 8 bytes. If an entire subrange of addresses is unused, the lower-level table for it is simply never created, and millions of empty entries do not physically exist.

We pay for this with translation requiring four memory accesses instead of one, and only then a fifth, for the data itself. If it were not for the next section, paging would be five times slower than direct addressing.

Alternatives that didn't catch on

An inverted page table stores one entry per physical frame instead of one per logical page, so its size depends on the amount of memory rather than on the number of processes. The problem is that lookup goes by content rather than by index, so hashing is needed, and shared memory is hard to implement. Hashed page tables solve the lookup but add collision handling. Both approaches were used on PowerPC and IA-64 and lost to multi-level tables because of their complexity.

TLB

The translation lookaside buffer is a small associative cache inside the MMU that holds a few dozen or a few hundred ready-made “page number → frame number” pairs.

On a hit, translation costs a fraction of a cycle. On a miss, all levels of the table have to be walked, which is four memory accesses, each of which can miss the data cache.

All of the practical efficiency of paging rests on the hit rate, and it is high thanks to locality: a program touches a small number of pages for a long time. Typically the hit rate is above 99%.

In profiling it looks like this: code that traverses a large data structure in random order is slow not only because of data cache misses but also because of TLB misses. These are different caches with different counters.

Context switches create a separate problem. The new process’s tables are different, so the old contents of the TLB are invalid, and flushing the TLB completely is expensive. That is why modern CPUs tag entries with an address space identifier, PCID on x86, and entries from different processes coexist peacefully.

Huge pages

The number of TLB entries is fixed. At 4 KiB per entry, a 1500-entry buffer covers about 6 MiB, while a database’s working set is measured in gigabytes. Misses become constant.

Huge pages, 2 MiB or 1 GiB on x86-64, solve this problem: one TLB entry covers 512 times more memory, and the gain for databases and virtual machines is noticeable immediately.

The price is coarse granularity. Internal fragmentation is now counted in megabytes, and evicting 2 MiB to disk costs more than 4 KiB. So huge pages are enabled selectively.

Segmentation

The historical alternative to paging. Instead of equal pieces, it uses variable-size regions by purpose: a code segment, a stack segment, a data segment. An address consists of a segment number and an offset, and the segment table stores the base and limit of each segment.

Its appeal is that the boundaries match the logical boundaries of the program. Running past the end of an array in its own segment is caught by the hardware, and access permissions naturally apply to the whole region.

The catch is that it has the same drawback as variable-size partitions: external fragmentation. That is why x86 in 32-bit mode combined both mechanisms: segmentation on top, paging underneath.

In 64-bit mode segmentation was effectively abolished. Segment bases are forced to zero, and all that is left of the mechanism are scraps such as FS and GS for thread-local storage.

Paging is not swapping

These two are easy to confuse, although they have little in common. Paging is an address translation mechanism: splitting the space into pages and mapping them to frames. It is always on, even when there is plenty of free memory and the disk is not involved at all. Swapping moves data between RAM and disk when memory runs short.

How it actually works in Linux

getconf PAGESIZE

The page size in bytes. On x86-64 it is 4096; on ARM64 it can be 16384 or 65536.

grep -E 'Huge|AnonHugePages' /proc/meminfo

The state of huge pages. AnonHugePages is how much memory is already covered by transparent huge pages, which the kernel assembles automatically.

grep Hugepagesize /proc/meminfo; grep -o pdpe1gb /proc/cpuinfo | head -1

Hugepagesize is the default huge page size, 2 MiB on x86-64. There is no need to look for a separate flag for them: in 64-bit mode they are always available. pdpe1gb, on the other hand, really does show whether the CPU supports 1 GiB pages.

The `pse` flag has nothing to do with it

It is often cited as a sign of support for two-megabyte pages, and that is a misunderstanding: pse (page size extension) refers to 4 MiB pages in 32-bit paging. It is always set on any modern CPU, so it checks nothing.

awk '/^Rss|^Pss|^AnonHugePages/ {s[$1]+=$2} END {for (k in s) print k, s[k]" kB"}' /proc/self/smaps

smaps gives a breakdown for every mapping. Pss is the share of shared pages divided by the number of users: a more honest estimate of consumption than Rss.

perf stat -e dTLB-load-misses,dTLB-loads,cache-misses -- sh -c 'i=0; while [ $i -lt 200000 ]; do i=$((i+1)); done'

TLB misses and data cache misses, separately. On a sequential traversal there are almost none of the former; with random access to a large structure they become a noticeable item of cost.

Common misconceptions

“Paging kicks in when memory runs out.” It does not kick in, because it is a way of addressing that is always on. Swapping is what involves the disk, and that is a completely different mechanism.

“The page table is stored in the CPU.” It lives in RAM. The CPU has only a register with the address of the table’s root, CR3 on x86, and a cache of ready translations, that is, the TLB.

“The TLB caches data.” The TLB caches translations; data is cached in L1, L2 and L3. These are different caches, they miss independently, and perf has different counters for them.

“A bigger page size is always better.” There really are fewer TLB misses, but internal fragmentation is larger and eviction more expensive. The gain comes where the working set is large and contiguous; for small processes huge pages only hurt.

“Paging eliminates fragmentation.” It eliminates external fragmentation. Internal fragmentation does not go anywhere; it just shrinks to half a page per process on average.

“Segmentation is obsolete and unnecessary.” The idea of protecting regions by purpose is alive and well: it moved into the permission bits of the page table entry. What did not survive is segmentation as a way of allocating memory.

Check yourself

1. Why is the page size always a power of two?

It is easier for a human to countSo that a logical address splits into page number and offset by simply cutting bits, without divisionThe POSIX standard requires itSo that a page fits into the CPU cache

2. A 32-bit system, 4 KiB pages, 4-byte entries. How large is a single-level page table per process?

4 KiB1 MiB4 MiB4 GiB

3. How does a multi-level page table save memory?

It compresses entriesLower-level tables are simply not created for unused address rangesIt stores the table on diskIt uses smaller pages

4. What exactly does the TLB cache?

Data from memoryReady-made “page number → frame number” pairsCPU instructionsFile contents

5. What is the difference between paging and swapping?

They are synonymsPaging is an address translation mechanism and is always on; swapping moves data to disk when memory runs shortPaging is for files, swapping is for processesPaging is done in hardware, and so is swapping

6. A database with a working set of several gigabytes suffers from TLB misses. What helps the most?

Reduce the page sizeEnable huge pages: one TLB entry will cover 2 MiB instead of 4 KiBEnlarge the swap fileAdd levels to the page table

Lab

A5 — page replacement simulator. From this module the lab needs the page table entry: the present bit, which distinguishes a hit from a page fault, and the accessed bit, on which the clock algorithm depends. The replacement algorithms themselves and the full lab description are in module 12.

Sources

• OSTEP: Paging: Introduction, Faster Translations (TLBs), Smaller Tables
• Silberschatz, Operating System Concepts, chapter 9
• Documentation/mm — memory management in Linux
• man 2 mmap, man 5 proc (the smaps section)