Unit 5: Memory Management

1. Basic Concepts

Logical vs. Physical Address Space

The concept of a logical address space that is bound to a separate physical address space is central to proper memory management.

• Logical Address (Virtual Address): An address generated by the CPU during program execution. It refers to the location relative to the program, not the actual hardware memory.
• Physical Address: The actual address of the memory unit (RAM) seen by the hardware.
• Memory Management Unit (MMU): A hardware device that maps virtual to physical addresses at run time.
  • In a simple scheme, the MMU adds the value in a Relocation Register to every logical address to generate the physical address.
  • Formula:

Overlays

Overlays are a technique used when the process size is larger than the allocated physical memory.

• Mechanism: The program is split into independent sections. Only the instructions and data required at a given time are kept in memory.
• Control: Traditionally managed by the programmer (user-level), not the OS. The programmer must design the code to load/unload modules explicitly.
• Status: Obsolete in modern general-purpose OSs due to Virtual Memory, but used in embedded systems.

Swapping

Swapping is a mechanism to temporarily move a process out of main memory to a "backing store" (disk) and bring it back later to continue execution.

• Roll out, Roll in: A higher priority process arrives; the OS swaps out the lower priority process to disk (Roll out) and loads the high priority one.
• Backing Store: A fast disk partition large enough to accommodate copies of all memory images for all users.
• Context Switch Time: Swapping significantly increases context switch time because disk transfer rates are slow compared to RAM speeds.

2. Memory Allocation Techniques

Contiguous Memory Allocation

In this scheme, each process is contained in a single contiguous section of memory.

1. Fixed Partitioning: Memory is divided into fixed-sized partitions.
   • Pros: Simple.
   • Cons: Leads to Internal Fragmentation; limit on process size.
2. Variable Partitioning: Memory is divided dynamically based on process size.
   • Allocation Strategies:
     • First-Fit: Allocate the first hole that is big enough. (Fastest).
     • Best-Fit: Allocate the smallest hole that is big enough. (Produces smallest leftover hole).
     • Worst-Fit: Allocate the largest hole. (Produces largest leftover hole).

Fragmentation

Fragmentation occurs when memory is broken into small, non-contiguous blocks.

• Internal Fragmentation:
  • Occurs when memory is allocated in fixed-sized blocks (partitions or pages).
  • If a process requests 50KB but the smallest block available is 64KB, the 14KB excess inside the allocated block is wasted.
• External Fragmentation:
  • Occurs in variable partitioning.
  • Total memory space exists to satisfy a request, but it is not contiguous.
  • Example: Two 50KB holes exist (100KB total), but a process needs an 80KB contiguous block. It cannot be loaded.
  • Solution: Compaction (Shuffling memory contents to place all free memory together) or Paging.

3. Paging (Non-Contiguous Allocation)

Paging removes the requirement of contiguous physical memory. It avoids external fragmentation and the need for compaction.

Simple Paging Scheme

• Physical Memory: Divided into fixed-sized blocks called Frames.
• Logical Memory: Divided into blocks of the same size called Pages.
• Page Table: A data structure kept in main memory that contains the base address of each page in physical memory.

Address Translation:
The CPU generates an address divided into two parts:

1. Page Number (p): Used as an index into the page table.
2. Page Offset (d): Combined with the base address to define the physical memory address.

Multi-Level Paging

If the logical address space is huge (e.g., 32-bit or 64-bit), the Page Table itself becomes too large to fit contiguously in memory.

• Solution: Page the page table.
• Two-Level Paging:
  • Level 1: Outer Page Table (indexes the Inner Page Table).
  • Level 2: Inner Page Table (indexes the actual Physical Frame).
  • This creates a "tree" structure of tables, saving memory by not allocating inner tables for unused logical space.

4. Segmentation

Segmentation supports the user view of memory. A program is a collection of segments. A logical address is a tuple: <segment-number, offset>.

Simple Segmentation

• Segments: Logical units such as main program, procedure, function, stack, symbol table, arrays. Segments are of variable length.
• Segment Table: Maps two-dimensional user-defined addresses into one-dimensional physical addresses. Each entry has:
  • Base: Starting physical address.
  • Limit: Length of the segment.
• Hardware Protection: The offset is compared with the Limit. If , a trap (segmentation fault) is generated.

Segmentation with Paging

Pure segmentation suffers from external fragmentation. Paging suffers from internal fragmentation. Many systems combine them (e.g., Intel x86).

• Mechanism:
  1. The Logical Address is <Segment #, Offset>.
  2. The Segment Table looks up the Segment # to find the Page Table for that specific segment.
  3. The Offset is broken into <Page #, Page Offset>.
  4. The Page Table maps the Page # to a Frame #.
• Benefit: Allows the logical benefits of segmentation (sharing code, protection) with the physical efficiency of paging (no external fragmentation).

5. Virtual Memory

Virtual memory allows the execution of processes that are not completely in memory. It separates logical memory from physical memory.

Demand Paging

Demand paging is the implementation of virtual memory where pages are loaded only when they are demanded during program execution.

• Lazy Swapper (Pager): Never swaps a page into memory unless that page will be needed.
• Valid/Invalid Bit: Each page table entry has a bit.
  • Valid (v): The page is in memory.
  • Invalid (i): The page is not in memory (or invalid address).

Page Fault Interrupt

When a process tries to access a page marked Invalid, a Page Fault Trap occurs.

Steps in Handling a Page Fault:

1. Trap: The CPU interrupts the current process and signals the OS.
2. Check: The OS checks the internal table. If the address is invalid -> Terminate. If valid but not in RAM -> Initiate load.
3. Find Frame: The OS finds a free frame in physical memory.
4. Disk Operation: The OS schedules a disk operation to read the desired page into the newly allocated frame.
5. Update Table: Once the read is complete, the OS updates the page table (sets Valid bit) and the frame table.
6. Restart: The instruction that caused the trap is restarted.

6. Page Replacement Algorithms

When a page fault occurs and there are no free frames, the OS must replace an existing page.

1. FIFO (First-In-First-Out)

• Logic: Replace the oldest page in memory.
• Implementation: A FIFO queue holds all pages in memory.
• Issue: Belady’s Anomaly – For some page replacement algorithms, the page-fault rate may increase as the number of allocated frames increases. FIFO suffers from this.

2. Optimal Page Replacement (OPT)

• Logic: Replace the page that will not be used for the longest period of time.
• Status: Theoretical only. Impossible to implement because it requires future knowledge of the reference string.
• Use: Used as a benchmark to measure other algorithms.

3. LRU (Least Recently Used)

• Logic: Replace the page that has not been used for the longest period of time. (Approximation of Optimal).
• Implementation:
  • Counters: Every page entry has a time-of-use field; replace the one with the smallest value.
  • Stack: Whenever a page is referenced, move it to the top. The bottom is the LRU page.
• Pros: Does not suffer from Belady's Anomaly. Good performance.
• Cons: High hardware overhead.

4. Counting Algorithms (Less Common)

• LFU (Least Frequently Used): Replace page with smallest count. Logic: An actively used page should have a large reference count.
• MFU (Most Frequently Used): Replace page with largest count. Logic: Smallest count was just brought in and has yet to be used.

Summary Comparison Table