Definition
Paging
Paging is a memory management technique that eliminates the need for contiguous allocation of physical memory. It divides the logical address space into fixed-size blocks called pages and the physical memory into blocks of the same size called frames.
Address Translation
A logical address is divided into a page number and a page offset. The OS uses a page table to translate the page number into a physical frame number.
- Page size: Typically a power of two (e.g., 4KB) to simplify bit-wise address translation.
- Physical Address Calculation:
- Mathematical: (Frame Number Page Size) Offset.
- Implementation: Binary concatenation of the frame number and the offset. Unlike segmentation, no addition is required because the page size is a power of two.
Analogies
The Carpet Tiles
Paging is analogous to covering a floor with small, fixed-size carpet tiles.
- Efficiency: Like tiling, most units fit perfectly into the room. Only the very last tile (the last page of a process) may need to be cut, resulting in minimal wastage (internal fragmentation).
- Contrast: This is more efficient than the “large carpet” (segmentation) approach, which requires extensive custom cutting and creates many unusable scraps (external fragmentation).
Characteristics
- External Fragmentation: Eliminated, as any free frame can be assigned to any page.
- Internal Fragmentation: Limited to the very last page of a process (if its size is not a multiple of the page size).
- Simplification: Simplifies loading and swapping, as the OS only needs to manage fixed-size blocks.