CS Notes 📚

Virtual memory

Virtual memory is a memory management technique that allows programs to use a large logical address space even when the available physical memory (RAM) is limited.

Each process is given its own virtual address space. The addresses used by the program are virtual addresses and must be translated into physical addresses before accessing RAM.

This translation is performed by hardware with support from the operating system.

Virtual memory provides several important capabilities:

• Programs can use more memory than physically available
• Processes remain isolated from each other
• Memory protection becomes easier
• Physical memory can be used more efficiently

Virtual address space

Each process runs within its own virtual address space. From the program’s perspective, memory appears as a continuous range of addresses.

A typical process memory layout includes:

• Code segment containing program instructions
• Data segment containing global variables
• Heap used for dynamic memory allocation
• Stack used for function calls and local variables

Even though the virtual memory appears contiguous, the actual physical memory may be scattered across different frames in RAM.

Virtual vs physical addresses

Programs access memory using virtual addresses generated by the CPU. These addresses cannot directly reference RAM.

Instead, they must be translated into physical addresses, which represent the real locations in memory.

Definitions:

• Virtual address: address generated by the CPU
• Physical address: actual location in RAM
• Address translation: conversion of virtual addresses to physical addresses

This translation is handled by the Memory Management Unit (MMU).

Paging

Virtual memory systems typically use paging.

Memory is divided into fixed size blocks:

• Pages in virtual memory
• Frames in physical memory

A page from virtual memory can be placed into any available frame in RAM.

Paging allows the operating system to map virtual memory used by programs to physical memory locations without requiring contiguous allocation.

Page tables

A page table stores the mapping between virtual pages and physical frames.

Each process typically has its own page table.

A page table entry may include:

• Frame number
• Valid or invalid bit
• Protection bits
• Dirty bit indicating modification
• Reference bit indicating recent usage

Example mapping:

Virtual page → Physical frame

0 → 5
1 → 12
2 → 3

The operating system uses the page table to determine where each virtual page is stored in physical memory.

Address translation

When a program accesses memory, the following steps occur:

1. The CPU generates a virtual address
2. The MMU extracts the page number and offset
3. The page table is checked for the corresponding frame
4. The physical address is constructed
5. The data is accessed from RAM

If the required page is not currently in memory, a page fault occurs.

Translation Lookaside Buffer (TLB)

Consulting the page table for every memory access would be slow. To improve performance, systems use a Translation Lookaside Buffer (TLB).

The TLB is a small and fast cache that stores recently used address translations.

Operation:

• If the translation is found in the TLB, it is called a TLB hit
• If the translation is not found, it is a TLB miss, and the page table must be checked

This significantly speeds up address translation.

Demand paging

Demand paging loads pages into memory only when they are needed.

Instead of loading the entire program into RAM at the beginning, pages are loaded when the program first accesses them.

Steps:

1. The program attempts to access a page
2. The page is not present in memory
3. A page fault occurs
4. The operating system loads the page from disk
5. Execution continues

Demand paging allows systems to run programs larger than the available physical memory.

Page faults

A page fault occurs when a process accesses a page that is not currently present in physical memory.

Handling a page fault involves several steps:

1. Hardware detects the missing page
2. Control transfers to the operating system
3. The OS locates the required page on disk
4. The page is loaded into a free frame
5. The page table is updated
6. The interrupted instruction resumes execution

Page faults are expensive because disk access is significantly slower than RAM access.

Page replacement

If physical memory is full and a new page must be loaded, the operating system must remove an existing page.

This decision is made using page replacement algorithms.

Common algorithms include:

FIFO (First In First Out)

• Removes the page that entered memory first

LRU (Least Recently Used)

• Removes the page that has not been used for the longest time

Optimal replacement

• Removes the page that will not be used for the longest time in the future
• Used mainly for theoretical comparison

Thrashing

Thrashing occurs when the system spends more time swapping pages between disk and memory than executing programs.

Symptoms:

• Very high page fault rate
• Low CPU utilization
• Heavy disk activity

Thrashing typically occurs when too many processes compete for limited memory.

Possible solutions include reducing the number of active processes or increasing physical memory.