Mastering Memory Management: From Allocation to Virtual Memory & Page Replacement

1 Memory Management Concepts

Memory management is the operating system's division and dynamic allocation of memory.

Address space: Logical address space: relative addresses starting from 0. Physical address space: the final address after translation.

Program execution: Compilation: source code → object modules. Linking: object modules and libraries → a single loadable module, forming the process's logical address space.

Loading: Absolute loading: load address determined at compile time. Relocatable loading: program placed according to available memory. Dynamic loading at runtime: the program is actually loaded just before execution.

2 Memory Overflow Prevention Mechanisms

How to prevent out‑of‑bounds memory access.

Set upper‑ and lower‑limit registers to store the process's address limits and check each access for overflow.

Relocation + limit registers: Relocation register stores the minimum physical address. Limit register stores the maximum logical address.

Access address (relative) is first compared with the limit; if within bounds, it is added to the relocation register to obtain the physical address.

Ensuring min + x where x < max guarantees the address stays within the allowed range.

3 Memory Allocation Mechanisms

3.1 Contiguous Allocation

Memory allocated to a user program is contiguous.

3.1.1 Single Contiguous

Memory is divided into system and user areas; only one program can reside in the user area at a time, preventing overflow.

3.1.2 Fixed‑Partition Allocation

The user area is split into fixed‑size partitions, each holding one job. Large programs may not fit; small programs cause internal fragmentation.

3.1.3 Dynamic Partition Allocation

When a program is loaded, a partition of the exact required size is created, leaving only the leftover space as external fragmentation. Fragmentation can occur when a process terminates, leaving a hole too small for other processes.

Dynamic allocation strategies:

First‑fit: scan from the beginning and allocate the first suitable partition (simple and often best).

Best‑fit: choose the partition with the smallest size difference (produces most fragmentation).

Worst‑fit: allocate the largest available partition.

Next‑fit: continue scanning from the last allocation point instead of restarting from the first partition (can leave many fragments at the end).

3.2 Non‑Contiguous Allocation

Processes can occupy memory blocks at different addresses; the memory does not need to be contiguous.

3.2.1 Paging

Memory is divided into fixed‑size pages; a process requests multiple pages that may reside at different locations.

Page table: each process control block (PCB) contains a page table register (PRT) indicating the start and length of the page table. The table maps page numbers and offsets to physical addresses using the formula: physical address = page number × page size + offset.

When a process accesses a virtual address, it first looks up the page table to find the corresponding physical address.

Translation Lookaside Buffer (TLB): caches recent virtual‑to‑physical address translations to speed up address translation.

Multi‑level page tables: when a single page table becomes too large, a hierarchy of page tables is used. The first‑level table points to second‑level tables, which finally point to the actual physical frames.

3.2.2 Segmentation

Unlike paging, segment length is not fixed, allowing variable‑size logical address spaces. Segmentation provides a two‑dimensional address (segment number + offset) and is useful for dynamic linking.

3.2.3 Segmented Paging

Programs are first divided into segments, then each segment is paged. The address consists of segment number, page number, and offset.

Row‑major traversal of a 2‑D array is faster than column‑major because CPU caches fetch contiguous memory blocks; column‑major access leads to cache misses and slower performance.

4 Virtual Memory

4.1 Concept

Virtual addresses allow a process to use more memory than physically available.

Features:

Multiprogramming – jobs can be loaded in multiple phases.

Swapping – memory pages can be exchanged during execution.

Virtualization – logical address space can be larger than physical memory.

Requirements: non‑contiguous allocation (paging, segmentation, or segmented paging) and hardware support for page tables, interrupts, and address‑translation mechanisms.

Theoretical basis: temporal locality (recently accessed data is likely to be accessed again) and spatial locality (nearby data is likely to be accessed).

4.2 Demand Paging

Demand paging adds two functions to basic paging:

Page request – when a page is not in memory, it is fetched from secondary storage.

Page replacement – unused pages are swapped out to make room for needed pages.

Page‑table entry fields include page number, physical frame number, present bit (P), access bit (A), modified bit (M), and swap‑area address.

A page‑fault interrupt occurs when a referenced page is absent, triggering the replacement algorithm.

4.3 Working Set Concept

Resident set: the set of pages actually loaded for a process (may be larger than the actively used pages).

Working set: the subset of pages referenced during a recent time window.

Monitoring the working set helps the OS decide which pages to keep in memory, reducing thrashing.

4.4 Page‑Replacement Algorithms

Optimal algorithm: replace the page whose next use is farthest in the future (theoretical, requires prediction).

First‑In‑First‑Out (FIFO): may cause Belady’s anomaly, where increasing allocated frames raises the page‑fault rate.

Least‑Recently‑Used (LRU): replace the page that has not been used for the longest time; often implemented with a priority queue.

Clock (Second‑Chance/NRU): each page has a reference bit; the clock hand scans pages, giving a second chance to pages with bit = 1.

Clock replacement steps:

Scan the circular list of pages.

If the reference bit is 1, set it to 0 and continue.

If the reference bit is 0, replace that page and advance the hand.

Improved clock adds a modified bit (M) to distinguish four classes:

A=0, M=0 – best candidate for replacement.

A=0, M=1 – not ideal, but replaceable.

A=1, M=0 – recently used, likely needed.

A=1, M=1 – recently used and modified.

Replacement order: first look for class 0 0, then 0 1, resetting bits as the hand passes.

4.5 Page‑Allocation Policies

Fixed allocation with local replacement – each process gets a fixed number of frames and replaces only within its own set.

Variable allocation with global replacement – any free frame can be taken from any process when a page fault occurs.

Variable allocation with local replacement – processes replace their own pages but can request additional frames when needed.

Allocation sources include the swap area (frequently swapped pages) and the file area (pages backed by files).