Unit 5: Memory Management

1. 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. The user program deals with logical addresses; it never sees the real physical address.
• Physical Address: An address seen by the memory unit (loaded into the memory-address register) used to access data in the main memory (RAM).
• Memory Management Unit (MMU): A hardware device that maps virtual to physical addresses at run time. The value in the relocation register is added to every address generated by a user process at the time it is sent to memory.

2. Contiguous Memory Allocation

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

Memory Protection

• Relocation Register: Contains the value of the smallest physical address.
• Limit Register: Contains the range of logical addresses (size of the process).
• Mechanism: The MMU checks if Logical Address < Limit Register. If true, it adds the Relocation Register value to map to physical memory. If false, a trap (addressing error) is generated.

Partitioning Strategies

1. Fixed Partitioning (Static): Memory is divided into fixed-sized partitions. One process per partition. Causes high internal fragmentation.
2. Variable Partitioning (Dynamic): Partitions are created dynamically to fit the exact size of the process. Causes external fragmentation.

Allocation Algorithms (Dynamic Partitioning)

• First-Fit: Allocate the first hole that is big enough. Fast.
• Best-Fit: Allocate the smallest hole that is big enough. Produces the smallest leftover hole.
• Worst-Fit: Allocate the largest hole. Produces the largest leftover hole (which might be useful).

3. Fragmentation

Fragmentation occurs when memory is broken into small, non-contiguous blocks, making it inefficient or impossible to allocate memory.

Internal Fragmentation

• Definition: Wasted space inside a partition.
• Cause: Occurs when memory is allocated in fixed-sized blocks (like pages or fixed partitions). If a process requires 100 bytes but is given a block of 128 bytes, 28 bytes are wasted.

External Fragmentation

• Definition: Wasted space outside partitions. Total memory space exists to satisfy a request, but it is not contiguous.
• Cause: Frequent loading and unloading of processes of different sizes.
• Solution: Compaction (Shuffle memory contents to place all free memory together in one large block) or Paging (allows non-contiguous allocation).

4. Swapping and Overlays

Swapping

A mechanism to temporarily move a process out of main memory to a backing store (disk) and then bring it back into memory for continued execution.

• Roll out, roll in: Used for priority-based scheduling. Lower-priority process is swapped out so higher-priority process can run.
• Context Switch Time: Major overhead in swapping is transfer time (disk I/O).

Overlays

An older technique used to enable a process to be larger than the amount of memory allocated to it.

• Concept: Keep in memory only those instructions and data that are needed at any given time.
• Implementation: Implemented by the user (programmer), not the OS. The programmer must divide the program into independent modules.

5. Paging

Paging is a memory management scheme that eliminates the need for contiguous allocation of physical memory.

Basic Concepts

• Frames: Physical memory is broken into fixed-sized blocks called frames.
• Pages: Logical memory is broken into blocks of the same size called pages.
• Page Table: A data structure maintained by the OS for every process. It contains the base address of each page in physical memory.

Address Translation Architecture

The CPU generates an address divided into two parts:

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

Formula: Physical Address = (Frame Number * Frame Size) + Offset

Multilevel Paging

For large logical address spaces (e.g., 64-bit), the page table itself becomes too large to fit in one contiguous block of memory.

• Solution: Paging the page table.
• Two-Level Paging: The outer page table maps to an inner page table, which maps to the frame.
• Structure: Logical address is split into | p1 | p2 | d |. p1 is index for outer table, p2 is index for inner table.

6. Segmentation

Segmentation supports the user view of memory. A program is a collection of segments (e.g., main program, stack, symbol table, square root function).

• Logical Address: Tuple <segment-number, offset>.
• 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.
• Protection: Validation bit (0/1) for read/write/execute privileges.

Segmentation with Paging

To solve external fragmentation in pure segmentation and the large table size of pure paging, systems (like Intel x86) use segmentation with paging.

1. CPU generates logical address (Selector + Offset).
2. Segmentation unit produces a Linear Address.
3. Paging unit maps Linear Address to Physical Address.

7. Virtual Memory

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

Demand Paging

Pages are loaded only when they are demanded during program execution.

• Lazy Swapper: Never swaps a page into memory unless that page will be needed.
• Valid-Invalid Bit: Associated with each page table entry.
  • Valid (v): The page is in memory.
  • Invalid (i): The page is not in memory (or invalid address).

Page Fault

A page fault occurs when a process tries to access a page that is marked Invalid (not currently in RAM).

Handling a Page Fault (Steps):

1. CPU references a page; hardware traps to OS (Page Fault Interrupt).
2. OS checks internal table. If invalid reference -> abort. If just not in memory -> continue.
3. OS finds a free frame in physical memory.
4. OS schedules disk operation to read the desired page into the newly allocated frame.
5. When disk read completes, OS modifies the page table (sets bit to Valid).
6. Restart the instruction that caused the trap.

8. Page Replacement Algorithms

When a page fault occurs and there are no free frames, the OS must replace a page currently in memory.

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

• The oldest page in memory is selected for replacement.
• Implementation: Use a FIFO queue.
• Belady’s Anomaly: Specific to FIFO—adding more frames can sometimes cause more page faults.

2. Optimal Page Replacement

• Replace the page that will not be used for the longest period of time.
• Pros: Guarantees the lowest possible page-fault rate.
• Cons: Impossible to implement practically because it requires future knowledge of the reference string. Used primarily for comparison/benchmarking.

3. LRU (Least Recently Used)

• Replace the page that has not been used for the longest period of time.
• Theory: Approximates Optimal by looking backward in time rather than forward.
• Implementation:
  • Counters: Every page entry has a time-of-use field.
  • Stack: Keep a stack of page numbers. When a page is referenced, move it to the top. The bottom is the LRU page.

4. Counting Algorithms

• LFU (Least Frequently Used): Replace page with smallest count.
• MFU (Most Frequently Used): Replace page with largest count (assumes smallest count was just brought in).