Paging
Chapter Seventy-Four
Syllabus topic Module 2, "Memory Management - Paging"
Pages 290 to 294 of 452
In one line
Cut physical memory into fixed sized frames, cut every process's address space into pages of exactly the same size, and then any page can go in any frame.
The idea, from the problem
Chapter seventy three ended with the fault: segments are variable sized, so a hole big enough for the whole segment has to be found, and external fragmentation follows.
Paging's insight is one sentence: make every piece the same size, and then no piece can be in the wrong place. There is no such thing as a hole being too small or a frame being unsuitable. Every free frame fits every page.
And the price, from Chapter seventy two: the last page of a process is not full, so internal fragmentation appears, bounded at half a page per process on average. Paging trades an unbounded problem for a bounded one.
The two words
| Word | Is a fixed sized piece of | Typical size |
|---|---|---|
| Frame | physical memory | 4 kilobytes |
| Page | a process's logical address space | the same 4 kilobytes |
A page and a frame are the same size, always, by definition. That is not a coincidence of implementation: it is what makes any page fit any frame, and it is the whole mechanism. A question that suggests they could differ has misunderstood the scheme.
Frames are physical and pages are logical, and getting the two words the right way round is worth marks. The sentence to hold: a page goes into a frame.
The page table
One entry per page of the process, and the entry holds the frame number that page is in.
| One table | per process: each process has its own |
| One entry | per page of that process's address space |
| The entry holds | the frame number, and some bits: valid, read only, modified, referenced |
| Where the table lives | in memory, pointed at by a register the kernel loads at a context switch |
A page table entry has no limit field, unlike Chapter seventy three's segment table, and the reason is worth giving: every page is exactly full, so there is nothing to bound. That single difference is the cleanest way to tell the two schemes apart in an answer.
The register that points at the table is the page table base register, and loading it is what makes a context switch expensive: it changes every translation the machine will do next.
The translation
The logical address is split in two, and the split is decided by the page size and nothing else.
| Part | Is | Used to |
|---|---|---|
| page number, p | the high bits | index the page table |
| offset, d | the low bits | say how far into the page, and it is not translated at all |
Paging
The three steps:
- Split the logical address into p and d.
- Look up entry p in the page table to get the frame number f.
- Join f to d: the physical address is f times the page size, plus d.
The offset passes through untouched, and that is the property that makes the whole thing work. The page size is a power of two, so the low bits of a logical address are already the offset within the page, and the low bits of the physical address are the same number. Nothing has to be added or carried. Chapter seventy five works the arithmetic.
The page size is always a power of two, and that is not a convention. It is what makes the split a matter of which bits rather than a division.
What the process knows
Nothing. A process's addresses are 0 upwards, contiguous as far as it can tell, and it has no way of discovering that page 3 is in frame 8 and page 4 in frame 1,207. Chapter sixty seven proved it cannot even read the mapping.
Compare segmentation, where the program supplies the segment number and therefore knows its program is in pieces. Paging is invisible to the program and segmentation is not, and that is the second great difference between them.
What the operating system must keep
Two structures, and a question asks for both.
| Structure | One per | Holds |
|---|---|---|
| Page table | process | which frame each of its pages is in |
| Frame table | the machine | for each frame: whether it is free, and if not, which process and which page is in it |
The frame table is the free list of Chapter seventy, reduced to something trivial: every frame is the same size, so the free list is just a list of numbers, or a bit per frame. There is no "find a hole big enough" step at all, which is the second cost paging removes.
Worked: a tiny machine
The standard small example, which makes the whole scheme visible.
A logical address space of 16 bytes, a page size of 4 bytes, so 4 pages; and a physical memory of 32 bytes, so 8 frames.
Suppose the page table is:
| Page | Frame |
|---|---|
| 0 | 5 |
| 1 | 6 |
| 2 | 1 |
| 3 | 2 |
Now translate. The page size is 4, so the page number is the address divided by 4 and the offset is the remainder.
| Logical | p = address / 4 | d = address mod 4 | frame | physical = frame x 4 + d |
|---|---|---|---|---|
| 0 | 0 | 0 | 5 | 5 × 4 + 0 = 20 |
| 3 | 0 | 3 | 5 | 5 × 4 + 3 = 23 |
| 4 | 1 | 0 | 6 | 6 × 4 + 0 = 24 |
| 9 | 2 | 1 | 1 | 1 × 4 + 1 = 5 |
| 13 | 3 | 1 | 2 | 2 × 4 + 1 = 9 |
Paging
Read logical 3 and logical 4. They are next to each other in the program and land at 23 and 24, which are next to each other by luck. Now read logical 4 and logical 9: adjacent pages, landing at 24 and 5, thousands of bytes apart on a real machine. The process cannot tell, and does not care.
And notice the frame table: frames 5, 6, 1 and 2 are used, and frames 0, 3, 4 and 7 are free. A fifth page would go in any of them, with no search and no fit.
What paging costs
Three costs, and each is a later chapter.
| Cost | Size | Answered by |
|---|---|---|
| Internal fragmentation | half a page per process | accepted, and it is why 4 kilobytes not 4 megabytes |
| A second memory access per access, to read the table | doubles the cost of every access | the translation cache, Chapter seventy six |
| The page table itself takes memory | 4 megabytes per process on a 32 bit machine | hierarchical paging, Chapter seventy eight |
The third is the one that surprises students and it is a standard sum. A 32 bit address space with 4 kilobyte pages has 2 to the power 20 pages, which is 1,048,576 entries; at 4 bytes each that is 4 megabytes of page table, per process. Chapter seventy eight works it out and fixes it.
Distinctions that carry marks
| Page | Frame | |
|---|---|---|
| A piece of | the logical address space | physical memory |
| Belongs to | a process | the machine |
| Same size as | the frame | the page |
| Numbered from | 0, per process | 0, for the whole machine |
| Paging | Segmentation | |
|---|---|---|
| Pieces | fixed size | variable size |
| Address supplied by the program | one number, split by the hardware | two numbers, segment and offset |
| Visible to the program | no | yes |
| Table entry | a frame number, no limit | a base and a limit |
| External fragmentation | none | yes |
| Internal fragmentation | half a page per process | none |
| Page table | Frame table | |
|---|---|---|
| One per | process | machine |
| Entry says | which frame this page is in | whether this frame is free, and whose page is in it |
What it does not mean
A page is not a piece of the program in any meaningful sense. The boundary falls wherever the page size falls, possibly in the middle of a function or an array. That is why the programmer is not told about it.
Paging does not need the process's pages to be in order in memory. They can be in any frames at all, which is the point.
Paging
The offset is not translated. Only the page number is looked up. The offset is copied straight through.
Paging is not virtual memory. Paging is a way of placing a process's pages in frames, and under plain paging every page is in memory. Keeping only some of them in memory is virtual memory, Chapter eighty.
Quick revision
- Paging cuts physical memory into frames and each address space into pages of
exactly the same size. Any page fits any frame, so there is no external fragmentation and no search for a hole.
- A frame is physical, a page is logical, and a page goes into a frame.
- Each process has its own page table, one entry per page, holding the frame number.
There is no limit field, because every page is full.
- The machine has one frame table, saying which frames are free and whose page is in each.
- The logical address splits into a page number and an offset; the page number is looked
up and the offset passes through untouched. The page size is a power of two so the split is a matter of bits.
- Paging is invisible to the program; segmentation is not.
- Three costs: internal fragmentation of half a page per process; a second memory access
per access, fixed by Chapter seventy six; and the page table's own size, 4 megabytes per process on a 32 bit machine, fixed by Chapter seventy eight.
Test yourself
- Define a page and a frame. A frame is a fixed sized piece of physical memory; a page is a
piece of a process's logical address space of exactly the same size. A page is placed into a frame.
- Why does paging have no external fragmentation? Every page is the same size as every
frame, so any free frame satisfies any page: no frame can be the wrong size or in the wrong place.
- What does a page table entry hold, and what does it not hold? The frame number that page
occupies, plus status bits. It holds no limit, because every page is exactly full.
- Give the three translation steps. Split the logical address into a page number and an
offset; look the page number up in the page table to get a frame number; join the frame number to the untranslated offset.
- Why must the page size be a power of two? So that the split into page number and offset is
a matter of which bits an address has, needing no division, and so the offset can be copied straight through. 6. A 16 byte address space, 4 byte pages, and page 2 is in frame 1. Where does logical address 9 land? 9 divided by 4 is page 2 with offset 1; frame 1 times 4 plus 1 gives physical address 5.
Paging
- Name the two tables the operating system keeps and what each is for. A page table per
process, saying which frame each of its pages is in; and one frame table for the machine, saying which frames are free and which page of which process is in each of the rest.
The rest of this subject
These notes are cut from the University's printed syllabus. Open the syllabus itself, or the past papers, for the same subject.