Introduction
Memory management is one of the most critical and complex components of any operating system. It determines how much memory is available to applications, how efficiently that memory is used, and how the system handles situations where demand exceeds physical capacity.
In this guide, we’ll explore everything from basic memory concepts to advanced virtual memory systems used in modern operating systems.
Memory Management Basics
The Memory Hierarchy
┌─────────────────────────────────────────────────────────────────┐
│ MEMORY HIERARCHY │
├─────────────────────────────────────────────────────────────────┤
│ │
│ Fastest ◄──────────────────────────────────────► Slowest │
│ │
│ ┌───────────────────────────────────────────────────────────┐ │
│ │ CPU Registers │ │
│ │ • Very small (16-64 registers) │ │
│ │ • Access time: < 1 nanosecond │ │
│ │ • Size: ~256 bytes │ │
│ └───────────────────────────────────────────────────────────┘ │
│ ▲ │
│ │ │
│ ┌───────────────────────────────────────────────────────────┐ │
│ │ CPU Cache (L1, L2, L3) │ │
│ │ • L1: 32-64 KB (core-specific) │ │
│ │ • L2: 256KB-1MB (per core) │ │
│ │ • L3: 4-32 MB (shared) │ │
│ │ • Access time: 1-10 nanoseconds │ │
│ └───────────────────────────────────────────────────────────┘ │
│ ▲ │
│ │ │
│ ┌───────────────────────────────────────────────────────────┐ │
│ │ Main Memory (RAM) │ │
│ │ • 8-64 GB typical │ │
│ │ • Access time: 50-100 nanoseconds │ │
│ │ • Volatile (data lost when powered off) │ │
│ └───────────────────────────────────────────────────────────┘ │
│ ▲ │
│ │ │
│ ┌───────────────────────────────────────────────────────────┐ │
│ │ Secondary Storage (SSD/HDD) │ │
│ │ • 1-10 TB typical │ │
│ │ • Access time: microseconds to milliseconds │ │
│ │ • Non-volatile │ │
│ └───────────────────────────────────────────────────────────┘ │
│ │
│ Principle: Smaller, faster, more expensive per byte │
│ │
└─────────────────────────────────────────────────────────────────┘
Memory Management Goals
┌─────────────────────────────────────────────────────────────────┐
│ MEMORY MANAGEMENT OBJECTIVES │
├─────────────────────────────────────────────────────────────────┤
│ │
│ 1. RELOCATION │
│ ┌─────────────────────────────────────────────────────────┐ │
│ │ Programs shouldn't need to know where they'll be loaded│ │
│ │ Physical addresses should be hidden from programs │ │
│ └─────────────────────────────────────────────────────────┘ │
│ │
│ 2. PROTECTION │
│ ┌─────────────────────────────────────────────────────────┐ │
│ │ Prevent processes from accessing each other's memory │ │
│ │ Enforce access control (read/write/execute) │ │
│ └─────────────────────────────────────────────────────────┘ │
│ │
│ 3. SHARING │
│ ┌─────────────────────────────────────────────────────────┐ │
│ │ Allow multiple processes to share memory │ │
│ │ Share code libraries, shared memory regions │ │
│ └─────────────────────────────────────────────────────────┘ │
│ │
│ 4. LOGICAL ORGANIZATION │
│ ┌─────────────────────────────────────────────────────────┐ │
│ │ Organize code and data separately │ │
│ │ Support different types of memory (fast/slow) │ │
│ └─────────────────────────────────────────────────────────┘ │
│ │
│ 5. PHYSICAL ORGANIZATION │
│ ┌─────────────────────────────────────────────────────────┐ │
│ │ Manage scattered memory fragments │ │
│ │ Use hierarchy: fast cache, slow RAM, disk │ │
│ └─────────────────────────────────────────────────────────┘ │
│ │
└─────────────────────────────────────────────────────────────────┘
Virtual Memory
Virtual memory is the foundation of modern memory management. It creates the illusion that each process has its own large, contiguous address space.
How Virtual Memory Works
┌─────────────────────────────────────────────────────────────────┐
│ VIRTUAL MEMORY CONCEPT │
├─────────────────────────────────────────────────────────────────┤
│ │
│ Process View (Virtual Addresses) │
│ ┌───────────────────────────────────────────────────────────┐ │
│ │ 0x00000000 ┌─────────────────────────────────────────┐ │ │
│ │ │ │ │ │
│ │ │ Code Segment │ │ │
│ │ 0x00400000 │ (text section) │ │ │
│ │ ├─────────────────────────────────────────┤ │ │
│ │ │ Data Segment │ │ │
│ │ 0x00401000 │ (globals, constants) │ │ │
│ │ ├─────────────────────────────────────────┤ │ │
│ │ │ Heap (dynamic allocation) │ │ │
│ │ 0x00410000 │ │ │ │
│ │ │ │ │ │
│ │ │ │ │ │
│ │ ├─────────────────────────────────────────┤ │ │
│ │ │ Unused │ │ │
│ │ ├─────────────────────────────────────────┤ │ │
│ │ │ Stack (function calls) │ │ │
│ │ 0x7FFF0000 │ │ │ │
│ │ 0xFFFFFFFF └─────────────────────────────────────────┘ │ │
│ │ Total: 4 GB virtual address space │ │
│ └───────────────────────────────────────────────────────────┘ │
│ │
│ │ │
│ │ MMU Translation │
│ ▼ │
│ │
│ Physical Memory (RAM) │
│ ┌───────────────────────────────────────────────────────────┐ │
│ │ 0x00000000 │ Kernel Space │ │
│ │ 0xC0000000 ├───────────────────────────────────────────┤ │
│ │ │ │ │
│ │ │ Process A Code [0x00400000 → 0x1000] │ │
│ │ │ Process A Data [0x00401000 → 0x2000] │ │
│ │ │ │ │
│ │ │ Process B Code [0x00400000 → 0x5000] │ │
│ │ │ │ │
│ │ │ Free Frame │ │
│ │ │ │ │
│ └───────────────────────────────────────────────────────────┘ │
│ │
└─────────────────────────────────────────────────────────────────┘
Address Translation
"""Virtual to physical address translation simulation."""
class AddressTranslation:
"""Simulate virtual address translation."""
def __init__(self, page_size: int = 4096):
self.page_size = page_size
self.page_table = {}
def virtual_to_physical(self, virtual_addr: int, pid: int) -> int:
"""Translate virtual address to physical address."""
# Extract page number and offset
page_number = virtual_addr // self.page_size
offset = virtual_addr % self.page_size
# Look up in page table
if pid not in self.page_table:
raise ValueError(f"No page table for process {pid}")
page_entry = self.page_table[pid].get(page_number)
if page_entry is None:
raise ValueError(f"Page fault: page {page_number} not mapped")
if not page_entry['present']:
raise ValueError(f"Page fault: page {page_number} not in memory")
# Calculate physical address
physical_frame = page_entry['frame']
physical_addr = (physical_frame * self.page_size) + offset
return physical_addr
def add_mapping(self, pid: int, virtual_page: int, physical_frame: int,
present: bool = True, writable: bool = True):
"""Add a page table entry."""
if pid not in self.page_table:
self.page_table[pid] = {}
self.page_table[pid][virtual_page] = {
'frame': physical_frame,
'present': present,
'writable': writable,
'accessed': False,
'dirty': False
}
# Example usage
translator = AddressTranslation(page_size=4096)
# Add mappings for a process
translator.add_mapping(pid=1001, virtual_page=0, physical_frame=0x1000) # Code
translator.add_mapping(pid=1001, virtual_page=1, physical_frame=0x1001) # Data
translator.add_mapping(pid=1001, virtual_page=2, physical_frame=0x1002) # Heap
# Translate a virtual address
virtual_addr = 0x00401050 # Inside data segment
physical_addr = translator.virtual_to_physical(virtual_addr, pid=1001)
print(f"Virtual: 0x{virtual_addr:08x} -> Physical: 0x{physical_addr:08x}")
Paging
Paging is the technique of dividing both virtual and physical memory into fixed-size blocks called pages and frames.
Page Table Structure
┌─────────────────────────────────────────────────────────────────┐
│ PAGE TABLE ENTRIES │
├─────────────────────────────────────────────────────────────────┤
│ │
│ ┌─────────────────────────────────────────────────────────┐ │
│ │ PAGE TABLE ENTRY (32-bit) │ │
│ ├─────────────────────────────────────────────────────────┤ │
│ │ Bit │ Name │ Description │ │
│ ├───────┼─────────────┼───────────────────────────────────┤ │
│ │ 0 │ Present (P) │ Page is in physical memory │ │
│ │ 1 │ Read/Write │ Read/Write or Read-only │ │
│ │ 2 │ User/Supervisor │ User or Kernel access │ │
│ │ 3 │ PWT │ Write-through policy │ │
│ │ 4 │ PCD │ Cache disable │ │
│ │ 5 │ Accessed │ Page has been accessed │ │
│ │ 6 │ Dirty │ Page has been modified │ │
│ │ 7 │ PAT │ Page attribute table │ │
│ │ 8 │ Global │ Global page (not flushed on CR3) │ │
│ │ 9-11 │ Available │ OS-specific use │ │
│ │ 12-31 │ Frame │ Physical frame number │ │
│ └───────┴─────────────┴───────────────────────────────────┘ │
│ │
│ Page Table Entry (x86-64, PAE) │
│ ┌─────────────────────────────────────────────────────────┐ │
│ │ 63 │ 12-51 │ 9-8 │ 7 │ 6 │ 5 │ 2 │ 1 │ 0 │ │
│ ├─────────┼────────────┼────────+---+---+---+---+---+────┤ │
│ │ Reserved│ Frame Addr │ Available │ XD│ G │ A │ PWT│ PCD│ │ │
│ │ │ │ │ │ │ │ │ │ │
│ └─────────┴────────────┴────────────┴───┴───┴───┴────┴────┘ │
│ │
└─────────────────────────────────────────────────────────────────┘
Multi-Level Page Tables
┌─────────────────────────────────────────────────────────────────┐
│ TWO-LEVEL PAGE TABLE STRUCTURE │
├─────────────────────────────────────────────────────────────────┤
│ │
│ Virtual Address: │
│ ┌───────────────┬───────────────┬───────────────┐ │
│ │ PD Index │ PT Index │ Offset │ │
│ │ (10 bits) │ (10 bits) │ (12 bits) │ │
│ └───────────────┴───────────────┴───────────────┘ │
│ │ │ │ │
│ ▼ ▼ │ │
│ ┌───────────────┐ ┌───────────────┐ │ │
│ │ Page Directory│ │ Page Table │ │ │
│ │ (4KB) │ │ (4KB) │ │ │
│ │ │ │ │ │ │
│ │ 1024 entries │ │ 1024 entries │ │ │
│ │ │ │ │ │ │
│ │ ┌───────────┐ │ │ ┌───────────┐ │ │ │
│ │ │ PDE 0 │─┼─┼─►│ PTE 0 │─┴─────► Physical Frame │
│ │ │ PDE 1 │ │ │ │ PTE 1 │ + Offset │
│ │ │ ... │ │ │ │ ... │ │
│ │ │ PDE 1023 │ │ │ │ PTE 1023 │ │
│ │ └───────────┘ │ │ └───────────┘ │
│ └───────────────┘ │ │
│ │ │
│ Benefit: Only allocate page tables for mapped virtual space │
│ │
└─────────────────────────────────────────────────────────────────┘
Page Table Implementation
// Simplified page table implementation
#include <stdint.h>
#include <stdbool.h>
#include <stdio.h>
#define PAGE_SIZE 4096
#define PTE_PRESENT 0x1
#define PTE_WRITABLE 0x2
#define PTE_USER 0x4
typedef struct {
uint64_t frame: 52; // Physical frame number
uint64_t available: 12; // Available for OS
uint64_t accessed: 1; // Accessed flag
uint64_t dirty: 1; // Modified flag
uint64_t pwt: 1; // Page write-through
uint64_t pcd: 1; // Cache disable
uint64_t accessed2: 1; // Another access flag
uint64_t ps: 1; // Page size (0=4KB)
uint64_t global: 1; // Global page
uint64_t available2: 3; // Available
uint64_t xd: 1; // Execute disable
uint64_t reserved: 1; // Reserved
} __attribute__((packed)) page_table_entry_t;
// Page directory entry (points to page table)
typedef page_table_entry_t page_directory_entry_t;
// Page table (array of PTE)
typedef page_table_entry_t page_table_t[1024];
// Page directory (array of PDE)
typedef page_directory_entry_t page_directory_t[1024];
// Simulate a page table
void setup_page_table(page_table_t *pt, uint64_t base_frame) {
for (int i = 0; i < 1024; i++) {
(*pt)[i].frame = base_frame + i;
(*pt)[i].present = 1;
(*pt)[i].writable = 1;
(*pt)[i].accessed = 0;
(*pt)[i].dirty = 0;
}
}
// Translate virtual address using two-level page table
uint64_t translate_address(
page_directory_t *pd,
uint64_t virtual_addr
) {
// Extract indices
uint64_t pd_index = (virtual_addr >> 22) & 0x3FF;
uint64_t pt_index = (virtual_addr >> 12) & 0x3FF;
uint64_t offset = virtual_addr & 0xFFF;
// Get page directory entry
page_directory_entry_t pde = (*pd)[pd_index];
if (!pde.present) {
printf("Page fault: PDE not present\n");
return 0;
}
// Get page table entry
page_table_t *pt = (page_table_t *)(pde.frame * PAGE_SIZE);
page_table_entry_t pte = (*pt)[pt_index];
if (!pte.present) {
printf("Page fault: PTE not present\n");
return 0;
}
// Calculate physical address
uint64_t physical_addr = (pte.frame * PAGE_SIZE) + offset;
return physical_addr;
}
int main() {
// Setup would happen in kernel
printf("Page table structure defined\n");
printf("Page size: %d bytes\n", PAGE_SIZE);
printf("Virtual address bits: %d\n", 32);
printf("Page offset bits: %d\n", 12);
printf("PDE/PT index bits: %d\n", 10);
return 0;
}
Translation Lookaside Buffer (TLB)
The TLB is a hardware cache that speeds up address translation by caching recent virtual-to-physical address translations.
┌─────────────────────────────────────────────────────────────────┐
│ TRANSLATION LOOKASIDE BUFFER (TLB) │
├─────────────────────────────────────────────────────────────────┤
│ │
│ Without TLB: │
│ ┌──────────┐ ┌──────────┐ ┌──────────┐ │
│ │ CPU │───►│ Page │───►│ RAM │ = 100+ cycles │
│ │ Request │ │ Table │ │ Access │ │
│ └──────────┘ └──────────┘ └──────────┘ │
│ │
│ With TLB: │
│ ┌──────────┐ ┌──────────┐ │
│ │ CPU │───►│ TLB │───► Hit: 1 cycle │
│ │ Request │ │ Cache │ Miss: +100 cycles │
│ └──────────┘ └──────────┘ │
│ │ │
│ ┌────┴────┐ │
│ │ │ │
│ Hit Miss ──► Page Table │
│ │ │ │
│ └────┬────┘ │
│ │ │
│ ▼ │
│ TLB Fill │
│ │
│ Typical TLB: 32-512 entries, 99%+ hit rate │
│ │
└─────────────────────────────────────────────────────────────────┘
TLB Simulation
"""TLB (Translation Lookaside Buffer) simulation."""
from dataclasses import dataclass
from typing import Optional, Dict
import random
@dataclass
class TLBEntry:
"""A TLB cache entry."""
virtual_page: int
physical_frame: int
valid: bool = True
accessed: bool = False
class TLBCache:
"""Simulated TLB with LRU replacement."""
def __init__(self, size: int = 16):
self.size = size
self.entries: Dict[int, TLBEntry] = {} # By virtual page
self.access_order = [] # For LRU
def translate(self, virtual_addr: int) -> Optional[int]:
"""Try to translate a virtual address."""
virtual_page = virtual_addr // 4096
offset = virtual_addr % 4096
if virtual_page in self.entries:
# TLB hit
entry = self.entries[virtual_page]
entry.accessed = True
# Update LRU
self.access_order.remove(virtual_page)
self.access_order.append(virtual_page)
return (entry.physical_frame * 4096) + offset
# TLB miss - would trigger page table walk
return None
def add_entry(self, virtual_page: int, physical_frame: int):
"""Add a new entry to TLB."""
# Evict if full (LRU)
if len(self.entries) >= self.size:
lru_page = self.access_order.pop(0)
del self.entries[lru_page]
# Add new entry
self.entries[virtual_page] = TLBEntry(
virtual_page=virtual_page,
physical_frame=physical_frame
)
self.access_order.append(virtual_page)
def get_stats(self) -> dict:
"""Get TLB statistics."""
total = len(self.access_order)
return {
'entries': total,
'max_entries': self.size,
'full': total >= self.size
}
class MemorySystem:
"""Simulated memory system with TLB and page table."""
def __init__(self, tlb_size: int = 16, ram_size: int = 1024):
self.tlb = TLBCache(tlb_size)
self.ram_size = ram_size
self.page_table: Dict[int, Dict[int, dict]] = {} # pid -> {vpage -> entry}
self.tlb_hits = 0
self.tlb_misses = 0
def add_process(self, pid: int, mappings: Dict[int, int]):
"""Add process with page mappings."""
# vpage -> pframe
self.page_table[pid] = {}
for vpage, pframe in mappings.items():
self.page_table[pid][vpage] = {
'frame': pframe,
'present': True,
'writable': True
}
# Also add to TLB
self.tlb.add_entry(vpage, pframe)
def access_memory(self, pid: int, virtual_addr: int) -> Optional[int]:
"""Access memory with translation."""
virtual_page = virtual_addr // 4096
# Check TLB first
result = self.tlb.translate(virtual_addr)
if result is not None:
self.tlb_hits += 1
return result
# TLB miss - check page table
self.tlb_misses += 1
if pid in self.page_table:
if virtual_page in self.page_table[pid]:
entry = self.page_table[pid][virtual_page]
# Add to TLB
self.tlb.add_entry(virtual_page, entry['frame'])
return (entry['frame'] * 4096) + (virtual_addr % 4096)
# Page fault
return None
def get_stats(self) -> dict:
"""Get memory system statistics."""
total = self.tlb_hits + self.tlb_misses
hit_rate = (self.tlb_hits / total * 100) if total > 0 else 0
return {
'tlb_hits': self.tlb_hits,
'tlb_misses': self.tlb_misses,
'tlb_hit_rate': f"{hit_rate:.2f}%",
'tlb_entries': self.tlb.get_stats()
}
# Example usage
mem = MemorySystem(tlb_size=4)
# Add a process with some mappings
mem.add_process(1001, {
0: 0x1000, # Code at frame 0x1000
1: 0x1001, # Data at frame 0x1001
2: 0x1002, # Heap at frame 0x1002
100: 0x2000, # Stack at frame 0x2000
})
# Access memory
print("Accessing virtual addresses:")
for va in [0x1000, 0x1050, 0x1000, 0x2000, 0x2050, 0x1000]:
pa = mem.access_memory(1001, va)
print(f" Virtual: 0x{va:08x} -> Physical: 0x{pa:08x}" if pa else " Page fault!")
print(f"\nStats: {mem.get_stats()}")
Page Replacement Algorithms
When physical memory is full, the OS must decide which pages to evict to make room for new pages.
Algorithms Comparison
┌─────────────────────────────────────────────────────────────────┐
│ PAGE REPLACEMENT ALGORITHMS │
├─────────────────────────────────────────────────────────────────┤
│ │
│ ┌─────────────────────────────────────────────────────────┐ │
│ │ OPTIMAL (Belady's Algorithm) │ │
│ │ ───────────────────────────────────────────────────── │ │
│ │ Replace page that won't be used for longest time │ │
│ │ Cannot be implemented (requires future knowledge) │ │
│ │ Used as theoretical bound │ │
│ │ Hit Rate: Best possible │ │
│ └─────────────────────────────────────────────────────────┘ │
│ │
│ ┌─────────────────────────────────────────────────────────┐ │
│ │ FIFO (First In First Out) │ │
│ │ ───────────────────────────────────────────────────── │ │
│ │ Replace oldest page in memory │ │
│ │ Simple but suffers from Belady's anomaly │ │
│ │ Hit Rate: Poor (ignores usage patterns) │ │
│ └─────────────────────────────────────────────────────────┘ │
│ │
│ ┌─────────────────────────────────────────────────────────┐ │
│ │ LRU (Least Recently Used) │ │
│ │ ───────────────────────────────────────────────────── │ │
│ │ Replace page not used for longest time │ │
│ │ Good approximation of OPT │ │
│ │ Hit Rate: Good (expensive to implement perfectly) │ │
│ └─────────────────────────────────────────────────────────┘ │
│ │
│ ┌─────────────────────────────────────────────────────────┐ │
│ │ CLOCK (Second Chance) │ │
│ │ ───────────────────────────────────────────────────── │ │
│ │ Circular buffer with reference bit │ │
│ │ Approximation of LRU without full history │ │
│ │ Hit Rate: Good (commonly used in practice) │ │
│ └─────────────────────────────────────────────────────────┘ │
│ │
│ ┌─────────────────────────────────────────────────────────┐ │
│ │ WORKING SET │ │
│ │ ───────────────────────────────────────────────────── │ │
│ │ Replace pages outside working set │ │
│ │ Based on locality principle │ │
│ │ Hit Rate: Very Good │ │
│ └─────────────────────────────────────────────────────────┘ │
│ │
└─────────────────────────────────────────────────────────────────┘
Implementation
"""Page replacement algorithm implementations."""
from collections import deque, OrderedDict
from typing import List, Set, Optional
class FIFOAlgorithm:
"""First-In-First-Out page replacement."""
def __init__(self, frames: int):
self.frames = frames
self.page_queue = deque()
self.page_faults = 0
def access(self, page: int) -> bool:
"""Access a page. Returns True on hit, False on fault."""
if page in self.page_queue:
return True # Hit
self.page_faults += 1
if len(self.page_queue) >= self.frames:
# Evict oldest
self.page_queue.popleft()
self.page_queue.append(page)
return False
def get_stats(self) -> dict:
return {'faults': self.page_faults}
class LRUAlgorithm:
"""Least Recently Used page replacement."""
def __init__(self, frames: int):
self.frames = frames
self.page_order = OrderedDict()
self.page_faults = 0
def access(self, page: int) -> bool:
"""Access a page."""
if page in self.page_order:
# Move to end (most recently used)
self.page_order.move_to_end(page)
return True
self.page_faults += 1
if len(self.page_order) >= self.frames:
# Evict least recently used (first item)
self.page_order.popitem(last=False)
self.page_order[page] = True
return False
class ClockAlgorithm:
"""Clock (Second Chance) algorithm."""
def __init__(self, frames: int):
self.frames = frames
self.pages = [None] * frames
self.reference_bits = [0] * frames
self.clock_hand = 0
self.page_faults = 0
def access(self, page: int) -> bool:
"""Access a page."""
# Check if page is in memory
if page in self.pages:
# Set reference bit
idx = self.pages.index(page)
self.reference_bits[idx] = 1
return True
# Page fault
self.page_faults += 1
# Find victim using clock algorithm
while True:
if self.reference_bits[self.clock_hand] == 0:
# Evict this page
self.pages[self.clock_hand] = page
self.reference_bits[self.clock_hand] = 0
self.clock_hand = (self.clock_hand + 1) % self.frames
break
else:
# Give second chance - clear reference bit
self.reference_bits[self.clock_hand] = 0
self.clock_hand = (self.clock_hand + 1) % self.frames
return False
class OptimalAlgorithm:
"""Optimal page replacement (Belady's algorithm)."""
def __init__(self, frames: int, future_accesses: List[int]):
self.frames = frames
self.future = future_accesses
self.page_faults = 0
def access(self, page: int, time: int) -> bool:
"""Access a page at given time."""
remaining = self.future[time:]
if page in set(self.pages[:self.frames] if any(self.pages) else []):
return True
self.page_faults += 1
if None in self.pages[:self.frames]:
# Free slot available
for i in range(self.frames):
if self.pages[i] is None:
self.pages[i] = page
break
else:
# Find page used furthest in future
page_to_evict = None
furthest_use = -1
for p in set(self.pages[:self.frames]):
try:
next_use = remaining.index(p)
except ValueError:
next_use = float('inf')
if next_use > furthest_use:
furthest_use = next_use
page_to_evict = p
# Evict
for i in range(self.frames):
if self.pages[i] == page_to_evict:
self.pages[i] = page
break
return False
# Comparison
def compare_algorithms(pages: List[int], num_frames: int) -> dict:
"""Compare different page replacement algorithms."""
results = {}
# FIFO
fifo = FIFOAlgorithm(num_frames)
for page in pages:
fifo.access(page)
results['FIFO'] = fifo.get_stats()
# LRU
lru = LRUAlgorithm(num_frames)
for page in pages:
lru.access(page)
results['LRU'] = lru.get_stats()
# Clock
clock = ClockAlgorithm(num_frames)
for page in pages:
clock.access(page)
results['Clock'] = clock.get_stats()
return results
# Example
if __name__ == "__main__":
# Page reference string
pages = [1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5]
frames = 3
print(f"Page reference: {pages}")
print(f"Number of frames: {frames}\n")
results = compare_algorithms(pages, frames)
for algo, stats in results.items():
print(f"{algo}: {stats['faults']} page faults")
Segmentation
Segmentation is an alternative (or complement) to paging that provides logical memory management.
Segmentation vs Paging
┌─────────────────────────────────────────────────────────────────┐
│ SEGMENTATION VS PAGING │
├─────────────────────────────────────────────────────────────────┤
│ │
│ SEGMENTATION │
│ ┌─────────────────────────────────────────────────────────┐ │
│ │ Logical view: Variable-sized segments │ │
│ │ ┌─────────┬─────────┬─────────┬─────────┐ │ │
│ │ │ Code │ Data │ Heap │ Stack │ │ │
│ │ │ seg 0 │ seg 1 │ seg 2 │ seg 3 │ │ │
│ │ └─────────┴─────────┴─────────┴─────────┘ │ │
│ │ 0 1000 5000 10000 │ │
│ │ │ │
│ │ • Visible to programs │ │
│ │ • Variable size │ │
│ │ • Protection per segment │ │
│ │ • Allows sharing entire segments │ │
│ └─────────────────────────────────────────────────────────┘ │
│ │
│ PAGING │
│ ┌─────────────────────────────────────────────────────────┐ │
│ │ Physical view: Fixed-size pages │ │
│ │ ┌────┬────┬────┬────┬────┬────┬────┬────┐ │ │
│ │ │ P0 │ P1 │ P2 │ P3 │ P4 │ P5 │ P6 │ P7 │ │ │
│ │ └────┴────┴────┴────┴────┴────┴────┴────┘ │ │
│ │ 4KB 4KB 4KB 4KB 4KB 4KB 4KB 4KB │ │
│ │ │ │
│ │ • Transparent to programs │ │
│ │ • Fixed size │ │
│ │ • No inherent protection │ │
│ │ • Internal fragmentation │ │
│ └─────────────────────────────────────────────────────────┘ │
│ │
│ SEGMENTED PAGING (Most common) │
│ ┌─────────────────────────────────────────────────────────┐ │
│ │ Best of both worlds: │ │
│ │ • Segments for logical organization │ │
│ │ • Pages within segments for physical management │ │
│ └─────────────────────────────────────────────────────────┘ │
│ │
└─────────────────────────────────────────────────────────────────┘
Swap Space
When physical memory is full, the OS uses disk space as temporary memory (swap).
┌─────────────────────────────────────────────────────────────────┐
│ SWAP SPACE MANAGEMENT │
├─────────────────────────────────────────────────────────────────┤
│ │
│ Physical Memory Swap Space (Disk) │
│ ┌─────────────┐ ┌─────────────┐ │
│ │ Page Frame │ │ Swap Page │ │
│ │ 0x1000 │ ◄────────►│ 0x0 │ │
│ ├─────────────┤ page │ (swap0) │ │
│ │ Page Frame │ fault │ │ │
│ │ 0x2000 │ ─────────►│ Swap Page │ │
│ ├─────────────┤ │ 0x1000 │ │
│ │ Page Frame │ │ (swap0) │ │
│ │ 0x3000 │ │ │ │
│ ├─────────────┤ ├─────────────┤ │
│ │ ... │ │ swap1 │ │
│ └─────────────┘ └─────────────┘ │
│ │
│ Swap Usage Patterns: │
│ • Linux: swappiness parameter controls tendency to swap │
│ • High swappiness (100): Swap aggressively │
│ • Low swappiness (10): Prefer RAM, swap only when necessary │
│ │
│ Commands: │
│ • swapon / swapoff - Enable/disable swap │
│ • swapon -s - Show swap usage │
│ • free -m - Show memory and swap │
│ │
└─────────────────────────────────────────────────────────────────┘
Memory Allocation
User-Space Allocation
// Memory allocation in C
#include <stdlib.h>
#include <stdio.h>
int main() {
// Stack allocation (automatic)
int stack_var = 42;
// Dynamic allocation (heap)
int *heap_var = malloc(sizeof(int));
if (heap_var == NULL) {
fprintf(stderr, "Allocation failed\n");
return 1;
}
*heap_var = 42;
// Allocating arrays
int *array = malloc(10 * sizeof(int));
// Allocating zeroed memory
int *zeroed = calloc(10, sizeof(int));
// Resizing allocated memory
int *resized = realloc(array, 20 * sizeof(int));
// Always free!
free(heap_var);
free(zeroed);
free(resized);
return 0;
}
# Memory allocation in Python
import gc
# Python manages memory automatically
# But understanding helps avoid issues
# Memory allocation
data = [] # Empty list (small overhead)
# Grow as needed
for i in range(1000):
data.append(i)
# Explicit garbage collection
gc.collect()
# Check memory usage
import sys
print(f"Size of list: {sys.getsizeof(data)} bytes")
# Object references
a = [1, 2, 3]
b = a # Same object
c = a.copy() # Different object
# Memory view
print(f"a is b: {a is b}") # True - same reference
print(f"a is c: {a is c}") # False - different object
Conclusion
Memory management is fundamental to operating system design. The key concepts we’ve covered:
- Virtual memory provides each process with its own address space, enabling protection, relocation, and efficient memory usage
- Paging divides memory into fixed-size pages, simplifying allocation and enabling demand loading
- Page tables map virtual pages to physical frames, with multi-level structures handling large address spaces efficiently
- TLB caches translations for fast access, achieving 99%+ hit rates in practice
- Page replacement algorithms (LRU, Clock, etc.) decide which pages to evict when memory is full
- Swap extends available memory using disk, but should be minimized for performance
Modern OSes combine all these techniques: segmented paging with TLB, working set algorithms, and sophisticated swapping policies.
External Resources
Books
- “Operating System Concepts” - Silberschatz, Galvin, Gagne
- “Understanding the Linux Kernel” - Bovet & Cesati
- “Computer Systems: A Programmer’s Perspective” - Bryant & O’Hallaron
Comments