VM

Virtual Memory Overview

• Definition: Virtual Memory is a memory management technique that addresses various issues related to memory management simultaneously.

Memory Management Issues Addressed

• Spatial Allocation Issues: Allows non-contiguous physical allocation while making it appear contiguous virtually.

• Physical Memory Limitation: Physical memory (DRAM) is limited in size. Virtual Memory lets address spaces be more extensive than the physical memory size, utilizing disk space.

• Process Isolation: Prevents one process from accessing the memory space of another process.

Non-contiguous Allocation

• Physical Memory Segmentation: Programs may receive several chunks of separate DRAM space, which are combined into one contiguous "virtual" space perceived by the program.

• Future Reference: This concept will be examined in more detail subsequently.

Dealing with Limited Memory

• Disk Utilization: If data associated with a process does not fit in memory, it must be kept on disk.

• CPU Operations: When needed by the CPU, the required data must be fetched from the disk into memory, necessitating evicting other data from memory.

• Swapping: The process of transferring data between memory and disk is termed swapping.

Swap Space

• Definition: A designated portion of the disk reserved for swapping is known as swap space.

• Difference from File I/O: Swapping is distinct from explicit file read/write operations conducted by programs and is typically invisible to the program.

Historical Context: Overlays

• Early Overlays: Initially, applications performed overlay techniques explicitly, even when a single application process could not fit entirely in memory.

Implications of Context Switching

• Inefficiency of Context Switching: Even if a process fits entirely in memory, excessive context switching among processes diminishes efficiency and counters the benefits of multiprogramming.

Need for Multiprogramming

• I/O Time Considerations: If a program spends a fraction f of its execution time on explicit I/O (read/write), then with p processes, the CPU efficiency can be computed as:
  $ext{CPU Efficiency} = (1 - f imes p)$

• Increasing Processes for Efficiency: To maintain higher CPU efficiency, the number of processes p must be increased. However, not all processes may reside in memory simultaneously, thus necessitating efficient memory management to keep essential parts of as many processes in memory as possible.

Virtual Memory Functionality

• Support for Large Programs: Virtual Memory allows programs larger than the available physical memory to run concurrently.

• Process Residency: Several programs can reside in physical memory or at least relevant portions of them.

• Non-contiguous Allocation Simplified: Programs benefit from non-contiguous memory allocation without increased programming complexity.

Example Diagram

• Virtual Memory Structure: Physical memory may have a size of 16KB while each virtual address space (for multiple processes) could range up to 1MB, showing multiple virtual spaces existing concurrently alongside limited physical memory.

Paging Mechanism

• Paging Definition: The OS manages fetching data either from physical memory or disk through a method called paging.

• Virtual Pages: Virtual address space is divided into units called "virtual pages," usually sized at 4KB or 8KB. For instance, a 1MB virtual address space could consist of 256 virtual pages of 4KB each.

• Physical Pages: Similarly, physical memory is also divided into physical pages corresponding to the virtual pages.

Key Concept: Page Transfer

• Active Pages: At any time, only a limited number of virtual pages can reside within the physical memory, with the remainder stored on disk in swap space.

• Page as Transfer Unit: A "page" serves as the unit of transfer between disk and physical memory.

Page Table Role and Structure

• OS Responsibility: The Operating System must track which virtual pages are currently present in physical memory and their respective locations, managed via a data structure known as a "page-table."

• Mapping: Page tables facilitate the mapping of virtual addresses to physical addresses.

Page Table Components

• Virtual Address Layout: Each virtual address can be broken down into the following components:

  • Virtual Page Number (VP#)

  • Offset in Page

• Physical Address: Physical addresses are also structured with a corresponding physical page number and offset related to the physical frame.

Example of Page Table

• Usage: An address such as LOAD [0xBADCOFFEE], R1 involves the lookup of virtual page number and corresponding offsets to determine the physical address and ensure data is obtained correctly from physical memory.

Address Space Calculation Example

• Virtual Address Space: For a 4GB virtual address space,
  $4GB = 2^{32} ext{bytes}$

• Page Size: Assuming a page size of 4096 bytes,
  $ext{No. of Virtual Pages} = rac{2^{32} ext{ bytes}}{2^{12} ext{ bytes}} = 2^{20}$

• Address Bit Calculation: The number of bits in the virtual address equals 32 bits, comprised of 20 bits for the page ID and 12 bits for the page offset.

• Physical Storage: For a physical memory size of 256KB,
  $ext{Physical Memory Size} = 2^{18} ext{ bytes}$
  $ext{No. of Physical Frames} = rac{2^{18} ext{ bytes}}{2^{12} ext{ bytes}} = 64$

Page Table Lookup Complexity

• Page-Table Lookup Frequency: Page table lookups occur on each memory reference, which can be costly if executed through software.
  
  

• Role of MMU (Memory-Management Unit): This hardware component is situated between the CPU and caches to optimize the lookup process.

MMU Functions

• Indexing: The MMU indexes into the page-table using the virtual address to retrieve mappings, checking the present bit to determine validity.

• Data Retrieval: If valid, the corresponding physical address is sent to the bus for execution; otherwise, a request to fetch from disk is initiated.

Multi-programming Strategies

• Address Mapping Switching: Address mappings can be altered during context switches to accommodate multiple processes within memory efficiently.

• Process Identification: Augment mappings with additional bits to encode process or address space identifiers.

Page Table Entry Format

• Components of Page Entry: Each entry in the page table includes:

  • Physical Page Number

  • Present/Absent Bit

  • Protection Bits (Read/Write/Execute)

  • Modified Bit (tracked during writes for page write-backs)

  • Referenced Bit (indicates read/write activity on a page)

  • Disable Caching (needed for memory-mapped I/O devices)

Practical Considerations

• Space and Time Issues: Addressing the significant space taken by page tables and the time required for lookups.

Space Concerns

• Size Calculation: Page table sizes can become excessively large. For instance, a 32-bit virtual address space with a 4KB page size would yield around 1 million entries.

• Logic for Sparse Processes: Employing multi-level page-tables leverages sparsity in the process address space.

Example of Linear Page Tables

• Calculation: If each page table entry occupies 8 bytes, a linear page table reflects the size based on the process's virtual address space, significantly larger compared to the actual occupied memory.

Implementation of Multi-level Page Tables

• Hierarchical Structures: A 2-level page table reduces the size considerably by using only necessary pages for mapping, such as 3 pages of page table entries at a 4KB size.

Address Translation Speed Requirements

• Critical Path Importance: Address translation must be fast as it is performed with each memory access instruction (loads/stores), forming the critical path of execution.

• Locality Exploitation: Address translation relies heavily on exploiting locality of access patterns to optimize performance.

TLB Operation

• Definition: TLBs (Translation Lookaside Buffers) serve as caches for page table entries, handling locality effectively.

• Locality Types:

  • Temporal Locality: Suggests that recently accessed data may be re-accessed shortly.

  • Spatial Locality: Indicates that adjacent locations are likely to be accessed soon.

• TLB Cache Capacity: Typically contains 64, 128, or 256 entries for quick access to mappings.

Address Translation Process Steps

1. Address Input: The CPU sends the virtual address to the MMU during instruction fetch or load/store operations.

2. TLB Search: The MMU conducts a parallel search in the TLB to see if the mapping exists.

3. Address Handling: If the mapping is found (TLB hit), the corresponding physical address is returned; otherwise (TLB miss), the MMU performs a lookup in the page table.

4. Table Lookup Result: Upon a successful page table lookup, the physical address is returned, and the mapping is inserted into the TLB, replacing any existing entry as necessary.

Impact of TLB Hits and Misses

• Evaluation of Lookup Times: The hit ratio h significantly influences average lookup times, calculated by the expression:
  $ext{Average Lookup Time} = 20 imes h + 100 imes (1 - h)$

• Criticality of Fast Lookups: Speed in address mapping and retrieval directly impacts system performance due to the continuous access required during execution.

Conclusion

• The address translation and virtual memory systems are crucial to operating system efficiency, enabling the management of larger-than-physical memory applications while optimizing performance through techniques such as paging, TLBs, and multi-level page tables.

• Understanding these components helps develop more efficient computing systems that effectively manage memory resources and maintain high CPU utilization rates.