Virtual Memory

Virtual memory is a memory management technique where the operating system uses a portion of the secondary(backup) memory to simulate additional RAM. The virtual address space and the physical address space, both are divided into sums of equal sizes as with cache; we had blocks so here we have what is called pages.

It's objectives are-

• To overcome the limitation of the physical memory size, with least inconvinience to the programmer so that the programmer does not have to bother about moving the data or instruction between virtual memory or the disk and the main memory.
• To allow multiple programs to share memory without interference.
• To simplify program relocation

Virtual memory is simply an illusion of a memory which is much larger than the physical memory or the main memory. The virtual address space and the physical address space, both are divided into sums of equal sizes called pages and the mapping takes place at the level of page. Virtual memory is implemented using hard disk drive which is non-volatile medium and has larger capacity at lower cost. Each virtual page has a place on the disk while some of these may also be in the main memory memory and it is this subset which is in the main memory can be made to change overtime as the need arises. The implementation of virtual memory relies on utilizing the hard disk drive (HDD) due to its larger capacity and non-volatile nature. In this setup, all virtual pages initially reside on the hard disk, with a subset stored in main memory, subject to change as needed. Both hardware within the processor and software, including the operating system, manage the complexities of virtual memory. However, significant differences exist due to the substantial speed gap between the hard disk and main memory. While hardware efficiently handles cache misses by quickly retrieving data from main memory, software manages the response to virtual memory misses, taking advantage of available time for retrieval. Additionally, terminology differs between virtual memory and caching systems, reflecting historical and design nuances. Effective management of miss rates is crucial in virtual memory systems to optimize performance.

Virtual memory implementation offers a distinct advantage over cache memory with its inherently lower miss rate, primarily due to the larger physical memory size compared to cache size. To keep miss rates low, strategic choices in page size and mapping are essential. Unlike cache memory, which limits block size to balance miss penalties, virtual memory benefits from larger page sizes, typically 4 to 16 kilobytes, enabling better data locality capture. Fully associative mapping is favored over set associative mapping in virtual memory to minimize conflicts and misses. Additionally, virtual memory systems prefer write back over write through strategies to optimize efficiency, despite longer write times.

Choosing an effective replacement policy is crucial in virtual memory management, with the least recently used (LRU) policy widely adopted for its effectiveness, albeit challenging to implement. While time-based tagging proves impractical for tracking usage, alternative approaches such as ordered lists of recently accessed pages or cache blocks are considered. However, the complexity of maintaining such lists poses practical challenges, especially in hardware implementation. Despite the difficulties, virtual memory systems aim to achieve LRU-like behavior to enhance performance.

The above figure which shows virtual memory on one side and physical memory on the other side. Each is divided into pages, each page of virtual memory each virtual page is either mapped to physical memory or to a disk. Each page must have its residence in on disk, some of them will also have residence on the physical memory. A mechanism is necessary to determine given a page where we place it in the physical memory and once we have placed it how it can be found later on. This process is referred to as translation of address.

Consider a virtual address with 32 bits, which can be divided into a page offset and a virtual page number. Assuming a page size of 4 kilobytes, 12 bits would specify the byte within a page, while the remaining 20 bits would represent the page number. With physical memory totaling 2^30 bytes, equivalent to 4 gigabytes, and virtual memory comprising 2^32 bytes, or 1 gigabyte, the physical memory address can also be divided into a page number and offset. The challenge lies in translating the virtual page number into a physical page number, a process requiring careful consideration and planning.

PAGE TABLE:

The page table is a lookup table used to map virtual addresses to physical addresses in virtual memory systems. It's typically implemented as an array or table, with each entry corresponding to a virtual page. Page tables allow for efficient memory management by enabling the system to handle larger address spaces than physical memory sizes while maintaining fast access times.

Lookup Process

1. When a memory access occurs, the system extracts the virtual page number from the virtual address.
2. It then uses the virtual page number to index the page table, retrieving the corresponding page table entry.
3. The page table entry contains the physical page number and a valid bit(0 or 1).
4. If the valid bit is set(1), the physical page number is used to form the physical address. If not(0), it triggers a page fault.

PAGE FAULT HANDLING

1. If the valid bit is not set in the page table entry, indicating the page is not in physical memory, a page fault occurs.
2. First of all the current process which had made this request is suspended.
3. The operating system then fetches the required page from disk into physical memory.
4. Meanwhile the disk is ready, several milliseconds are going to elapse and can execute thousands and thousands of instructions so control is transferred to another process which is waiting for execution.
5. Once fetched, the page table is updated with the new physical page number, and the instruction is re-executed.

COMPARISON WITH CACHE

Cache	Page table
Directly access cache blocks based on index bits without consulting a lookup table initially.	Requires a lookup process through the page table to translate virtual addresses to physical addresses before accessing physical memory.
Can be direct-mapped or fully associative, with fixed or flexible mappings of memory blocks to cache lines.	Each virtual page has a one-to-one mapping with a physical page, eliminating the need for tag comparisons.
Number of entries equals the number of cache blocks.	Number of entries equals the number of virtual pages in the address space.
Direct-mapped caches offer faster access but may suffer from higher cache misses compared to fully associative caches.	Adds an extra step in memory access but facilitates efficient management of larger address spaces in virtual memory systems.

**HOW BIG IS THE PAGE TABLE? ** add address translation dia

Suppose the virtual address is 32 bits, page size is 4 kilobytes and each page table entry is 4 bytes.

Virtual address: 32 bits

Page size: 4 kilobytes (or 2^12 bytes)

Page table entry size: 4 bytes

Page table entry structure: Valid bit + Physical page number + Additional information

Calculating Number of Page Table Entries

Number of virtual pages = Total virtual memory size / Page size

                    = 2^32 / 2^12 

                    = 2^20

Each virtual page corresponds to one entry in the page table.

Size of Page Table

Size of the page table = Number of page table entries × Size of each entry

                   = 2^20 entries × 4 bytes per entry 

                   = 2^20 × 4 bytes

                   = 4 megabytes.

Now there are hundreds and thousands of processes each one has to consider and they are allocated with same amount of virtual space. Trying to stuff it with several hundreds of page tables will simply leave no space for other useful things.

HANDLING LARGE PAGE TABLES:

1. BOUND THE PAGE TABLE SIZE:

• To efficiently manage memory usage and accommodate the dynamic needs of programs, a technique called "bound the page table size" can be employed.

• Dynamic Memory Allocation: Instead of allocating a fixed amount of virtual memory space to each program, the system dynamically adjusts the size of the virtual memory space based on the actual memory requirements of the program.

• Register for Bound Tracking: A register is used to keep track of the upper bound of the program's virtual memory space. This bound can be adjusted dynamically as the program's memory requirements change.

• Reduced Page Table Size: By adjusting the virtual memory size, the size of the page table is also reduced accordingly. This ensures that only the necessary portion of the page table is allocated, reducing memory overhead.

• Independent Growth of Stack and Heap: Programs typically have two dynamically growing areas: the stack and the heap. By allowing these areas to grow independently in opposite directions, memory usage can be optimized.

2. EXPLOIT SPARSENESS

• The inverted page table approach efficiently manages sparse virtual memory systems by using associative memory structures.
• It reduces memory overhead by storing entries only for pages present in physical memory, organized based on physical page numbers.
• Hashing techniques are applied to quickly retrieve physical page numbers corresponding to virtual page numbers, resembling a cache-like organization.

This approach optimizes memory usage and enhances performance in virtual memory management.

3. USE MULTIPLE LEVELS [TWO LEVEL]

In the context of managing virtual memory efficiently, a common technique is to use either a two-level page table or paging the page table.

Segmented Virtual Memory

• The virtual address space is organized into segments, which are larger chunks of memory.
• Each segment is further divided into smaller units called pages.

Page Tables for Segments

• Instead of having a single page table for the entire virtual address space, one page table is allocated for each segment.
• This allows for flexibility in memory management, as only the relevant page tables need to be kept in the main memory at any given time.

Segment Table Management

• A segment table is used to keep track of the location of page tables.
• It indicates which page tables are currently in main memory and which are stored on disk.
• By tracking only the active page tables, memory usage is optimized.

TWO LEVEL PAGE TABLE STRUCTURE

Each segment of memory has its own page table, labeled from 0 to n-1. These smaller page tables are more manageable and require less memory than a single large page table. Additionally, not all of these page tables need to reside in main memory at the same time, allowing for better memory utilization.

To access a specific page table, the system first consults a segment table. This table contains entries pointing to the starting addresses of the page tables for each segment. When a virtual address is provided, it is divided into three parts: the segment number, the page number within the segment, and the byte number within the page.

By using the segment number extracted from the virtual address, the system can efficiently locate the corresponding entry in the segment table. This entry then provides the starting address of the page table for the specific segment. This segmented approach to page table management enhances memory efficiency and allows for more flexible memory allocation.

Using the page number from the virtual address, it indexes into the page table to retrieve the physical address or page number. If the page table is in physical memory, this two-step process efficiently locates the desired entry. However, if the page table is not in memory, a page fault occurs, necessitating the table's retrieval into memory.

The segment table's starting address is often stored in a register for quick access. Page faults can happen at either the page table or specific page level, prompting the system to load necessary data into memory before continuing the memory access operation.