Memory Management

Memory Hierarchy (fastest to slowest):

┌─────────────────┐  Fastest, Most Expensive
│    Registers    │  (bytes)
├─────────────────┤
│      Cache      │  (KB-MB)
├─────────────────┤
│   Main Memory   │  (GB) - RAM
├─────────────────┤
│  Secondary      │  (TB) - SSD/HDD
│  Storage        │
└─────────────────┘  Slowest, Cheapest

Why Memory Management? • Multiple processes need memory simultaneously • Protect processes from each other • Share memory efficiently • Handle more programs than physical memory allows

Address Types: • Logical/Virtual Address: Generated by CPU, used by program • Physical Address: Actual location in RAM • Memory Management Unit (MMU): Converts logical to physical

Memory Allocation Goals:

1. Maximum memory utilization
2. Fast access
3. Protection between processes
4. Support for multiprogramming

Each process gets a contiguous block of memory.

Fixed Partitioning:

┌────────────────────┐
│   OS (fixed)       │
├────────────────────┤
│ Partition 1 (4KB)  │
├────────────────────┤
│ Partition 2 (8KB)  │
├────────────────────┤
│ Partition 3 (16KB) │
└────────────────────┘

• Simple but inflexible • Internal Fragmentation: Wasted space within partition

Variable Partitioning: • Partitions created as needed • No internal fragmentation • External Fragmentation: Scattered free spaces

Allocation Strategies:

Fragmentation:

External Fragmentation:
┌────┐ ┌────┐ ┌────┐
│ P1 │ │Free│ │ P2 │  Total free = 20KB but not contiguous
└────┘ └────┘ └────┘  Can't fit 15KB process!

Solution: Compaction
┌────┐ ┌────┐ ┌───────────────────┐
│ P1 │ │ P2 │ │   Free (20KB)     │
└────┘ └────┘ └───────────────────┘

Paging divides memory into fixed-size blocks to eliminate external fragmentation.

Key Terms: • Page: Fixed-size block in logical memory • Frame: Fixed-size block in physical memory • Page Table: Maps pages to frames

How Paging Works:

Logical Address Space        Physical Memory
┌──────────────┐            ┌──────────────┐
│   Page 0     │ ──────────►│   Frame 5    │
├──────────────┤            ├──────────────┤
│   Page 1     │ ──────────►│   Frame 2    │
├──────────────┤            ├──────────────┤
│   Page 2     │ ──────────►│   Frame 8    │
└──────────────┘            └──────────────┘

Page Table:
Page 0 → Frame 5
Page 1 → Frame 2
Page 2 → Frame 8

Address Translation:

Logical Address = Page Number + Page Offset

If page size = 4KB (2^12):
Address 8196 = 0010 | 0000 0000 0100
               ────   ──────────────
              Page 2   Offset 4

Physical Address = (Frame Number × Page Size) + Offset

Page Table Entry (PTE) Contains: • Frame number • Valid/Invalid bit • Protection bits (R/W/X) • Dirty bit (modified) • Reference bit (accessed)

Multi-Level Paging: • Page table itself can be large • Use page table for page table • Example: 2-level paging

Page Directory → Page Table → Frame

Translation Lookaside Buffer (TLB): • Cache for page table entries • If TLB hit: 1 memory access • If TLB miss: 2+ memory accesses • TLB is small (64-1024 entries) but fast

Segmentation divides memory into logical segments of variable size.

Segments represent logical units: • Code segment • Data segment • Stack segment • Heap segment

Logical Address:

Logical Address = <Segment Number, Offset>

Segment Table:
┌─────────┬─────────┬────────┐
│ Segment │  Base   │  Limit │
├─────────┼─────────┼────────┤
│    0    │  1400   │   400  │  (Code)
│    1    │  6300   │  1100  │  (Data)
│    2    │  4300   │  1000  │  (Stack)
└─────────┴─────────┴────────┘

Address <1, 500>:
1. Check: 500 < 1100 (limit)? Yes ✓
2. Physical = 6300 + 500 = 6800

Paging vs Segmentation:

Segmentation with Paging (Intel x86):

Logical → Segment Table → Linear → Page Table → Physical
         (Segmentation)         (Paging)

• Combines benefits of both • Segment for logical division • Paging for memory management

Virtual Memory allows executing programs larger than physical memory.

Key Concept: • Not all program needs to be in memory • Load pages only when needed (demand paging) • Use disk as extension of RAM

Benefits: • Run programs larger than RAM • More processes in memory (better multiprogramming) • Less I/O for loading programs • Memory isolation between processes

Demand Paging:

1. Process references a page
2. If page in memory → access it
3. If page not in memory → PAGE FAULT
   a. OS finds page on disk
   b. Loads page into free frame
   c. Updates page table
   d. Restarts instruction

Page Fault Handling:

                           ┌─────────────┐
Reference ──► Page Table ──►│ Valid = 0   │──► PAGE FAULT
                           └─────────────┘
                                  │
                                  ▼
                           ┌─────────────┐
                           │   Trap to   │
                           │     OS      │
                           └──────┬──────┘
                                  │
                    ┌─────────────┴─────────────┐
                    │                           │
              Free frame?                 No free frame
                    │                           │
            Load from disk           Page Replacement
                    │                           │
                    └─────────────┬─────────────┘
                                  │
                           Update page table
                                  │
                           Restart instruction

Copy-on-Write: • Parent and child initially share pages • When either writes, copy that page • Saves memory for fork()

When memory is full and new page needed, which page to replace?

Goal: Minimize page faults

1. FIFO (First In First Out) • Replace oldest page • Simple but poor performance • Belady's Anomaly: More frames can cause more faults!

2. Optimal (OPT) • Replace page not used for longest time in future • Best possible but requires future knowledge • Used for comparison (theoretical)

3. LRU (Least Recently Used) • Replace page not used for longest time in past • Good performance, approximates OPT • Implementation: Counter or Stack

4. LRU Approximation - Clock (Second Chance)

           ┌───► Frame 0 (R=1) ──► Frame 1 (R=0) ──┐
           │                                       │
           │     Hand points to next victim        │
           │                                       │
           └── Frame 3 (R=1) ◄── Frame 2 (R=1) ◄──┘

When replacing:
1. If R=0: Replace this page
2. If R=1: Set R=0, move to next
3. Keep going in circle

Example (3 frames):

Reference: 7 0 1 2 0 3 0 4

FIFO:
7 0 1 → 2 replaces 7 → 2 0 1 → 3 replaces 0 → 2 3 1 → 0 replaces 1 → ...
Page Faults: 6

LRU:
7 0 1 → 2 replaces 7 → 2 0 1 → 3 replaces 1 → 2 0 3 → ...
Page Faults: 5

Thrashing: • Too many processes, not enough frames • Constant page faults • CPU utilization drops • Solution: Reduce multiprogramming, working set model

Thrashing: System spends more time paging than executing.

Cause:

More processes → Less frames each → More page faults
→ More I/O wait → CPU idle → OS adds more processes
→ Even less frames → THRASHING!

Graph:

CPU
Util.│           ****
     │         **    *
     │       **       *
     │     **          *
     │   **             ****
     │ **                   Thrashing
     │**
     └───────────────────────────
        Degree of Multiprogramming

Working Set Model: • Working Set = Pages used in recent Δ time • Give each process its working set size • If sum of working sets > available frames, suspend a process

Page Fault Frequency (PFF):

Page
Fault│
Rate │    Upper Limit ─────────────────
     │              *
     │            *
     │          *
     │    Lower Limit ─────────────────
     │  *
     └───────────────────────────────
        Frames Allocated

- Above upper: Give more frames
- Below lower: Take frames away

Solutions to Thrashing:

1. Use working set model
2. Page fault frequency control
3. Reduce degree of multiprogramming
4. Add more RAM
5. Use local replacement (process only replaces its own pages)