A program that uses virtual memory generates virtual addresses as it executes instructions. The addresses that the program generates go from 0 up to the maximum address and form a set of numbers called the program's address space. Since these addresses are not real, we sometimes call this the program's virtual address space.
Usually, the number of bits in addresses determines the size of the address space. For example the VAX uses 32-bit addresses although one of these bits was used to tell if the address was a special system address or just an ordinary user address. Thus, VAX addresses are actually 31 bits long. 231-1 is 2,147,483,647, which is the largest address that a program running on the VAX can generate in an instruction. The reason why we subtract 1 is because 0 is the first address and all 1's is the last address, and
111111111111111111111111111111
(31 ones) is 2,147,483,647, computed by 231-1.
In the old days, an architecture may have had the capacity for a large address space but the particular model that a user bought might have less memory. For example, on the early CDCs, which did not use virtual memory, addresses were 18 bits long, giving a total address space of 262,144 words. However, many smaller models were sold that had fewer words of memory, sometimes only half of this: 131,072 words. Programs written for those smaller models had to take this into account and not have extremely large arrays, for example. If a program ran that tried to access a non-existent memory word, a run-time error would be generated by the hardware and the program would be killed with a nastygram from the OS.
When a computer has virtual memory, the program can generate any address and it is the job of the hardware to translate that virtual address to a physical one. Even when the page containing the virtual address is not currently in a frame, virtual address can be translated into a real address. How does the hardware do this, detect errors, and cause disk reads to bring the page into memory? It does it with the help of that master utility program, the operating system, and a special data structure.
The heart of the translation process is a data structure called the page table. This is a one-dimensional array of items which enables the hardware to quickly look up a virtual address and find its equivalent physical address, or detect that there is no such physical address.
Fig. 12.5.1 shows a page table for the system described above. Since there are 8 pages in the program's address space, there are 8 entries in the page table.
There are different implementations of page tables, but they usually contain the following:
If the page is not currently in physical memory, then the dirty bit is ignored and the physical frame number is invalid. Only the disk address matters. If the page is in a frame of physical memory, then all the fields are valid.
When the program references memory in a page that is in a frame, which it can tell by examining the present/absent bit, it copies out the physical frame number and inserts that into the MAR of the memory hardware. For a write operation, the dirty bit is set so that when this page is evicted from this frame, the contents will be saved back to the swap area of the disk instead of thrown aware. Reads do not change the dirty bit. A page's dirty bit is initialized to 0 when it is loaded into a frame.
If the page is not currently in a frame, then the operating system is called into action. The job is usually suspended until the OS can schedule a convenient time to copy the page. This event is called a page fault, although the program is not really at fault!
When the OS finally gets back to the suspended job, it first looks to see if there is a vacant frame. If there is, it finds the page on disk by looking up its disk address. Then it reads the entire page from the disk by starting up special hardware to transfer in a large block of memory without constant supervision of the main CPU. While this is going on the OS continues working on some other job and only returns to the job when the block transfer is done. Then it updates the page table by inserting the frame number into the entry, setting the dirty bit to 0 and the present/absent bit to 1. Finally, the operating system marks the job as ready to run and when all other higher priority jobs have received their fair time slices, the OS turns control back to this job. Page faults are serious occurrences and should be minimized.
Disk addresses can be quite long. Typically, they include the disk drive number, the platter or surface in that disk drive, the track and finally the sector number. It is not uncommon for disk addresses to be 40 bytes long. In fact, they are usually so big that it is impractical to keep all of them in memory in the page table, so they are usually stored in another table on disk and only read in when needed. In this case, the page table in memory would only need the frame number, the dirty bit and the present/absent bit.
One way of avoiding saving long disk addresses in the page table is to calculate the disk address during a page fault. This can be done if the pages are stored on disk in a contiguous swap area, which is very common. In this case, all that is needed is the starting disk address which the operating system can store in just one place.
