Memory Management & Virtual Memory

Address Space Virtualization

Virtual Memory provides process isolation by mapping contiguous Virtual Addresses used by software to non-contiguous Physical RAM Frames via the hardware Memory Management Unit (MMU).

Memory Management Unit (MMU):

• Translates virtual address tuple (Page Number, Offset) into physical address tuple (Frame Number, Offset).
• Enforces page protection bits (Read, Write, Execute, User/Kernel Mode).
• Triggers a Page Fault exception when a virtual page isn't present in physical memory.

# Linux mmap Virtual Memory Allocation Example
#include <sys/mman.h>
#include <stdio.h>

int main() {
    // Requesting 4KB virtual page allocation from kernel
    void *ptr = mmap(NULL, 4096, PROT_READ | PROT_WRITE, MAP_PRIVATE | MAP_ANONYMOUS, -1, 0);
    printf("Allocated Virtual Address: %p\n", ptr);
    munmap(ptr, 4096);
    return 0;
}

Page Tables & Cache Acceleration

Paging splits virtual address spaces into fixed-size blocks (typically 4 KB).

Key Components:

• Page Table Entry (PTE): Stores Frame Number, Present Bit ($P$), Dirty Bit ($D$), and Access Permissions.
• Translation Lookaside Buffer (TLB): A high-speed associative hardware cache inside the CPU that caches recent Virtual-to-Physical translations, achieving $O(1)$ hit times.
• Hierarchical (4-Level) Paging: Maps large 64-bit address spaces using sparse page directories (PML4 \to PDPT \to PD \to PT), saving physical memory.

// Effective Memory Access Time (EMAT) Calculation
// EMAT = (TLB_Hit_Rate * TLB_Access_Time) + (TLB_Miss_Rate * (TLB_Access_Time + Memory_Access_Time * Page_Table_Levels))
double compute_emat(double hit_rate, double tlb_time, double mem_time, int levels) {
    return (hit_rate * tlb_time) + ((1.0 - hit_rate) * (tlb_time + (levels + 1) * mem_time));
}

Memory Allocation Algorithms

Variable allocation strategies allocate contiguous memory segments to requesting processes:

Allocation Heuristics:

• First Fit: Allocates the first free hole that is large enough. Fast search time.
• Best Fit: Allocates the smallest free hole that is large enough. Leaves behind tiny unusable holes (High External Fragmentation).
• Worst Fit: Allocates the largest free hole available. Leaves large residual holes.

Compaction & Defragmentation:

External fragmentation is resolved by shifting active processes in physical RAM to coalesce contiguous free memory space into a single block.

// C Buddy Allocator Concept
void* buddy_malloc(size_t size) {
    // Splits power-of-two memory blocks recursively
    return NULL;
}

Handling Page Faults & RAM Eviction

When physical RAM is full during a Page Fault, the OS page replacement algorithm selects a victim page to evict to swap disk:

Replacement Algorithms:

• First-In-First-Out (FIFO): Evicts the oldest loaded page. Suffers from Belady's Anomaly (increasing frame count can increase page fault rate).
• Least Recently Used (LRU): Evicts the page that hasn't been accessed for the longest time (Optimal practical approximation).
• Clock (Second Chance) Algorithm: Uses a circular queue and a reference bit to approximate LRU with low overhead ($O(1)$).

# LRU Cache Page Replacement Simulation in Python
class LRUCache:
    def __init__(self, capacity: int):
        self.cap = capacity
        self.cache = {} # OrderedDict for O(1) eviction
        
    def get(self, page_id: int) -> int:
        if page_id not in self.cache:
            return -1
        val = self.cache.pop(page_id)
        self.cache[page_id] = val
        return val

Over-Commitment & System Thrashing

Thrashing occurs when a system spends more time servicing page faults than executing instructions.

Causes & Mitigations:

• Occurs when total memory required by active processes exceeds total available physical RAM.
• Working Set Model: Tracks the set of pages accessed by a process in the last $\Delta$ time units. If total Working Set size $> \text{RAM capacity}$, the OS suspends lower-priority processes to prevent thrashing.

# Checking Linux Swap & Memory Pressure Signals
free -h
vmstat 1 5
cat /proc/sys/vm/swappiness