Memory management, paging and virtual memory notes — Unit 4

Main memory (RAM) is a large array of bytes, each with its own address. For a program to be executed, it must be loaded from the hard disk into main memory and placed within a process.

⇒1.1 Logical vs. Physical Addresses

This is the most critical concept in OS memory management.

• Logical Address (Virtual Address): An address generated by the CPU during execution. The user program only sees logical addresses. It thinks it owns memory from address 0 to N.
• Physical Address: The actual physical location on the RAM chip. The hardware sees this.

The translation from Logical to Physical address is done in hardware by the Memory-Management Unit (MMU).

Early operating systems used contiguous allocation. A process had to be stored in a single, unbroken block of physical memory.

⇒2.1 The Allocation Strategies

When a process needs 100KB, and RAM has "holes" (empty spaces) of 50KB, 200KB, and 120KB, which hole does the OS use?

• First-Fit: Allocates the first hole that is big enough. (Fastest).
• Best-Fit: Allocates the smallest hole that is big enough. Leaves the smallest leftover hole.
• Worst-Fit: Allocates the largest hole available. Idea is that the leftover hole will be large enough to be useful for another process.

Contiguous allocation suffers from a fatal flaw: Fragmentation.

⇒3.1 External Fragmentation

As processes are loaded and removed, free memory is broken into little pieces. Total free memory space exists to satisfy a new request, but it is not contiguous.

(Solution: Compaction. The OS pauses the system and physically shuffles all processes together to create one large free block. Very slow).

⇒3.2 Internal Fragmentation

Occurs when memory is divided into fixed-size blocks. If a block is 4KB, and a process requests 3KB, it is given the full 4KB block. The leftover 1KB is entirely wasted and trapped inside the allocated block.

Paging completely solves External Fragmentation by breaking the rule that processes must be contiguous. The physical memory of a process can be scattered anywhere in RAM.

⇒4.1 The Mechanism

• Physical Memory (RAM) is divided into fixed-size blocks called Frames.
• Logical Memory (the program) is divided into blocks of the exact same size called Pages.
• When a program is executed, its Pages are loaded into any available Frames in RAM.

The MMU translates the Logical Address into a Physical Address using a Page Table.

Every logical address generated by the CPU is divided into two parts:

• Page Number (p): Used as an index into the Page Table.
• Page Offset (d): The exact location within that page.

The Page Table contains the base address of each page in physical memory (the Frame Number).

The MMU takes the Page Number, looks up the corresponding Frame Number in the Page Table, and attaches it to the Offset to create the Physical Address.

(Note: Because frame size = page size, the offset never changes during translation. Only the page number is replaced by the frame number).

The Page Table itself is stored in main memory. Therefore, translating an address requires a memory access, and then reading the actual data requires a second memory access. Paging halves CPU performance.

To solve this, the MMU includes a specialized, ultra-fast hardware cache called the TLB.

The TLB caches recently used `[Page Number : Frame Number]` translations.

• TLB Hit: Translation found in hardware instantly. 1 memory access total.
• TLB Miss: Translation not found. Must access Page Table in RAM, update TLB, then access data. 2 memory accesses total.

Effective Access Time (EAT) = $Hit\_Ratio \times (Cache\_Time + Mem\_Time) + (1 - Hit\_Ratio) \times (Cache\_Time + 2 \times Mem\_Time)$.

Paging divides a program into fixed-size, meaningless mathematical blocks.
Segmentation divides a program into variable-sized, logical chunks that make sense to the programmer (e.g., The Main Program, The Stack, The Math Library).

⇒7.1 Segment Table

A logical address consists of `<Segment Number, Offset>`.

The Segment Table stores two values for each segment:

• Base: The physical starting address of the segment in RAM.
• Limit: The length of the segment.

The MMU checks if `Offset < Limit`. If true, it computes `Physical Address = Base + Offset`. If false, it generates a Segmentation Fault (meaning the program tried to read outside its segment).

Virtual Memory allows the execution of processes that are not completely in memory. It abstracts main memory into a massive uniform array, separating logical memory from physical memory.

⇒8.1 Demand Paging

The standard implementation of virtual memory. Instead of loading an entire program into RAM at startup, pages are only loaded from the hard disk into RAM when they are actually demanded during execution.

The Page Table gains a Valid/Invalid Bit.
`1` = Page is in RAM.
`0` = Page is still on the disk.

If a program tries to access a page marked `Invalid` (0) in the Page Table, a Page Fault hardware trap occurs.

⇒9.1 Handling a Page Fault

• 1. CPU traps to the OS.
• 2. OS checks if the memory reference is valid or an illegal memory access.
• 3. If valid, the OS finds a free Frame in physical RAM.
• 4. The OS schedules a disk read to bring the missing Page into the free Frame.
• 5. When the disk read finishes, the OS updates the Page Table (sets valid bit to 1).
• 6. The OS restarts the instruction that caused the fault. To the program, it seems as if the page was in RAM all along.

What happens during a Page Fault if there are NO free frames left in RAM? The OS must evict a page from RAM to make room. This is Page Replacement.

⇒10.1 The Routine

• 1. Find the location of the desired page on the disk.
• 2. Find a free frame. If none exists, use a Page Replacement Algorithm to select a "Victim Frame".
• 3. If the Victim Frame has been modified (Dirty bit = 1), write its contents back to the disk.
• 4. Load the desired page into the newly freed frame.
• 5. Update page tables and restart the instruction.

Disk I/O is incredibly slow. The goal of a Replacement Algorithm is to minimize the total number of page faults.

⇒11.1 First-In, First-Out (FIFO)

The simplest algorithm. The OS maintains a queue. When a page must be replaced, the oldest page (the one brought into memory first) is chosen as the victim.

Performance: Generally poor. The oldest page might contain heavily used initialization variables that the program accesses constantly.

⇒11.2 Belady's Anomaly

Common sense dictates that adding more physical RAM should decrease the number of page faults. However, with the FIFO algorithm, there are specific reference strings where adding more frames actually increases the number of page faults. This mathematical quirk is known as Belady's Anomaly.

⇒12.1 The Optimal Algorithm

Replace the page that will not be used for the longest period of time in the future.

Performance: Mathematically guarantees the lowest possible page fault rate for a fixed number of frames. It never suffers from Belady's Anomaly.

Flaw: It requires the OS to see into the future. Because it is impossible to predict future memory requests of a program, the Optimal Algorithm cannot be implemented in a real operating system. It is purely a theoretical benchmark used to judge how good other algorithms are.

⇒13.1 Least Recently Used (LRU)

Since we can't look into the future, we look into the past. LRU replaces the page that has not been used for the longest period of time.

Based on the principle of temporal locality, pages recently used will likely be used again.

Performance: Very good. Consistently close to the Optimal benchmark. Never suffers from Belady's Anomaly.

Implementation Cost: High. Requires substantial hardware assistance. Either every page must have a timestamp updated on every single memory access, or the OS must maintain a linked list stack that is reordered on every memory access.

Unit 4 is the core of memory theory.

⇒14.1 University Exam Checklist

• Explain Internal and External Fragmentation. Which one affects Paging?
• Draw a diagram showing how a Logical Address is translated to a Physical Address using a Page Table.
• Calculate the Effective Access Time (EAT) given a TLB hit ratio and memory access times.
• Explain the concept of Demand Paging and outline the 6 steps of handling a Page Fault.
• Solve a numerical problem tracking page faults for a given reference string using FIFO, Optimal, and LRU algorithms.
• What is Belady's Anomaly? Which algorithm suffers from it?