Chapter 13: Virtual Memory

In this chapter, we introduce virtual memory. Most modern computer systems use a hard driver made of magnetic or solid-state storage as the lowest level in the memory hierarchy. The virtual memory is located in the lowest level of the memory hierarchy while still provide the speed of faster memory for most accesses. Processors can access data anywhere using virtual addresses that specify the location in virtual memory. We also introduce virtual memory definitions and show how to translate the virtual address into the physical address.

Objectives

By the end of this chapter you should be able to:

• Differentiate virtual and physical addresses
• Identify the difference between virtual memory analogue and cache memory analogue
• Recognize the address translation in virtual address
• Carry out the address translation from virtual address to physical address
• Demonstrate knowledge of page table
• Identify features of translation lookaside buffer

13.1 Virtual Memory Address

There are three memory types in the memory hierarchy, i.e. cache, main memory, virtual memory, as shown in the following figure. As we discuss in the cache memory, the cache memory (SRAM) is fast but it can only keep small amount of data because it is very expensive. The virtual memory gives the illusion of bigger memory. Ideally, we have no limitation to store data in the virtual memory, where the main memory (DRAM) acts as cache for hard disk. That means we can make a copy a chunk of data from virtual memory to main memory.

Fig. ‑. Memory Hierarchy Pyramid

The following table describes the cache and virtual memory analogues.

Table ‑. Cache/Virtual Memory Analogues

When the system makes a copy data from main memory to cache memory, it does in a unit of block, where cache memory is exactly a memory unit. When the system makes a copy data from virtual memory to main memory, it does in a unit of page. Virtual memory is not a memory unit, it is a technique. The page size is the amount of memory transferred from hard disk (Virtual memory) to DRAM at once. The typical page size is between 1 KB and 8 KB and is generally 4 KB for 32-bit systems. The page number is the number of bits required to represent the pages in Virtual Address Space, where the page offset is the number of bits required to represent particular word in a page or page size of Virtual Address Space or word number of a page.

The data is stored in virtual memory and processors use virtual addresses when they execute. The entire virtual address space is stored on a hard drive and only subset of virtual address data moves in physical memory (DRAM). Accordingly, CPU translates virtual addresses into physical addresses (DRAM addresses) so that it can find the physical location of data in DRAM. If data is not in DRAM fetched from hard drive, it is called “page fault”, which is a similar concept of “miss”. As shown in the following figure, the address translation determines physical address from virtual address, where the page table is used as a lookup table to translate virtual addresses to physical addresses.

Fig. ‑. Virtual and Physical Addresses

As shown in the above figure, Virtual memory is divided into virtual pages, typically 4 KB in size. Physical memory is likewise divided into physical pages of the same size (4 KB). A virtual page may be located in physical memory (DRAM) or on the disk. Some virtual pages are present in physical memory, and some are located on the disk. The process of determining the physical address from the virtual address is called address translation. When we execute a program, we expect that most memory accesses got hit in physical memory. But what if the program size is bigger than DRAM size? In this case, we cannot move all the programs to the physical memory. The programs can have the large capacity in virtual memory. The programmer no longer needs to worry about the amount of physical memory available. All the programs will be stored in the virtual memory with virtual memory address. The system only makes a copy required data from virtual memory to physical memory.

Address Translation

The following figure illustrates how to translate a virtual address to a physical address. In this example, we assume that the system has the following specification:

• Virtual memory size: 2 GB = 2³¹ bytes
• Physical memory size: 128 MB = 2²⁷ bytes
• Page size: 4 KB = 2¹² bytes

Fig. ‑. Address Translation

In the figure above, the least significant 12 bits indicate the page offset and require no translation. The upper 19 bits of the virtual address specify the virtual page number (VPN) and are translated to a 15-bit physical page number (PPN).

We can extract the following values for the give system:

• Virtual address: 31 bits
• Physical address: 27 bits
• Page offset: 12 bits = 3 hexes
• # Virtual pages = 2³¹/2¹² = 2¹⁹ (VPN = 19 bits)
• # Physical pages = 2²⁷/2¹² = 2¹⁵ (PPN = 15 bits)

The following figure shows the virtual page number 5 mapping to the physical page number 1, virtual page number 0x7FFFC mapping to physical page number 0x7FFE, and so forth. For example, virtual address 0x53F8 (an offset of 0x3F8 within virtual page 5) maps to physical address 0x13F8 (an offset of 0x3F8 within physical page 1). The least significant 12 bits of the virtual and physical addresses are the same (0x3F8) and specify the page offset within the virtual and physical pages. Only the page number needs to be translated to obtain the physical address from the virtual address.

Fig. ‑. VPN Mapping to PPN

Exercises

1. Let’s assume we have the virtual memory system with the given Fig. 13-4. What is the physical address of the virtual address 0x0000247C?

Answer)

• VPN = 0x00002
• VPN 0x00002 maps to PPN 7FFF
• 12-bit page offset = 0x47C
• Physical address = 0x7FFF47C

1. Consider a virtual memory system that can address a total of 2³² bytes. You have unlimited hard drive space, but are limited to only 8 MB of semiconductor (Physical) memory. Assume that virtual and physical pages are each 4 KB in size. Configuration of the virtual and physical memory addresses, as follows:

The virtual memory address consists of virtual page number (VPN) and page offset. The physical memory address consists of physical page number (PPN) and page offset.

The lengths of page offset are same.

The total number of the virtual page: 2³² / 2¹² = 2²⁰. That means a total of 20 bits are used for the virtual page number.

The total number physical page: 8 MB / 4 KB = 2²³ / 2¹² = 2¹¹. That means a total of 11 bits are used for the physical page number.

13.2 Page Table

Let’s look at how to perform translation with the page table. The page table has the entry for each virtual page, where entry fields have the following information:

• Valid bit (V): set to 1 if the page is in physical memory
• Physical page number (PPN): where the page is located in the main memory

Fig. ‑. Page Table Translation

As shown in left side of Fig. 13-5, the virtual address consists of virtual page number (VPN) and page offset. The VPN 0x00002 is translated into physical page number (PPN) 0x7FFF using the given page table. If the PPN 0x7FFF is already in the page table and the valid bit set to 1, then the system will get “hit”. The PPN 0x7FFF in page table is mapped to the PPN in physical address. The page offset of virtual address is directly translated into the page offset of physical address.

Translation Lookaside Buffer (TLB)

The page table is large and is usually located in physical memory. If a processor executes load or store instruction, the system requires two accesses of the main memory:

• one for translation (page table read)
• another to access data (after translation)

These accesses eventually degrade the memory performance in half, unless we get clever way to access the memory.

Translation Lookaside Buffer (TLB) is small cache of most recent translations, and reduces the number of memory accesses for most loads/stores from 2 to 1.

Fig. ‑. Paging Hardware With TLB

The CPU only looks at the virtual (logical) address which consists of VPN and PO. If the corresponding PPN is already in Translation look-aside buffers, the system will get TLB hit. VPN is directly translated into PPN using TLB located within CPU. In this case, only one memory access is required.

If the page number is not in the TLB (TLB miss), the system searches the page table which is located in the main memory. After getting PPN in the main memory, it can translate VPN into PPN, and then access the data located in the memory. In this case, two memory accesses are required.

When we run multiple processes (programs) at once, each process has its own page table. Each process can use entire virtual address space. A process can only access physical pages mapped in its own page table.

Virtual Memory Settings

In the Window Search window, type “Advanced System Settings” and click it. You can see the following figure. Then Click “Setting”.

In the System Properties window, click the Advanced tab. You can check the virtual memory size.

Virtual Memory for 64-bit versions of Windows

• How to determine the appropriate page file size for 64-bit versions of Windows

Exercises

1. What is the physical address of virtual address 0x00005F20 with the given page table? (assume 12-bit page offset)

Answer) The least significant 12 bits of the virtual and physical addresses are the same (0xF20) and specify the page offset both the virtual and physical pages. According, the virtual page number 5 is mapping to the physical page number 1 in the page table. The virtual address 0x00005F20 is translated into the physical address 0x0001F20, as shown below:

1. What is the physical address of virtual address 0x000073E0 with the given page table? (assume 12-bit page offset)

Answer) The least significant 12 bits of the virtual specify the page offset. According, the virtual page number (VPN) is 7. The corresponding physical page number is not valid (blank) in the page table. If the processor attempts to access a virtual address that is not in physical memory, a page fault occurs, and the operating system loads the page from the hard disk into physical memory.

1. What is the physical address of virtual address 0x7FFFCA20 with the given page table? (assume 12-bit page offset)