Segmentation Vs Paging - Learning Module

Loading content...

0/240

Fragmentation Differences: Internal vs External

The Hidden Cost of Memory Management

Fragmentation is the silent enemy of efficient memory utilization. It represents memory that exists but cannot be used productively—a form of invisible waste that accumulates over time as processes allocate and deallocate memory.

Understanding fragmentation is critical because it directly impacts:

Memory utilization: How much of your physical RAM actually holds useful data
Allocation failures: When allocation requests fail despite "free" memory existing
System performance: When fragmentation forces expensive compaction or swapping
Scalability limits: Maximum number of concurrent processes a system can support

Segmentation and paging exhibit fundamentally different fragmentation characteristics. This difference is one of the primary factors driving the industry's shift toward paging as the dominant memory management scheme.

What You Will Master

By the end of this page, you will deeply understand internal and external fragmentation, why segmentation suffers from external fragmentation while paging suffers from internal fragmentation, the quantitative 50% rule for segmentation, and the practical implications of each fragmentation type for system design and performance.

Fragmentation Taxonomy

Before comparing how segmentation and paging handle fragmentation, we must precisely define the two fundamental types of memory fragmentation.

External Fragmentation: The Allocation Problem

External fragmentation occurs when free memory exists but is scattered in non-contiguous chunks, none large enough to satisfy an allocation request. The memory is "free" from the system's perspective but unusable for the requesting process.

Total free memory: 100KB
Largest contiguous block: 25KB
Allocation request: 50KB
Result: ALLOCATION FAILURE (despite 100KB free)

External fragmentation is caused by the accumulation of variably-sized holes as processes with different memory requirements allocate and deallocate memory over time.

Internal Fragmentation: The Allocation Waste

Internal fragmentation occurs when allocated memory exceeds the amount actually needed. The extra memory is assigned to a process but lies unused—wasted inside the allocation.

Allocation unit: 4KB pages
Process needs: 9KB
Allocated: 12KB (3 pages)
Wasted: 3KB (internal fragmentation)

Internal fragmentation is caused by allocation schemes that round up requests to fixed-size units.

Fragmentation Types Comparison
Characteristic	External Fragmentation	Internal Fragmentation
Location of waste	Outside allocated regions (between them)	Inside allocated regions
Memory status	Marked as free but unusable	Marked as allocated but unused
Caused by	Variable-size allocations	Fixed-size allocation units
Detection	Compare total free vs largest hole	Audit allocated vs used per allocation
Grows over time?	Yes (accumulates with churn)	No (fixed overhead per allocation)
Can cause failure?	Yes (allocation denied)	No (just waste)
Solution approaches	Compaction, paging	Smaller allocation units, exact-fit

Segmentation and External Fragmentation

Segmentation suffers from external fragmentation because segments have variable sizes. This is an inherent consequence of the design—the very feature that makes segmentation semantically meaningful (variable-sized logical units) is also its greatest weakness.

How External Fragmentation Develops in Segmented Systems:

Consider a system with 1MB of physical memory starting empty:

external_fragmentation_example.txt
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
Initial State: 1MB contiguous free memory
├──────────────────────────────────────────────────────────────┤
│                       FREE (1024KB)                           │
└──────────────────────────────────────────────────────────────┘
 
After Process A allocates code (100KB), data (50KB), stack (25KB):
├──────────┬─────────┬───────┬─────────────────────────────────┤
│ A:Code   │ A:Data  │A:Stack│           FREE (849KB)          │
│  100KB   │  50KB   │ 25KB  │                                 │
└──────────┴─────────┴───────┴─────────────────────────────────┘
 
After Process B allocates code (200KB), data (100KB):
├──────────┬─────────┬───────┬─────────┬─────────┬────────────┤
│ A:Code   │ A:Data  │A:Stack│ B:Code  │ B:Data  │ FREE(549KB)│
│  100KB   │  50KB   │ 25KB  │  200KB  │  100KB  │            │
└──────────┴─────────┴───────┴─────────┴─────────┴────────────┘
 
After Process A terminates (frees 175KB):
├──────────────────────────────┬─────────┬─────────┬──────────┤
│         FREE (175KB)         │ B:Code  │ B:Data  │ FREE     │
│  (3 non-contiguous holes)    │  200KB  │  100KB  │ (549KB)  │
└──────────────────────────────┴─────────┴─────────┴──────────┘
 
After Process C allocates 150KB segment:
├─────────────┬───────┬────────┬─────────┬─────────┬──────────┤
│ C:Segment   │ FREE  │        │ B:Code  │ B:Data  │ FREE     │
│   150KB     │ 25KB  │        │  200KB  │  100KB  │ (549KB)  │
└─────────────┴───────┴────────┴─────────┴─────────┴──────────┘
 
After more allocations/deallocations...
├───┬───┬──────┬────┬─────┬───────┬────┬──────────┬───┬───────┤
│ D │ F │ FREE │ B  │ FREE│   E   │FREE│    G     │ F │ FREE  │
│ 30│ 45│  12  │200 │  8  │  150  │ 20 │   250    │ 80│  129  │
└───┴───┴──────┴────┴─────┴───────┴────┴──────────┴───┴───────┘
 
Current state analysis:
  Total free: 12 + 8 + 20 + 129 = 169KB
  Largest hole: 129KB
  Request for 160KB segment: DENIED (external fragmentation!)

The Fragmentation Cascade

External fragmentation worsens over time. As processes come and go, memory becomes increasingly checkered with small holes. Eventually, the system appears to have plenty of free memory but cannot satisfy reasonable allocation requests. This is sometimes called 'memory swiss cheese.'

The 50% Rule (Fifty Percent Rule)

Knuth's 50% rule provides a theoretical framework for understanding external fragmentation in systems using first-fit or best-fit allocation:

After a system reaches steady state, approximately N/2 holes exist for N allocated segments.

This means:

If you have 100 segments allocated, expect ~50 holes
Memory utilization approaches ~66% at steady state
~33% of memory may be lost to external fragmentation

The mathematical derivation shows that in steady state:

For every 2 segments allocated, approximately 1 hole is created
The ratio of holes to segments approaches 0.5
Average memory utilization stabilizes around 2/3

fifty_percent_rule.pseudo
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
// Simulation of the 50% Rule
// This demonstrates external fragmentation in segmented systems
 
class FragmentationSimulator:
    def __init__(self, total_memory):
        self.total_memory = total_memory
        self.segments = []      # (start, size) tuples
        self.holes = [(0, total_memory)]  # Initially one big hole
        
    def allocate(self, size):
        """First-fit allocation"""
        for i, (start, hole_size) in enumerate(self.holes):
            if hole_size >= size:
                # Allocate from this hole
                self.segments.append((start, size))
                
                if hole_size == size:
                    # Exact fit: hole disappears
                    self.holes.pop(i)
                else:
                    # Partial fit: hole shrinks
                    self.holes[i] = (start + size, hole_size - size)
                return True
        return False  # No hole large enough
        
    def deallocate(self, segment_idx):
        """Free a segment, creating/extending a hole"""
        start, size = self.segments.pop(segment_idx)
        
        # Insert new hole and merge with neighbors if adjacent
        self.holes.append((start, size))
        self.merge_adjacent_holes()
        
    def get_fragmentation_stats(self):
        total_hole_size = sum(size for _, size in self.holes)
        largest_hole = max(size for _, size in self.holes) if self.holes else 0
        
        return {
            'num_segments': len(self.segments),
            'num_holes': len(self.holes),
            'hole_to_segment_ratio': len(self.holes) / max(1, len(self.segments)),
            'total_free': total_hole_size,
            'largest_hole': largest_hole,
            'fragmentation_ratio': 1 - (largest_hole / max(1, total_hole_size))
        }
 
# After reaching steady state with 100 segments:
# Typical result: ~50 holes (50% rule confirmed)
# Total free: ~33% of memory
# Largest hole: ~10% of total free
# Many allocations fail despite "available" memory

Paging and Internal Fragmentation

Paging completely eliminates external fragmentation by using fixed-size allocation units. Any free frame can satisfy any page request—no searching for "big enough holes" is ever required. However, this benefit comes at the cost of internal fragmentation.

How Internal Fragmentation Occurs in Paged Systems:

When a process's memory needs don't align perfectly with page boundaries, the last page is only partially used:

internal_fragmentation_example.txt
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
Page size: 4096 bytes (4KB)
 
Process A memory requirements:
  Code segment:   12,500 bytes
  Data segment:    8,200 bytes
  Stack segment:   3,100 bytes
  Total needed:   23,800 bytes
 
Page allocation:
  Code:   12,500 / 4096 = 3.05 → 4 pages allocated
          Waste: (4 × 4096) - 12,500 = 3,884 bytes internal fragmentation
          
  Data:    8,200 / 4096 = 2.00 → 2 pages allocated  
          Waste: (2 × 4096) - 8,200 = 0 bytes (perfect fit!)
          
  Stack:   3,100 / 4096 = 0.76 → 1 page allocated
          Waste: (1 × 4096) - 3,100 = 996 bytes internal fragmentation
 
Summary:
  Actual need:      23,800 bytes
  Allocated:        28,672 bytes (7 pages × 4096)
  Internal frag:     4,880 bytes
  Waste percentage:  17.0%

Expected Internal Fragmentation (Statistical Analysis):

For processes with random memory requirements:

On average, half a page is wasted per segment/region
Expected waste per allocation = PageSize / 2
With 4KB pages: average 2KB waste per logical region

For a typical process with N logical regions:

Expected internal fragmentation = N × (PageSize / 2)
With 5 regions and 4KB pages: ~10KB expected waste per process

This is bounded and predictable, unlike external fragmentation which grows unboundedly.

Internal Fragmentation vs Page Size
Page Size	Avg Waste/Region	5 Regions	10 Regions	TLB Efficiency
512 bytes	256 bytes	1.25 KB	2.5 KB	Excellent
1 KB	512 bytes	2.5 KB	5 KB	Very Good
4 KB	2 KB	10 KB	20 KB	Good
2 MB (huge)	1 MB	5 MB	10 MB	Excellent
1 GB (gigantic)	512 MB	2.5 GB	5 GB	Maximum

The Page Size Tradeoff

Larger pages reduce page table size and improve TLB efficiency (more memory mapped per TLB entry). However, they increase internal fragmentation. The 4KB page size used in most systems represents a careful balance between these competing concerns. Modern systems also support 'huge pages' (2MB, 1GB) for applications with large, dense memory regions where TLB efficiency outweighs fragmentation concerns.

Quantitative Fragmentation Comparison

Let's compare fragmentation behavior quantitatively using realistic system parameters.

fragmentation_analysis.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
"""
Fragmentation Analysis: Segmentation vs Paging
System: 4GB physical memory, 100 concurrent processes
"""
 
import math
 
class FragmentationAnalysis:
    @staticmethod
    def segmentation_analysis(
        total_memory_mb: int = 4096,    # 4GB
        num_processes: int = 100,
        avg_segments_per_process: int = 5
    ):
        """Analyze external fragmentation in segmented system"""
        
        total_segments = num_processes * avg_segments_per_process  # 500
        
        # Fifty percent rule: ~0.5 holes per segment at steady state
        expected_holes = total_segments * 0.5  # 250 holes
        
        # Average memory utilization under external fragmentation
        # Theoretical: ~66% utilization at steady state
        utilization_rate = 0.67
        usable_memory_mb = total_memory_mb * utilization_rate
        wasted_memory_mb = total_memory_mb * (1 - utilization_rate)
        
        # Probability of allocation failure
        # Increases as fragmentation worsens
        # Rough model: failure rate ∝ requested_size / largest_hole
        avg_segment_size_mb = usable_memory_mb / total_segments
        
        return {
            "scheme": "Segmentation",
            "total_memory_mb": total_memory_mb,
            "expected_holes": int(expected_holes),
            "utilization_rate": f"{utilization_rate:.0%}",
            "usable_memory_mb": f"{usable_memory_mb:.0f}",
            "wasted_memory_mb": f"{wasted_memory_mb:.0f}",
            "waste_percentage": f"{(1-utilization_rate):.0%}",
            "fragmentation_type": "External (unbounded)",
            "grows_over_time": True,
            "allocation_failures": "Possible despite free memory"
        }
    
    @staticmethod
    def paging_analysis(
        total_memory_mb: int = 4096,
        num_processes: int = 100,
        avg_regions_per_process: int = 5,
        page_size_kb: int = 4
    ):
        """Analyze internal fragmentation in paged system"""
        
        total_regions = num_processes * avg_regions_per_process  # 500
        page_size_bytes = page_size_kb * 1024
        
        # Expected internal fragmentation: PageSize/2 per region
        avg_waste_per_region_bytes = page_size_bytes / 2  # 2048 bytes
        total_waste_bytes = total_regions * avg_waste_per_region_bytes
        total_waste_mb = total_waste_bytes / (1024 * 1024)
        
        # With paging, all remaining memory is perfectly usable
        # No external fragmentation means no allocation failures
        waste_percentage = total_waste_mb / total_memory_mb
        utilization_rate = 1 - waste_percentage
        
        return {
            "scheme": "Paging (4KB pages)",
            "total_memory_mb": total_memory_mb,
            "regions": total_regions,
            "utilization_rate": f"{utilization_rate:.2%}",
            "usable_memory_mb": f"{total_memory_mb - total_waste_mb:.0f}",
            "wasted_memory_mb": f"{total_waste_mb:.1f}",
            "waste_percentage": f"{waste_percentage:.2%}",
            "fragmentation_type": "Internal (bounded)",
            "grows_over_time": False,
            "allocation_failures": "Never due to fragmentation"
        }
 
# Run analysis
seg = FragmentationAnalysis.segmentation_analysis()
pag = FragmentationAnalysis.paging_analysis()
 
"""
RESULTS:
========
Segmentation:
  - Waste: ~1.3 GB (33% of 4GB)
  - Fragmentation grows over time
  - Allocation failures possible
 
Paging (4KB):
  - Waste: ~0.5 MB (0.01% of 4GB)
  - Fragmentation bounded
  - Allocation never fails due to fragmentation
  
Paging wins by orders of magnitude in memory efficiency!
"""

Fragmentation Impact Analysis (4GB System, 100 Processes)
Metric	Segmentation	Paging (4KB)
Memory waste	~1,350 MB (33%)	~0.5 MB (0.01%)
Waste growth	Unbounded over time	Bounded, constant
Allocation failures	Common as fragmentation grows	Never due to fragmentation
Compaction needed	Periodically required	Never required
Predictability	Low (depends on allocation history)	High (statistically bounded)

Why This Comparison Matters

The dramatic difference in memory waste (33% vs 0.01%) explains why paging became the dominant memory management scheme. While segmentation provides better semantic organization, the external fragmentation problem made it impractical as a standalone technique for large, long-running systems.

Compaction: The Segmentation Band-Aid

To combat external fragmentation, segmented systems can perform memory compaction—relocating segments to consolidate free space into larger contiguous regions.

The Compaction Process:

compaction_process.txt
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
Before Compaction:
┌───────┬──────┬────────┬──────┬───────┬──────┬────────────────┐
│ Seg A │ FREE │  Seg B │ FREE │ Seg C │ FREE │     FREE       │
│  100K │  40K │  200K  │  30K │  50K  │  80K │     500K       │
└───────┴──────┴────────┴──────┴───────┴──────┴────────────────┘
Total free: 650K, Largest hole: 500K, Holes: 4
 
Compaction in progress (segments being relocated):
┌───────┬────────┬───────┬─────────────────────────────────────┐
│ Seg A │  Seg B │ Seg C │           COMPACTING...             │
│  100K │  200K  │  50K  │      (updating base registers)      │
└───────┴────────┴───────┴─────────────────────────────────────┘
 
After Compaction:
┌───────┬────────┬───────┬─────────────────────────────────────┐
│ Seg A │  Seg B │ Seg C │          FREE (650K)                │
│  100K │  200K  │  50K  │   ← Single contiguous region!       │
└───────┴────────┴───────┴─────────────────────────────────────┘
Total free: 650K, Largest hole: 650K, Holes: 1

Compaction Costs and Limitations:

Why Compaction is Expensive

•Memory bandwidth consumption: Every byte of every segment must be copied to its new location. For GBs of memory, this takes seconds to minutes.
•System pause required: Processes cannot execute during compaction because their segments are moving. This creates unacceptable latency for interactive systems.
•I/O interference: Compaction saturates the memory bus, starving other system activities.
•Base register updates: Every segment table entry must be updated with new base addresses atomically—a complex synchronization problem.
•Frequency: External fragmentation rebuilds after compaction, requiring repeated compaction cycles.
•Diminishing returns: System spends increasing time compacting as process churn increases.

Paging Has No Analogous Problem

Paging completely sidesteps the need for compaction. Since any page can map to any frame, there's no such thing as 'holes' in available memory—every free frame is equally usable for any allocation. This is one of the most compelling advantages of paging over pure segmentation.

Real-World Implications

Understanding fragmentation differences has practical implications for system design and application development.

Segmentation Challenges

•Long-running servers suffer increasing fragmentation
•Memory allocation becomes slower over time
•System may refuse reasonable allocation requests
•Periodic compaction creates latency spikes
•Hard to predict memory availability
•Capacity planning is difficult

Paging Advantages

•Memory behavior is predictable and consistent
•Allocation is O(1) with a free frame list
•Never fails due to fragmentation alone
•No compaction overhead—ever
•Easy capacity planning (just count frames)
•Works well for any system lifetime

Why Modern Systems Choose Paging:

The fragmentation characteristics of paging make it the clear choice for:

Server systems: Long uptimes mean external fragmentation would accumulate to critical levels
Cloud environments: Unpredictable workloads require predictable memory behavior
Mobile devices: Cannot afford compaction latency during user interaction
Real-time systems: Bounded memory allocation time is critical

The internal fragmentation of paging is a small, bounded, predictable cost. The external fragmentation of segmentation is a large, growing, unpredictable liability.

Summary: Fragmentation Trade-offs

Key Takeaways

•External fragmentation (segmentation) grows unboundedly over time; internal fragmentation (paging) is bounded and predictable
•The 50% rule shows segmentation loses ~33% of memory to fragmentation at steady state
•Paging wastes less than 1% of memory to internal fragmentation in typical workloads
•Compaction is expensive and only temporarily fixes external fragmentation
•Paging is universally preferred for fragmentation behavior in production systems
•The fragmentation trade-off is a primary reason paging displaced segmentation as the dominant technique

Fragmentation Mastery Complete

You now understand why fragmentation behavior is one of the decisive factors in choosing between segmentation and paging. The next page explores sharing differences—another dimension where these schemes behave very differently.