Paging

Paging

Paging permits a process's physical address space to be noncontiguous. It divides the program into equal-sized pages and memory into equally sized frames, so each page can occupy one frame.

Because a process is spread among frames, its page table identifies the frame holding each page, mapping logical addresses to physical addresses.

Each address is split into a page number and an offset. The CPU looks up the page number in the page table and replaces it with the mapped frame number, retaining the offset to form a physical address.

Paging eliminates external fragmentation for ordinary single-page allocation: any free frame can hold a requested page. It still has internal fragmentation when a process's requirement is not a page-size multiple and its final frame is partially unused.

An important feature is the separation of the user's view of memory from physical memory. The OS controls address mappings; ordinary user programs use logical addresses rather than directly choosing physical locations.

Predivided memory avoids segmentation's small-gap problem for ordinary single-page allocation. Releasing memory in whole pages does not leave unusable free pieces smaller than a page.

If memory is insufficient, the OS can swap eligible, recently unused pages out to disk and swap them in when needed. Transfers can involve one or a few pages rather than a whole process, although disk I/O can still cause substantial delay.

With demand paging, loading a program need not load all pages at once. Pages are loaded when execution needs their instructions or data.

Translation Lookaside Buffer

Program locality means that instruction and data accesses tend to concentrate in a small area. For a period, execution usually stays within part of the program and accesses a limited set of memory regions.

This allows frequently used page mappings to be cached in faster hardware. The CPU's translation lookaside buffer, TLB, is such a cache. Address lookup checks the TLB first and consults the regular page table on a miss.