Virtual Memory

My opinion is that learning these last few topics requires lots of diagrams and someone to actually show you how it works. The textbook and lecture notes are very comprehensive in this, so these notes are a poor substitute for them.

Why virtual memory?

1. From the programmer's point of view, it is desirable to have a really large address space. The programmer may not really need to use all of that space, but it sure is nice to know that you will not be constrained by not having enough addressable memory. Note the difference between "addressable memory" and actual "physical memory". The programmer just wants to see a huge flat address space. How the machine provides that should be invisible to him.

2. From the hardware designer's point of view, there isn't enough physical memory to give the programmers what they want. But one thing we know about programs is that we don't need to keep the entire program and data space in physical memory all at once, let alone the entire address space. Therefore we can put some parts of the program in memory and parts of it on disk, and swap them in and out as needed. Only a small part of the program will be running at one time. Swapping from or to disk is a small penalty we have to pay for providing a large address space.

Another benefit of having virtual memory is that each program can have its own address space. There is no way a program can know about the existence of other programs out there. We know that all MIPS programs start at 0x00400000. With virtual memory we can have several MIPS programs running at the same time. The address 0x00400000 is different for each program, although each program believes it is the only one running on the machine and that it is really starting at 0x00400000. The hardware provides the mechanism and the OS provides the management. The OS maintains the virtual spaces of every program that is running on the system. Thus programs are protected from each other, and we can do multiprogramming.

In the simplest sense, virtual memory is just a mapping mechanism translating the virtual address space to the actual physical memory space, plus some management functions.

Similarities with caches

Although virtual memory and caches have different objectives, their mechanisms are basically the same. For example:

1. Both involve a mapping from a large space to a small space. Caches maps physical memory to the cache blocks, so that memory accesses can be faster. Virtual memory maps a large virtual address space to physical memory, so as to provide the illusion of a large address space.

2. Both require some management. Due to the limited space available, we must decide what to keep in the cache/page table, and what to keep out there. The LRU algorithm is common to both caches and virtual memory.

3. A cache miss is the same as a page fault. A cache block is the same as a page. We replace a cache block, and its virtual memory equivalent is to swap in from disk. While we do a write back for caches, we do a swap out to disk in virtual memory. There are many more such analogies.

Mapping Mechanism

Note that virtual memory requires hardware support. For example, when the processor executes a load word instruction, it gets a virtual address to load from. The hardware has to intercept that address and translate it to the physical location and loads from that physical location. But since page tables are usually managed by software (i.e. the operating system), one way to do this is to trap to the OS and let the OS handle the translation.

The first thing we have to do is to decide on the size of our pages. We need N bits to reference within a page of size 2^N. The considerations here are similar to block sizes in caches. Large pages are good for spatial locality but that would also mean that we wouldn't be able to hold as many pages in memory. Large pages also impose a heavier penalty on page faults. The difference from caches here is that for caches we can choose the number of cache blocks we want and we use the tag to resolve collisions. But for virtual memory it is different, so don't get too caught up in the analogies between caches and virtual memory. The number of entries in our page table is the size of the virtual space divided by the size of our pages (for single-level paging system). Therefore, small pages will result in a large page table, and remember that our page table has to share physical memory space with the pages that we can hold in memory. Note that not all the pages have to be in memory, some can be on disk.

If we have a 32-bit address space, and we want pages of size 2^N, then we need N bits for the page offset and (32-N) bits for the virtual page number. The virtual page number is your index to the page table. From there, you get the physical page number, which is the location of the page in physical memory (only when the valid bit is set, otherwise you must look for it on disk). The page offset is just the offset from that location. So you'll add the two together to get the actual physical address.

Usually, the pages will be aligned such that instead of adding the two numbers together, you just need to store a much shorter physical page number and concatenate the page offset to it. This is the scheme shown in the textbook. So suppose you have a M-bit physical address space, the number of bits required for the physical page number is just (M-N).

What's in a page table?

The lecture notes and textbook are pretty clear on this. The most important ones are the physical page number (of course) and the valid bit. The dirty bit is used for efficiency, so that you don't need to write to the disk when you don't need to. Other stuff that may be in a page table includes access rights (read-only, read/write, execute, etc). Those depend on the OS.

Every process has its own page table. The OS will manage the creation and deletion of the page tables as new process start executing and/or old processes complete. This is why we don't usually have hardware page tables. There's only so much hardware can do and hardware page tables will also limit the kinds of OSes that can run on the machine.

Virtual Memory and Caches

Caches cache on physical memory, but to get the physical address we need to first do the translation from virtual address to physical address, which means going to the page table, and hence it means accessing main memory. That would defeat the original purpose of having a cache, which is to not access main memory as much as we can.

The solution is that since the problem is that we don't want to go out to the page table to get the mapping all the time, what we'll do is to simply cache the mappings as well. This is a separate hardware cache, and we call this the Translation Look-aside Buffer (TLB). Given a virtual address, the TLB finds out the physical address. What about virtual addresses from different processes? (thanks to Nemanja for answering this) What happens is that the OS will either clear or swap out the TLB to disk when it switches process, so the TLB applies only to the current process that's running.

Multi-Level Page Tables

Suppose we have a 4 Gb virtual space and we want 4 Kb pages (example in lecture notes). That results in a 4 Mb page table! How can reduce the size of the page table? One solution is to use multiple levels of page tables. The diagram in the lecture notes is very clear. You get to choose the size of your pages and the size of the 2nd-level page tables, what's left is the size of your top-level page table. The top-level page table is now much smaller, at the cost of one more level of of redirection and more management overhead. Now you can swap in/out the 2nd-level age tables as well as the pages themselves. There is no need to keep all the 2nd-level page tables in memory, otherwise we wouldn't get the space savings. There is now an added complexity because the OS has to decide how many 2nd-level page tables share memory with the pages themselves.

Written by : Gek Siong Low (cs61c-tb), Spring 1999