Section 12.6
Dynamic Address Translation

Let's examine in greater detail how virtual addresses are split up into component pieces and translated. Suppose that a machine has 24 bits in its virtual addresses, which implies that it's virtual address space is 2²⁴ words long, or 16,777,216 words. Further suppose that pages are 1K long. Remember that 1K = 1024. This means there will be 16,777,216 ÷ 1024 = 16384 pages in a program at maximum. Since 10 bits are required to count from 0 up to 1023, 10 bits out of the 24 would be the offset within the page and 14 bits of the 24 would be the page number. Fig. 12.6.1 shows this split of the 24 bits of a virtual address.

Fig. 12.6.1: Split-up of the bits of a virtual address

The offset within the page is the same as the offset within the frame, since pages and frames are the same size. The page number is what must be translated into a frame number, which can only be done by looking up the page number in the page table, finding what is there and inserting that into the upper part of the MAR.

Fig. 12.6.2 illustrates this process using 24 bit virtual addresses and 1K pages (and frames) on a machine with only 1/2 Megabyte (524,288 bytes) of real memory. Dividing 524,288 by the page size (1024) gives us 512, which is the number of frames. Thus, the 16,384 pages of a program, its total virtual memory, must be somehow placed into 512 frames of real memory, and this of course is assuming that one program gets all of real memory, a very unrealistic assumption. Since there is only half a megabyte of real memory, the MAR would only be 19 bits long.

Fig. 12.6.2: Dynamic address translation

Computers that use virtual memory do not implement virtual memory in software, which would be unbearably slow. Instead, they put extra gates and circuits on the chip to do the dynamic address translation. In some older units, the circuitry to do this was put on a separate chip called the MMU, or Memory Management Unit. Nowadays, it is more common to bundle the MMU in with the ALU and registers on the main processing chip.

A more interesting question is where the page table resides. As we shall see in the next section, there are ways of making dynamic address translation go faster on average. But it still helps if the page table lookup is very fast.

Some systems store the page table in main memory. This works but is slow. It also detracts from memory that programs might use for useful work. If the system has a separate MMU chip, the page table or tables (if there is more than one program running at the same time) may be stored in high speed memory on that chip. When the MMU is just a part of the main processing chip, as is common nowadays, the page tables might be kept in very high speed RAM on the chip. Such RAM is called a cache (pronounced "cash") because its existence is kept secret, or hidden, from the general programmer. The French word for "to hide" is cacher (pronounced "cash-AY"). We will study more about cache memories later, since they are used in other ways. The main drawback is that when the page table gets to be very big, it is no longer practical to keep it in these special high speed and expensive memory. So we are again forced to resort to main memory.