Part 6 of 7 · 4 min read
Gains and costs
What paging gives, and what it costs
Paging gives the kernel several things at once.
- No external fragmentation. Any free frame fits any page.
- Non-contiguous processes. A process can be larger than any single free region.
- Protection. Each process has its own table, so it can reach only frames that its table maps. The control bits add finer rules: a page can be read-only, or marked as not executable.
- Sharing. Two processes can map the same frame in their tables. Both libraries and code can have one physical copy for many processes (page 6).
- Moving. The kernel can move a page to a different frame, and change one table entry, without the process noticing.
In plain words: The kernel keeps a separate table for each process. At a context switch (Level 1), it loads the address of the next process's table into a register of the processor. On x86-64, this register is CR3. Changing it makes all later accesses use the new table. This is the paging form of loading the base register of page 1.
The cost is the lookup. Without help, every memory access of a program needs two memory accesses: one to read the page table entry, and one to read the data. A program would run at half speed. With a multi-level table (page 4), a lookup takes even more reads. Page 5 shows the cache of recent translations, the TLB, which makes the cost small in the usual case.
Paging
Paging is a memory management scheme in which the virtual address space of each process is divided into equal pages that are mapped, through a per-process page table, to equal frames anywhere in the physical memory.
Example: a process whose pages sit in frames 5, 9, 7 and 2 still sees one continuous range of addresses from 0 to 4,095.
Common mistake
The offset is never changed by the translation. If a student's answer has a different offset in the physical address, the arithmetic has gone wrong. Only the page number is replaced by the frame number.
Interview angle
"Explain how virtual memory works." Start with pages and frames, then the split of an address into page number and offset, then the page table lookup. Add the two costs (extra memory accesses, and the table size) and say that the TLB and multi-level tables address them.
Check yourself: 1. Name two things that paging gives that base and limit did not. 2. What does the kernel do with the page table register at a context switch? 3. Why would every access be twice as slow without a TLB?
Words you will meet
| Word | Meaning |
|---|---|
| Page | A fixed-size block of the virtual address space |
| Frame | A fixed-size block of physical memory |
| Page number | The high bits of a virtual address |
| Offset | The low bits, the position inside a page |
| Page table | The per-process table that maps pages to frames |
| PTE | One entry of the page table |
| Present bit | Tells whether the page is in memory |
| Dirty bit | Set by the hardware when the page is written |
| Accessed bit | Set by the hardware when the page is used |
| CR3 | The x86-64 register that points to the current page table |
Quick notes
- A page is a fixed-size block of a process's virtual address space, and a frame is a block of the same size in the physical memory; paging places each page in some frame, in any order.
- A page table is a per-process table, kept in memory, that holds for each virtual page the number of the frame that contains it, together with control bits; the hardware.
- A page table entry (PTE) is one record of a page table: it holds the frame number of a page and control bits such as present, writable, user, accessed and dirty, which the hardware checks and updates on each access.
- 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.
- Paging is a memory management scheme in which the virtual address space of each process is divided into equal pages that are mapped, through a per-process page table, to equal frames anywhere in the physical memory.