Memory Management

Memory management is a crucial function of the operating system that handles the allocation, tracking, and management of computer memory.

Overview

Memory management is responsible for:

Allocating memory to processes when needed
Deallocating memory when no longer needed
Keeping track of memory usage
Managing swapping between main memory and disk
Protecting memory spaces of different processes

Memory Hierarchy

         ┌─────────────────────┐
         │     Registers       │  ← Fastest, Smallest, Most Expensive
         ├─────────────────────┤
         │       Cache         │
         │   (L1, L2, L3)      │
         ├─────────────────────┤
         │    Main Memory      │
         │       (RAM)         │
         ├─────────────────────┤
         │   Secondary Storage │
         │   (SSD/HDD)         │
         ├─────────────────────┤
         │   Tertiary Storage  │  ← Slowest, Largest, Cheapest
         │   (Tape, Cloud)     │
         └─────────────────────┘

Address Binding

The process of associating program instructions and data to physical memory addresses.

Binding Times

Stage	Description	Flexibility
Compile Time	Absolute addresses generated	Must recompile if location changes
Load Time	Relocatable code, addresses generated at loading	Can load anywhere, but fixed after loading
Execution Time	Addresses generated at runtime	Allows process to move in memory

Logical vs Physical Address

Logical Address	Physical Address
Generated by CPU	Actual memory location
Also called virtual address	Address seen by memory unit
Seen by user program	User never sees this
Range: 0 to max	Mapped from logical address

Memory Management Unit (MMU)

Hardware device that maps virtual to physical addresses
Contains relocation register (base register)
Physical Address = Logical Address + Relocation Register

Memory Allocation Strategies

Contiguous Allocation

Memory is allocated in contiguous blocks.

Fixed (Static) Partitioning

Memory divided into fixed-size partitions
Each partition holds exactly one process
Internal Fragmentation: Wasted space within partition

Variable (Dynamic) Partitioning

Partitions created dynamically based on process size
No internal fragmentation
External Fragmentation: Free memory scattered in small pieces

Allocation Algorithms

Algorithm	Description	Pros	Cons
First Fit	Allocate first hole that fits	Fast	Fragments memory at front
Best Fit	Allocate smallest hole that fits	Minimizes wasted space	Leaves tiny holes, slow
Worst Fit	Allocate largest hole	Leaves larger remaining holes	Poor memory utilization
Next Fit	Like first fit, but starts from last allocation	Distributes allocation	May fragment uniformly

Fragmentation

Internal Fragmentation

Wasted space inside allocated partition
Occurs in fixed partitioning
Memory allocated is larger than needed

Example:

Partition size: 10 KB
Process size: 8 KB
Internal fragmentation: 2 KB

External Fragmentation

Wasted space outside allocated partitions
Free memory exists but not contiguous
Cannot allocate to process even if total free > required

Solutions:

Compaction: Move processes to create large contiguous block (expensive)
Paging: Non-contiguous allocation
Segmentation: Logical division of address space

Paging

Paging allows non-contiguous memory allocation, eliminating external fragmentation.

Concepts

Physical Memory → Divided into Frames (fixed size)
Logical Memory → Divided into Pages (same size as frames)
Page size = Frame size (typically 4 KB)

Address Translation

Logical Address consists of:

Page Number (p) - Index into page table
Page Offset (d) - Offset within the page

Logical Address: [ Page Number | Page Offset ]
                       ↓
                 Page Table
                       ↓
Physical Address: [ Frame Number | Frame Offset ]

Page Table

Maps page number to frame number
One page table per process
Stored in main memory
Page Table Base Register (PTBR) points to page table

Calculations

Number of pages = Logical address space / Page size
Number of frames = Physical memory / Frame size

Bits for page offset = log₂(Page size)
Bits for page number = log₂(Number of pages)

Example:

Logical address space: 2^16 bytes (64 KB)
Page size: 2^12 bytes (4 KB)
Physical memory: 2^15 bytes (32 KB)

Solution:

Number of pages = 2^16 / 2^12 = 16 pages
Number of frames = 2^15 / 2^12 = 8 frames
Page number bits = 4, Offset bits = 12

Translation Lookaside Buffer (TLB)

High-speed cache for page table entries
Reduces memory access time
Associative memory (parallel search)

TLB Working

CPU generates logical address
Check TLB for page number
- TLB Hit: Get frame number directly
- TLB Miss: Access page table in memory

Effective Access Time (EAT)

EAT = (TLB Hit Ratio × TLB Access Time) + (TLB Miss Ratio × (TLB + Memory + Memory))

Example:

TLB access time: 10 ns
Memory access time: 100 ns
Hit ratio: 90%

EAT = 0.9 × (10 + 100) + 0.1 × (10 + 100 + 100)
EAT = 0.9 × 110 + 0.1 × 210
EAT = 99 + 21 = 120 ns

Multi-Level Paging

For large address spaces, single-level page table becomes too large.

Two-Level Paging

Logical Address: [ Outer Page # | Inner Page # | Page Offset ]
                       ↓               ↓
                 Outer Page       Inner Page
                   Table            Table
                                      ↓
                               Frame Number

Advantage: Only load needed page tables into memory

Example

32-bit logical address
Page size: 4 KB (12 bits offset)
20 bits for page number
Two-level: 10 bits outer, 10 bits inner

Inverted Page Table

One entry per physical frame (instead of per logical page)
Reduces memory usage
Slower lookup (must search entire table)
Solution: Hash table for faster search

Segmentation

Segmentation divides memory based on logical divisions of a program.

Segments

Segment	Contents
Code	Program instructions
Data	Global variables
Stack	Local variables, function calls
Heap	Dynamic allocation

Segment Table

Each entry contains:

Base: Starting address of segment
Limit: Length of segment

Address Translation

Logical Address: [ Segment Number | Offset ]
                        ↓
                  Segment Table
                   [Base, Limit]
                        ↓
Physical Address = Base + Offset (if Offset < Limit)

Segmentation with Paging

Combines benefits of both:

Logical division (segmentation)
No external fragmentation (paging)

Intel x86 uses this approach

Comparison: Paging vs Segmentation

Aspect	Paging	Segmentation
Division	Fixed-size pages	Variable-size segments
View	Physical view	Logical view
Fragmentation	Internal	External
Sharing	Difficult	Easy (share segments)
Protection	Page level	Segment level
User Awareness	Invisible to user	Visible to user

Memory Protection

Protection Bits

Valid-Invalid Bit: Indicates if page is valid
Read/Write/Execute Bits: Access permissions
User/Supervisor Bit: Privilege level

Shared Pages

Multiple processes share same physical frames
Used for: Shared libraries, code sharing
Only one copy of shared code in memory

Important Interview Questions

Q1: What is the difference between internal and external fragmentation?

A: Internal fragmentation is wasted space within allocated blocks (fixed partitioning). External fragmentation is free memory scattered across multiple non-contiguous locations (variable partitioning).

Q2: What is the purpose of TLB?

A: TLB is a fast cache that stores recent page table entries, reducing the number of memory accesses needed for address translation from 2 to 1 on a TLB hit.

Q3: Why is paging preferred over contiguous allocation?

A: Paging eliminates external fragmentation, allows non-contiguous allocation, easier memory management, and better memory utilization.

Q4: What is the page fault?

A: A page fault occurs when a process tries to access a page not currently in main memory. The OS must load the page from secondary storage.

Q5: How does multi-level paging save memory?

A: Multi-level paging only keeps the outer page table in memory, loading inner page tables on demand, reducing memory overhead for sparse address spaces.

Quick Reference

Term	Formula/Definition
Physical Address	Logical Address + Base Register
Page Number	Logical Address / Page Size
Page Offset	Logical Address % Page Size
EAT (with TLB)	Hit × (t_tlb + t_mem) + Miss × (t_tlb + 2×t_mem)
Page Table Size	Number of Pages × Entry Size