Memory Management: Segmentation and Paging

Efficient memory management is the bedrock of any modern operating system, allowing multiple processes to run concurrently while protecting them from each other and maximizing the use of physical hardware. Two fundamental techniques—segmentation and paging—provide different models for organizing a process's logical view of memory and mapping it onto physical RAM. Understanding their mechanisms, trade-offs, and how they are combined is essential for grasping how software efficiently utilizes finite physical resources.

Logical versus Physical Address Spaces

At the core of memory management is the distinction between logical and physical addresses. A logical address (or virtual address) is generated by the CPU during program execution; it is the address the process thinks it is using. The set of all such addresses is the process's logical address space. A physical address is the actual location in the computer's main memory (RAM). The memory management unit (MMU) is the hardware component responsible for translating every logical address issued by the CPU into a corresponding physical address before the memory access is performed. This translation is what enables the powerful abstractions of segmentation and paging, providing isolation, relocation, and more efficient use of memory.

Segmentation: Variable-Size Logical Units

Segmentation is a memory management scheme that supports the user's view of memory. A program is logically divided into segments: a code segment, a data segment, a stack segment, and potentially others like a heap segment. Each segment is a variable-sized, logically distinct unit. From the process's perspective, an address is specified as a two-part quantity: a segment number and an offset within that segment.

The operating system maintains a segment table for each process. Each entry in this table contains a base address, which is the starting physical address of that segment in memory, and a limit, which is the length of the segment. When the CPU generates a logical address <segment, offset>, the MMU uses the segment number as an index into the segment table. It checks that the offset is less than the segment limit (providing protection) and then adds the offset to the segment's base address to produce the physical address.

The primary advantage of segmentation is that it mirrors the program's logical structure, making it intuitive and simplifying sharing and protection (e.g., code segments can be marked read-only). However, its use of variable-sized blocks leads directly to the problem of external fragmentation. As segments of different sizes are allocated and freed, free memory becomes broken into many small, non-contiguous holes. Although the total free memory may be sufficient for a new segment, no single hole may be large enough to satisfy the request. Compacting memory to consolidate free space is possible but is often prohibitively expensive.

Paging: Fixed-Size Physical Frames

Paging is a memory management scheme that eliminates the problem of external fragmentation by dividing physical memory into fixed-sized 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 physical frames; these frames need not be contiguous. This completely divorces the user's view of memory (a contiguous logical space) from the physical reality of where pages are stored.

The operating system maintains a page table for each process to track the mapping of logical pages to physical frames. Every logical address is divided into two parts: a page number (p) and a page offset (d). If a logical address space is $2^m$ bytes and the page size is $2^n$ bytes, then the higher-order m-n bits specify the page number, and the lower-order n bits specify the offset. The page number is used as an index into the page table, which yields the base address of the corresponding physical frame. The physical address is constructed by concatenating this frame number with the unchanged page offset.

Paging solves external fragmentation because any free frame can hold any page. However, it introduces internal fragmentation. Since memory is allocated in fixed-size chunks, the last page of a process is likely to be only partially filled. On average, half a page is wasted per process. The choice of page size is a critical trade-off: larger pages increase internal fragmentation but decrease the size of the page table and the frequency of costly page faults.

Implementing Page Tables and Handling Page Faults

Managing the page table efficiently is a major design concern. Simple page tables store one entry per logical page, which can become enormous for modern 64-bit address spaces. Techniques like multi-level paging (e.g., a page directory pointing to page tables) are used to keep the structures manageable, though they add an extra memory access for translation. This overhead is mitigated by a hardware cache called the Translation Lookaside Buffer (TLB), which stores recent page-to-frame mappings.

A page fault occurs when a process attempts to access a page that is not currently resident in physical memory. The page table entry will have a valid-invalid bit marked "invalid." This trap triggers the operating system's page fault handler. The handler:

1. Checks an internal table to see if the reference was valid or invalid (e.g., a programming error).
2. If valid, it finds a free frame. If none are free, it invokes a page replacement algorithm (like LRU) to select a victim frame to evict.
3. It schedules a disk operation to read the required page into the newly allocated frame.
4. It updates the page table (and TLB) to reflect the new mapping.
5. Finally, it restarts the instruction that caused the trap.

The process is unaware that this happened; it experiences only a slight delay. Effective page fault handling and replacement algorithms are crucial for the performance of virtual memory systems.

Combined Systems: Segmentation with Paging

Pure segmentation suffers from external fragmentation, and while pure paging is efficient, it loses the logical, protection-oriented benefits of segmentation. Most modern architectures (like x86-64) use a combined system that employs segmentation and paging together. In this scheme, segmentation is still used at the logical level to define segments for code, data, and stack. However, instead of each segment being a single contiguous block in physical memory, each segment is itself divided into pages.

The logical address is now a triple: <segment, page, offset>. The segment selector is used to find a segment descriptor, which contains the base linear address of that segment's page table. The page number portion of the address is then used to index into that segment's page table to find the physical frame. This approach provides the logical organization and fine-grained protection of segmentation while gaining the non-contiguous allocation and efficiency benefits of paging. The operating system manages the physical memory entirely in terms of pages and frames, with segmentation acting as a higher-level organizational layer.

Common Pitfalls

1. Confusing Internal and External Fragmentation: A common mistake is to attribute the wrong type of fragmentation to each scheme. Remember: Segmentation causes external fragmentation (free memory is scattered into small holes between allocated segments). Paging causes internal fragmentation (unused space within the last allocated fixed-size block).

1. Misunderstanding Address Translation in Paging: When calculating a physical address from a logical address [p|d], students often mistakenly add the offset d to the frame number. The correct operation is to replace the logical page number p with the physical frame number from the page table, keeping the offset d the same. The physical address is [frame number | d].

1. Overlooking the TLB's Role: It's easy to think of page table lookup as a single memory access. In reality, without a TLB, each logical memory reference would require two physical memory accesses: one to read the page table entry and one to perform the actual data access. The TLB, as a cache for page table entries, is what makes paging practical for performance-critical systems.

1. Assuming Page Faults are Errors: A page fault is not a program crash or error (like a segmentation fault). It is a normal, handled event in a virtual memory system that allows the OS to dynamically load pages on demand. Confusing a "page fault" with a "segmentation fault" (an invalid memory access) indicates a misunderstanding of the mechanism.

Summary

• Segmentation divides memory into variable-sized logical units, aligning with the program's structure but leading to external fragmentation.
• Paging divides memory into fixed-sized pages/frames, eliminating external fragmentation at the cost of internal fragmentation and requiring complex page table management.
• Critical operations include page table lookup (often accelerated by a TLB) and handling page faults, which allow the OS to load pages dynamically from disk.
• Modern systems typically combine segmentation with paging, using segmentation for logical organization and protection, and paging for physical memory management, getting the best of both worlds.
• Implementing these systems requires careful consideration of trade-offs: page size, table structure, and replacement algorithms all dramatically impact system performance and efficiency.