Questions: Memory Management: Paging and Segmentation

Question 1

A system uses segmentation for memory management. After many processes have run, allocated memory, and terminated, the system begins to struggle to find contiguous space for new segments even though total free memory appears sufficient. What problem is occurring?

• A. Internal fragmentation — segments are leaving unused space at their ends
• B. External fragmentation — free memory is scattered in small non-contiguous gaps between segments
• C. Page table overflow — the segment table has run out of entries
• D. Cache thrashing — segments are evicting each other from the CPU cache

Answer: (B)

External fragmentation is the characteristic failure mode of segmentation: because segments are variable in size, allocating and freeing them over time leaves scattered 'holes' of free memory. Even if total free space is larger than the requested segment, no single contiguous block is large enough. This is the fundamental problem that fixed-size paging solves — because any page can go into any frame, there is no external fragmentation.

Question 2

What is internal fragmentation in a paging system?

• A. Fragmentation caused by page table entries pointing to the wrong physical frames
• B. Wasted space when the last page of a process is not fully utilized
• C. The overhead cost of maintaining multilevel page tables
• D. Fragmentation caused when two processes share the same physical frame

Answer: (B)

Internal fragmentation occurs because pages have a fixed size (e.g., 4 KB) and a process's last page is rarely exactly full. If a process needs 5 KB of memory, it gets two 4 KB pages (8 KB total), wasting up to 3 KB in the second page. This is the tradeoff paging accepts: no external fragmentation (any page fits any frame), but up to page-size-minus-one bytes wasted per process. This differs from external fragmentation, which is wasted space between allocations.

Question 3

In a paging system, any virtual page can be placed into any available physical frame, regardless of its position in memory.

• T. True
• F. False

Answer: True

This is the key advantage of fixed-size paging: because all pages and frames are the same size, there is no requirement that a process's pages occupy contiguous physical memory. The page table simply records which physical frame holds each virtual page. This eliminates external fragmentation entirely — the OS never has to search for a contiguous block large enough for a variable-size allocation. Pages can be scattered throughout physical RAM without any effect on the process's view of a contiguous virtual address space.

Question 4

Segmentation eliminates fragmentation problems because each segment is sized exactly to fit the logical program unit it represents.

• T. True
• F. False

Answer: False

Segmentation eliminates internal fragmentation (segments are exactly sized to their contents) but creates external fragmentation. The problem is not whether individual segments fit their contents — they do — but what happens over time as segments of different sizes are allocated and freed. The gaps left by freed segments are rarely exactly the right size for new allocations, so free memory gradually becomes scattered into unusable fragments. This external fragmentation is the primary reason paging, not segmentation, won as the dominant memory management scheme.

Question 5

Why do modern operating systems primarily use paging rather than segmentation, even though segmentation more naturally reflects how programs are logically organized?

Model answer: Paging uses fixed-size pages and frames, which eliminates external fragmentation — any page can go into any frame, so allocation is simple and predictable. Segmentation uses variable-size segments, which causes external fragmentation over time as differently-sized holes accumulate in memory. Managing variable-size allocations at hardware speed, maintaining compaction, and avoiding fragmentation are engineering problems that grow severe at scale. The logical elegance of segmentation (code, stack, heap as distinct segments) doesn't outweigh the practical cost of external fragmentation.

Modern x86-64 architectures support segmentation for backward compatibility but flatten it — all segments share the same base address and have the same limit, effectively disabling segmentation as a real memory division mechanism. The OS relies entirely on paging with multilevel page tables and TLB caching for performance. The lesson: the scheme with the simpler allocation model won, even at the cost of internal fragmentation.