Virtual Memory Address Translation

In a system with virtual memory the main memory can be viewed as a cache for the disk, which serves as the lower-level store. Due to the enormous difference between memory access times and disk access times, a fully-associative caching scheme is used. That is, the entire main memory is a single set - any page can be placed anywhere in main memory. This makes the set field of the address vanish. All that remains is a tag and an offset.

Since the tag field just identifies a page it is usually called the page number field.

20 12
page number offset

Logical Addresses

With a virtual memory system, the main memory can be viewed as a local store for a cache level whose lower level is a disk. Since it is fully associative there is no need for a set field. The address just decomposes into an offset field and a page number field. The number of bits in the offset field is determined by the page size. The remaining bits are the page number.

An Example

A computer uses 32-bit byte addressing. The computer uses paged virtual memory with 4KB pages. Calculate the number of bits in the page number and offset fields of a logical address.

Answer

Since there are 4K bytes in a cache block, the offset field must contain 12 bits (212 = 4K). The remaining 20 bits are page number bits.

Thus a logical address is decomposed as shown below.

Page Tables

Virtual memory address translation uses page tables. These are simple arrays in memory indexed by page number. A page table base register (PTBR) holds the base address for the page table of the current process.

Each page table entry contains information about a single page. The most important part of this information is a frame number — where the page is located in physical memory. Address translation combines the frame number with the offset part of a logical address to form a physical address.

The Page Table Base Register (PTBR)

Each process running on a processor needs its own logical address space. This can only be realized if each process has its own page table. To support this, a processor that supports virtual memory must have a page table base register that is accessible by the operating system. For operating system security, this register is only accessible when the processor is in system mode.

The operating system maintains information about each process in a process control block. The page table base address for the process is stored there. The operating system loads this address into the PTBR whenever a process is dispatched.

Page Table Entries

A page table entry contains information about an individual page in a process's logical address space. It typically has a size of 4 bytes (32 bits). It contains the following kinds of information.

When the hardware attempts to access memory and the valid bit is false, the hardware does not need any of the remaining information. It just triggers an exception to bring up the operating system. The operating system can set the valid bit to false for pages that are swapped out to a disk. It can use all of the bits except the valid bit to record the disk location.

With 32 bit physical addresses and 4KB pages the frame number only requires 20 bits. Then a 4B page table entry provides more than enough bits.

Logical Memory Access

A logical memory access (instruction fetch, load, or store) involves two physical memory acesses:

If nothing is done about it, this doubles the latency for logical memory accesses. All but the very earliest processors that supported virtual memory have used a translation lookaside buffer to eliminate most of the page table entry retrievals.

The Translation Lookaside Buffer

The translation lookaside buffer is just a cache that holds recently accessed page table entries. It can achieve very small miss rates with just a few thousand entries.

 
=
 
logical address space size
 
×
 
page table size
page table entry size
page size
 
=
 
4GB
 
×
 
 
=
 
page table size
4B 4MB
4KB

Page Table Size

The size of a page table is given by the following equation.

For example, many processors have 32-bit logical addresses, which results in a 4GB logical address space size. The page table entries size is usually 4B. If the page size is 4KB then the page table size is

This is excessive, especially on a processor that is running hundreds or even thousands of processes. About 15 years ago, many introductory programming classes had all students running their programs on a mainframe computer. Imagine perhaps 400 students running "Hello, World!" programs, each using 4MB just for page tables.

Most processors use multilevel page tables to reduce the size of page tables for small programs.

Multilevel Page Tables

Multilevel page tables are split into two or more levels. For example, a 2-level table is organized as follows.

  • Low-level tables a like single level tables except that each one only covers a small chunk of the logical address space.
  • High-level tables have entries for each chunk in the logical address space. Each entry has the following information:
    • a valid bit which is true only if its chunk has been allocated to the process by the operating system
    • the address of the low-level table for the chunk

For chunks that have not been allocated to the process, the false valid bit triggers a hardware exception. Since the chunk is not allocated by the operating system there is no need for a low-level table. If a process only needs a small amount of memory it will have one high-level table and only a small number of low-level tables. Each of these tables is typically only a few KB.