Paging
Understand how operating systems divide memory into fixed-size pages for efficient memory management.
Introduction
Paging is a memory management scheme that eliminates the need for contiguous allocation of physical memory. It divides physical memory into fixed-size blocks called frames and logical memory into blocks of the same size called pages. When a process is to be executed, its pages are loaded into any available memory frames from their source (a file system or backing store). Paging allows the physical address space of a process to be non-contiguous. This technique was developed to solve the problems of external fragmentation and the need to fit varying size chunks into the backing store. Paging is one of the most important concepts in modern operating systems.
Why Paging Is Needed
- •Contiguous memory allocation leads to external fragmentation
- •Memory holes form when processes of different sizes are loaded and unloaded
- •Compaction is expensive and time-consuming
- •Variable-size partitions are hard to manage efficiently
- •Physical memory addresses are exposed to programs
- •Fixed-size pages eliminate external fragmentation
- •Any free frame can hold any page
- •Simple allocation: just find any free frame
- •Logical addresses become independent of physical locations
- •Memory protection is easier to implement
Core Concept Explanation
In paging, the logical address space is divided into pages and the physical address space is divided into frames of the same size. When a process needs memory, its pages can be placed in any available frames.
Key Terms
How It Works (Step by Step)
- 1The CPU generates a logical address
- 2The logical address is divided into page number (p) and offset (d)
- 3The page number is used as an index into the page table
- 4The page table entry gives the frame number
- 5The physical address is formed by combining frame number and offset
- 6Memory is accessed at the physical address
Step-by-Step Worked Example
Consider a system with page size of 4 bytes, physical memory of 32 bytes (8 frames), and logical address space of 16 bytes (4 pages). We want to translate logical address 5.
| Step | Page | RAM State | Action | Result |
|---|---|---|---|---|
| 1 | 5 | Logical Address = 5 | Divide logical address into page number and offset. Page size = 4, so we need 2 bits for offset. | 5 in binary = 0101. Page Number = 01 (1), Offset = 01 (1) |
| 2 | 1 | Page Table: [Page 0→Frame 5, Page 1→Frame 6, Page 2→Frame 1, Page 3→Frame 2] | Look up Page 1 in page table. | Page 1 maps to Frame 6 |
| 3 | 6 | Frame Number = 6 | Combine frame number with offset. Frame 6 in binary = 110. | Physical Address = 110 (frame) + 01 (offset) = 11001 = 25 |
Logical address 5 translates to physical address 25. The page table enabled this translation without requiring contiguous memory allocation.
Real-Life Analogy
The Book and Page Numbers
Think of a book with chapters that can be printed on any available sheets of paper. Imagine you're printing a book, but instead of printing pages in order on consecutive sheets, you can print any page on any available sheet. Each sheet (frame) can hold exactly one page of content. When you need to find Chapter 3, Page 2: 1. You look up in your index (page table) where that page was printed 2. The index tells you it's on Sheet #15 3. You go to Sheet 15 to find the content This is exactly how paging works: - The book content is divided into fixed-size pages - Physical paper sheets are the frames - The index is the page table - Finding content = address translation
Mapping to Technical Concepts
No External Fragmentation
Since all frames are the same size, any frame can hold any page.
Efficient Memory Use
Memory can be allocated in any order, maximizing utilization.
Easy to Implement Swapping
Pages can be easily moved between RAM and disk.
Memory Protection
Each page can have protection bits (read, write, execute).
Shared Pages
Multiple processes can share the same physical frame (e.g., shared libraries).
Internal Fragmentation
The last page may not be completely filled, wasting space within the page.
Page Table Overhead
Page tables consume memory, especially for large address spaces.
Memory Access Time
Each memory access requires a page table lookup, doubling access time without TLB.
Fixed Page Size
The page size may not be optimal for all types of programs.
💡 Common Student Confusions
Page and Frame are the Same Thing
Pages are in logical memory, frames are in physical memory. They are of the same size but represent different concepts.
Paging Eliminates All Fragmentation
Paging eliminates external fragmentation but introduces internal fragmentation.
Page Table is Stored in the CPU
Page tables are stored in main memory. Only a pointer (PTBR) and TLB cache are in hardware.
📝 Exam-Oriented Answer
Definition
Paging is a memory management scheme that permits the physical address space of a process to be non-contiguous by dividing logical memory into pages and physical memory into frames of equal size.
Key Points
- • Logical memory divided into pages, physical memory into frames
- • Page table maps page numbers to frame numbers
- • Logical address = Page Number + Offset
- • Physical address = Frame Number + Offset
- • TLB caches recent translations for performance
- • Eliminates external fragmentation
- • May cause internal fragmentation
Advantages
- • No external fragmentation
- • Simple memory allocation
- • Supports virtual memory implementation
Disadvantages
- • Internal fragmentation in last page
- • Page table overhead
- • Double memory access without TLB
Conclusion
Paging is essential for modern memory management, enabling virtual memory and efficient multi-programming.
📌 Final Summary
- 1Paging divides logical memory into pages and physical memory into frames
- 2Page table maintains mapping between page numbers and frame numbers
- 3Logical address consists of page number and offset
- 4TLB caches translations for faster memory access
- 5Eliminates external fragmentation but may cause internal fragmentation
- 6Enables implementation of virtual memory and memory protection