Virtual Memory | Address Mapping | Computer Architecture

Virtual Memory – In the memory hierarchy system, the information is stored in auxiliary memory. Whenever it is needed by the CPU, information is brought into main memory. Virtual memory is a concept used by the operating system.

This concept gives the illusion to the programmer or user that a larger memory space is available, which is equal to the totality of auxiliary memory. In this concept, the physical address referenced by the CPU goes through a mechanism called address mapping. The newly generated address is called a virtual address. This is done dynamically while programs are executed in the processor.

The translation or mapping is handled automatically by the virtual memory systems by means of a mapping table. The virtual address is used by a programmer, and the set of such addresses is named the address space. An address in main memory is called a physical address, and a set of such addresses is called the memory space. The address space is allowed to be larger than the memory space in computers with virtual memory. The computers which are not having virtual memory concept have the same memory space and address space. The address and memory space are divided into groups of fixed size. The groups in the address space are called pages. The term block refers to groups of memory space of the same size.

Virtual Memory Example

Consider an example of a computer with an address space of 8k and a memory space of 4k. If address and memory space are divided into groups of 1k words, eight pages, and four blocks are obtained as shown in the figure below. The figure shows that at any time, up to four pages of address space may reside in the main memory in any one of the four blocks.

Virtual Memory Address Mapping Techniques

The virtual address space is defined as the set of all locations that can be referenced by the programmer. To execute the program, the virtual address must be mapped to the physical address in main memory. This process is defined as address mapping. The physical addresses in main memory are sequential in nature, whereas virtual addresses used by the programmer may be non-linear in nature. 

Therefore, before executing a program, it and its data must be linearized by transforming them into a set of contiguous word sequences. Each word sequence must also fit in the main memory 

There are two address mapping techniques that are used to map the virtual addresses into physical addresses.

1. Paging
2. Segmentation

Paging

The paging is hardware oriented technique for managing physical memory. This is introduced so that large programs can run on computers with small physical memories. In this, the computer loads into main memory only those parts of the program that it currently needs for execution. The remaining part of the program resides in external storage until needed.

In a paging system, the virtual address is considered to be represented by two numbers: a page number address and a line number within the page. The line number of the line address is the same. The only mapping required is from a page number to a block number. The organization of memory mapping using the page system is shown below. The memory page table consists of eight words, one for each page. The content of the word denotes the block number where the page is stored in main memory. A presence bit is also attached to each word, which indicates whether the page has been transferred from auxiliary memory to main memory or not. A ‘1’ in the presence bit indicates, page is available in main memory, whereas ‘0’ indicates the unavailability of the page in main memory.

Let the virtual address be (1001010111001)₂. The page number of this address (100)₂, whereas the line number is (1010111001)₂, as shown in the figure above. The memory page table shows that pages (001)₂, (010)₂, (100)₂, and (110)₂ are now available in main memory. The contents of the word in the memory page table at the page address are (10)₂ or (2)_10. The corresponding presence bit is 1. It means the desired page (page number 100₂) is transferred to the main memory in block 2. The line number from the virtual address is transferred into the low-order bits of the memory address register. Now the physical address is available, and the data in block 2 with line number address (1010111001)₂, will be moved to the memory buffer register (MBR) for further processing.

Page Fault:

A virtual memory system is a combination of hardware and software techniques. The software part of the system decides

1. Which page in main memory should be removed to make free space available for a new page. 
2. When a new page is to be transferred from auxiliary memory to main memory. 
3. Where the page is to be stored in main memory. 

The hardware part of the virtual memory system is responsible for the memory mapping mechanism.  When a program starts execution, one or more pages are transferred into main memory, and the page table is set to indicate their position. The program is executed from the main memory until it attempts to reference a page that is not available in main memory and is still in the auxiliary memory. This condition is called a page fault.

If a page fault occurs during execution, the program is suspended, and the required page will be loaded into main memory. If the main memory is full, it would be necessary to remove a page from the memory block to make space for a new page. Two algorithms are used for the replacement procedure: (i) first-in first-out (FIFO) and (ii) least recently used (LRU). As the name suggest the FIFO algorithm selects for replacement the page that has been in memory from the longest time. The LRU algorithm works on the assumption that the least recently used page is a better choice for removal.

Segmentation

Another method of address mapping is named segmentation. In the segmentation technique, a program is divided into variable-length sections. These sections are called segments. A segment can be a set of data or a function within the program. This technique keeps a table, named the segment table, which contains the same information that the page table contains in paging. 

Segmentation has a number of advantages to the programmer over a non-segmented space :

1. It simplifies the handling of data structures. The data structure can be assigned its own segment, and the operating system will expand or shrink the segment as needed. 
2. Segmentation allows the programmer to alter and recompile a portion of a program without requiring the complete program to be relinked and reloaded. 
3. It allows sharing among various processes. A program can place a utility program in a segment that can be addressed by other processes.
4. It provides protection because a segment can be constructed to contain a well-defined set of programs or data. Various access privileges can be provided to that segment to different authorities.

The above mentioned advantages are available with segmentation, whereas paging provides an efficient form of memory management. These two can be combined to obtain the advantage of two. This is called segmented page mapping.

In segmented page mapping, the virtual address is divided into three fields :

1. Segment number 
2. Page number. 
3. Word offset (Line number). 

In the same way, a physical address has two fields: 

1. Block number. 
2. Word offset 

The segmented page mapping is performed with the two mapping tables, the segment table and the page table, as shown in the figure below. The segment number of the virtual address specifies the address for the segment table. The entry in the segment table is a pointer address for a page table base. The page table base is added to the page number given in the page field of the virtual address. The sum produces a pointer address to an entry in the page table. The value retrieved from the page table gives the block number in physical memory. The concatenation of the block field with the word field produces the final physical mapped address.

Difference Between Paging and Segmentation

Paging and segmentation are two techniques that are used for address mapping. There are differences between these two techniques, as follows:

1. Paging requires a simpler memory allocation than segmentation. 
2. Paging is hardware-oriented, whereas segmentation reflects the logical structure of the program. 
3. Paging partitions the physical address space while segmentation partitions the virtual address space.
4. Pages have a fixed size for a given system, and segments may have different sizes in a given system. 
5. In paging, the entire program needs to be created as a single module to be loaded into memory as a unit. This is not required for segmentation.
6. Segmentation has external fragmentation, while no external fragmentation occurs in paged systems, but internal fragmentation may occur.