Memory Management

This lesson covers how the operating system manages main memory in depth — paging, segmentation, virtual memory and disk thrashing — and shows how a logical address is translated into a physical one. It also weighs the cost and benefit of virtual memory.

---

Spec Mapping

This lesson develops OCR H446 section 1.2.1 (Operating Systems), specifically the OS's role in memory management. It requires you to explain paging and segmentation, how the OS maps logical (virtual) addresses to physical addresses, the operation and trade-offs of virtual memory, and how excessive paging leads to disk thrashing. It builds on the overview given in the Operating System Functions lesson and connects forward to secondary storage (the swap/page file lives on disk) and to the fetch–decode–execute cycle (every instruction fetch generates an address that must be translated).

---

Why Memory Management Matters

The OS must:

• Allocate memory to each process so it has space for its code, data and stack.
• Protect each process's memory from being accessed by other processes.
• Optimise memory usage so that as many processes as possible can run simultaneously.
• Handle situations where the total memory required by all running processes exceeds the physical RAM.

To do all this, the OS gives each process its own logical (virtual) address space — a private, contiguous-looking range of addresses starting at zero — and quietly maps those logical addresses onto wherever the data actually lives in physical RAM. The process never sees the physical addresses, which is what makes protection and flexible placement possible. Translating logical to physical addresses, transparently and fast, is the central problem of this lesson.

---

Paging

How Paging Works

The OS divides virtual memory (the logical address space seen by each process) into fixed-size blocks called pages and divides physical RAM into fixed-size blocks of the same size called frames (commonly 4 KB each). Because pages and frames are identical in size, any page can go in any free frame.

Virtual page (Process A)	Mapped to physical frame
Page 0	Frame 1
Page 1	Frame 3
Page 2	Frame 2

Physical frame	Contents
Frame 0	Process B, Page 1
Frame 1	Process A, Page 0
Frame 2	Process A, Page 2
Frame 3	Process A, Page 1
Frame 4	(free)

Process A's pages do not need to be contiguous in physical RAM — the page table records the mapping. From Process A's point of view its memory is one continuous block (pages 0, 1, 2 in order); in reality those pages are scattered across frames 1, 3 and 2, and Process B's page sits in between.

Page Table

Each process has its own page table that maps virtual page numbers to physical frame numbers.

Virtual Page	Physical Frame	Valid Bit	Dirty Bit
0	1	1	0
1	3	1	1
2	2	1	0
3	-	0	0

• Valid bit (present bit): 1 if the page is currently in RAM; 0 if it is not (it has been swapped to disk or never loaded).
• Dirty bit: 1 if the page has been modified since it was loaded; this tells the OS the page must be written back to disk before its frame can be reused.

Logical-to-Physical Address Translation

This is the heart of paging. A logical address generated by the CPU is split into two parts:

• the high bits are the page number (which page within the process), and
• the low bits are the offset (how far into the page the byte is).

The page number indexes the page table to find the frame number; the offset is then simply copied across unchanged, because pages and frames are the same size. The frame number combined with the original offset is the physical address.

flowchart LR
    LA["Logical address<br/>page number | offset"]
    LA -->|page number| PT["Page table<br/>(indexed by page no.)"]
    LA -->|offset unchanged| OFF["offset"]
    PT -->|frame number| FN["frame number"]
    FN --> PA["Physical address<br/>frame number | offset"]
    OFF --> PA
    PT -. "valid bit = 0" .-> PF["Page fault →<br/>load page from disk"]

Worked Example — Translating an Address

Suppose the page size is 256 bytes, so the offset is 8 bits (because $2^{8} = 256$28=256). The CPU issues the 16-bit logical address 0000 0001 0100 0000.

Step 1 — split the address. The low 8 bits are the offset; the rest is the page number.

$\text{page number} = 00000001_2 = 1 \qquad \text{offset} = 01000000_2 = 64$page number=000000012​=1offset=010000002​=64

Step 2 — look up the page in the page table. From the table above, page 1 → frame 3, and the valid bit is 1, so the page is in RAM.

Step 3 — form the physical address. Keep the offset (64) and combine it with frame 3:

$\text{physical address} = (\text{frame} \times \text{page size}) + \text{offset} = (3 \times 256) + 64 = 832$physical address=(frame×page size)+offset=(3×256)+64=832

So logical address 320 (which is $1 \times 256 + 64$1×256+64) maps to physical address 832. Notice the offset never changes — only the page/frame number is translated. If instead we had asked for page 3 (valid bit = 0), the lookup would fail and the MMU would raise a page fault, triggering the virtual-memory machinery described later.

The Memory Management Unit (MMU)

The translation above happens in hardware, in the Memory Management Unit (MMU) — a component (today usually on the CPU) that performs the page-table lookup on every memory access. Doing this lookup for every instruction would be ruinously slow if it always meant a second trip to RAM, which is why the TLB exists.

Translation Lookaside Buffer (TLB)

The TLB is a small, very fast cache inside the MMU that stores the most recently used page-to-frame mappings. On each access the MMU checks the TLB first:

• TLB hit — the mapping is found instantly; no page-table access needed.
• TLB miss — the MMU must read the page table in RAM (slower), then caches the result in the TLB.

Because programs exhibit locality of reference (they keep using the same handful of pages), the TLB hit rate is usually very high, so the average translation cost is close to a single fast cache lookup. This is the same locality principle that makes CPU caches effective.

Advantages of Paging

Advantage	Explanation
No external fragmentation	Pages can be placed in any free frame; they do not need to be contiguous
Simple allocation	The OS just needs to find any free frame
Effective virtual memory	Pages not currently needed can be stored on disk
Memory protection	Each process has its own page table; it cannot access another process's frames

Disadvantages of Paging

Disadvantage	Explanation
Internal fragmentation	The last page of a process may not be completely full, wasting space within the frame
Page table overhead	Each process needs its own page table, which uses memory. For large address spaces, page tables can be very large
Translation overhead	Every memory access requires a page table lookup (mitigated by the TLB)

Internal fragmentation worked example: a process needing 9 KB with a 4 KB page size requires 3 pages (12 KB allocated). The third page holds only 1 KB of real data, so 3 KB inside that frame is wasted — that waste inside an allocated block is internal fragmentation, and it is the price paging pays for never having external fragmentation.

---

Segmentation

How Segmentation Works

Instead of dividing memory into fixed-size pages, segmentation divides it into variable-size segments based on the logical structure of the program.

Segment	Typical Content
Code segment	The program's instructions
Data segment	Global and static variables
Stack segment	Function call frames, local variables, return addresses
Heap segment	Dynamically allocated memory

Each segment has:

• A base address (where the segment starts in physical memory).
• A limit (the length of the segment).

Segment Table

Segment	Base Address	Limit
Code	0x1000	4096
Data	0x3000	2048
Stack	0x5000	1024

Worked Segmentation Translation

A segmented logical address is a pair: a segment number and an offset within that segment. Translation adds the offset to the segment's base address — but first the OS checks the offset against the segment's limit, which is how segmentation enforces protection.

Suppose a program issues the logical address (segment = Data, offset = 100). From the table the Data segment has base 0x3000 and limit 2048:

$\text{check: } 100 < 2048 \;\checkmark \qquad \text{physical address} = 0x3000 + 100 = 0x3064$check: 100<2048✓physical address=0x3000+100=0x3064

If instead the offset were 5000, the check $5000 < 2048$5000<2048 fails, so the hardware raises a protection fault and the access is denied — a process cannot read past the end of its own segment, nor into a neighbouring one. Contrast this with paging: there, the offset cannot exceed the page size by construction, so no explicit limit check is needed. Segmentation must check because segments vary in size; paging gets the same protection "for free" from fixed-size pages.

Advantages of Segmentation

Advantage	Explanation
Matches program structure	Each segment corresponds to a logical unit (code, data, stack) — intuitive for programmers and compilers
No internal fragmentation	Segments are exactly the size needed
Sharing and protection	Individual segments can have different access permissions (e.g. code segment can be read-only and shared between processes)

Disadvantages of Segmentation

Disadvantage	Explanation
External fragmentation	As segments are created and destroyed, gaps of unusable free memory appear between them
Complex allocation	The OS must find a contiguous block of free memory large enough for each segment
Variable size management	More complex than paging because segments differ in size

---

Paging vs Segmentation Comparison

Feature	Paging	Segmentation
Division basis	Physical (fixed-size blocks)	Logical (variable-size program sections)
Block size	Fixed (e.g. 4 KB)	Variable
External fragmentation	None	Yes
Internal fragmentation	Yes (last page)	None
Programmer visibility	Invisible to the programmer	Reflects program structure
Address translation	Page table	Segment table
Sharing	Page-level sharing (less intuitive)	Segment-level sharing (natural for code sharing)

Combined Paging and Segmentation

Many modern systems use segmented paging — the address space is first divided into segments, and then each segment is divided into pages. This combines the logical structure of segmentation with the efficient memory management of paging.

---

Virtual Memory

Virtual memory allows processes to use more memory than the physical RAM available by storing inactive pages on secondary storage (the swap file or page file). It is the pay-off of paging: because the page table can mark a page as not present (valid bit = 0), a process can have far more logical pages than there are physical frames, and the OS keeps only the actively-used pages in RAM.

How Virtual Memory Works

1. The OS allocates a virtual address space to each process that may be larger than physical RAM.
2. Only the pages currently being used are kept in RAM.
3. Pages that are not currently needed are stored on disk in the swap file.
4. When a process accesses a page that is not in RAM, a page fault occurs: a. The OS finds the page on disk. b. If RAM is full, the OS selects a page to evict (swap out) using a page replacement algorithm. c. If the evicted page has been modified (dirty bit = 1), it is written back to disk. d. The required page is loaded into the freed frame. e. The page table is updated and the process resumes.

Page Replacement Algorithms

When RAM is full and a new page must be loaded, the OS must decide which existing page to evict. This decision is made by a page replacement algorithm.

First In, First Out (FIFO)

Aspect	Detail
Rule	Evict the page that has been in RAM the longest
Implementation	Maintain a queue of pages in the order they were loaded. Remove from the front
Advantage	Simple to implement
Disadvantage	Does not consider how often or how recently a page was used. May evict a frequently used page (Belady's anomaly — adding more frames can sometimes increase page faults with FIFO)

Least Recently Used (LRU)

Aspect	Detail
Rule	Evict the page that has not been accessed for the longest time
Implementation	Track the time of last access for each page. Evict the page with the oldest timestamp
Advantage	Good performance — recently used pages are likely to be used again (temporal locality)
Disadvantage	Expensive to implement — requires tracking access times for every memory reference

Clock Algorithm (Second Chance)

Aspect	Detail
Rule	A modified FIFO that gives each page a "second chance" before eviction
Implementation	Pages are arranged in a circular buffer with a pointer (the "clock hand"). Each page has a reference bit (set to 1 when accessed). When a page must be evicted, the hand moves around: if the reference bit is 1, set it to 0 and skip; if the reference bit is 0, evict that page
Advantage	Good approximation of LRU with lower overhead
Disadvantage	Slightly less accurate than true LRU

Worked Example — FIFO vs LRU

Consider 3 frames and the page reference string: 7, 0, 1, 2, 0, 3, 0, 4

FIFO: