Comprehensive Study Notes on Main Memory and Virtual Memory Systems

Fundamentals of Main Memory Management

To share the CPU effectively among a set of processes, multiple processes must reside simultaneously in main memory. Operating systems employ memory management schemes to ensure safe and efficient sharing of main memory space across active processes.

Hardware Space Isolation

In modern computer hardware, each executing process is assigned a completely separate memory space. This isolation prevents processes from interfering with one another's memory allocations or corrupted data states.

Memory Management Unit (MMU) & Address Spaces

Memory management requires distinguishing between the address space generated by program code and the actual physical RAM location.

Logical vs. Physical Addresses

• Logical (Virtual) Address: An address generated directly by the CPU during instruction execution. The user program operates entirely within logical address spaces ranging from $0$ to $\text{max}$.
• Physical Address: The hardware location loaded into the memory-address register (MAR) and recognized by the physical memory unit.
• Memory Management Unit (MMU): A hardware device responsible for executing run-time mapping from logical addresses to physical addresses.

Base Register Address Relocation

Under basic relocation hardware schemes, a Base Register ($B$) holds the physical starting address of a process's allocated space in RAM:

• Logical address range generated by CPU: $0 \text{ to } \text{max}$
• Physical address mapped by MMU: $B + 0 \text{ to } B + \text{max}$
• Mathematical Mapping Equation:

$\text{Physical Address} = \text{Base Register Value} + \text{Logical Address}$

Contiguous Memory Allocation

In contiguous memory allocation, each process is held in a single continuous section of physical memory adjacent to the section containing the next process. Physical memory is divided into fixed or variable-sized partitions, where each partition holds exactly one process.

Unused blocks of available memory are referred to as holes. The operating system maintains an allocation table recording which portions of memory are occupied and which remain free.

Dynamic Storage Allocation Strategies

When a process request of size $n$ arrives, the operating system selects an available hole from the free list using one of three primary strategies:

1. First-Fit: Allocates the first hole in memory that is large enough to satisfy request $n$. Search stops as soon as a qualifying hole is found.
2. Best-Fit: Allocates the smallest hole that is large enough to satisfy request $n$. Requires searching the entire list unless it is ordered by size. Produces the smallest leftover hole.
3. Worst-Fit: Allocates the largest available hole in memory. Requires searching the entire list unless sorted by size. Produces the largest leftover hole.

Allocation Example & Walkthrough

Consider a physical memory layout containing processes and unallocated holes:

• Operating System occupies high memory ($880000 \text{ to } 1024000$).
• Active process blocks reside at physical bounds such as $256000$, $300040$, $420940$, and $459060$.
• Available free holes exist at specific intervals: Hole 1 ($100000\, \text{KB}$) and Hole 2 ($144000\, \text{KB}$).

When Process 7 arrives requesting allocation:

• First-Fit inspects holes sequentially from low to high memory and assigns Process 7 to Hole 1 ($100000\, \text{KB}$).
• Best-Fit evaluates both holes and assigns Process 7 to Hole 1 ($100000\, \text{KB}$) to minimize leftover space.
• Worst-Fit evaluates both holes and assigns Process 7 to Hole 2 ($144000\, \text{KB}$) to maximize remaining hole size.

Memory Fragmentation Problems

Contiguous memory allocation suffers from two forms of memory degradation:

• External Fragmentation: Occurs when total memory space exists to satisfy a process allocation request, but the available space is split across non-contiguous holes.

• Internal Fragmentation: Occurs when physical memory is partitioned into fixed-size blocks. Memory allocated to a process is slightly larger than requested, leaving unallocated, wasted space internal to the partition.

Non-Contiguous Allocation: Paging

Paging is a memory management scheme that allows a process's physical address space to be non-contiguous, eliminating external fragmentation.

Frame, Page, and Page Table Structures

• Frames: Fixed-sized blocks into which physical memory is divided.
• Pages: Fixed-sized blocks into which logical memory is divided. Pages are identical in size to physical frames, with sizes represented as powers of 2.
• Page Table: A kernel data structure mapping logical process pages to physical memory frames.

Logical Address Structure and Translation

An address generated by the CPU is divided into two distinct components:

1. Page Number ($p$): Used as an index into the process page table to locate the corresponding frame base address.
2. Page Offset ($d$): The specific byte displacement within the target page or frame.

Address Translation Process

1. CPU generates a logical address containing $(p, d)$.
2. MMU extracts page number $p$ and indexes into the page table.
3. The page table returns physical frame number $f$ stored at index $p$
4. Page number $p$ is replaced by frame number $f$.
5. Offset $d$ remains unchanged.
6. The final physical address is constructed as $(f, d)$.

Paging Calculations & Examples

Given a logical address format with $m$ high-order page bits and $n$ low-order offset bits:

$\text{Page Size} = 2^n$$\text{Total Logical Address Space} = 2^{m+n}$$\text{Number of Addressable Pages} = \frac{2^{m+n}}{2^n} = 2^m$

Calculation Problem 1

If offset bits $n = 2$ and page number bits $m = 4$:

• Page Size: $2^2 = 4\, \text{addresses}$
• Addressable Pages: $2^4 = 16\, \text{pages}$
• Total Logical Memory Size: $2^{4+2} = 2^6 = 64\, \text{addresses}$

Calculation Problem 2

Given a logical address space of $2^6 = 64$ addresses and a page size of $2^2 = 4$ addresses:

• Low-order offset bits ($n$): $n = 2$
• Number of pages: $\frac{64}{4} = 16 = 2^4$
• High-order page bits ($m$): $m = 4$

Virtual Memory Management

Virtual memory separates logical memory as perceived by software developers from physical storage memory, enabling programs to execute even if their size exceeds physical RAM.

Demand Paging Mechanics

Demand paging loads pages into main memory only as they are referenced during execution.

Each page table entry includes a Valid-Invalid Bit:

• Valid ($v$): Indicates the associated page is currently loaded in physical RAM.
• Invalid ($i$): Indicates the page either is out of the process's logical address space or resides strictly on secondary storage (backing store).

Page Fault Execution Sequence

Attempting to access a page marked invalid ($i$) triggers a hardware trap called a Page Fault.

1. Memory reference instruction is issued by the CPU.
2. Page table lookup detects valid-invalid bit set to $i$, generating a trap signal to the operating system.
3. OS checks internal process tables to confirm whether the access reference was legal.
4. OS locates the missing page on the backing store disk.
5. OS selects a free frame from the system Free-Frame List.
6. OS schedules a secondary storage read operation to copy the page into the allocated free frame.
7. Page table entry is updated: frame number set to allocated location, bit modified to valid ($v$).
8. OS resumes and restarts the instruction that caused the original fault.

Page Replacement Algorithms

When a page fault occurs and no frames remain on the free-frame list, page replacement is performed to evict an existing page from physical RAM to make room for the incoming page.

First-In-First-Out (FIFO) Algorithm

Tracks the time each page was brought into main memory. Replaces the oldest loaded page.

• Drawback: May evict heavily used pages or early initialized variables required throughout program lifetime.
• Trace Example: Reference string 7, 0, 1, 2, 0, 3, 0, 4, 2, 3, 0, 3, 2, 1, 2, 0, 1, 7, 0, 1 allocated across 3 physical frames produces 15 total page faults.

Optimal Page Replacement Algorithm

Replaces the page that will not be accessed for the longest duration in the future.

• Advantage: Guarantees the lowest theoretical page fault rate for a given frame allocation.
• Drawback: Cannot be implemented in practice, as it requires future knowledge of reference strings.

Least Recently Used (LRU) Algorithm

Replaces the page that has not been accessed for the longest duration in past execution history.

• Approximates Optimal replacement by relying on temporal locality of reference.

Frequency-Based Algorithms (LFU and MFU)

Maintains a counter tracking the number of references made to each active page:

• Least Frequently Used (LFU): Replaces the page with the lowest reference count.
• Most Frequently Used (MFU): Replaces the page with the highest reference count (assuming pages with low counts were recently loaded and need time to execute).

Frequency Algorithm Tracing Example

Consider reference string sequence: 0, 4, 6, 4, 4, 6, 4, 9 Prior to processing request 9, page access frequency totals are:

• Page 0: 1 access
• Page 4: 4 accesses
• Page 6: 2 accesses

Replacement behavior upon encountering page 9:

• LFU Strategy: Evicts Page 0 (smallest access count = 1).
• MFU Strategy: Evicts Page 4 (highest access count = 4).

Translation Look-Aside Buffer (TLB)

The Translation Look-aside Buffer (TLB) is a fast hardware associative cache built into the MMU that stores recent logical-to-physical address mappings.

Hardware Features

• Contains associative key-value entries: Key = Page Number ($p$), Value = Frame Number ($f$).
• Size is limited (typically between 32 and 1024 entries) to ensure single-cycle hardware lookup speed.
• Managed using replacement algorithms similar to page replacement policies when full.

Lookup Operations

• TLB Hit: Page number $p$ is found in the TLB. Frame number $f$ is retrieved immediately, allowing direct construction of physical address $(f, d)$.
• TLB Miss: Page number $p$ is not present in the TLB.
  1. MMU performs a lookup in the main memory page table.
  2. Page Table Hit: Frame number $f$ is extracted from the page table entry, and mapping $(p, f)$ is written into the TLB.
  3. Page Fault: Entry in page table is marked invalid ($i$), triggering a trap to the OS page fault handler.

Comprehensive System Calculations & Simulation

Quantitative Problem Analysis

Given system parameters:

• Physical Memory Size: 32 addresses ($2^5$
• Virtual Memory Size: 64 addresses ($2^6$
• Offset Bits: 2 bits

Solutions:

1. Virtual Address Bit Length:

$\text{Virtual Bits} = \log_2(64) = 6\, \text{bits}$

2. Single Page/Frame Size:

$\text{Page Size} = 2^{\text{offset bits}} = 2^2 = 4\, \text{addresses}$

3. Page Number Allocation Bits:

$\text{Page Bits} = \text{Total Virtual Bits} - \text{Offset Bits} = 6 - 2 = 4\, \text{bits}$

4. Total Physical Frames:

$\text{Frames} = \frac{\text{Physical Memory Size}}{\text{Page Size}} = \frac{32}{4} = 8\, \text{frames}$

5. Total Virtual Pages:

$\text{Pages} = \frac{\text{Virtual Memory Size}}{\text{Page Size}} = \frac{64}{4} = 16\, \text{pages}$

ParaCache Simulation Summary

Simulation Configuration Parameters:

• Physical Page Size: 32 ($2^5$ total addresses across 8 frames)
• Offset Bits: 2 (yielding 4 addresses per page)
• Virtual Memory Size: 64 ($2^6$ total addresses across 16 pages)
• TLB Entries: 5

Instruction Trace Execution (LOAD 6 over address sequence 7, 8, 9, 10):

• Instruction 0: Miss
• Instruction 1: TLB Hit
• Instruction 2: TLB Hit
• Instruction 15: Miss
• Instruction 4: Miss
• Instruction 3: TLB Hit

Simulated Performance Metrics:

• Hit Rate: $50\%$
• Miss Rate: $50\%$