Paging & Segmentation

Paging & Segmentation

Why This Matters

Think of paging like organizing books in a library by fixed-size shelves. Each shelf holds the same number of books. When you need a book, you find which shelf it's on. Segmentation is like organizing by sections (fiction, non-fiction, reference)—each section can be different sizes. Paging and segmentation are two ways operating systems organize memory.

This matters because memory management affects performance. Paging avoids external fragmentation (no wasted space between allocations) but can have internal fragmentation (pages might be partially empty). Segmentation has external fragmentation (variable sizes leave gaps) but matches logical structure (code, data, stack). Understanding these helps you understand how your application's memory is managed.

In interviews, when someone asks "How does the OS manage memory?", they're testing whether you understand paging and segmentation. Do you know the trade-offs? Can you explain how address translation works? Most engineers don't. They just allocate memory and wonder why the system slows down.

What Engineers Usually Get Wrong

Most engineers think "paging and segmentation are the same thing." But they're different. Paging uses fixed-size blocks (pages), while segmentation uses variable-size blocks (segments). Modern systems often use both—segmentation for logical organization, paging for physical management. This is called "paged segmentation."

Engineers also don't understand fragmentation. Paging avoids external fragmentation (no gaps between pages) but can have internal fragmentation (pages partially empty). Segmentation has external fragmentation (gaps between segments) but no internal fragmentation (segments are exactly the size needed). Understanding this helps you understand memory efficiency.

How This Breaks Systems in the Real World

A service was allocating many small memory blocks. With segmentation, this created external fragmentation—lots of small gaps between segments. Over time, there was plenty of free memory, but no single gap was large enough for new allocations. The system started failing allocations even though memory wasn't full. The fix? Use paging, which avoids external fragmentation. Or use memory compaction to defragment memory.

Another story: A service was allocating large memory blocks. With paging, this created internal fragmentation—pages were partially empty. If a process needed 4.1KB, it got 8KB (two 4KB pages), wasting 3.9KB. Over time, this wasted memory accumulated. The fix? Use larger pages (2MB instead of 4KB) for large allocations, or use segmentation for variable-size allocations.

---

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

Feature	Paging	Segmentation
Size	Fixed-size pages	Variable-size segments
Fragmentation	Internal (pages too large)	External (small free chunks)
Logical structure	No (linear address space)	Yes (code, data, stack)
Sharing	Difficult	Easy (share segments)
Protection	Per page	Per segment
Management	Simple	Complex

---

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:

Feature	Paging	Segmentation
Size	Fixed	Variable
Fragmentation	Internal	External
Structure	Linear	Logical
Sharing	Difficult	Easy

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

---

Failure Stories You'll Recognize

The External Fragmentation: A service was allocating many small memory blocks. With segmentation, this created external fragmentation—lots of small gaps between segments. Over time, there was plenty of free memory, but no single gap was large enough for new allocations. The system started failing allocations even though memory wasn't full. The fix? Use paging, which avoids external fragmentation. Or use memory compaction to defragment memory.

The Internal Fragmentation: A service was allocating large memory blocks. With paging, this created internal fragmentation—pages were partially empty. If a process needed 4.1KB, it got 8KB (two 4KB pages), wasting 3.9KB. Over time, this wasted memory accumulated. The fix? Use larger pages (2MB instead of 4KB) for large allocations, or use segmentation for variable-size allocations.

The Fragmentation Confusion: A team was experiencing memory issues but didn't understand fragmentation. They thought "free memory" meant they could allocate it, but external fragmentation meant no single gap was large enough. The system failed allocations even though there was free memory. The fix? Understand fragmentation. Monitor memory usage and fragmentation. Use paging to avoid external fragmentation, or use compaction to defragment.

What Interviewers Are Really Testing

They want to hear you talk about paging and segmentation as trade-offs, not absolutes. Junior engineers say "paging is better than segmentation." Senior engineers say "paging avoids external fragmentation but has internal fragmentation. Segmentation matches logical structure but has external fragmentation. Modern systems use paged segmentation to get the best of both. Understand fragmentation and choose based on your use case."

When they ask "How does the OS manage memory?", they're testing:

• Do you understand paging vs segmentation?

• Do you know the trade-offs (fragmentation, complexity)?

• Can you explain how address translation works?

• 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

How InterviewCrafted Will Teach This

We'll teach this through production failures, not definitions. Instead of memorizing "paging uses fixed-size pages," you'll learn through scenarios like "why did our system fail allocations even though there was free memory?"

You'll see how memory management affects system performance and reliability. When an interviewer asks "how does the OS manage memory?", you'll think about paging, segmentation, fragmentation, and trade-offs—not just "the OS uses paging."

• Memory Management - Comprehensive overview of memory management including paging and segmentation
• Virtual Memory - How paging enables virtual memory and address translation
• Page Faults and Page Replacement - How paging enables page faults and replacement algorithms
• Process vs Thread - How paging and segmentation enable process isolation and memory protection
• System Calls - How processes request memory operations through system calls