Topic Overview

Paging & Segmentation

Master memory management techniques: paging (fixed-size) and segmentation (variable-size), their advantages, disadvantages, and when to use each.

Paging and segmentation are two memory management techniques used by operating systems. Paging divides memory into fixed-size pages, while segmentation divides memory into variable-size segments based on logical units.

Paging

Paging divides memory into fixed-size blocks called pages.

How Paging Works

Physical Memory: Divided into frames (fixed-size)
Virtual Memory: Divided into pages (same size as frames)

Page Table: Maps virtual pages to physical frames

Example:

Virtual Address: 0x1234
  Page Number: 0x1 (page 1)
  Offset: 0x234 (offset within page)
  
Page Table:
  Page 1 → Frame 5
  
Physical Address: 0x5234
  Frame Number: 5
  Offset: 0x234 (same)

Advantages

  • No external fragmentation: Pages are fixed-size
  • Simple allocation: Allocate pages, not variable blocks
  • Efficient swapping: Easy to swap pages to disk
  • Simple management: Page table straightforward

Disadvantages

  • Internal fragmentation: Page may be larger than needed
  • Page table overhead: Large page tables for large address spaces
  • No logical structure: Doesn't reflect program structure

Segmentation

Segmentation divides memory into variable-size segments based on logical units.

How Segmentation Works

Process Memory: Divided into segments
  - Code segment
  - Data segment
  - Stack segment
  - Heap segment

Segment Table: Maps segments to physical addresses

Example:

Logical Address: [Segment Number | Offset]
  Segment 0 (Code): Base = 0x1000, Limit = 0x2000
  Segment 1 (Data): Base = 0x3000, Limit = 0x1000
  
Segment Table:
  Segment 0 → Base: 0x1000, Limit: 0x2000
  Segment 1 → Base: 0x3000, Limit: 0x1000

Advantages

  • Logical organization: Reflects program structure
  • Easy sharing: Share code segments between processes
  • Protection: Different protection per segment
  • No internal fragmentation: Segments fit exactly

Disadvantages

  • External fragmentation: Free memory in small chunks
  • Complex management: Must manage variable-size segments
  • Slower allocation: Must find fitting segment
  • Compaction needed: Periodically compact memory

Comparison

FeaturePagingSegmentation
SizeFixed-size pagesVariable-size segments
FragmentationInternal (pages too large)External (small free chunks)
Logical structureNo (linear address space)Yes (code, data, stack)
SharingDifficultEasy (share segments)
ProtectionPer pagePer segment
ManagementSimpleComplex

Paged Segmentation

Combines both: Segments divided into pages.

Segmentation: Logical organization
Paging: Within segments, use paging

Benefits of both:
  - Logical structure (segmentation)
  - No external fragmentation (paging)

Example:

Segment 0 (Code):
  Page 0 → Frame 5
  Page 1 → Frame 8
  Page 2 → Frame 12

Segment 1 (Data):
  Page 0 → Frame 20
  Page 1 → Frame 25

Examples

Paging Implementation

class PagingSystem:
    def __init__(self, page_size=4096):
        self.page_size = page_size
        self.page_table = {}  # page → frame
        self.frames = {}  # frame → page
    
    def translate(self, virtual_address):
        """Translate virtual address to physical address"""
        page_number = virtual_address // self.page_size
        offset = virtual_address % self.page_size
        
        if page_number not in self.page_table:
            # Page fault
            frame_number = self.allocate_frame()
            self.page_table[page_number] = frame_number
            self.frames[frame_number] = page_number
        
        frame_number = self.page_table[page_number]
        physical_address = (frame_number * self.page_size) + offset
        
        return physical_address
    
    def allocate_frame(self):
        """Allocate free frame"""
        for frame in range(1000):  # Assume 1000 frames
            if frame not in self.frames:
                return frame
        raise MemoryError("No free frames")

Segmentation Implementation

class SegmentationSystem:
    def __init__(self):
        self.segment_table = {}  # segment → (base, limit)
    
    def translate(self, logical_address):
        """Translate logical address to physical address"""
        segment_number = logical_address >> 16  # High 16 bits
        offset = logical_address & 0xFFFF  # Low 16 bits
        
        if segment_number not in self.segment_table:
            raise SegmentationFault("Invalid segment")
        
        base, limit = self.segment_table[segment_number]
        
        if offset >= limit:
            raise SegmentationFault("Offset out of bounds")
        
        physical_address = base + offset
        return physical_address
    
    def create_segment(self, segment_number, size):
        """Create new segment"""
        base = self.allocate_memory(size)
        self.segment_table[segment_number] = (base, size)
        return base

Common Pitfalls

  • Not understanding fragmentation: Internal vs external. Fix: Understand paging has internal, segmentation has external
  • Page size too large: Wastes memory. Fix: Choose appropriate page size (typically 4KB)
  • Not using paged segmentation: Missing benefits of both. Fix: Use paged segmentation for best of both
  • Segment table overhead: Large segment tables. Fix: Use paged segmentation to reduce overhead

Interview Questions

Beginner

Q: What is the difference between paging and segmentation?

A:

Paging:

  • Fixed-size: Memory divided into fixed-size pages
  • No external fragmentation: Pages are same size
  • Simple management: Easy to allocate pages
  • No logical structure: Linear address space

Segmentation:

  • Variable-size: Memory divided into variable-size segments
  • External fragmentation: Free memory in small chunks
  • Logical structure: Reflects program (code, data, stack)
  • Easy sharing: Share segments between processes

Key Differences:

FeaturePagingSegmentation
SizeFixedVariable
FragmentationInternalExternal
StructureLinearLogical
SharingDifficultEasy

Example:

Paging:
  Page 0, Page 1, Page 2... (all same size)

Segmentation:
  Code segment, Data segment, Stack segment (different sizes)

Intermediate

Q: Explain how paging works. What is a page table and how does address translation work?

A:

Paging Process:

  1. Divide memory into pages

    Virtual Memory: Pages (fixed-size, e.g., 4KB)
Physical Memory: Frames (same size as pages)

  2. Page table maps pages to frames

    Page Table:
  Page 0 → Frame 5
  Page 1 → Frame 8
  Page 2 → Frame 12

  3. Address translation

    Virtual Address: 0x1234
  Page Number: 0x1 (page 1)
  Offset: 0x234 (offset within page)

Page Table Lookup:
  Page 1 → Frame 5

Physical Address: 0x5234
  Frame Number: 5
  Offset: 0x234 (same)

Page Table Entry (PTE):

[Frame Number | Present | Modified | Referenced | Protection]

Flags:

  • Present: Page in memory (1) or on disk (0)
  • Modified: Page has been written to
  • Referenced: Page recently accessed
  • Protection: Read, write, execute permissions

Benefits:

  • No external fragmentation
  • Simple allocation
  • Efficient swapping

Senior

Q: Design a memory management system that combines paging and segmentation. How do you handle address translation, protection, and optimize for performance?

A:

class PagedSegmentationSystem {
  private segmentTable: SegmentTable;
  private pageTables: Map<number, PageTable>;
  private tlb: TLB;
  
  constructor() {
    this.segmentTable = new SegmentTable();
    this.pageTables = new Map();
    this.tlb = new TLB({ size: 64 });
  }
  
  // 1. Address Translation (Two-level)
  translateAddress(logicalAddress: number): number {
    // Split logical address
    const segmentNumber = (logicalAddress >> 16) & 0xFFFF;
    const offset = logicalAddress & 0xFFFF;
    
    // Get segment descriptor
    const segment = this.segmentTable.get(segmentNumber);
    if (!segment) {
      throw new SegmentationFault();
    }
    
    // Check bounds
    if (offset >= segment.limit) {
      throw new SegmentationFault();
    }
    
    // Get page number within segment
    const pageNumber = Math.floor(offset / PAGE_SIZE);
    const pageOffset = offset % PAGE_SIZE;
    
    // Get page table for segment
    let pageTable = this.pageTables.get(segmentNumber);
    if (!pageTable) {
      pageTable = this.createPageTable(segmentNumber);
      this.pageTables.set(segmentNumber, pageTable);
    }
    
    // Translate page to frame
    const frameNumber = pageTable.getFrame(pageNumber);
    if (frameNumber === null) {
      // Page fault
      return this.handlePageFault(segmentNumber, pageNumber, pageOffset);
    }
    
    // Calculate physical address
    return (frameNumber * PAGE_SIZE) + pageOffset;
  }
  
  // 2. Segment Table
  class SegmentTable {
    private segments: Map<number, SegmentDescriptor>;
    
    get(segmentNumber: number): SegmentDescriptor | null {
      return this.segments.get(segmentNumber) || null;
    }
    
    createSegment(segmentNumber: number, limit: number, protection: Protection): void {
      const base = this.allocateMemory(limit);
      this.segments.set(segmentNumber, {
        base,
        limit,
        protection,
        pageTableBase: this.allocatePageTable()
      });
    }
  }
  
  // 3. Page Table per Segment
  class PageTable {
    private entries: Map<number, PageTableEntry>;
    
    getFrame(pageNumber: number): number | null {
      const entry = this.entries.get(pageNumber);
      if (!entry || !entry.present) {
        return null;
      }
      return entry.frameNumber;
    }
  }
  
  // 4. Protection
  class ProtectionManager {
    checkAccess(segment: SegmentDescriptor, accessType: 'read' | 'write' | 'execute'): boolean {
      switch (accessType) {
        case 'read':
          return segment.protection.read;
        case 'write':
          return segment.protection.write;
        case 'execute':
          return segment.protection.execute;
      }
      return false;
    }
  }
  
  // 5. TLB (Translation Lookaside Buffer)
  class TLB {
    private entries: Map<string, TLBEntry>;
    
    lookup(segmentNumber: number, pageNumber: number): TLBEntry | null {
      const key = `${segmentNumber}:${pageNumber}`;
      return this.entries.get(key) || null;
    }
    
    insert(segmentNumber: number, pageNumber: number, frameNumber: number): void {
      const key = `${segmentNumber}:${pageNumber}`;
      this.entries.set(key, { frameNumber, timestamp: Date.now() });
    }
  }
}

Features:

  1. Two-level translation: Segment → Page → Frame
  2. Protection: Per segment and per page
  3. TLB: Fast translation cache
  4. Logical structure: Segments reflect program structure
  5. No external fragmentation: Paging within segments

Key Takeaways

  • Paging: Fixed-size pages, no external fragmentation, simple management
  • Segmentation: Variable-size segments, logical structure, easy sharing
  • Paged segmentation: Combines both (segments divided into pages)
  • Address translation: Two-level (segment → page → frame)
  • Fragmentation: Paging has internal, segmentation has external
  • Protection: Per segment and per page
  • Best practices: Use paged segmentation for best of both, optimize with TLB

About the author

InterviewCrafted helps you master system design with patience. We believe in curiosity-led engineering, reflective writing, and designing systems that make future changes feel calm.