Session 4.3 – Non-Contiguous Memory Allocation

Learning Objectives

By the end of this session, you will be able to:

Understand the fundamental concepts of paging and non-contiguous memory allocation
Explain the structure and function of page tables
Perform logical to physical address translation
Analyze the role and benefits of Translation Lookaside Buffer (TLB)
Compare different page table structures (single-level, multi-level, inverted)
Calculate memory overhead and address translation efficiency

Introduction to Non-Contiguous Memory Allocation

Non-contiguous memory allocation allows a process's logical address space to be mapped to non-contiguous physical memory locations. This approach eliminates external fragmentation and provides better memory utilization.

                                    Advantages
                                    Eliminates external fragmentation
Better memory utilization
Supports virtual memory
Process size not limited by largest free block
Simplified memory allocation

                                

                                    Challenges
                                    Address translation overhead
Memory overhead for page tables
Internal fragmentation in pages
Complex hardware requirements
TLB management complexity

                                

Memory Allocation Comparison

Contiguous Allocation

Process A

Fragmentation

Process B

Fragmentation

Process C

External fragmentation problem

Non-Contiguous (Paging)

Frame 0: A-P0

Frame 1: B-P0

Frame 2: A-P1

Frame 3: C-P0

Frame 4: B-P1

No external fragmentation

Paging Concepts

Paging is a memory management scheme that eliminates the need for contiguous allocation of physical memory. The basic idea is to divide physical memory into fixed-size blocks called frames and logical memory into blocks of the same size called pages.

Key Terminology

Page: Fixed-size block of logical memory
Frame: Fixed-size block of physical memory
Page Table: Maps logical pages to physical frames
Page Number (p): Index into page table

Page Offset (d): Displacement within page/frame
Frame Number (f): Physical frame identifier
Page Size: Typically power of 2 (4KB, 8KB)
Internal Fragmentation: Unused space in last page

Paging Mechanism Overview

Logical Memory

Page 0

Page 1

Page 2

Page 3

Page Table

Page	Frame
0	1
1	4
2	0
3	7

Physical Memory

Frame 0: P2

Frame 1: P0

Frame 2: Other

Frame 3: Other

Frame 4: P1

Frame 5: Other

Frame 6: Other

Frame 7: P3

Page Size Considerations

Page Size	Advantages	Disadvantages	Best Use Case
Small (1KB-4KB)	Less internal fragmentation Better memory utilization	Large page tables More TLB misses	Memory-constrained systems
Large (64KB-1MB)	Smaller page tables Fewer TLB misses Better I/O performance	More internal fragmentation Longer loading times	High-performance systems

Page Tables

Page tables are the core data structure in paging systems, maintaining the mapping between logical pages and physical frames. Each process has its own page table.

Page Table Entry (PTE) Structure

Typical Page Table Entry (32-bit):
┌──────────────────────┬─┬─┬─┬─┬─┬─┬─┬─┐
│   Frame Number       │V│R│W│X│U│G│A│D│
│      (20 bits)       │ │ │ │ │ │ │ │ │
└──────────────────────┴─┴─┴─┴─┴─┴─┴─┴─┘

Control Bits:
V = Valid bit (page is in memory)
R = Read permission
W = Write permission  
X = Execute permission
U = User/Supervisor bit
G = Global bit (for TLB)
A = Access bit (recently accessed)
D = Dirty bit (modified since loaded)

Page Table Storage

Location: Main memory (too large for registers)
Base Register: Page Table Base Register (PTBR)
Size: One entry per logical page
Access: Through memory management unit (MMU)

Memory Overhead

Example Calculation:

32-bit address space = 2³² bytes
4KB page size = 2¹² bytes
Pages needed = 2³²/2¹² = 2²⁰ = 1M pages
Page table size = 1M × 4 bytes = 4MB per process

Address Translation Process

Address translation converts logical addresses to physical addresses using the page table. This process is handled by the Memory Management Unit (MMU).

Translation Algorithm

Address Translation Steps:
1. Extract page number (p) from logical address
2. Extract page offset (d) from logical address
3. Use page number as index into page table
4. Retrieve frame number (f) from page table entry
5. Check valid bit and permissions
6. Construct physical address: (f × page_size) + d

Logical Address Format (32-bit, 4KB pages):
┌────────────────────┬────────────────┐
│   Page Number (p)  │ Page Offset(d) │
│     20 bits        │    12 bits     │
└────────────────────┴────────────────┘

Physical Address Format:
┌────────────────────┬────────────────┐
│  Frame Number (f)  │ Page Offset(d) │
│     20 bits        │    12 bits     │
└────────────────────┴────────────────┘

Address Translation Example

Given: Logical Address = 8196 (decimal), Page Size = 4096 bytes

Step 1: Parse Logical Address

Logical Address: 8196
Binary: 0010000000000100

Page Number (p): 8196 ÷ 4096 = 2
Page Offset (d): 8196 % 4096 = 4

Or using bit manipulation:
p = 8196 >> 12 = 2
d = 8196 & 0xFFF = 4

Step 2: Translate Address

Look up Page Table[2]:
Assume Frame Number = 6

Physical Address:
= Frame Number × Page Size + Offset  
= 6 × 4096 + 4
= 24576 + 4
= 24580

Binary: 0110000000000100

Translation Performance Impact

Performance Concern: Each logical address translation requires at least one additional memory access to read the page table entry. This doubles the memory access time, creating the need for Translation Lookaside Buffers (TLB).

Translation Lookaside Buffer (TLB)

The TLB is a high-speed cache that stores recently used page table entries to avoid repeated memory accesses during address translation.

CPU
~1 cycle

→

TLB
1-2 cycles

→

Main Memory
100+ cycles

→

Storage
10⁶+ cycles

TLB Lookup Algorithm

Address Translation with TLB:
1. Extract page number from logical address
2. Search TLB for page number
3. If TLB hit:
   a. Retrieve frame number from TLB
   b. Construct physical address
   c. Access memory location
4. If TLB miss:
   a. Access page table in memory
   b. Retrieve frame number
   c. Update TLB with new entry
   d. Construct physical address
   e. Access memory location

TLB Entry Format:
┌─────────────┬──────────────┬──────────────┐
│ Page Number │ Frame Number │ Control Bits │
└─────────────┴──────────────┴──────────────┘

TLB Performance Metrics

Hit Ratio: Percentage of TLB hits
Miss Penalty: Extra time for page table access
Effective Access Time: Average memory access time

Formula:
EAT = (Hit Ratio × TLB Time) + 
      (Miss Ratio × (TLB Time + Memory Time + Memory Time))

Example:
Hit Ratio = 98%
TLB Time = 2ns
Memory Time = 100ns

EAT = 0.98×2 + 0.02×(2+100+100) = 6.0ns
                                    

TLB Management

Context Switching: TLB flush or process tags
Replacement Policy: LRU, FIFO, Random
Size: Typically 32-1024 entries
Associativity: Fully associative or set-associative
Address Space ID: Support for multiple address spaces

Advanced Page Table Structures

As address spaces grow larger, simple page tables become impractical due to their size. Several advanced structures address this problem.

1. Multi-Level Page Tables

Hierarchical structure that reduces memory overhead by only allocating page table space as needed.

Two-Level Page Table Structure

Logical Address (32-bit, 4KB pages, 4-byte PTEs):
┌──────────┬──────────┬────────────────┐
│   P1     │    P2    │ Page Offset(d) │
│ 10 bits  │ 10 bits  │    12 bits     │
└──────────┴──────────┴────────────────┘

Translation Process:
1. P1 indexes into outer page table
2. P2 indexes into inner page table  
3. Frame number + offset = physical address

Memory Savings:
- Single-level: 1M entries × 4 bytes = 4MB
- Two-level: 1K + (active pages/1K) × 4KB ≈ 8KB for typical process

2. Inverted Page Tables

One entry per physical frame instead of per logical page, reducing memory overhead but complicating lookups.

Inverted Page Table Entry:
┌─────────────┬─────────────┬──────────────┐
│ Process ID  │ Page Number │ Control Bits │
└─────────────┴─────────────┴──────────────┘

Advantages:
- Memory usage proportional to physical memory size
- Suitable for large address spaces

Disadvantages:
- Complex lookup (requires hash table or search)
- Shared pages are difficult to implement

3. Hashed Page Tables

Uses hash function to map page numbers to page table entries, efficient for sparse address spaces.

Hash Function Example:
hash(page_number) = page_number % hash_table_size

Collision Handling:
- Chaining: Linked list of entries with same hash
- Open addressing: Linear probing or quadratic probing

Best For:
- 64-bit address spaces
- Sparse memory usage patterns

Page Table Structure Comparison

Structure	Memory Overhead	Access Time	Best Use Case
Single-Level	High (O(virtual pages))	O(1)	Small address spaces
Multi-Level	Low (O(used pages))	O(levels)	Hierarchical access patterns
Inverted	Very Low (O(physical frames))	O(log n) or O(n)	Large, sparse address spaces
Hashed	Medium	O(1) average	Very large, sparse address spaces

Practical Examples

Address Translation Example

Problem:

Given a system with 16-bit logical addresses, 4KB page size, and the following page table:

Page	Frame	Valid
0	5	1
1	2	1
2	8	1
3	-	0

Translate the following logical addresses:

0x1004 (4100 decimal)
0x2800 (10240 decimal)
0x3FFE (16382 decimal)

Solution:

Page Size = 4KB = 4096 bytes = 2¹² bytes
Page Offset bits = 12
Page Number bits = 16 - 12 = 4

Address 0x1004 (4100):
Page Number = 4100 ÷ 4096 = 1
Page Offset = 4100 % 4096 = 4
Frame Number = Page Table[1] = 2
Physical Address = 2 × 4096 + 4 = 8196 (0x2004)

Address 0x2800 (10240):
Page Number = 10240 ÷ 4096 = 2  
Page Offset = 10240 % 4096 = 2048
Frame Number = Page Table[2] = 8
Physical Address = 8 × 4096 + 2048 = 34816 (0x8800)

Address 0x3FFE (16382):
Page Number = 16382 ÷ 4096 = 3
Page Table[3] is invalid → Page Fault!

TLB Performance Calculation

Scenario:
- TLB access time: 1ns
- Memory access time: 100ns  
- TLB hit ratio: 95%

Without TLB:
Each memory access requires:
1. Page table access: 100ns
2. Data access: 100ns
Total: 200ns per access

With TLB:
TLB Hit (95%): 1ns (TLB) + 100ns (data) = 101ns
TLB Miss (5%): 1ns (TLB) + 100ns (page table) + 100ns (data) = 201ns

Effective Access Time = 0.95 × 101 + 0.05 × 201 = 105.9ns

Performance Improvement:
Speedup = 200/105.9 ≈ 1.89× faster with TLB

Session Summary

Key Concepts

Paging: Non-contiguous memory allocation using fixed-size blocks
Page Tables: Mapping structure from logical to physical addresses
Address Translation: Hardware-based conversion process
TLB: High-speed cache for page table entries
Advanced Structures: Multi-level, inverted, and hashed page tables

Performance Insights

TLB Critical: 95%+ hit ratios essential for good performance
Page Size Trade-off: Small pages vs. large pages
Memory Overhead: Multi-level tables reduce space requirements
Translation Cost: Additional memory accesses for each reference
Locality Benefits: Spatial and temporal locality improve TLB performance

Next Session Preview

Session 4.4 will cover Segmentation, exploring segment-based memory management, segment tables, and the combination of segmentation with paging for optimal memory management solutions.