Memory Management: Contiguous Allocation and Paging Architecture

Memory management is a core operating system responsibility that orchestrates how multiple concurrent processes share the physical RAM without interfering with one another. It ensures isolation, speed, protection, and efficient allocation and deallocation of memory resources.

1. Why Do We Need Memory Management?

Modern computer systems execute multiple processes simultaneously. If processes could access or overwrite each other's memory spaces arbitrarily, data corruption, security breaches, and unpredictable crashes would occur.

• Process Isolation: Ensures that Process A cannot read or write into the memory space allocated to Process B.
• Resource Optimization: Manages limited physical RAM efficiently so that high-priority tasks execute quickly.
• Allocation and Deallocation: Dynamically assigns memory blocks when programs launch and reclaims them safely when programs terminate.

2. Core Mental Model: The Memory Hierarchy

Memory in a computer system is organized into a hierarchical pyramid. As you move from top to bottom, storage components change drastically in speed, size, and cost per gigabyte.

Real-Life Analogy

Think of memory hierarchy like office storage:

• Registers are like the notes written directly on your hand (instantly accessible, extremely tiny capacity).
• Cache is like the post-it notes on your desk monitor.
• RAM is your main physical desk where active work folders lie.
• Secondary Storage (SSD/HDD) is your filing cabinet down the hall.
• Network Storage is a warehouse across town.

3. Address Binding: From Source Code to Physical RAM

Before a program executes, its symbolic addresses (variable names, function labels) must be mapped to physical addresses in hardware. This transition occurs in three distinct phases:

1. Compile Time: If the compiler knows beforehand exactly where the process will reside in memory, it generates absolute code containing physical addresses. If the starting location changes, recompilation is required.
2. Load Time: If the exact memory location is unknown at compile time, the compiler generates relocatable code. The final binding is delayed until the program is loaded into main memory.
3. Execution Time (Run Time): If the process can be migrated from one memory segment to another during execution, binding is delayed until run-time. Hardware support (such as base and limit registers or a Memory Management Unit) is required.

4. Logical vs. Physical Address Space

A fundamental distinction in operating systems separates what the CPU sees from what the physical RAM holds:

• Logical Address (Virtual Address): Generated by the CPU. This is the virtual address space that the user process believes it occupies.
• Physical Address: The actual hardware address resident on the RAM memory chip.

The Memory Management Unit (MMU) is a hardware component that performs run-time mapping, translating logical CPU addresses into their corresponding physical RAM addresses.

5. Contiguous Memory Allocation: Fixed vs. Dynamic Partitioning

Contiguous allocation requires each process to be placed in a single, unbroken block of physical memory.

Fixed Partitioning (Static Partitioning)

• RAM is divided into static, predefined partitions at system startup.
• Analogy: Cutting a large cake into fixed equal slices beforehand. If a small child eats a slice, they might leave half behind, causing waste.
• Limitation: If a process is larger than the partition, it cannot run. If it is smaller, internal space is wasted.

Dynamic Partitioning

• Partitions are dynamically created and sized according to the exact requirements of incoming processes.
• Memory allocation forms a flexible layout where free holes are scattered across RAM.

6. Fragmentation: Internal vs. External

As dynamic allocation and deallocation proceed, memory becomes fractured, leading to fragmentation issues.

• Internal Fragmentation: Occurs inside an allocated partition. If a partition is allocated $4\text{ KB}$ to a process that only needs $3\text{ KB}$, the remaining $1\text{ KB}$ inside that block goes unused and wasted.
• External Fragmentation: Occurs outside allocated partitions. Total free memory across the system is sufficient to satisfy a request, but it is split into non-contiguous scattered blocks, making it impossible to seat a large contiguous process.

Note: External fragmentation is notoriously expensive and disruptive in operating systems, often requiring compaction techniques to shuffle memory blocks together.

7. Memory Allocation Strategies

When a process requests memory in a dynamic partition scheme, the operating system uses specific placement algorithms:

8. Paging Architecture

Paging eliminates the need for contiguous allocation by breaking physical and logical memory into fixed-size blocks.

• Pages: Logical memory is broken into fixed-size blocks called pages.
• Frames: Physical memory (RAM) is broken into fixed-size blocks of the exact same size called frames.

The Page Table

The operating system maintains a Page Table for each process. The page table acts as the translation dictionary, mapping every logical page number to its corresponding physical frame number in RAM.

Address translation uses two components:

• Page Number ($p$): Used as an index into the page table.
• Page Offset ($d$): Combined with the base address of the physical frame to define the exact physical memory location.

9. Advanced Paging: Multi-Level Paging and Inverted Page Tables

As systems grew to support 64-bit architectures and massive address spaces, traditional single-level page tables became too large to fit inside contiguous memory.

• Multi-Level Paging: Breaks the page table itself into smaller, tree-structured hierarchical pages. If a portion of the address space is unused, entire intermediate page table branches can be omitted, saving significant memory.
• Inverted Page Table: Instead of maintaining one page table entry per logical page for every process, an inverted page table maintains one entry per physical frame currently in RAM. This globally tracks which process and page currently occupy each physical frame, drastically reducing memory overhead for systems with immense logical address spaces.

10. Summary and Key Takeaways

• Memory hierarchy ranges from fast, expensive, volatile CPU registers down to slow, cheap secondary storage and network volumes.
• Address binding transitions symbolic code through compile time, load time, and execution time.
• Logical addresses are generated by the CPU, while physical addresses point to actual hardware locations in RAM via the MMU.
• Fixed partitioning suffers from internal waste, whereas dynamic partitioning introduces external fragmentation as processes enter and leave.
• Allocation strategies like First Fit, Best Fit, Worst Fit, and Next Fit dictate how free memory blocks are selected.
• Paging solves contiguous allocation constraints by dividing logical memory into pages and physical memory into frames.
• Page tables map logical pages to physical frames, managed via hardware MMU lookups.
• Multi-level paging and inverted page tables optimize memory consumption for modern large-scale systems.