Memory Management: Differences and Connections Between Paging and Segmentation

Problem Description
Memory management is one of the core functions of an operating system. Paging and segmentation are two mainstream non-contiguous memory allocation management techniques. An interviewer may ask you to explain the basic principles of these two mechanisms, compare their differences in detail, and describe how they can be combined (paged segmentation) to leverage their respective strengths and mitigate weaknesses.

Knowledge Explanation

Step 1: Understanding the Basic Goals and Motivation
Early operating systems primarily used contiguous memory allocation (e.g., single contiguous allocation, fixed partition allocation). However, this approach tends to generate a large amount of memory fragmentation, leading to low memory utilization. Non-contiguous memory allocation allows a process's memory space to be scattered across different locations in physical memory, thereby reducing fragmentation and improving memory utilization and system concurrency. Paging and segmentation are two key technologies that implement non-contiguous allocation.

Step 2: In-depth Understanding of Paging Mechanism

1. Core Idea: Divide both the process's logical address space and the system's physical address space into fixed-size, equal-length "pages." A process's pages can be loaded into any available physical "page frame" in memory.
2. Key Components:
   • Page: A fixed-size unit of the process's logical address space.
   • Page Frame: A fixed-size unit of physical memory, exactly the same size as a page.
   • Page Table: Maps logical page numbers to physical page frame numbers. Each process has its own page table. A page table entry typically contains the physical page frame number and some control bits (e.g., present bit, dirty bit).
3. Address Translation Process:
   • The address issued by the CPU is a logical address, consisting of a page number and a page offset.
   • The page table base register in the Memory Management Unit (MMU) points to the current process's page table.
   • Use the page number as an index to look up the page table, obtaining the corresponding physical page frame number.
   • Physical Address = Physical Page Frame Number × Page Size + Page Offset.
   • Note: The page offset is directly copied during translation because page and page frame sizes are equal.
4. Advantages:
   • Efficient memory utilization, reduces external fragmentation (but can cause internal fragmentation).
   • Transparent to programmers and compilers; the operating system handles all management tasks.
5. Disadvantages:
   • Page size is fixed, independent of the program's logical structure, which is not conducive to program modularization management and protection.

Step 3: In-depth Understanding of Segmentation Mechanism

1. Core Idea: Divide the process's address space into several variable-sized "segments" according to the program's own logical relationships. Examples include code segment, data segment, stack segment, etc. Each segment is a complete logical unit.
2. Key Components:
   • Segment: A variable-sized unit of the process's logical address space with logical meaning.
   • Segment Table: Maps logical segment numbers to the starting address (base address) of that segment in physical memory. Each process has a segment table. A segment table entry contains the segment base address, segment length (for bounds checking), and some protection bits.
3. Address Translation Process:
   • The logical address issued by the CPU consists of a segment number and a segment offset.
   • The MMU uses the segment number as an index to look up the segment table, obtaining the segment's base address and length.
   • Critical Security Check: First, check if the segment offset is less than the segment length to prevent access violations.
   • If the check passes, then Physical Address = Segment Base Address + Segment Offset.
4. Advantages:
   • Reflects the program's logical structure, making it easier to implement sharing and protection of code and data (different access permissions can be set for different segments, e.g., read-only, executable).
   • Segments can grow dynamically, facilitating management.
5. Disadvantages:
   • Prone to external fragmentation (due to variable segment lengths). Although compaction can solve this, it is costly.

Step 4: Systematic Comparison of Paging and Segmentation
We can now make a precise comparison across multiple dimensions:

Step 5: Understanding the Combined Scheme – Paged Segmentation Memory Management
To combine the strengths of both (paging's efficiency and segmentation's logical structure), modern operating systems (e.g., Linux) widely use paged segmentation memory management.

1. Core Idea: First, divide the program into several segments according to logical modules (benefit of segmentation). Then, divide each segment into fixed-size pages (benefit of paging).
2. Address Translation Process (Logical Address -> Physical Address):
   • The logical address becomes segment number, page number within segment, and page offset.
   • Use the segment number to look up the segment table, finding the starting address of the page table corresponding to that segment.
   • Use the page number within segment as an index to look up within the found page table, obtaining the physical page frame number.
   • Physical Address = Physical Page Frame Number × Page Size + Page Offset.
3. Advantages:
   • Retains the logical benefits of segmentation, facilitating sharing and protection.
   • Inherits the memory management benefits of paging, avoids external fragmentation, and improves memory utilization.

Through these five steps, we have analyzed, from simple to deep, the two core memory management technologies of paging and segmentation, clarified their differences and connections, and explained how modern operating systems integrate them for application.