04 Memory Management
Table of Contents
Overview
Operating system memory management is a fundamental aspect of computer systems that plays a critical role in ensuring the efficient and secure utilization of a computer's memory resources. It is the operating system's responsibility to oversee the allocation, tracking, protection, and organization of memory in a way that allows multiple processes to run concurrently while safeguarding the integrity of each process's data.
Core Functions
Memory management encompasses several essential functions:
Memory Allocation
Allocates memory to processes, determining how much memory each process can use through physical RAM or virtual memory
Memory Protection
Enforces mechanisms preventing processes from interfering with one another's memory areas, crucial for system stability and security
Address Translation
Maps virtual memory addresses to physical memory locations, allowing processes to operate with dedicated memory abstraction
Swapping and Paging
Transfers parts of a process's data or code between RAM and disk storage when physical RAM becomes insufficient
Memory Cleanup
Releases memory used by completed or terminated processes and reclaims resources
Fragmentation Management
Manages internal and external memory fragmentation through compaction and allocation algorithms
Memory Sharing
Provides mechanisms for processes to share memory, facilitating efficient inter-process communication
Effective memory management is crucial for optimizing a computer's performance and enabling multiple programs to run simultaneously without conflicts. The specific strategies and mechanisms vary depending on the operating system's design and the underlying hardware architecture.
Address Translation
Virtual and Physical Addresses
Virtual Address Space Physical Address Space
0x00000000
┌─────────────────┐ 0x00000000
│ │ ┌──────────────┐
│ text │───────────────>│ Page Frame │
│ │ ┌────>│ Page Frame │
└─────────────────┘ │ ├──────────────┤
0x10000000 │ │ Page Frame │
┌─────────────────┐ │ ├──────────────┤
│ │──────────┘ │ Page Frame │
│ data │─────┐ ├──────────────┤
│ │ │ │ │
└─────────────────┘ └─────────>│ Page Frame │
╎ ├──────────────┤
╎ │ Page Frame │
┌─────────────────┐ ┌────>│ Page Frame │
│ │ │ ├──────────────┤
│ stack │──────────┘ │ Page Frame │
│ │ └──────────────┘
└─────────────────┘ 0x00ffffff
0x7fffffff
Process views contiguous virtual memory,
mapped to non-contiguous physical framesVirtual addresses and physical addresses are central concepts in computer memory management:
Virtual Address:
A virtual address is an address generated by a program running on a computer. It represents the memory location that the program believes it is accessing.
Virtual addresses are used to create an abstraction layer that separates a program's view of memory from the actual physical memory. This allows for greater flexibility in memory management.
Virtual addresses are generated by processes, and they allow processes to operate as if they have their dedicated contiguous memory space.
Physical Address:
A physical address is the actual location in the computer's physical memory, such as RAM (Random Access Memory).
The physical address represents the real, tangible location where data is stored in the computer's hardware memory chips.
Physical addresses are used by the computer's hardware to access and retrieve data from memory.
Translation Process
The translation from virtual addresses to physical addresses is primarily achieved through the Memory Management Unit (MMU) in coordination with the operating system:
Virtual Address Splitting
Virtual address is split into two parts: virtual page number (VPN) and offset within the page
The offset represents the location within the page and does not require translation
Page Table Lookup
VPN is used as an index into the page table
Page table stores the mapping between virtual and physical addresses
Retrieved page table entry contains the physical page frame number (PFN) corresponding to the virtual page
Address Formation
Physical address is formed by concatenating the PFN from the page table entry with the offset from the original virtual address
This combination creates the physical memory address that the CPU uses to access data in RAM
Access Control
MMU checks the permissions specified in the page table entry before allowing access
If access is allowed, the CPU can read from or write to that memory location
If access is not permitted, the MMU raises an exception or interrupt, indicating a memory protection violation
Page Fault Handling
If the page table entry indicates that the required page is not currently in physical memory (marked as invalid), a page fault occurs
Operating system loads the required page from secondary storage into an available page frame in RAM
Page table entry is updated to indicate the new location in physical memory
This translation process ensures that a program interacts with its virtual address space while the operating system manages the mapping to physical memory. It enables multiple processes to run concurrently without interfering with each other, provides memory protection, and enables efficient utilization of physical memory resources.
Page Tables
Page tables are a fundamental component of modern computer memory management, enabling memory protection, efficient use of physical memory, and the safe and concurrent execution of multiple processes. They are a critical part of the interaction between the CPU, the memory management unit (MMU), and the operating system in a virtual memory environment.
Key Characteristics:
Data structure used in virtual memory systems to manage the mapping between virtual and physical addresses
Provides a mechanism for translating virtual addresses used by processes into actual physical memory locations
Enables processes to have the illusion of a contiguous, dedicated memory space while sharing the underlying physical memory
Page Table Entry (PTE)
┌────────────────┬──────────────┬────────────┬───────────┬─────────┬───────┐
│ Frame Number │ Present/ │ Protection │ Reference │ Caching │ Dirty │
│ │ Absent │ │ │ │ │
└────────────────┴──────────────┴────────────┴───────────┴─────────┴───────┘
Physical Frame Valid Bit R/W/X Bits Access Bit Cache Modified
Number (PFN) Control Bit
Optional Information (Hardware-Specific)A typical page table entry (PTE) includes the following components:
Virtual Page Number (VPN)
Stores the portion of the virtual address that represents the page number; used to index the page table to find the corresponding entry
Page Frame Number (PFN)
Holds the physical page frame number in RAM where the corresponding virtual page is located; enables CPU to access the actual data in physical memory
Valid/Invalid Bit
Indicates whether the page is currently in physical memory (valid) or not (invalid)
Read/Write Permissions
Specifies whether the page is read-only, read-write, or has other access permissions
Dirty Bit
Indicates whether the page has been modified since it was last loaded from secondary storage
Accessed Bit
Marks whether the page has been accessed recently
Additional Bits/Fields
Hardware-specific control bits for memory protection, cache management, or other features
Multi-Level Page Table
Level 1 Level 2 Virtual Memory
Page Table Page Tables
┌──────────┐ ┌──────────┐ ┌──────────────┐
│ PTE 0 │────────>│ PTE 0 │────────>│ VP 0 │
├──────────┤ ├──────────┤ ├──────────────┤
│ PTE 1 │─┐ │ ... │ │ ... │
├──────────┤ │ ├──────────┤ ├──────────────┤
│PTE 2 │ │ │ PTE 1023 │ ┌───>│ VP 1023 │
│(null) │ │ └──────────┘ │ ├──────────────┤
├──────────┤ │ │ │ VP 1024 │
│PTE 3 │ │ ┌──────────┐ │ ├──────────────┤
│(null) │ │ │ PTE 0 │ │ │ ... │
├──────────┤ │ ├──────────┤ │ ├──────────────┤
│PTE 4-7 │ │ │ ... │ │ │ VP 2047 │
│(null) │ │ ├──────────┤ │ ├──────────────┤
├──────────┤ │ │ PTE 1023 │────┘ │ │
│ PTE 8 │─┘ └──────────┘ │ Gap │
├──────────┤ │ (unallocated)│
│PTE 9-1K │ ┌──────────┐ │ │
│(null) │ │1023 null │ ├──────────────┤
└──────────┘ │ PTEs │ │ 1023 │
├──────────┤ │ unallocated │
│ PTE 1023 │────────>│ pages │
└──────────┘ ├──────────────┤
│ VP 9215 │
└──────────────┘
Only allocated regions have page table entries in Level 2Multi-level page tables, also known as hierarchical page tables, are used in virtual memory systems to address the challenges posed by large address spaces and to efficiently manage memory resources. They organize the page table structure into multiple levels, creating a hierarchical tree-like structure.
Motivation
Why Multi-Level Page Tables Are Needed:
Memory Overhead
In systems with large address spaces, maintaining a flat page table requires an entry for every possible virtual address, even if unused. Multi-level page tables allocate entries only where needed, reducing memory overhead
Sparse Address Spaces
If a significant portion of the virtual address space is unused or sparsely populated, flat page tables waste memory. Multi-level page tables allocate memory only for actively used regions
Operation
Hierarchical Structure:
Page table structure is organized into multiple levels, forming a tree
Number of levels and size of each table are determined by the system's architecture and design
Address Translation:
Virtual address is divided into multiple fields
Each field indexes a page table at a specific level
Most significant bits index the top-level page table, leading to intermediate-level page tables
Final-level page table provides the physical page frame number corresponding to the virtual address
Memory Hierarchy:
Top-level page table: Covers a large portion of the address space; entries point to intermediate-level page tables
Intermediate-level page tables: Cover smaller address ranges; map virtual addresses to lower-level page tables or physical frames
Lowest-level page tables: Map virtual addresses to physical page frames
Dynamic Memory Allocation:
Page table entries are allocated on demand
Unused portions of the address space do not require page table entries, saving memory
Access Control and Page Fault Handling:
MMU checks permissions before allowing access
If a page is not present in physical memory (page fault), the operating system loads the necessary page from secondary storage and updates the page table entries
Paging
Paging is a memory management scheme that eliminates the need for contiguous allocation of physical memory and thus eliminates the problems of fragmentation.
Page Load
Loading a Page:
Page Fault Occurs
Process tries to access a virtual page that is not currently in physical memory (RAM)
Page table indicates that the page is not present in memory
Page Fault Handling
Operating system's Memory Management Unit (MMU) traps the page fault
Control transfers to the page fault handler, which is responsible for managing page faults
Determine Page Location
Page fault handler checks the process's page table to find the location of the required page in secondary storage (hard drive or SSD)
Load the Page
Operating system initiates a read operation to transfer the required page from secondary storage into an available physical memory frame
Operation is typically done asynchronously; process may be scheduled to wait while the page is being loaded
Update Page Table
Once the page is loaded into a page frame, the page table entry for that virtual page is updated to indicate it is now present in physical memory
Page table entry is also updated with the physical address of the page frame
Restart the Faulting Instruction
After the required page is loaded into memory, the instruction that caused the page fault is restarted
Page is now in memory, and the instruction can execute as expected
Page Replacement
Evicting a Page:
Page Replacement Decision
When a page fault occurs due to a lack of free memory frames, the operating system's page replacement algorithm determines which page to evict or replace
Select a Page to Evict
Page replacement algorithm selects a candidate for eviction based on the policy's criteria (e.g., least recently used)
Check for Dirty Bit
Before evicting a page, the operating system checks if the page has been modified (dirty bit set)
If dirty, the page must be written back to secondary storage to preserve data integrity
Write Back (if necessary)
If the selected page is dirty, it is written back to its location in secondary storage (e.g., swap file on disk) to ensure changes are saved
Update Page Table
Page table is updated to reflect that the evicted page is no longer in memory
Page table entry for that page is marked as not present
Load New Page
Page frame that previously held the evicted page is now available for a new page
Page fault handling process brings in the new page
Continue Execution
Once the new page is loaded, the process that encountered the page fault can continue executing
Page Replacement Algorithms
Page replacement algorithms manage the allocation of physical memory when it becomes full. The choice of algorithm significantly impacts system performance:
FIFO (First-In-First-Out)
Replaces the oldest page in memory
Simple to implement
Doesn't consider access history or page importance
LRU (Least Recently Used)
Replaces the page that has not been used for the longest period
Good performance for typical access patterns
True LRU can be expensive to implement; approximations often used
LFU (Least Frequently Used)
Replaces the page referenced the least number of times
Eliminates infrequently used pages
May not work well when pages have high initial usage but low later usage
ARC (Adaptive Replacement Cache)
Self-tuning algorithm that adapts to changing access patterns
Combines benefits of LRU and LFU; adapts to workload changes
More complex implementation
MFU (Most Frequently Used)
Replaces the page used most frequently
Assumes past frequent use won't continue
Counter-intuitive; rarely optimal in practice
Memory Allocation
Memory allocation algorithms are techniques used by operating systems to manage and allocate memory to processes efficiently. These algorithms determine how processes are assigned memory space, whether in physical RAM or virtual memory.
Allocation Strategies
Contiguous Memory Allocation
Each process is allocated a contiguous block of memory
Simple but subject to fragmentation
Paging
Divides physical memory into fixed-size frames and virtual memory into fixed-size pages
Avoids external fragmentation; simplifies memory management
Segmentation
Divides memory into variable-sized segments, each representing different types of data or code
More flexibility than paging; can suffer from external fragmentation
Dynamic Memory Allocation
Allocates memory at runtime using functions like malloc, free, and realloc
Managed through heap memory algorithms
Contiguous Allocation Algorithms
First Fit
Allocates the first available block large enough to accommodate the process
Fast; may lead to external fragmentation
Best Fit
Allocates the smallest available block that is large enough
Reduces external fragmentation; slower search time
Worst Fit
Allocates the largest available block
Can lead to increased fragmentation
Advanced Allocation Techniques
Buddy System:
Memory is allocated in fixed-sized blocks (powers of 2)
Blocks are merged with their "buddy" when freed, forming larger blocks
Advantages: Efficient allocation and deallocation
Disadvantages: Can lead to internal fragmentation
Slab Allocation:
Used in the Linux kernel for memory allocation
Memory is organized into caches or "slabs" of objects with similar sizes
Advantages: Reduces memory fragmentation; improves allocation efficiency
Use Case: Kernel object allocation
Segregated Free Lists:
Maintains separate free lists for different allocation sizes
Commonly used in dynamic memory allocators
Advantages: Fast allocation for common sizes; reduced fragmentation
Use Case: Heap management in user-space allocators
Bounded Buffer Allocation:
Allocates memory within a fixed-sized buffer
Use Case: Real-time and embedded systems requiring predictable memory allocation and leak prevention
Allocation Trade-offs
The choice of memory allocation algorithm depends on several factors:
System Characteristics:
Real-time vs. general-purpose systems
Memory size and architecture
Workload patterns
Design Trade-offs:
Fragmentation: Internal vs. external fragmentation
Efficiency: Speed of allocation and deallocation
Overhead: Metadata and bookkeeping costs
Predictability: Deterministic vs. best-effort allocation
References
Course Materials:
CS 6200: Introduction to Operating Systems - Georgia Tech OMSCS
Textbooks:
Arpaci-Dusseau and Arpaci-Dusseau, Operating Systems: Three Easy Pieces
Last updated