Topic 7 - Virtual Memory

Chapter Overview

• Virtual Memory involves techniques to manage memory allocation, allowing secondary memory to be treated as part of main memory.

Outlines

• Overview of key topics:

  • Hardware and Control Structures

  • Locality and Virtual Memory

  • Paging

  • Segmentation

  • OS Software

  • Fetch Policy

  • Placement Policy

  • Replacement Policy

Virtual Memory Terminology

• Virtual Memory: A scheme where secondary memory is addressed as if it were main memory.

  • Addresses generated by programs are distinct from physical addresses used by the memory system.

  • Limited by computer system's addressing scheme and available secondary memory.

• Virtual Address: Assigned to a location in virtual memory to be accessed as main memory.

• Virtual Address Space: The virtual storage assigned to a process.

• Address Space: Range of memory addresses available to a process.

• Real Address: Actual storage location's address in main memory.

Hardware and Control Structures

• Two fundamental memory management characteristics:

  1. All memory references are logical addresses dynamically translated to physical addresses at runtime.

  2. A process can be divided into non-contiguous pieces in main memory.

• Not all pages or segments must be in memory simultaneously for execution.

Execution of a Process

• The OS loads parts of the program into main memory:

  • Resident Set: Portion of a process currently in memory.

  • An interrupt occurs when a required address is not in memory, leading to a blocking state for the process.

• Disk I/O Read Request: When a logical address is being brought into memory, another process runs while waiting for the disk I/O.

  • Upon completion, the OS places the affected process back in the Ready state.

Implications of Virtual Memory

• Enhances memory utilization by allowing more processes to reside in memory.

• Processes may exceed physical memory size; OS utilizes paging or segmentation for efficient loading.

  • The OS dynamically loads required pieces of a process.

• Enables smoother multitasking and efficient processor utilization.

Real vs. Virtual Memory

• Real Memory: Actual RAM in a system.

• Virtual Memory: Disk storage that complements RAM, enabling multiprogramming and reducing constraints of main memory.

Characteristics of Paging and Segmentation

• Paging:**

  • Main memory partitioned into fixed-size frames.

  • Internal fragmentation occurs, but not external fragmentation.

  • Requires a page table for managing process addresses.

• Segmentation:

  • Segments based on programmer-defined structures; varies in size.

  • No internal fragmentation; may lead to external fragmentation.

  • A segment table tracks each segment’s address and length.

Thrashing

• A situation where the system spends excessive time swapping pieces instead of executing instructions.

• The OS predicts least-frequently used pieces to minimize thrashing occurrences.

Principle of Locality

• Memory references typically cluster to a few pieces of a process over short periods, allowing predictive loading of needed items to minimize thrashing.

Support for Virtual Memory

• Requires hardware support for paging and segmentation.

• The OS software must manage the movement of pages or segments effectively between secondary and main memory.

Paging Mechanism

• Pages facilitate virtual memory, as seen in systems like the Atlas computer.

  • Each process has a unique page table, containing frame numbers for the pages in RAM.

Address Translation

• Utilizes Translation Lookaside Buffer (TLB) for quick access to page table entries, reducing the number of memory accesses required.

  • Each memory reference may involve fetching the page table entry and obtaining data itself, potentially doubling access time.

Page Size Considerations

• Smaller pages reduce internal fragmentation but can increase the size of page tables.

• Larger page sizes favor efficient data transfer from secondary memory, balancing overall memory management characteristics.

Segmentation Advantages

• Memory organized into segments allows easier management of growing data structures.

• Enhances program updates and sharing between processes while providing protection.

Operating System Policies for Virtual Memory

• Key decisions include:

  • Fetch Policy: Determines when to load pages (demand paging vs. prepaging).

  • Placement Policy: Where in memory to place process pieces.

  • Replacement Policy: Which page to replace when memory is full.

Fetch Policy – Demand Paging

• Pages are only brought into memory upon reference, often leading to high initial page faults but stabilizing over time due to locality principles.

Fetch Policy – Prepaging

• Anticipates future needs by loading additional pages, which is efficient if the pages are stored contiguously, but may introduce inefficiency if extra pages go unused.

Replacement Policy

• Determines which page to replace, aiming for the least likely referenced page to minimize overhead costs.

• Common strategies:

  • Optimal, Least Recently Used (LRU), First-In-First-Out (FIFO), Clock.

Specific Replacement Algorithms

• LRU: Replaces the least recently accessed page; complex due to tracking access history.

• FIFO: Simplistic circular buffer approach; removes the oldest page regardless of use.

Summary of Key Concepts

• Overview of essential concepts related to virtual memory:

  • Hardware and control structures

  • Locality and virtual memory principles

  • Paging and segmentation characteristics

  • Role of OS software in memory management policies.

Chapter Overview

Virtual Memory is a vital concept in modern operating systems, encompassing techniques for managing memory allocation. These techniques enable the computer to treat secondary memory (like hard drives or SSDs) as an extension of the main memory (RAM), allowing for more efficient use of memory resources and enhancing system performance.

Outlines

Overview of key topics:

• Hardware and Control Structures: Understanding the underlying hardware and how it interacts with virtual memory.

• Locality and Virtual Memory: The principle of locality, emphasizing how programs often access a small portion of memory frequently, impacting virtual memory management.

• Paging: A method of dividing memory into fixed-size blocks to facilitate easier management and allocation.

• Segmentation: Differentiating memory into segments that reflect the program's logical structure rather than fixed sizes.

• OS Software: The software components that manage virtual memory.

• Fetch Policy, Placement Policy, Replacement Policy: Strategies used by the operating system to manage the movement and allocation of pages in memory.

Virtual Memory Terminology

• Virtual Memory: A system whereby secondary memory is addressed as though it is part of primary memory (RAM). It allows for larger processes to be run, even if they do not fit into main memory all at once.

• Virtual Address: An address used by a program to access a location in virtual memory, which may differ from the actual physical address.

• Virtual Address Space: The total range of addresses that a process can use; each process has its own virtual address space.

• Address Space: The available range of memory addresses that a process can utilize to store data.

• Real Address: The actual location of data in RAM, referred to during physical memory access.

Hardware and Control Structures

Two fundamental characteristics of memory management in virtual systems:

1. Logical Addressing: All memory references during execution are logical addresses that get translated into physical addresses dynamically.

2. Non-contiguous Execution: A process's memory can be scattered throughout physical memory; it is not required that every page or segment be loaded into memory at the same time for a process to execute successfully.

Execution of a Process

• Loading in Memory: The operating system (OS) loads the parts of a program that are needed into main memory based on demand.

• Resident Set: The active portion of a process's memory that currently resides in physical RAM, enabling quick access to active instructions and data.

• Interrupt Handling: An interrupt occurs when a process tries to access a memory address not found in the resident set, leading to a state called "page fault," where the process is blocked until the required data is loaded.

• Disk I/O Read Request: This allows another process to execute while the system fetches the necessary data from secondary storage, ensuring efficient CPU utilization.

Implications of Virtual Memory

Virtual memory significantly enhances overall memory utilization by transforming how processes are loaded and managed:

• Scalability: Processes can use more memory than may be available physically due to the OS using paging and segmentation strategies.

• Multitasking Efficiency: Virtual memory enables multiple processes to run simultaneously, as the OS handles memory allocation dynamically, improving efficiency and system responsiveness.

Real vs. Virtual Memory

• Real Memory: The physical RAM directly used by the system to store data.

• Virtual Memory: Storage on disk that acts as an overflow for RAM, allowing systems to effectively handle situations where the demand for memory exceeds physical memory availability, facilitating multiprogramming and reducing constraints imposed by finite RAM.

Characteristics of Paging and Segmentation

• Paging: Main memory is divided into equal-sized frames. This method can lead to internal fragmentation since not all space in a frame may be utilized, but it avoids the complexities associated with external fragmentation. Each process has a page table corresponding to its virtual addresses.

• Segmentation: Memory is divided into segments of varying sizes based on the program's logical structure (e.g., functions, arrays). While it eliminates internal fragmentation, it can result in external fragmentation due to the varying size of segments.

Thrashing

Thrashing happens when the operating system spends excessive time managing the loading and swapping of pages rather than executing processes. It frequently occurs when there are not enough frames allocated to active processes. To minimize thrashing, the OS attempts to predict the least-used pages and manage load in an optimized manner.

Principle of Locality

This principle reflects the tendency for memory references to cluster around certain active segments. Programs often access the same data or instructions over short periods, permitting the OS to load required items preemptively, thus reducing the frequency of page faults and enhancing performance.

Support for Virtual Memory

For effective operation, virtual memory requires:

• Hardware Support: Features in the CPU and memory management unit (MMU) to facilitate paging and segmentation.

• OS Management: Software mechanisms that intelligently handle the transfer of data between secondary memory and RAM, maintaining pace with program demands.

Paging Mechanism

Paging underpins virtual memory systems like the Atlas computer:

• Each process is allocated a unique page table that maintains its mapping of virtual pages to frames in RAM, thus facilitating effective addressing and memory management.

Address Translation

The Translation Lookaside Buffer (TLB) acts as a cache for page table entries to accelerate access times, thereby minimizing the number of memory accesses needed during execution.

Page Size Considerations

• Smaller page sizes generally reduce internal fragmentation; however, they can lead to larger page tables due to the increased number of pages.

• Conversely, larger pages, while less efficient in terms of addressing simplicity, can enable more effective data transfer from secondary storage, optimizing overall memory management.

Segmentation Advantages

Leveraging memory organized into segments aids in managing dynamic data structures effectively, supports program upgrades, and allows sharing of code and resources across processes with enforced protection mechanisms.

Operating System Policies for Virtual Memory

The OS must make critical decisions governing the management of virtual memory, such as:

• Fetch Policy: When the OS decides to load pages; this can be either demand paging (loading pages when required) or prepaging (anticipating future requirements).

• Placement Policy: Directions on where in main memory incoming pages should be placed.

• Replacement Policy: Guidelines for which loaded pages to discard to make room for new pages when memory is full.

Fetch Policy – Demand Paging

In demand paging, pages are only loaded when referenced, resulting in an initial spike in page faults but generally stabilizing as locality helps in maintaining required data in memory over time.

Fetch Policy – Prepaging

The OS anticipates potential page references and loads additional pages pre-emptively. While this can be efficient when pages are contiguous, it may also result in unnecessary memory load when the predicted pages are not used.

Replacement Policy

Determining which page to replace is critical and involves strategies to minimize performance overhead:

• Optimal: Replaces the page that will not be used for the longest period in the future.

• Least Recently Used (LRU): Removes the least recently accessed page, although it can be complex due to tracking access patterns.

• First-In-First-Out (FIFO): Simplistic method that removes the oldest page in memory, without considering how often it has been accessed.

• Clock: A more efficient variant of FIFO that maintains a circular buffer and allows for better decision-making on replacements based on reference bits.

Summary of Key Concepts

This overview encapsulates the essential concepts related to virtual memory, focusing particularly on:

• Hardware and control structures involved.

• Principles of locality and patterns of memory references.

• Detailed characteristics of paging and segmentation techniques.

• The pivotal role of operating system software in managing memory policies effectively, ensuring optimal utilization of resources and performance enhancement.