Part 2 of 7 · 2 min read
The idea
Think of it this way. A library book is made of chapters, and a copy of a very long book can be stored on many different shelves. Each chapter fits on any shelf slot of the right size, and an index card says which shelf holds which chapter. The reader asks for "chapter 7" and the librarian looks at the card. The analogy stops in one place: the reader of a book gets chapters from a shelf, while a processor does the lookup in hardware, on every memory access.
In plain words: Paging works the same way. The virtual address space of a process is cut into equal pieces called pages. The physical memory is cut into pieces of the same size called frames. Any page can be put into any frame, and a table says which. The pages of a process need not be next to each other in the physical memory, nor in any order.
The size is a power of two, usually 4,096 bytes (4 KiB). The power of two matters: it lets the hardware split an address by cutting its bits, with no division.
Compare with page 2. External fragmentation is gone, because any free frame fits any page: a free frame is never too small. Internal fragmentation remains, but it is less than one page per region of the process, and only the last page of each region is partly empty.
Page and frame
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.
Example: with 4 KiB pages, virtual addresses 0 to 4,095 form page 0, and the kernel can keep page 0 in any free frame of the physical memory.
Check yourself: 1. Why does paging remove external fragmentation? 2. What is the relation between the size of a page and the size of a frame? 3. In the library analogy, what plays the part of the index card?