Desktop version

Home arrow Computer Science

  • Increase font
  • Decrease font

<<   CONTENTS   >>

Virtual Memory


In the early days of computers, memories were expensive and small, and a large program was then traditionally executed with the use of secondary memory, such as disk. A particular strategy was then used, called Overlays, in which a large program to be placed in the disk is divided by the developer into a number of small independent pieces (modules), such that each piece could be then fit into the available main memory. When the large program is executed, the overlay mechanism properly monitors the to and fro journey of each of these small modules from disk to main memory as and when needed and vice-versa, in place of fetching the entire large program in the small available memory. Here, the programmer has to do everything in relation to create and manage the overlays, and as such, they must have the required expertise about the overlay technique and its implementation, apart from having adequate skill to develop the algorithms to solve their own problems. The overlay technique could, however, somehow handle the more complicated time-sharing multiprogramming environment of those days, but that too in a limited way, and thus has been in wide use for this purpose over many years, and is still in heavy use for different purposes.

In 1961, a group of people at Manchester, UK, proposed a method for the automatic execution of the overlay process without any involvement and intervention of the programmers, and even no intimation to them about its internal working. This approach has been subsequently implanted in what is now called virtual memory. This memory is created in a portion of the secondary memory by computer hardware, and casts an illusion to the user as if a large memory space, almost equal to the totality of secondary memory, is available to them for their use. It is physically a part of secondary memory, but behaves like a primary memory to the user, that is why, it lies somewhere in between primary memory and secondary memory, and hence, is legitimately called virtual memory. Virtual memory on its own automatically monitors the two levels of the memory hierarchy represented by main memory and secondary storage. But, it should, however, be noted that while virtual memory is created by the computer hardware, but is managed only by the operating system. That is why discussions over virtual memory appear both in the domain of computer architecture as well as in the operating system. It was first used in the computers during the 1960s, and by the early 1970s, virtual memory has been available on almost all computers. Even earlier microprocessors, including Intel 80386 and Motorola 68030 had a highly sophisticated virtual memory system. Without virtual memory, it would have been impossible to develop a time-sharing multi programmed computer system that is most common in any present-day environment.

Address Space

Each word in the physical memory is identified by a unique physical address and all such memory words in the main memory form a physical address space or memory space. In systems with virtual memory, the address generated during the compilation of a program, and subsequently used by the system is called the virtual address, and the set of such addresses form a virtual address space or simply address space. The users are informed that they have such total address space for their use. During execution, the virtual addresses are issued by the processor, but memory addresses only are required for processing. That is why, only currently executable programs or parts of the programs are brought from virtual memory into a smaller amount of physical memory which are then shared among those programs. The virtual addresses of the executing program while being issued must be then translated into their corresponding physical addresses of the locations where the said program (or part of the program) is placed in the main memory. However, the address translation mechanisms and management policies being used are often affected by the virtual memory model used, and by the organisation of the disk arrays, and certainly also of the main memory. Virtual memory approach also simplifies loading of the programs for execution, and permits necessary relocation of codes and data, allowing the same program to run in any location in physical memory with appropriate address mapping as discussed later.

Address Mapping

With virtual memory, the CPU generates virtual addresses, which are then translated by a combination of hardware and software tools to physical addresses that are used to access main memory. This process is called memory mapping or address translation. Let V be the virtual addresses generated by the CPU during the execution of a program. Let M be the set of physical addresses assigned and allocated to run this program. The automatic mechanism of a virtual memory system implements the following mapping:

Since the physical memory location of any particular virtual address is dynamically (during run time) allocated and deallocated, the same virtual address may be allocated at different memory locations at different times during execution. Hence, mapping is a function of time. Thus, mapping can be elaborately defined as:

when the virtual address v can be uniquely mapped into m by the function f(v), there is a memory hit in M. When/(i>) = ф, this indicates that the referenced item addressed by v is not found at that time in memory, the situation is a memory miss. The performance of the virtual memory is highly influenced by the efficiency of this address translation process. In a multiprocessor system, the implementation of virtual memory is even more complex due to presence of additional problems like protection, coherence, and consistency, and hence, different types of address translation mechanisms are employed that mostly depend on the architecture of the computer systems.

Types of Virtual Memory

The virtual address space is divided into units (similar to modules used in the overlay approach) called pages, and the corresponding unit of same size in the physical memory are called page frames or blocks. Two types of virtual memory models are common. They are the following:

i. Private virtual memory which is used both in uniprocessor (single CPU) and in multiprocessor computer system. In case of a uniprocessor system, the entire virtual memory space is assigned to the single processor, no question arises with regard to being private or public. In case of a multiprocessor system, each processor is given a private virtual memory space. Virtual pages from different virtual spaces are mapped into the same physical memory. Here, the physical memory is shared by all processors.

ii. Shared virtual memory, in which different disjoint virtual address spaces for different processors are present in a single globally shared virtual space. An appropriate locking mechanism is required to safeguard each virtual space for making them to be mutually exclusive. Some areas of virtual space can also be shared by multiple processors at the same time.

A brief detail of this topic with appropriate figures is given in the following web site:

Address Translation Mechanisms

This mechanism involves the translation process of virtual addresses to physical addresses as shown in Figure 4.13. Various schemes for the translation process are in wide use. In any case, the translation process requires the use of translation maps or mapping table which can be realized in various ways. The mapping table may be stored

a. in a separate cache memory

b. in main memory

c. in associative memory.

For the case (a) above, an additional memory unit is required as well as one extra memory access time. For the case (b), the table itself takes space from main memory reducing the available area for the user to use. Moreover, two access to memory is required to provide data to CPU, in effect, the program will be then running at half speed.

Wherever the mapping table is stored, a mapping function is applied to the virtual address to generate a pointer to the mapping table. Both the main memory and virtual memory can be handled with either paged memory management or segmented memory management. But we confine our approach here only with paged memory management. Both the physical (main) memory and virtual memory are divided here into fixed-size


A scheme of mapping a virtual address to a physical address using memory map table.

units, called page frames and pages, respectively. Page tables (if more than one) are created, and are used as a mapping table to translate between pages and page frames. The page table entries are essentially containing address pairs (virtual page, page frame). As an analogy, у =f(x) if x is the page,/is the page table, then у is the page frame. All exchange of information between virtual memory and main memory is carried out at the page level. As soon as an application program enters the execution state, the related information is injected into the page table. One page table can be created to accommodate many user processes or each process can use its own page table, and hence, the number of page tables (due to many processes being active) maintained in the main memory can be then very large.

Address translation mechanism and related virtual memory management functions are handled by a specialized unit called a memory management unit (MMU) which is nowadays inside the CPU, and is positioned between the effective-address generation unit (EAU) of the CPU and main memory as shown in Figure 4.13. MMU receives virtual addresses from the EAU, and converts them to the corresponding physical addresses for transmission to M or to memory cache, if it is present. The MMU also handles memory protection violation, swapping of data between main memory and secondary memory, and other exceptional situations that might happen.

<<   CONTENTS   >>

Related topics