Virtual Memory

Virtual memory is a memory management technique used by computer operating systems to provide an illusion of a larger, contiguous, and more accessible memory space than the physical RAM (Random Access Memory) available on a system.

Here’s an explanation of virtual memory:

Purpose:

Virtual memory allows programs to use more memory than physically available by utilizing disk storage as an extension of RAM.

Address Space:

Each process is given its own virtual address space, which may exceed the physical RAM capacity.

Paging:

Virtual memory divides memory into fixed-size blocks called pages. When a process requests memory, the OS maps pages between physical RAM and disk storage.

Page Faults:

If a requested page is not in physical RAM (a page fault), the OS swaps out a less-used page from RAM to disk and loads the required page from disk into RAM.

Demand Paging:

Only pages needed by the program are loaded into physical memory, reducing initial memory overhead.

Swap Space:

Disk space reserved by the operating system for storing pages temporarily when physical RAM is full.

Performance:

Virtual memory allows for efficient multitasking and enables running large programs, but excessive paging can lead to performance degradation due to disk I/O.

TLB (Translation Lookaside Buffer):

A cache-like structure that stores recently accessed virtual-to-physical address translations, speeding up memory access.

Fragmentation:

Virtual memory can suffer from fragmentation, both internal (within pages) and external (between pages), impacting performance and efficiency.

Management:

Virtual memory is managed by the operating system’s memory management unit (MMU) and includes algorithms for page replacement, allocation, and address translation.

Overcommitment:

Some operating systems allow overcommitment, where the total virtual memory allocated to processes exceeds the physical RAM plus swap space, relying on the assumption that not all processes will require all their allocated memory simultaneously.

Address Space and Memory Space:

An address used by a programmer will be termed as a virtual address and set of such addresses is the address space.

• An address in main memory is known as a physical address.

• The set of these locations is termed as memory space. So address space is set of addresses produced by programs as they reference instructions and data, memory space comprises actual main memory locations directly addressable for processing.

Diagram of Address Space and Memory Space:

• Supposes a computer which has a main-memory capacity of 64K words (K=1024). 16-bits are required to specify a physical address in memory because 64K = 2¹⁶. Assume that computer has auxiliary memory for storing information equivalent to capacity of 16 main memories. Let’s signify address space by N and memory space by M we then have for this illustration: N = 16 × 64 K = 1024K and M = 64K.

• In a multiprogramming computer system, data and programs are transferred to and from auxiliary memory and main memory based on demands obliged by CPU. Suppose program 1 is currently being executed in CPU. Program 1 and a part of its associated data are moved from secondary memory in the main memory as displayed in Figure below. Parts of programs and data require not being in contiguous locations in memory because information is being moved in and out and empty spaces may be available in scattered locations in memory.

Address Mapping Using Pages:

A physical memory is broken down into groups of equal size called blocks or page frame and the groups of address space of the same size as block is called pages.

Consider a computer a with address space =8K and memory space=4K

Associative Memory Page Table:

An associative memory page table is a data structure used in computer operating systems to translate virtual addresses generated by the CPU into physical addresses in main memory (RAM).

• Unlike traditional page tables that use hierarchical structures like tables or trees, an associative memory page table employs associative memory (also known as content-addressable memory or CAM) to enable rapid address translation.

Here’s how an associative memory page table works:

1. Translation Process:
   • When a CPU generates a virtual address, it needs to be translated into a physical address to access data in main memory.
   • The virtual address typically consists of a page number and an offset within the page.
   • The associative memory page table stores mappings between virtual page numbers and corresponding physical page frame numbers.
2. Content-Addressable Memory (CAM):
   • Associative memory allows for parallel search and retrieval based on content rather than addresses.
   • In the context of a page table, each entry in the associative memory contains a virtual page number (or a portion thereof) and the corresponding physical page frame number.
   • When the CPU generates a virtual address, the virtual page number is presented to the associative memory, which searches for a match.
   • If a match is found, the associated physical page frame number is retrieved, enabling the CPU to access the corresponding data in main memory.
3. Rapid Address Translation:
   • The use of associative memory for page table lookup enables rapid address translation, as the entire memory can be searched in parallel for a matching virtual page number.
   • This approach eliminates the need for sequential searches typically associated with hierarchical page table structures, resulting in faster address translation and reduced memory access latency.
4. Scalability and Efficiency:
   • Associative memory page tables can efficiently handle large address spaces, as the search time remains constant regardless of the number of entries in the page table.
   • Additionally, associative memory page tables are particularly suitable for systems with variable memory allocation requirements, as they can dynamically adapt to changes in the mapping between virtual and physical addresses.

Page Replacement:

Page replacement is a crucial aspect of virtual memory management in operating systems.

• When a program requires more memory than is physically available, virtual memory allows the operating system to use disk storage as an extension of RAM.

• However, since physical memory is limited, the operating system must decide which pages of memory to keep in RAM and which ones to swap out to disk. Page replacement algorithms govern this decision-making process.

Here’s how page replacement in virtual memory typically works:

1. Page Fault:
   • When a program attempts to access a page that is not currently in RAM, a page fault occurs.
   • The operating system intercepts this page fault and triggers a page replacement algorithm to select a page to evict from RAM to make space for the requested page.
2. Page Replacement Algorithms:
   • Various page replacement algorithms exist, each with its own criteria for selecting which page to replace.
   • Common page replacement algorithms include:
     • Optimal: Replaces the page that will not be used for the longest period in the future. This algorithm provides the best possible theoretical performance but is impractical to implement as it requires knowledge of future memory accesses.
     • FIFO (First-In-First-Out): Replaces the oldest page in memory, i.e., the page that has been in memory the longest. It’s simple to implement but may suffer from the “Belady’s anomaly,” where increasing the number of frames can lead to an increase in page faults.
     • LRU (Least Recently Used): Replaces the page that has not been accessed for the longest period of time. This algorithm is more complex to implement but generally performs well in practice.
     • LFU (Least Frequently Used): Replaces the page with the fewest accesses since it was loaded into memory. This algorithm considers the frequency of page accesses.
     • Clock (Second-Chance): Similar to FIFO but incorporates a “use bit” for each page to determine whether it has been accessed since the last examination. Pages are evicted if their use bit is not set.
     • LRU Approximation: Provides an approximation of LRU using additional data structures or algorithms that are simpler to implement but still aim to evict the least recently used pages.
3. Page Replacement Process:
   • When a page is selected for replacement, the operating system writes the page’s contents back to disk if it has been modified (dirty), updating the corresponding page table entry to indicate that the page is no longer in memory.
   • The operating system then loads the requested page from disk into the newly vacated memory frame and updates the page table accordingly.
   • Finally, the program’s execution resumes, and the requested memory access is allowed to proceed.