Contiguous vs Non-Contiguous Memory Allocation

Definition

Contiguous Memory Allocation: Allocate one continuous block of physical memory addresses

Non-Contiguous Memory Allocation: Allocate scattered blocks of physical memory, logical contiguity maintained by OS

Both have different trade-offs in complexity, fragmentation, and performance.

Contiguous Memory Allocation

Concept

Process gets one continuous block of physical addresses:

Physical Memory Layout:
┌──────────────┐ 1000000
│ Process A    │ (continuous block)
│              │
├──────────────┤ 1005000
│ Process B    │ (continuous block)
│              │
├──────────────┤ 1012000
│ Free Space   │
└──────────────┘

Address Calculation

Simple and fast:

Virtual address: 1500
Base address: 1000000
Physical address = Base + Virtual
                 = 1000000 + 1500
                 = 1001500

No complex lookup needed!

Protection

Simple bounds checking:

Virtual address = 3000
Base = 1000000
Limit = 5000 (process size)

Check: 3000 < 5000? Yes, allowed
Physical = 1000000 + 3000 = 1003000

Virtual address = 6000
Check: 6000 < 5000? No, violation!
Segmentation fault!

Advantages

1. Fast Address Translation

• Just addition: Physical = Base + Virtual
• No table lookup
• Cache friendly

2. Simple Management

• Easy to understand
• Predictable

3. Low Overhead

• One Base/Limit register pair per process
• No page/segment tables

Disadvantages

1. External Fragmentation

Free space becomes scattered:

After allocation and deallocation:
┌──────────────┐ 0
│ Process A    │ (2000 bytes)
├──────────────┤ 2000
│    FREE      │ (300 bytes)
├──────────────┤ 2300
│ Process B    │ (1500 bytes)
├──────────────┤ 3800
│    FREE      │ (500 bytes)
├──────────────┤ 4300
│ Process C    │ (1000 bytes)
├──────────────┤ 5300
│    FREE      │ (700 bytes)
└──────────────┘ 6000

Problem: Process D needs 600 bytes

• Free blocks: 300, 500, 700 bytes
• None contiguous for 600 bytes!
• Total free space: 1500 bytes (enough!)
• Unusable: Can’t allocate

Fragmentation

External Fragmentation Ratio:

$$\text{Fragmentation} = \frac{\text{Total free but unusable space}}{\text{Total memory}}$$

Can be 30-40% of memory wasted!

Non-Contiguous Memory Allocation

Concept

Process address space scattered in physical memory, OS maintains mapping:

Virtual Address Space:    Physical Memory:
0 ────────────→ Frame 5
1 ────────────→ Frame 12
2 ────────────→ Frame 3
3 ────────────→ Frame 8
...

Process sees: 0, 1, 2, 3, ... (contiguous)
Physically: Scattered in frames 5, 12, 3, 8, ... (non-contiguous)

Implementation: Two Main Approaches

Paging

Divide into fixed-size pages:

Virtual Address: 0-4095 (Page 0)
        ────────────────→ Frame 5 (4096-8191)

Virtual Address: 4096-8191 (Page 1)
        ────────────────→ Frame 12 (49152-53247)

Virtual Address: 8192-12287 (Page 2)
        ────────────────→ Frame 3 (12288-16383)

Page table maps virtual page to physical frame:

Page Table:
Virtual Page | Physical Frame
─────────────┼──────────────
     0       |      5
     1       |      12
     2       |      3
     3       |      8

Segmentation

Divide into logical segments (code, data, stack):

Segment 0 (Code): Virtual 0-1999
        ────────→ Physical 10000-11999

Segment 1 (Data): Virtual 0-3999
        ────────→ Physical 20000-23999

Segment 2 (Stack): Virtual 0-999
        ────────→ Physical 30000-30999

Segment table:

Segment Table:
Segment | Base  | Limit
────────┼───────┼──────
  0     | 10000 | 2000
  1     | 20000 | 4000
  2     | 30000 | 1000

Address Translation (Paging Example)

Virtual Address: 5000
Page Size: 4096 bytes

Virtual Page Number = 5000 / 4096 = 1
Offset in page = 5000 % 4096 = 904

Page Table[1] = Frame 12
Physical Address = 12 * 4096 + 904
                 = 49152 + 904
                 = 50056

Advantages of Non-Contiguous

1. No External Fragmentation (Paging)

Fixed-size units, no wasted space between allocations:

Free frames: Frame 5 empty, Frame 12 empty, Frame 20 empty
Need 2 frames? Allocate Frame 5 and Frame 12
No wasted space!

2. Process Can Be Larger Than RAM (Virtual Memory)

Process size: 1GB
RAM: 512MB
Physical pages in RAM: some subset
Rest of pages on disk (swapped)
Process works fine, just slower when accessing disk pages

3. Memory Protection

• ✓ Process can’t access other process pages
• ✓ Enforced at hardware level (page table)

4. Sharing

Can share memory:

Page 5: Code (shared between 3 processes)
Process A page table: page 0 → frame 5
Process B page table: page 2 → frame 5
Process C page table: page 1 → frame 5
All see same physical memory!

Disadvantages of Non-Contiguous

1. Address Translation Overhead

Every memory access needs translation:

Virtual 5000
├─ Calculate virtual page: 5000/4096 = 1
├─ Look up page table[1]: Access memory
├─ Get frame: 12
├─ Calculate physical: 12*4096 + offset
└─ Access physical address

Three memory accesses for one data fetch!
(Without TLB - see next)

2. Internal Fragmentation (Paging)

Last page usually not full:

Process size: 5000 bytes
Page size: 4096 bytes
Need 2 pages: 4096 + 4096 = 8192 bytes
Wasted: 8192 - 5000 = 3192 bytes

3. Complex Management

• Page tables take memory
• Complex algorithms for replacement, etc.

Example Waste:

Process: 10 million processes on system
Page size: 4096 bytes
Average page table: 256 entries
Average memory for page tables: 10M × 256 × 8 bytes = 20GB!

Comparison

Solutions to External Fragmentation (Contiguous)

1. Compaction

Move processes to eliminate holes:

Before:
┌──────────┐
│ Proc A   │ (2000)
├──────────┤ Free 300
├──────────┤
│ Proc B   │ (1500)
├──────────┤ Free 500
├──────────┤
│ Proc C   │ (1000)
└──────────┘

After compaction:
┌──────────┐
│ Proc A   │ (2000)
├──────────┤
│ Proc B   │ (1500)
├──────────┤
│ Proc C   │ (1000)
├──────────┤ Free 1300
└──────────┘

Now can allocate 600-byte process!
But compaction is expensive!

Cost:

• Stop all processes
• Move memory around
• Update base registers
• Can take milliseconds!

2. Use Non-Contiguous Allocation

Instead of fixing fragmentation, use paging or segmentation.

Modern Systems

Most modern systems use non-contiguous (paging) because:

• ✓ Virtual memory support (programs > RAM)
• ✓ No external fragmentation
• ✓ Hardware TLB speeds up translation
• ✓ Protection mechanism

Summary

Contiguous allocation is simple and fast but causes external fragmentation wasting memory. Non-contiguous allocation (paging/segmentation) eliminates fragmentation and enables virtual memory but requires address translation overhead. Hardware TLB caches translations to reduce overhead. Modern systems choose non-contiguous allocation because memory is expensive and waste is unacceptable. Paging is simplest non-contiguous approach. Compaction can recover fragmented space but is expensive. Understanding both important for system design.