Paging in operating systems (CMP)
Paging is a memory management scheme that eliminates the need for contiguous allocation of physical memory, thereby addressing issues like external fragmentation. It allows the operating system to retrieve data from secondary storage in blocks, known as pages.
Key Concepts of Paging
1. **Pages and Frames**:
**Page**: A fixed-size block of virtual memory.
**Frame**: A fixed-size block of physical memory (RAM). The size of a page and a frame is usually the same.
2. **Virtual Memory**:
Paging enables a process to use more memory than is physically available by using disk space as an extension of RAM. The operating system keeps track of all pages and their corresponding frames.
3. **Page Table**:
Each process has a page table that maps virtual pages to physical frames. The page table contains:
**Frame number**: The corresponding physical frame for each virtual page.
**Status bits**: Information like whether the page is in memory, modified, or referenced.
4. **Page Replacement**:
When a page not currently in memory is accessed (a page fault), the OS must decide which page to replace if memory is full. Common algorithms include:
**Least Recently Used (LRU)**: Replaces the page that has not been used for the longest time.
**First-In-First-Out (FIFO)**: Replaces the oldest page in memory.
**Optimal**: Replaces the page that will not be used for the longest period in the future (theoretical and not implementable in practice).
Advantages of Paging
**Eliminates External Fragmentation**: Since pages can be loaded into any available frame, fragmentation is minimized.
**Efficient Memory Utilization**: Processes can use non-contiguous physical memory.
**Simplified Memory Management**: Easier for the OS to manage memory allocation and protection.
Disadvantages of Paging
**Internal Fragmentation**: If a process does not fully utilize the last page, the remaining space is wasted.
**Overhead**: Maintaining page tables can add overhead, particularly for processes with a large number of pages.
**Page Fault Overhead**: Frequent page faults can lead to significant performance degradation, especially if the system relies heavily on swapping pages in and out of memory.
Summary
Paging is a foundational technique in modern operating systems that facilitates efficient memory management and virtual memory implementation. By allowing non-contiguous memory allocation, it enhances both the utilization of memory and the flexibility of process management.
