Paging and address translation

Why it exists

With contiguous allocation a process needs one big hole, holes fragment, and compaction is expensive. Paging removes the requirement of contiguity. Physical memory is cut into equal fixed-size frames, the logical address space into pages of the same size, and any page can go into any free frame. A page table records where each page is. The programmer still sees one contiguous address space; the hardware translates every address. Paging is the basis of virtual memory and is the most examined topic of operating systems in GATE, almost always as a calculation: how many bits is the page number, how big is the page table, what physical address does this logical address map to.

Prerequisites

You need the aim of memory management, fragmentation and the idea of logical and physical addresses from memory management basics and process address space.

Precise definitions

Pages and frames. Physical memory is divided into frames of size $2^n$ bytes. The logical address space of a process is divided into pages of the same size. A page is loaded into any free frame; the frames of one process need not be adjacent.

Logical address. For $m$-bit logical addresses and a page size of $2^n$ bytes:

$\underbrace{p}_{m - n \text{ bits: page number}} \quad \underbrace{d}_{n \text{ bits: offset}}$

The page number $p$ is the high-order $m - n$ bits; the offset $d$ is the low-order $n$ bits. Equivalently $p = \lfloor L / 2^n \rfloor$ and $d = L \bmod 2^n$.

Page table. An array, one entry per page, indexed by the page number. Entry $p$ holds the frame number $f$ in which page $p$ is stored, plus control bits (valid/invalid, read/write/execute protection, and for virtual memory referenced and modified (dirty)).

Translation. For a logical address with page number $p$ and offset $d$: look up $f = \text{page table}[p]$ (if the valid bit is 0, a page fault), and form the physical address

$P = f \cdot 2^n + d,$

which in bits is simply the frame number followed by the unchanged offset. The offset is not changed, and neither is its size.

Sizes (all from the number of bits).

Where the page table is. For speed the page table of the running process is conceptually in registers, but a large one lives in main memory, and a page-table base register (PTBR) (and a length register) points to it. Every memory reference then needs two memory accesses (one for the page-table entry, one for the data) unless a translation cache, the TLB, holds the entry (TLB). A context switch loads the PTBR of the new process.

Fragmentation. Paging has no external fragmentation (any free frame will do), but it has internal fragmentation: the last page of a process is usually only partly used. If a process needs $S$ bytes with pages of $P$ bytes, it takes $\lceil S/P \rceil$ pages and wastes $(-S) \bmod P$ bytes. Averaged over random sizes the waste is about $P/2$ per process (exactly $(P - 1)/2$ over all residues).

Choice of page size. Smaller pages waste less in the last page but need larger page tables (and more disk transfers per byte); larger pages shrink the table but waste more. For an average process size $s$ and page-table entry size $e$, the overhead per process is $\dfrac{s\,e}{p} + \dfrac{p}{2}$, minimized at

$p = \sqrt{2\,s\,e}.$

For $s = 1$ MB and $e = 8$ bytes that is 4096 bytes: this is why 4 KB is a common page size.

Protection and sharing. The valid bit marks which pages belong to the process; protection bits allow read-only or execute-only pages. Pages can be shared between processes by putting the same frame number in several page tables (for example the code of a program or a library, which must be reentrant, not modified while running).

Frame table. The operating system keeps a table with one entry per frame: whether it is free, and if allocated, to which process.

How it works

The animation uses a 14-bit logical address space with 1 KB pages: the 4 high bits are the page number (16 pages) and the 10 low bits the offset. The physical memory has 32 KB (32 frames, 5-bit frame numbers). Five addresses are translated; two of them hit invalid pages. Watch the frame number replace the page number while the offset is copied unchanged.

Worked examples

#include <stdio.h>
 
#define OFFSET_BITS 10
#define PAGES 16
 
int main(void) {
    /* page table of a process: frame number of each page, -1 = not in memory */
    int frame[PAGES] = {5, 9, 2, -1, 17, 3, -1, 20, 1, 30, -1, 12, -1, -1, -1, -1};
    unsigned logical[5] = {2565, 5123, 3082, 10216, 15360};
    for (int i = 0; i < 5; i++) {
        unsigned p = logical[i] >> OFFSET_BITS, d = logical[i] & ((1u << OFFSET_BITS) - 1);
        if (frame[p] < 0) { printf("logical %5u: page %2u offset %4u -> page fault\n", logical[i], p, d); continue; }
        unsigned physical = ((unsigned)frame[p] << OFFSET_BITS) | d;
        printf("logical %5u: page %2u offset %4u -> frame %2d -> physical %5u\n", logical[i], p, d, frame[p], physical);
    }
    /* the same arithmetic with division and remainder */
    printf("5123 = %u * 1024 + %u\n", 5123u / 1024u, 5123u % 1024u);
    /* sizes: 32-bit logical addresses, 4 KB pages, 4-byte page table entries */
    unsigned long long pages = 1ull << (32 - 12);
    printf("pages in the address space: %llu, page table size: %llu KB\n", pages, pages * 4 / 1024);
    /* a process of 100000 bytes needs how many 4096-byte pages, and how much is wasted in the last? */
    unsigned size = 100000, page = 4096;
    unsigned need = (size + page - 1) / page, last = size - (need - 1) * page;
    printf("process of %u bytes: %u pages, last page uses %u bytes, internal fragmentation %u bytes\n", size, need, last, page - last);
    /* the page size minimising (page table entries per process + wasted half page): s = 1 MB process, e = 8-byte entries */
    double s = 1 << 20, e = 8, best = 0, best_cost = 1e30;
    for (double pz = 256; pz <= 65536; pz *= 2) {
        double cost = s * e / pz + pz / 2;
        if (cost < best_cost) { best_cost = cost; best = pz; }
    }
    printf("best page size among powers of two: %.0f bytes (overhead %.0f bytes per process)\n", best, best_cost);
    return 0;
}

logical  2565: page  2 offset  517 -> frame  2 -> physical  2565
logical  5123: page  5 offset    3 -> frame  3 -> physical  3075
logical  3082: page  3 offset   10 -> page fault
logical 10216: page  9 offset 1000 -> frame 30 -> physical 31720
logical 15360: page 15 offset    0 -> page fault
5123 = 5 * 1024 + 3
pages in the address space: 1048576, page table size: 4096 KB
process of 100000 bytes: 25 pages, last page uses 1696 bytes, internal fragmentation 2400 bytes
best page size among powers of two: 4096 bytes (overhead 4096 bytes per process)

Cheat box

Traps and GATE patterns

Connections

Paging replaces the single base register of process address space by a table, and fixes the external fragmentation of contiguous allocation. A page table of $2^{20}$ entries is too large to store flat, which leads to multilevel, hashed and inverted tables; the cost of two accesses per reference is attacked by the TLB. Allowing the valid bit to mean "on disk" gives virtual memory and demand paging.

PYQs

A system has a Translation Lookaside Buffer
(TLB) that has a reach of 1 MB. TLB reach is
defined as the total amount of physical memory that
can be accessed through the TLB entries.

The paging system uses pages of size 4 KB. The
virtual address space is 64 GB and physical address
space is 1 GB.

If each TLB entry stores:
●
a 4-bit process id
●
page number
●
frame number
●
a 2-bit control field

then the size of the TLB (in bytes) is ______.

Note:
1K = 210, 1M = 220, 1G = 230.

A computer system supports a logical address space
of 232bytes. It uses two-level hierarchical paging
with a page size of 4096 bytes. A logical address is
divided into a b-bit index to the outer page table, an
offset within the page of the inner page table, and an
offset within the desired page. Each entry of the inner
page table uses eight bytes. All the pages in the
system have the same size.The value of b is ______.

Consider a demand paging memory management
system with 32-bit logical address, 20-bit physical
address, and page size of 2048 bytes. Assuming that
the memory is byte addressable, what is the
maximum number of entries in the page table?

A disk of size 512M bytes is divided into blocks of
64K bytes. A file is stored in the disk using linked
allocation. In linked allocation, each data block
reserves 4 bytes to store the pointer to the next data
block. The link part of the last data block contains
a NULL pointer (also of 4 bytes). Suppose a file of
1M bytes needs to be stored in the disk. Assume,
1K = 210 and 1M = 220. The amount of space in
bytes that will be wasted due to internal
fragmentation is ______. (Answer in integer)

Which
of
the
following
tasks
is/are
the
responsibility/responsibilities
of
the
memory
management unit (MMU) in a system with paging-
based memory management?

Consider a memory management system that uses a
page size of 2 KB. Assume that both the physical and
virtual addresses start from 0. Assume that the pages
0, 1, 2, and 3 are stored in the page frames 1, 3, 2, and
0, respectively. The physical address (in decimal
format) corresponding to the virtual address 2500 (in
decimal format) is _________

OPERATING SYSTEMS

In the context of the operating system, which of the
following statements is/are correct with respect to
paging?

Consider a system with byte-addressable memory, 32
bit logical addresses, 4 kilobyte page size and page
table entries of 4 bytes each. The size of the page table
in the system in megabytes is ___________

A computer system implements 8 kilobyte pages and
a 32-bit physical address space. Each page table entry
contains a valid bit, a dirty bit, three permission bits,
and the translation. If the maximum size of the page
table of a process is 24 megabytes, the length of the
virtual address supported by the system is ________
bits.

The essential content(s) in each entry of a page
table is/are

Self-check

Revision card

References