Lesson 9.1: Paging — COMP 3150

01 Introduction

Unit 8 ended with segmentation, the scheme that divides a process's address space into logical segments, each with its own base and limit. Segmentation provides a logical view of memory and a fine-grained protection model, but it retains the central weakness of every variable-size allocation scheme: external fragmentation. Because segments are variable-sized, allocating them from physical memory eventually leaves the memory scattered with holes too small for any future segment. Compaction can consolidate the holes, but compaction is expensive, and the fragmentation returns as the system continues to run.

Paging is the alternative, and it is the memory-management scheme that every modern general-purpose operating system uses. The idea is simple but profound: instead of dividing memory into variable-sized regions matched to the objects they hold, divide both the logical address space and the physical memory into fixed-size blocks — pages in the logical address space, frames in physical memory — and allow any page to be placed in any frame. Because all blocks are the same size, there is no requirement that a process's memory be contiguous, and the fragmentation that arises from variable-size allocation cannot occur.

The consequences are dramatic. External fragmentation is eliminated: a free frame can hold any page, so a request for a page can always be satisfied if any frame is available, regardless of where that frame is. The only fragmentation that remains is internal: the last page of a process's address space may not be fully used, so a small amount of memory is wasted at the boundary. This waste is bounded by the page size — typically 4 KB — and is therefore negligible compared to the external fragmentation that a contiguous allocator would suffer.

Paging also provides the infrastructure for virtual memory, the set of techniques that the rest of Unit 9 presents. Because the mapping from pages to frames is expressed in a table that the operating system controls, the operating system can choose to leave some pages unmapped, to map some pages to disk rather than to physical memory, to share pages among processes, and to load pages on demand. Every one of these capabilities depends on the fundamental separation that paging introduces: the process's logical address space and the physical memory are no longer the same thing.

This lesson presents the paging mechanism. It defines pages and frames, describes the page table, and traces paged address translation from logical to physical addresses. It shows how paging eliminates external fragmentation, and it quantifies the small internal fragmentation that remains. It presents the two-memory-access problem — the cost of consulting the page table on every access — and explains how the translation lookaside buffer (TLB), the subject of Lesson 9.3, addresses it. It presents the frame table, the protection bits, and the sharing of pages among processes. It closes with a comparison of paging and segmentation, and a preview of the virtual-memory techniques that the rest of the unit presents.

Prerequisites

This lesson builds on the whole of Unit 8, and in particular on Lessons 8.2 (address binding, logical versus physical addresses, the MMU), 8.4 (contiguous allocation and the placement algorithms), 8.5 (fragmentation, external and internal, and the buddy system), and 8.6 (segmentation). The distinction between logical and physical addresses from Lesson 8.2 is used throughout, and the terminology of fragmentation from Lesson 8.5 is assumed. No prior knowledge of page tables, TLBs, or virtual memory is required; all are introduced here or in the lessons that follow.

02 Learning objectives

By the end of this lesson you will be able to

Define pages and frames and describe the paging model of memory.
Describe the page table and trace a paged address translation from logical to physical address.
Explain how paging eliminates external fragmentation and quantify the internal fragmentation that remains.
Explain the two-memory-access problem and describe the role of the TLB in mitigating it.
Describe the frame table, the valid bit, and the protection bits, and explain how pages are shared among processes.

This lesson contributes to U9.1 and U9.2, and to course learning outcomes CLO1, CLO4, and CLO6.

03 Required reading

Operating System Concepts — Chapter 10, Sections 10.1–10.3, Background, Demand Paging, and Copy-on-Write, and Chapter 9, Section 9.3, Paging. The standard treatment of the paging model, the page table, and paged address translation.
Tanenbaum & Bos — Modern Operating Systems, Chapter 3, Section 3.3, Virtual Memory, through the subsection on paging. A complementary treatment that develops the page-table mechanism from first principles.
OSTEP — Chapter 18, Paging: Introduction. The clearest available treatment of the paging mechanism, its advantages over segmentation, and the two-memory-access problem. OSTEP's worked examples are the basis for the worked example in this lesson.
Silberschatz et al. — Chapter 10, Sections 10.1–10.3, and Chapter 9, Section 9.3. Read the discussion of the two-memory-access problem and the TLB, which is presented briefly here and developed in detail in Lesson 9.3.
Denning, P. J. — Virtual Memory. ACM Computing Surveys, 1970. The paper that framed the paging mechanism for a generation of system designers. Read sections 1 and 2 on the paging model and the working-set concept.
Kilburn, T., Edwards, D. B. G., Lanigan, M. J., & Sumner, F. H. — One-Level Storage System. IRE Transactions on Electronic Computers, 1962. The paper that introduced the paging mechanism, describing the Atlas computer's one-level store.
Linux man pages: man 3 getpagesize, man 2 getpagesize, man 2 mmap, man 5 proc (the /proc/<pid>/maps and /proc/<pid>/pagemap interfaces), man 3 posix_memalign.

Reading strategy

Read the OSTEP chapter first. It develops the paging mechanism in stages, starting with the segmentation scheme of Lesson 8.6, showing what paging changes, and ending with the two-memory-access problem that motivates the TLB. Then read the Silberschatz section for the formal definitions and the worked examples. The chapter covers a great deal of material — the page table, the TLB, protection, shared pages, and the structure of the page table — and the six remaining lessons of Unit 9 will expand on each of these topics in turn. Read the chapter as an overview that establishes the vocabulary, and expect the individual lessons to develop each part in detail.

04 Core content

4.1 The paging model

Paging divides both the logical address space and the physical memory into fixed-size blocks of the same size.

Page: A fixed-size block of the logical address space. A process's address space is divided into pages, numbered from 0. The page size is chosen by the hardware architecture; typical values are 4 KB on x86-64, 4 KB on ARM64 (with 16 KB and 64 KB options), and 8 KB on some RISC architectures. The page size is a power of two, which makes the address split — page number and offset — a matter of bit extraction.
Frame: A fixed-size block of physical memory, the same size as a page. Physical memory is divided into frames, numbered from 0. The frames are the physical resource that the operating system allocates to processes; a process's page is placed in some frame, and the mapping from the page to the frame is what the page table records.

The essential difference from the contiguous allocation schemes of Unit 8 is that the blocks are fixed-size and the pages need not be contiguous. A process's page 0 might be in frame 5, its page 1 in frame 22, its page 2 in frame 3, and so on. The physical memory contains frames allocated to various processes and frames that are free, and the frames can be in any order. What matters is that the operating system maintains the mapping from each process's pages to their frames, and that the MMU uses the mapping on every memory access.

Figure 9.1 — The paging model. The logical address space is divided into pages; physical memory is divided into frames of the same size. The process's page table records the frame for each page, and the pages can be scattered anywhere in physical memory. In this example, page 0 is in frame 5, page 1 in frame 2, page 2 in frame 7, and page 3 in frame 0. Frames 1 and 4 hold pages of other processes; frames 3 and 6 are free.

4.2 The page table

The mapping from a process's pages to their frames is recorded in the process's page table. The page table is an array indexed by page number; each entry — called a page-table entry or PTE — holds at least the frame number for the corresponding page. In a simple scheme, the page table has one entry per page in the process's logical address space, and the entry's content is the frame number.

The page table is per-process. Each process has its own page table, describing the mapping of its own pages. When the scheduler switches from one process to another, it also switches the page table that the MMU uses, so that the incoming process's logical addresses are translated using its own mapping. The page table's location in physical memory is recorded in a page-table base register (PTBR) — called CR3 on x86-64 and TTBR0_EL1 on ARM64 — and the table's size is recorded in a page-table length register (PTLR), used to check the page number against the table's bounds.

In practice, the page table is more complex than a simple array of frame numbers. Modern systems use multi-level page tables (page tables of page tables) to avoid allocating a full table for every process, and the page table entries contain additional fields: a valid bit indicating whether the entry is in use, a dirty bit indicating whether the page has been written, an accessed bit used by replacement algorithms, and the protection bits — read, write, execute — that describe what operations are permitted on the page. The full detail of the page table's structure is the subject of Lesson 9.2; for this lesson, the simple model — one entry per page, holding the frame number — is sufficient.

The page table itself resides in physical memory, and the operating system accesses it as ordinary memory. The MMU does not have a copy of the page table in hardware; it consults the table in memory on every access. This is the source of the two-memory-access problem, which is discussed in section 4.4.

4.3 Paged address translation

The translation of a paged logical address to a physical address is a straightforward process, performed by the MMU on every memory access.

Split the logical address. Because the page size is a power of two, the split is a matter of bit extraction: the low n bits of the address are the page offset (where n is the number of bits required to represent the page size), and the high bits are the page number. For a 4 KB page size (2¹² bytes), the low 12 bits are the offset and the remaining bits are the page number.
Check the page number. The MMU checks the page number against the page-table length register. If the page number is out of range, the access is invalid and a fault is raised.
Look up the page number in the page table. The MMU reads the page-table entry for the page number from the page table in memory, obtaining the frame number.
Check the valid bit and the protection bits. If the valid bit is clear, the page is not currently in memory (a condition that arises in demand paging, Lesson 9.4) and a fault is raised. If the access type is not permitted by the protection bits, a fault is raised.
Replace the page number with the frame number. The physical address is the frame number concatenated with the page offset. The page offset is unchanged, because the page and the frame are the same size.
Access the physical address. The physical address is placed on the memory bus, and the memory system fetches or stores the data.

The key observation is that the page offset is preserved unchanged. Because pages and frames are the same size, the offset within the page is the same as the offset within the frame. Only the page number changes — the page number in the logical address becomes the frame number in the physical address. This is why the translation is so simple, and why the page size being a power of two matters: it makes the split and the concatenation simple bit operations.

Figure 9.1b — Paged address translation. The logical address is split into a page number and a page offset. The page number indexes into the page table, which yields the frame number. The physical address is the frame number concatenated with the page offset, which is unchanged. The example shows the translation of logical address 0x2468 to physical address 0x5468, with page number 2, offset 0x468, and frame 5.

4.4 The two-memory-access problem

The paged address translation described above requires two memory accesses for every logical access:

The page-table access. The MMU must read the page-table entry from the page table, which is stored in physical memory.
The data access. Once the frame number is known, the MMU must perform the actual memory access to the data at the resulting physical address.

This two-memory-access problem doubles the cost of every memory reference. On a processor where a main-memory access takes 200 cycles, every load or store would take 400 cycles — an unacceptable performance penalty. The problem is fundamental to any scheme that stores the translation information in memory rather than in hardware.

The standard solution is the translation lookaside buffer (TLB), a small, fast, hardware-managed cache of recently used page-table entries. The TLB is a key component of every modern processor, and it is the subject of Lesson 9.3. When a logical address is translated, the MMU first checks the TLB; if the page-table entry is present (a TLB hit), the translation is performed directly, with no memory access to the page table. If the entry is not present (a TLB miss), the MMU reads the page table from memory, caches the entry in the TLB, and then performs the data access. In practice, the TLB's hit rate is very high — typically 99 percent or better — because programs have locality, and the effective cost of address translation is much closer to a single memory access than to two.

The two-memory-access problem is the principal cost of paging, and the TLB is the mechanism that mitigates it. Without the TLB, paging would be prohibitively expensive; with it, paging is nearly free in the common case. This is one of the central design trade-offs of memory management: the flexibility of the paging scheme is worth the hardware cost of the TLB, and the TLB's effectiveness depends on the locality of the program's accesses.

4.5 The frame table and memory allocation

Just as the page table describes the mapping from the process's pages to the physical frames, the operating system maintains a frame table that describes the state of each frame in physical memory. The frame table has one entry per frame, and each entry records at least:

Whether the frame is free or allocated.
If allocated, which process owns the frame (and, if the process is running, which page of that process's address space occupies the frame).
Reference information — the time of the last access, the number of accesses, and similar statistics — used by the page-replacement algorithm of Lesson 9.6.

When a page fault occurs — that is, when a process accesses a page that is not currently in memory, a condition that arises in demand paging and is the subject of Lesson 9.4 — the operating system must find a free frame to hold the page. It consults the frame table, selects a free frame, updates the frame table and the process's page table, and loads the page from disk into the frame. If no frame is free, the operating system must choose a frame to evict, using the page-replacement algorithm of Lesson 9.6, and write the evicted page back to disk (or to swap) if the page has been modified.

The frame table is the operating system's view of physical memory, in the same way that the page table is the MMU's view of the process's address space. The two tables must be kept consistent: when the operating system assigns a frame to a page, it updates both. If the two are inconsistent — if the page table says a page is in one frame and the frame table says the frame holds a different page — the memory system will read or write the wrong data, and the result is a corruption bug that can be very hard to diagnose.

In practice, most operating systems do not maintain the page table and the frame table as separate, independent structures. Instead, they use a unified representation in which each page's metadata contains the frame number, and the frame's metadata contains a pointer to the page. The two are two views of the same information, kept in sync by the kernel's memory-management code.

4.6 Protection and sharing

Paging provides protection at the granularity of a page, through the protection bits in each page-table entry. Just as segmentation's per-segment protection allowed the code segment to be read-execute and the data segment read-write, paging's per-page protection allows the same distinctions at page granularity. The pages that hold the program's code can be marked read-execute; the pages that hold the data can be marked read-write; the pages that hold constant data can be marked read-only.

The protection bits are enforced by the MMU, in hardware, on every access. An attempt to write to a read-only page raises a fault, which the operating system handles by terminating the process (typically with the SIGSEGV signal on Unix). This is the same protection model as segmentation's, but at page granularity instead of segment granularity. Because pages are smaller than segments — 4 KB versus whatever size a segment happens to be — the protection is finer-grained, and the operating system can enforce the distinctions at a finer level of detail.

Paging also supports sharing. Because the page table maps a page number to a frame number, two processes' page tables can map different page numbers to the same frame. When a shared library is used by two processes, its code pages are mapped into both processes' address spaces, and both processes read the same physical memory. The shared pages must have compatible protection bits: they must be read-execute for both processes, so that neither can modify the code that the other is executing.

Sharing is the mechanism by which libraries, memory-mapped files, and interprocess communication through shared memory are implemented. The classic example is the C library: when a program uses printf, the code for printf is in a page that is shared by every process on the system that uses the library. The physical memory holds one copy of the page, and dozens or hundreds of processes map it into their address spaces. This is a significant memory saving, and it is one of the principal advantages of paging.

Sharing requires care with respect to writes. If a shared page is read-only — as the code pages are — the sharing is straightforward, because no process can modify the page that another process is reading. If a shared page is writable, the sharing must be handled more carefully: if two processes both write to the same page, they will interfere with each other, and the result is likely to be incorrect. The operating system can handle this in two ways. It can mark the page read-only for both processes and raise a fault when either tries to write, at which point it can make a private copy of the page for the writer (this is copy-on-write, the subject of section 4.7). Or it can leave the page writable and rely on the processes to coordinate their access through some synchronization mechanism (a lock or a semaphore), which is the mechanism used for shared memory in interprocess communication.

4.7 Copy-on-write

Copy-on-write (COW) is a technique that exploits paging to make sharing efficient when the shared data may be modified. The idea is to map the same frame into multiple processes' address spaces, but to mark the pages read-only. When a process tries to write to the page, the MMU raises a protection fault, and the operating system's fault handler makes a private copy of the page for the writer, updates the writer's page table to point to the new frame, and then restarts the write. The result is that the two processes share the page as long as neither writes to it, and each process has its own private copy as soon as it writes.

Copy-on-write is used extensively in modern operating systems. The most important example is the fork() system call: when a process forks, the child is a copy of the parent, and the traditional implementation copies the parent's entire address space into the child. With copy-on-write, the child's page table is a copy of the parent's, mapping the same frames, and both page tables are marked read-only. The two processes share all pages until one writes, at which point only the written page is copied. For a process that forks and then immediately calls execve — the common case for launching a new program — no page is ever copied, and the fork is nearly free.

Other uses of copy-on-write include: shared libraries' data pages, which are shared initially and copied when a process writes; memory-mapped files, which are mapped read-only and copied on write; and virtual machine snapshots, where the snapshot shares the running VM's pages until the running VM writes to them. In each case, the mechanism is the same: share the page, mark it read-only, and let the fault handler make a private copy when it is written.

Copy-on-write is an elegant application of paging's flexibility. It converts a seemingly expensive operation — copying memory — into a cheap one, by exploiting the fact that the copy is not actually needed until the pages diverge. The mechanism demonstrates one of paging's central properties: because the mapping from pages to frames is controlled by the operating system, the operating system can implement policies — sharing, laziness, demand loading — that would be impossible in a scheme where the mapping was fixed in hardware.

4.8 Paging versus segmentation

Paging and segmentation differ in their unit of allocation and in how they treat the address space.

Paging versus segmentation
Aspect	Paging	Segmentation
Unit of allocation	Fixed-size pages (e.g., 4 KB)	Variable-size segments
Logical structure	The address space is a single flat sequence of pages	The address space is a numbered collection of segments
Address form	(page number, page offset)	(segment number, offset)
External fragmentation	Eliminated — any free frame can hold any page	Present — variable-size segments leave holes
Internal fragmentation	Present, bounded by the page size	Absent — segments are sized to the logical parts
Protection granularity	Per page	Per segment — matches the program's logical structure
Sharing granularity	Per page	Per segment
Two-memory-access cost	Yes — the page table is in memory; mitigated by the TLB	No — the segment table is small and can be partly cached
Where used today	Universally in every modern system	Historically; now used only for specific purposes (thread-local storage)

The comparison shows why paging won. Segmentation's unique contribution is the logical structure — the segment number makes the program's structure visible to the hardware — but that structure can be provided by the software without hardware support. Paging's unique contribution is the elimination of external fragmentation, and that requires the hardware's cooperation because only the hardware can translate an address. The two schemes are not mutually exclusive — the 32-bit x86 architecture combined them, as we saw in Lesson 8.6 — but modern architectures have settled on paging alone, because paging provides the essential benefit and the logical structure is easy to provide in software.

4.9 Common misconceptions

"A page and a frame are the same thing."

A page is a block of the logical address space; a frame is a block of physical memory. They are the same size, and the mapping between them is what the page table records.

"Paging means the address space is on disk."

Paging is the mechanism that makes it possible to place some of the address space on disk, but paging itself is just the mapping from pages to frames. Demand paging, the subject of Lesson 9.4, is the technique that brings pages from disk on demand.

"The page size can be anything."

The page size must be a power of two, because the translation relies on splitting the address into a page number and an offset, and on concatenating the frame number with the offset. Powers of two make this a matter of bit manipulation.

"A larger page size is always better."

Larger pages reduce the size of the page table and increase the TLB's reach, but they increase the internal fragmentation and the cost of transferring a page between memory and disk. The optimal page size is a trade-off.

"The page table is in the MMU."

The page table is in physical memory, and the MMU consults it on every access. Only the page-table base register and the TLB are in the MMU's hardware.

"Paging eliminates all fragmentation."

Paging eliminates external fragmentation but retains internal fragmentation. The last page of a process's address space may not be fully used, wasting up to page_size − 1 bytes.

"Page tables are always one level deep."

Modern page tables are multi-level — for example, four levels on x86-64. The multi-level structure avoids allocating a full table for every process and is the subject of Lesson 9.2.

"The page offset can change during translation."

The page offset is unchanged. Because pages and frames are the same size, the offset within the page is the same as the offset within the frame. Only the page number is replaced by the frame number.

05 Worked example

The following example traces paged address translation for several logical addresses, computes the resulting physical addresses, and quantifies the internal fragmentation of a process whose address space does not fill its last page.

Paged address translation with a small page table

A process has a 4 KB page size (so the page offset is 12 bits) and a small address space of 8 pages (32 KB). Its page table is:

Page	Frame	Valid	Protection
0	5	1	read, execute
1	2	1	read, write
2	7	1	read, write
3	0	1	read, write
4	9	1	read, write
5	3	1	read, write
6	—	0	—
7	—	0	—

Pages 6 and 7 are marked invalid: the process's address space is only 6 pages, so pages 6 and 7 are not part of the address space. Any access to them will raise a fault.

We translate six logical addresses.

Logical address	Page	Offset	Frame	Physical address	Result
`0x0000`	0	0x000	5	`0x5000`	valid — code at start of the address space
`0x0ABC`	0	0xABC	5	`0x5ABC`	valid — code at offset 0xABC in page 0
`0x1234`	1	0x234	2	`0x2234`	valid — data at offset 0x234 in page 1
`0x2468`	2	0x468	7	`0x7468`	valid — data at offset 0x468 in page 2
`0x5432`	5	0x432	3	`0x3432`	valid — data at offset 0x432 in page 5
`0x6000`	6	0x000	—	—	fault — page 6 is not valid

The pattern is straightforward. The logical address is split into a page number (the high bits) and a page offset (the low 12 bits). The page number is looked up in the page table; the frame number it gives is concatenated with the offset to produce the physical address. The offset is unchanged: a logical address at offset 0xABC in page 0 becomes a physical address at offset 0xABC in frame 5.

The fault case at the end is instructive. A logical address of 0x6000 has page number 6 — which is a valid page number (the address space is 8 pages, so page numbers 0 through 7 are in range) — but the page-table entry for page 6 has the valid bit clear. This means that page 6 is not part of the process's address space. The process has tried to access memory outside its own address space, and the MMU raises a fault. The operating system's handler would then terminate the process with a SIGSEGV signal.

Internal fragmentation

The process's address space is 6 pages. If the process's actual memory usage is, say, 20 KB, then the address space must be at least ⌈20 KB / 4 KB⌉ = 5 pages (20 KB). But if the process's actual usage is 20.5 KB, then ⌈20.5 / 4⌉ = 6 pages (24 KB), and the last page contains 24 − 20.5 = 3.5 KB that the process does not use.

Requested	Pages allocated	Memory allocated	Internal fragmentation	Fraction wasted
16 KB	4	16 KB	0 KB	0%
17 KB	5	20 KB	3 KB	15%
20 KB	5	20 KB	0 KB	0%
20.5 KB	6	24 KB	3.5 KB	14.6%
32 KB	8	32 KB	0 KB	0%

The internal fragmentation is at most page_size − 1 bytes, which for 4 KB pages is 4 KB − 1 byte ≈ 4 KB. On average, for a request whose size is uniformly distributed, the waste is half a page — about 2 KB. Compared to the external fragmentation of contiguous allocation (which, per the 50-percent rule of Lesson 8.5, loses about half the memory), this is a dramatic improvement.

The internal fragmentation is the only form of fragmentation that paging incurs. There is no external fragmentation: any free frame can hold any page, so a request for a page always succeeds if a frame is available, regardless of where that frame is. This is the essential advantage of paging over the contiguous allocation schemes of Unit 8.

Effect of page size

The choice of page size affects both the internal fragmentation and the size of the page table. The table below compares three page sizes for a process whose actual memory usage is 100 KB, plus a workload with a small average allocation size.

Page size	Pages for 100 KB	Memory allocated	Internal frag.	Page-table size (8 MB address space)
4 KB	25	100 KB	0 KB	2048 entries × 8 bytes = 16 KB
4 KB (100.5 KB usage)	26	104 KB	3.5 KB	2048 entries × 8 bytes = 16 KB
64 KB (2 MB address space)	2	128 KB	27.5 KB	32 entries × 8 bytes = 256 bytes
2 MB (huge page)	1	2 MB	1.9 MB	4 entries × 8 bytes = 32 bytes

The trade-off is clear. Larger pages reduce the size of the page table — fewer entries, less memory, better TLB coverage — but they increase the internal fragmentation — a process that uses a fraction of a large page wastes the rest. Modern systems therefore use a mix of page sizes: 4 KB for general-purpose memory, 2 MB or 1 GB "huge pages" for memory-intensive applications (large databases, virtual machines, scientific computing) where the page-table savings and TLB coverage outweigh the internal fragmentation.

Sharing in the worked example

Suppose a second process P₂ shares P₁'s page 0 (a shared library's code). P₂'s page table maps page 0 to frame 5, the same frame that P₁'s page table maps page 0 to. The two processes' page tables are separate, but they point to the same physical frame, and the two processes share the code in that frame.

The code page must be marked read-execute in both page tables, so that neither process can modify the code the other is executing. If P₁ were to write to page 0, the MMU would raise a fault, the operating system's handler would terminate P₁ with SIGSEGV, and P₂'s code would remain intact. This is the protection mechanism that makes sharing safe: the hardware enforces the protection bits on every access, so a process cannot corrupt another process's memory even when the two share a physical page.

The sharing saves memory. If P₁ and P₂ each had their own copy of the code, the physical memory would hold two copies. With sharing, the physical memory holds one copy, and both page tables point to it. On a system with many processes using the same library, the savings are substantial: a 2 MB library used by 100 processes saves nearly 200 MB of physical memory.

06 Interactive activity

Activity · implement and explore paged address translation

The goal of this activity is to implement paged address translation, test it with the worked example, and observe paging in a live system. Work through the steps in your course VM.

Implement paged address translation. Write a program that defines a page table (as in the worked example) and translates logical addresses to physical addresses. The translation should:

Extract the page number and offset from the logical address.
Check the page number against the page table's bounds.
Look up the frame number in the page table.
Check the valid bit and raise a fault if it is clear.
Compute the physical address as frame × page_size + offset.

#include <stdio.h>
#include <stdint.h>

#define PAGE_SIZE  4096
#define PAGE_SHIFT 12
#define PAGE_COUNT 8

struct pte {
    int frame;      /* valid only if valid == 1 */
    int valid;
    int prot;       /* bitmask */
};

struct pte page_table[PAGE_COUNT] = {
    { .frame = 5, .valid = 1, .prot = 0x5 },  /* read + execute */
    { .frame = 2, .valid = 1, .prot = 0x3 },  /* read + write */
    { .frame = 7, .valid = 1, .prot = 0x3 },
    { .frame = 0, .valid = 1, .prot = 0x3 },
    { .frame = 9, .valid = 1, .prot = 0x3 },
    { .frame = 3, .valid = 1, .prot = 0x3 },
    { .frame = 0, .valid = 0, .prot = 0x0 },
    { .frame = 0, .valid = 0, .prot = 0x0 },
};

uint64_t translate(uint32_t logical, int access) {
    uint32_t page   = logical >> PAGE_SHIFT;
    uint32_t offset = logical & (PAGE_SIZE - 1);

    if (page >= PAGE_COUNT) {
        printf("fault: page number out of range\n");
        return 0;
    }

    struct pte *entry = &page_table[page];

    if (!entry->valid) {
        printf("fault: page %u not valid\n", page);
        return 0;
    }

    if ((access & entry->prot) != access) {
        printf("fault: protection violation\n");
        return 0;
    }

    return (uint64_t)entry->frame * PAGE_SIZE + offset;
}

Test with the worked example. Test the translate function with the six addresses from the worked example. Verify that the first five succeed and the sixth faults. Print the physical address for each successful translation.

struct test {
    uint32_t logical;
    int access;
    const char *desc;
} tests[] = {
    { 0x0000, 0x4, "code at 0x0000" },
    { 0x0ABC, 0x4, "code at 0x0ABC" },
    { 0x1234, 0x2, "data write at 0x1234" },
    { 0x2468, 0x1, "data read at 0x2468" },
    { 0x5432, 0x1, "data read at 0x5432" },
    { 0x6000, 0x1, "read at 0x6000 (page 6)" },
};

Try protection faults. Add test cases that violate the protection bits:
- Write to page 0 (the code page), which is read-execute only.
- Execute page 1 (the data page), which is read-write only.
Verify that the translate function raises a fault for both.
```
{ 0x0000, 0x2, "write to code page (should fault)" },
{ 0x1234, 0x4, "execute data page (should fault)" },
```
Add a second process sharing a page. Write a second page table for a process P₂ whose page 0 maps to the same frame 5 as P₁'s page 0, but whose other pages map to different frames. Translate the same logical addresses under both page tables and confirm that:
- An access to page 0 in either process produces the same physical address.
- An access to page 1 in the two processes produces different physical addresses.
```
struct pte page_table2[PAGE_COUNT] = {
    { .frame = 5, .valid = 1, .prot = 0x5 },  /* same code page */
    { .frame = 12, .valid = 1, .prot = 0x3 }, /* different data page */
    /* ... */
};
```
Examine a real process's page table. On a Linux system, the /proc/<pid>/maps file shows the process's virtual memory regions — the segments of the address space with their permissions. Read it for a running process.
```
cat /proc/self/maps | head -20
```
Each line shows a virtual address range, the permissions (read, write, execute), the offset, the device, the inode, and the file (if the region is file-backed). Notice that the permissions vary: the code regions are r-x, the data regions are rw-, and the read-only data regions are r--. This is the page-level protection of paging in action.

Observe the page size. Write a small program that reports the system's page size and uses mmap to allocate a page-aligned region.

#include <stdio.h>
#include <unistd.h>
#include <sys/mman.h>

int main(void) {
    long page_size = sysconf(_SC_PAGESIZE);
    printf("page size: %ld bytes\n", page_size);

    void *p = mmap(NULL, page_size, PROT_READ | PROT_WRITE,
                   MAP_PRIVATE | MAP_ANONYMOUS, -1, 0);
    if (p == MAP_FAILED) { perror("mmap"); return 1; }

    printf("mmap returned address: %p\n", p);
    printf("is it page-aligned? %s\n",
           ((unsigned long)p % page_size == 0) ? "yes" : "no");

    munmap(p, page_size);
    return 0;
}

Compile and run. The page size should be 4096 bytes on a typical x86-64 system, and the mmap address should be a multiple of the page size.

Inspect huge pages. On a system that supports huge pages, examine the /proc/meminfo file for the huge-page statistics.
```
grep -i huge /proc/meminfo
```
The output shows the size of the huge pages (typically 2 MB on x86-64), the total number, the free number, and the reserved number. This illustrates the trade-off between page size and page-table size: huge pages are larger, so the page table is smaller and the TLB covers more memory, but the internal fragmentation is higher.
Read man 5 proc for the pagemap interface. The /proc/<pid>/pagemap file gives per-page information about a process's address space. Reading it requires root privileges, but the man page describes the format.
```
man 5 proc | grep -A 20 pagemap
```
What information does each pagemap entry contain? How could this be used to observe the paging behaviour of a running process? (Hint: the present bit and the swapped bit indicate whether a page is resident in memory or on disk.)

Reflect: paging is the fundamental mechanism that underlies every modern memory-management scheme. Its central idea — separate the logical address space from the physical memory, and allow the operating system to control the mapping — is what makes demand paging, copy-on-write, shared libraries, and virtual memory possible. What would a system look like without paging? What would it gain in simplicity, and what would it lose in flexibility? How would a system that used segmentation alone compare to a paging-based system?

07 Knowledge check

Check your understanding

Question 1

Define a page and a frame. How does the paging model differ from the contiguous allocation models of Unit 8? What is the page table, and what does each entry contain?

Show answer

A page is a fixed-size block of the logical address space. A frame is a fixed-size block of physical memory, the same size as a page. The page size is chosen by the hardware; typical values are 4 KB (x86-64, ARM64) and 8 KB (some RISC architectures). Both the logical address space and physical memory are divided into blocks of this size, and the blocks are numbered from 0. The paging model differs from the contiguous allocation models of Unit 8 in the fundamental requirement that the process's memory be contiguous. In a contiguous allocation scheme, the process's entire address space must be a single contiguous region of physical memory. In a paged scheme, the process's pages can be placed anywhere in physical memory: page 0 might be in frame 5, page 1 in frame 22, page 2 in frame 3, and so on. The mapping from pages to frames is recorded in the page table, and the MMU uses this mapping to translate logical addresses to physical addresses on every access. The page table is a per-process array indexed by page number. Each entry — a page-table entry or PTE — contains at least the frame number for the corresponding page. In practice, page-table entries also contain a valid bit (indicating whether the page is in memory), a dirty bit (indicating whether the page has been written), protection bits (read, write, execute), and other fields used by the operating system's memory-management policies. The page table is stored in physical memory, and its base address is held in the page-table base register (PTBR), which is set by the operating system on each context switch.

Question 2

Describe the process of translating a paged logical address to a physical address. Why must the page size be a power of two, and why is the page offset unchanged during the translation?

Show answer

The translation proceeds as follows. First, the logical address is split into a page number (the high bits) and a page offset (the low bits). Second, the page number is checked against the page-table length register; if it is out of range, a fault is raised. Third, the page number is used to index into the page table, and the corresponding page-table entry is read from physical memory. Fourth, the valid bit and the protection bits are checked; if the page is not valid or the access is not permitted, a fault is raised. Fifth, the frame number from the page-table entry is concatenated with the page offset to produce the physical address. Sixth, the physical address is placed on the memory bus. The page size must be a power of two because the split and the concatenation are bit operations. Splitting the address into a page number and an offset requires shifting the address right by the number of bits needed to represent the offset; concatenating the frame number with the offset requires shifting the frame number left by the same number of bits. Both operations are simple when the page size is a power of two, because the number of bits is an integer and the operations are straightforward bit manipulations. For non-power-of-two page sizes, the split would require a division, which is much slower. The page offset is unchanged during the translation because pages and frames are the same size. A byte at offset d within a logical page is at the same offset d within the frame that holds that page. The translation therefore changes only the page number — it is replaced by the frame number — and the offset is preserved. This is the essential property that makes the translation simple, and it is why the page size must be the same in the logical and physical address spaces.

Question 3

What is the two-memory-access problem? Why is it a problem, and how does the translation lookaside buffer (TLB) address it?

Show answer

The two-memory-access problem is the fact that paged address translation requires two memory accesses for every logical access. The first access reads the page-table entry from the page table, which is stored in physical memory. The second access reads or writes the data at the physical address that the translation produces. In a system without any special hardware support, a single load or store instruction would therefore take twice as long as it would on a system without paging. On a processor where main memory takes 200 cycles to access, every logical access would take 400 cycles, which is an unacceptable performance penalty. The translation lookaside buffer (TLB) is a small, fast, hardware-managed cache of recently used page-table entries, and it is the standard solution to this problem. The TLB is a content-addressable memory that holds a small number of page-table entries — typically 32 to 1024 entries on modern processors. When a logical address is translated, the MMU first checks whether the page-table entry for the page number is present in the TLB. If it is — a TLB hit — the translation is performed using the cached entry, with no memory access to the page table, and only the data access is required. If the entry is not in the TLB — a TLB miss — the MMU reads the page table from memory, caches the entry in the TLB, and then performs the data access. Because of the locality of reference (Lesson 8.1), the TLB's hit rate is very high — typically 99 percent or better on real workloads — and the effective cost of address translation is much closer to a single memory access than to two. The TLB is the subject of Lesson 9.3, which presents its structure, its replacement policies, and the details of its interaction with the rest of the memory system.

Question 4

How does paging eliminate external fragmentation? Does it eliminate internal fragmentation? Give a concrete example of each, and explain the trade-off in choosing a page size.

Show answer

Paging eliminates external fragmentation by removing the requirement that a process's memory be contiguous. In a contiguous allocation scheme, a request can only be satisfied if a single contiguous region of the required size is available. In a paged scheme, the process's address space is divided into pages, and any free frame can hold any page, regardless of where in physical memory it is. A request for a page always succeeds if any frame is free, and a process's pages are placed in whatever frames are available. The external fragmentation that arises from variable-size allocation — the accumulation of holes too small for any future request — cannot occur in a paged scheme, because all blocks are the same size and any block can substitute for any other. Paging does not eliminate internal fragmentation. The last page of a process's address space may not be fully used, and the unused portion is wasted. For example, a process with 20.5 KB of code and data, with a 4 KB page size, occupies six pages (24 KB), of which the last page contains 3.5 KB of unused space. The internal fragmentation is at most page_size − 1 bytes, which is 4095 bytes for 4 KB pages; on average, for a uniformly distributed request size, the waste is about half a page — about 2 KB. Compared to the external fragmentation of contiguous allocation, which per the 50-percent rule of Lesson 8.5 loses about half the memory, the internal fragmentation of paging is negligible. The choice of page size is a trade-off between the two forms. Larger pages reduce the size of the page table (fewer entries, less memory, better TLB coverage) but increase the internal fragmentation (the last page wastes more). Smaller pages do the opposite. Modern systems use a mix: 4 KB for general-purpose memory, and 2 MB or 1 GB huge pages for memory-intensive applications where the page-table savings and TLB coverage outweigh the internal fragmentation. The 4 KB default is a compromise that balances the two.

Question 5

How does paging support protection and sharing? Explain the role of the protection bits in each page-table entry, and describe how two processes can share a page. What is copy-on-write, and how does it exploit paging?

Show answer

Paging supports protection through the protection bits in each page-table entry. Each page can be marked with the operations permitted on it: read, write, execute. The MMU checks the access type against the page's bits on every access, and raises a fault if the access is not permitted. The pages that hold code can be marked read-execute; the pages that hold data can be marked read-write; the pages that hold constant data can be marked read-only. This is the hardware foundation of the W^X policy (write-xor-execute), and it enforces the distinctions between code, data, and constants at page granularity. Paging supports sharing because two processes' page tables can map different page numbers to the same frame. When a shared library is used by two processes, its code pages are mapped into both processes' address spaces, and both processes read the same physical memory. The shared pages must have compatible protection bits: they must be read-execute for both processes, so that neither can modify the code the other is executing. The sharing saves memory: the physical memory holds one copy of the shared page, and both processes' page tables point to it. Copy-on-write (COW) is a technique that exploits paging to make sharing efficient when the shared data may be modified. The idea is to map the same frame into multiple processes' address spaces, but to mark the pages read-only. When a process tries to write to the page, the MMU raises a protection fault, and the operating system's fault handler makes a private copy of the page for the writer, updates the writer's page table to point to the new frame, and restarts the write. The result is that the two processes share the page as long as neither writes to it, and each process has its own private copy as soon as it writes. Copy-on-write is used extensively in modern operating systems; the classic example is fork(), where the child shares the parent's pages until one of them writes, at which point only the written page is copied. For a process that forks and immediately calls execve, no page is ever copied, and the fork is nearly free.

08 Unit discussion

Discussion prompt

Paging is arguably the single most important idea in modern memory management. Its central insight is that the mapping from a process's logical addresses to the physical memory can be expressed in a data structure that the operating system controls, and that the MMU can consult on every access. This separation of logical from physical addresses, introduced in Lesson 8.2 as execution-time binding, becomes in paging a programmable interface between the software and the hardware.

The flexibility this provides is enormous. Because the mapping is in software, the operating system can: leave pages unmapped (so a null-pointer dereference faults instead of silently corrupting memory); share pages among processes (so libraries and memory-mapped files consume one copy instead of many); mark pages read-only (so a program cannot modify its own code); map the same file into multiple processes' address spaces; keep some pages on disk and bring them in on demand (demand paging, Lesson 9.4); and make a private copy of a page only when it is written (copy-on-write). Each of these capabilities is a policy decision that the operating system makes, and each depends on the fact that the hardware consults the page table rather than treating the logical address as the physical address.

The cost is the two-memory-access problem, mitigated by the TLB, and the memory required for the page tables themselves, mitigated by multi-level page tables. The hardware and the operating system cooperate to make the cost small enough to be acceptable, and the result is a system where the flexibility of full virtual memory is available at nearly the cost of raw physical memory access.

Consider a system that did not use paging — a system that used only the base-and-limit scheme of Lesson 8.2, or the segmentation scheme of Lesson 8.6. What would such a system lose? Which of the modern capabilities that we take for granted — shared libraries, memory-mapped files, copy-on-write fork, on-demand paging, virtual machines — would be impossible or much more expensive? What would the system gain, and would the gain be worth the loss? Post your response to the Unit 9 discussion forum and reply to at least two classmates. Supports CLO1, CLO4, and CLO6.

09 Practice exercise

This ungraded exercise consolidates the lesson and prepares you for Lesson 9.2. Aim to spend 60–90 minutes on it.

Define the terms. Write concise definitions of the following terms in your own words: page, frame, page table, page-table entry, page-table base register, page-table length register, page offset, page number, frame number, valid bit, dirty bit, protection bits, frame table. For each, state whether it is part of the hardware's view, the operating system's view, or both.
Translate addresses by hand. A process has a 4 KB page size and a page table with the following entries: page 0 → frame 3, page 1 → frame 7, page 2 → frame 1, page 3 → frame 11, page 4 → frame 0 (invalid), page 5 → frame 8, page 6 → frame 4, page 7 → frame 6 (invalid). Translate the following logical addresses, stating the page number, offset, frame number, physical address, and whether the access succeeds or faults:
- 0x0000
- 0x0FFF
- 0x1000
- 0x2FFF
- 0x4A00
- 0x5010
- 0x6000
- 0x7123
Compute internal fragmentation. For a 4 KB page size, compute the internal fragmentation for the following process sizes:
- 1024 bytes
- 4096 bytes
- 4097 bytes
- 8000 bytes
- 16384 bytes
- 16385 bytes
Present the results in a table with columns for the process size, the number of pages, the memory allocated, the internal fragmentation, and the fraction wasted. Then compute the average internal fragmentation for these six sizes.
Design a page table for a small process. A process has 16 KB of code, 8 KB of read-only data, 12 KB of read-write data, a 16 KB heap, and an 8 KB stack. It also uses a shared library whose code occupies 64 KB. Design a page table for this process with a 4 KB page size. Specify the number of pages, the frame numbers (you may choose them from the frames 0 through 63), and the protection bits for each page. Then compute the total physical memory the process requires and the total memory that is shared with other processes.
Explain the two-memory-access problem. Write a short paragraph (150–200 words) explaining the two-memory-access problem to a programmer who has never heard of paging. Your explanation should include: what the problem is, why it arises, what the cost would be without any special hardware, and how the TLB mitigates it. Do not use the phrase "page table" more than three times.
Design an experiment for copy-on-write. Write a small program that uses fork() to create a child process. Before forking, allocate a large array (say, 100 MB) and fill it with data. In the child, write to a single element of the array, and then exit. Use /proc/<pid>/maps or top to observe the memory usage of the parent and child before and after the child's write. How much memory does the child consume before the write? How much after? Explain what you observe in terms of copy-on-write.
```
#include <stdio.h>
#include <stdlib.h>
#include <unistd.h>
#include <sys/wait.h>

int main(void) {
    size_t n = 100 * 1024 * 1024;
    char *buf = malloc(n);
    for (size_t i = 0; i < n; i++) buf[i] = 1;

    pid_t pid = fork();
    if (pid == 0) {
        /* child */
        buf[0] = 2;
        printf("child: wrote one byte\n");
        sleep(3);       /* give the parent a chance to observe */
        _exit(0);
    } else {
        /* parent */
        wait(NULL);
    }
    free(buf);
    return 0;
}
```
Read the OSTEP chapter. Read OSTEP Chapter 18, Paging: Introduction. Compare its presentation of the paging mechanism to this lesson. What additional considerations does OSTEP raise — for example, the issue of page-table size, the multi-level page table, and the translation procedure? Write a short paragraph summarising the differences.
Reflect. In your own words, explain why paging eliminates external fragmentation but not internal fragmentation. Then describe one situation in your own experience — a program you have written or a system you have used — where the page size or the paging mechanism affected the behaviour of the system. What was the effect, and what would have changed if the page size had been different?

10 Summary

Paging divides the logical address space into fixed-size pages and physical memory into fixed-size frames of the same size. A process's pages can be placed anywhere in physical memory, so the process's memory need not be contiguous.
The page table is a per-process array indexed by page number. Each entry (a page-table entry, or PTE) contains the frame number for the corresponding page, along with a valid bit, protection bits, and other fields.
Paged address translation splits the logical address into a page number and a page offset, uses the page number to index the page table, and concatenates the resulting frame number with the page offset. The page offset is unchanged because pages and frames are the same size.
The page size must be a power of two, because the translation relies on bit extraction and concatenation. The page-table base register (PTBR) holds the page table's address, and the page-table length register (PTLR) holds its size.
Paging eliminates external fragmentation entirely: any free frame can hold any page, so a request for a page always succeeds if a frame is free. Paging retains internal fragmentation, because the last page of a process's address space may not be fully used; this waste is bounded by page_size − 1 bytes.
The two-memory-access problem is that paged address translation requires two memory accesses for every logical access: one to read the page-table entry, and one to access the data. The translation lookaside buffer (TLB) is a small hardware cache of recently used page-table entries, and it mitigates the problem by providing the translation on a TLB hit without any memory access to the page table.
The frame table is the operating system's record of the state of each frame: whether it is free or allocated, which process owns it, and the statistics used by the page-replacement algorithm. It must be kept consistent with the per-process page tables.
Paging provides protection at page granularity through the protection bits in each page-table entry, and sharing by allowing multiple page tables to map different page numbers to the same frame. Shared pages must have compatible protection bits.
Copy-on-write exploits paging to make sharing efficient: shared pages are marked read-only, and a private copy is made for a writer on its first write. The classic example is fork(), where the child shares the parent's pages until one of them writes.
Paging differs from segmentation in its unit of allocation (fixed-size pages versus variable-size segments), its treatment of fragmentation (external eliminated versus internal absent), and its protection granularity (per page versus per segment). Every modern general-purpose system uses paging; segmentation survives only for specific purposes such as thread-local storage on x86-64.

Looking ahead

This lesson presented the paging mechanism: pages and frames, the page table, paged address translation, the two-memory-access problem, and the frame table. The treatment has assumed the simplest possible page table — a single-level array with one entry per page of the address space. In practice, this simple structure is too large: on a 64-bit system with 4 KB pages, a flat page table would have 2⁵² entries, which is far too much memory to allocate for each process. Lesson 9.2 presents the multi-level page table, the structure that modern systems use to keep the page table small while still supporting a large address space. The lesson covers the two-level, three-level, and four-level structures, the inverted page table, the hashed page table, and the practical considerations that shape the page table's design.

11 References

Silberschatz, A., Galvin, P. B., & Gagne, G. Operating System Concepts, 10th ed., Chapter 9, Section 9.3, and Chapter 10, Sections 10.1–10.3.
Arpaci-Dusseau, R. H., & Arpaci-Dusseau, A. C. Operating Systems: Three Easy Pieces, Chapter 18, Paging: Introduction. Available online at ostep.org.
Tanenbaum, A. S., & Bos, H. Modern Operating Systems, 4th ed., Chapter 3, Section 3.3.
Denning, P. J. Virtual Memory. ACM Computing Surveys, 1970. The paper that framed the paging mechanism for a generation of system designers.
Kilburn, T., Edwards, D. B. G., Lanigan, M. J., & Sumner, F. H. One-Level Storage System. IRE Transactions on Electronic Computers, 1962. The paper that introduced the paging mechanism, describing the Atlas computer's one-level store.
Bryant, R. E., & O'Hallaron, D. R. Computer Systems: A Programmer's Perspective, 3rd ed., Chapter 9, Virtual Memory. The programmer's view of paging, including the page table, the TLB, and the practical considerations of writing paging-aware code.
Love, R. Linux Kernel Development, 3rd ed., Chapter 12, Memory Management. The Linux kernel's implementation of paging, including its page-table structure, the reverse mapping, and the page-replacement algorithm.
Linux man-pages: man 3 getpagesize, man 2 mmap, man 2 mprotect, man 2 madvise, man 5 proc.