This is the second in a series of columns on how hardware architectures influence software performance. Last month (Editor's Note: 20 years ago), we examined two trade-offs in cache structures: write-through versus write-back and direct-mapped versus associative. This month we look at virtual memory and its interface with caches. This topic is particularly important to programmers working with multitasking systems. The way the hardware implements virtual memory addresses can drastically impact code performance.

Virtual memory allows the program to use a larger addressing space than is offered by the actual bit width of a processor. A processor with a 16-bit-wide address bus (for example, the Z80) can directly access two 16-memory addresses. A virtual memory system is typically employed when the same processor accesses a larger range of addresses, typically 232 or about 2,000 Mbytes.

Obviously, this is a larger addressing range than most people need. However, with virtual addressing this large space can be put to good use. One common way to realize a large addressing space is segmentation, which translates the logical address generated by a program into a linear address by adding it to a segment offset. Here, however, we'll examine a more sophisticated virtual-memory mechanism called paging.

Paging is used to translate a linear address into a physical address. Some systems don't use paging but do use segmentation, in which case the linear address generated by adding a segment offset to a logical address is equivalent to a physical address. Some systems use paging but not segmentation, in which case the linear address is the same as the logical address generated by the program.

Whether or not segmentation is employed or the linear address is the same as the logical address, paging translates the linear address into a physical address by adding an offset to the linear address. The offset is found in a page-table entry, which is found by an indexed offset in a page-table directory. The base of the page-table directory itself is directly addressed by an on-chip control register, called a root register.

Hierarchy of offsets
That may seem a little confusing, so let's look at it from another perspective. Figure 1 shows a typical paging system (the one used by the 80386).

View the full-size image

The program generates a 32-bit linear address divided into three parts: a directory index, a page-table reference, and a page offset. The upper 10 bits of the 32-bit linear address, the directory index, are added to the page-table directory base in the root register. The page-table directory entry contains the address of a page table. The next 10 bits of the linear address are then added to the page-table address to find the required page reference in the table. Finally, the last 12 bits of the 32-bit linear address are added to an entry in the page table to find the actual physical address.