Virtual Memory

This document explains in a fair amount of detail the paged virtual memory system in line with the discussions of the CPS 104 lectures and notes on the subject.

• General Description
  • Impetus for Virtual Memory
  • What Virtual Memory Is
  • The Virtual Address
  • Pages, and the Virtual Page Number
  • The Virtual Page Number through Examples
• Three Main Parts of Virtual Memory
  • Main Memory (RAM)
  • Secondary Memory (Disk)
  • The Page Table
  • Entry of the Page Table
• Finding the Real Address
  • Selecting a Frame to Replace on Page Fault (NRU and LRU)
  • Replacing the Frame
  • Summary : Virtual to Physical Address

In order to get much of anything out of this document, the reader should be at least a little familiar with virtual memory. I do not intend for this document to be used for a student that knows nothing about virtual memory but wants to learn. I do not believe that it is suited for that task. I instead intend it for someone that has at least given the class notes and the book’s section on virtual memory a once-over.

Like all of my writings, it is long. Also like all of my writings, I have attempted to write it so each section is largely independent of the others, so that if you are unfamiliar with one aspect of virtual memory, you can jump to that particular section and skip the rest.

Also, virtual memory is not a trivial concept like floating point or two’s complement. I like to think I can explain things well, but that doesn’t mean that you can not read carefully and still walk away with a good understanding.

General Description

This section contains a very broad description of the paged virtual memory system.

Impetus for Virtual Memory

The problem is this. Memory addresses are comprised of 32 bits, and each different address references a different byte. 2³² is about four billion bytes. How many computers have four gigabytes worth of main memory? What if a program attempts to access memory outside of that address space? Can we count on programmers to do the right things with memory all the time? What if two systems have different amounts of memory? In order to make a program compatible with both machines we would have to limit our usage of memory to the addresses valid in the machine with the least amount of memory. So what’s the point of buying extra RAM if all programs are written to run on a system with a minimum thirty-two megabytes of RAM?

There are other problems too, all because the address space does not truly reflect the amount of RAM available. Wouldn’t it be nice if we could fool programs into thinking that they have a lot more RAM available to them than they truly do?

What Virtual Memory Is

Virtual memory is a system by which the machine or operating system fools processes running on the machine into thinking that they have a lot more memory to work with than the capacity of RAM would indicate. It does this by storing the most recently used items in RAM, and storing the lesser used items in the slower disk memory, and interchanging data between the two whenever a disk access is made. In this way, memory appears to programs to be a full 32 bit address space, when it fact memory space is probably only a mere fraction of that.

The Virtual Address

How can this be done? We are able to address byte 0xFFFFFFFF. But there is no byte 0xFFFFFFFF in our main memory. So where is byte 0xFFFFFFFF? Somewhere other than byte 0xFFFFFFFF in RAM, since such an index that large does not exist in RAM. Obviously, the relation between an address and its actual location in memory is not as simple as previously thought. Your friend told you the memory you’re looking for at address 0x00000010 is stored in the seventeenth byte in main memory. Your “friend” lied to you.

The way it works: The programs request memory at a certain address. Now, this address isn’t the REAL address for this data; it is a virtual address. The memory system then checks to see where the data for this virtual address really is, based on a reference to something called the page table. After looking up this address in the page table to tell where it is, it does one of two things. If the memory is already in main memory, it returns the real address in main memory, at which point the write to or reading from memory is done. If the data we’re looking for is not yet in RAM, then the memory system retrieves the data from the disk (where data that cannot fit in RAM is stored), puts it into RAM, and THEN returns the address at which it can be found.

Pages, and the Virtual Page Number

To take advantage of spacial locality as well as hardware issues with disk mass storage, it is important to know that just as lines of data in cache would often be larger than one byte or four bytes (in some systems cache lines are thirty-two or sixty-four bytes), “lines” of data in a virtual memory system are often 2048 bytes, 4096 bytes, or 8192 bytes. Also, these “lines” are called pages. The page is the quantum unit of transfer between disk and main memory in a virtual memory system, just as a line was the quantum unit of transfer between cache and RAM. If you ask for a word of memory not in RAM, not just the word, but a whole page’s worth of data from the disk is loaded into RAM.

Pages in a virtual address space are continuous. In a 4096 byte page virtual memory system, the first page in virtual memory would be addresses 0x00000000 to 0x00000FFF. The last page in virtual memory would be 0xFFFFF000 to 0xFFFFFFFF. In this example, the first twenty bits uniquely identify each page in the virtual address space. Therefore, since each page in the virtual address space may be uniquely identified by a certain number of the leading bits of the virtual address, we call that number the “virtual page number.”

If we have an N bit virtual address space (in our example it is thirty two), and we have 2^M page size (in our example, M = 12), then the leading N-M bits (in our example the leading 32-12 = 20 bits) comprise the virtual page number that uniquely identifies each page in the virtual address space.

The lower M bits tell us which byte of this page is the byte we’re looking for, and is called the “page offset.” The page offset is more or less the exact analogy of the cache’s “byte select field.” It tells us which byte of our 2^M byte page we’re trying to access.

The Virtual Page Number through Examples

For some examples of this, I provide some virtual addresses with the page size of the system. I then tell what the page is, and what the page offset is.

1. Virtual address 0x000A502F, with page size of 4K bytes: A page size of 4K = 4096 = 2¹², so the last 12 bits are used as the page offset to tell just what byte of the page we want. Therefore the first 20 bits uniquely identify this page, and comprise the virtual page number.

   Virtual Page Number	Page Offset
   0000 0000 0000 1010 0101	0000 0010 1111

   So the virtual page number is 165, and 47 is the page offset. So we’re looking for the 48th byte (since 0 page offset indicates the 1st byte of the page) of the 166th page (similarly, since a page number of 0 indicates the 1st page).

2. Virtual address 0x000A502F, with page size of 2K bytes. The same address, but different page size. A page size of 2K = 2048 = 2¹¹, so the last 11 bits are used as the page offset to tell just what byte of the page we want. Therefore the first 21 bits uniquely identify this page, and comprise the virtual page number.

   Virtual Page Number	Page Offset
   0000 0000 0000 1010 0101 0	000 0010 1111

   So the virtual page number is 330, and 47 is the page offset. So we’re looking for the 48th byte of the 331th page.

• Virtual address 0x009B18A0, with page size of 4K bytes. A page size of 4K = 4096 = 2¹², so the last 12 bits are used as the page offset to tell just what byte of the page we want. Therefore the first 20 bits uniquely identify this page, and comprise the virtual page number.

  Virtual Page Number	Page Offset
  0000 0000 1001 1011 0001	1000 1010 0000

  So the virtual page number is 2481, and 2208 is the page offset. So we’re looking for the 2208th byte of the 2481th page.

• Virtual address 0x009B18A0, with page size of 2K bytes. The same address, but different page size. A page size of 2K = 2048 = 2¹¹, so the last 11 bits are used as the page offset to tell just what byte of the page we want. Therefore the first 21 bits uniquely identify this page, and comprise the virtual page number.

  Virtual Page Number	Page Offset
  0000 0000 1001 1011 0001 1	000 1010 0000

  So the virtual page number is 4963, and 160 is the page offset. So we’re looking for the 4964th byte of the 161th page.

Three Main Parts of Virtual Memory

As implied above, virtual memory consists of three main parts. First, there is the main memory (RAM), which holds recently used chunks (pages) of memory. Second, there is the secondary memory (disk), which stores the chunks (pages) not currently being used. Thirdly, there is the page table, which tells us just where on the disk or in RAM the particular chunk of data we’re looking for is.

Main Memory (RAM)

The main memory system is where the more recently used pages are stored. Each page is stored into subdivisions of memory called “frames.” A frame size is the same as our page size. If we have a 4096 byte page size, then each frame will hold 4096 bytes to accommodate the pages. The first frame will take up actual addresses 0x00000000 to 0x00000FFF. The second frame will take up address 0x00001000 to 0x00001FFF. Etc. If physical memory is 256 megabytes as it is on my computer, the last page would be from 0x0FFFF000 to 0x0FFFFFFF. Notice that the range of addresses covers 4096 bytes. (It actually be a little more complicated than that, but for our purposes this will suffice.)

Also, though I used similar numbers in my example of different pages in the virtual memory space, it is important to remember that in these frames, the frame that consists of physical addresses 0x00001000 to 0x00001FFF probably does not consist of the same data contained in the virtual addresses 0x00001000 to 0x00001FFF.

A concept that will become important later is the “frame number.” In the example above, the frame number of the first frame will be 0. The second frame will have frame number 1. Similarly, the frame number of the physical address 0x0005ACC0 in a system with a 4K page size will be frame number 0x5A. However, the same address in a system with a 2K page size will have frame number 0xB5 (comprised of the leading 21 bits rather than the first 20 bits).

Think of main memory as short term fast storage of the pages we are currently working on, like a cache.

Secondary Memory (Disk)

The disk memory is a repository for pages not currently in use. When a page needs to be brought to memory, the appropriate page is found and transferred to main memory. Whenever a page that has been modified during its time in main memory, it is written to disk. Think of the pages on the disk as being in long term storage.

The Page Table

The page table is what keeps track of where pages are, and what their properties are. The system updates the page table as changes in the state of the system warrant. It makes sense that there are as many entries in the page table as there are pages in our virtual address space. Therefore, in a virtual address space addressed by 32 bits, at 4K per page that’s 2²⁰ pages, and hence 2²⁰ entries in the page table. The first entry in the page table contains information about the first page. The second entry contains information about the second page. Etc. If we have a virtual address with virtual page number 56 (and hence is the 57th page), we can find information about that page in the 57th entry in the page table.

Entry of the Page Table

So what is in an entry of the page table? Since the virtual address and the physical address need not have much relation to each other, it is important to know just where we can find memory. Also, we may want to be able to tell certain things about memory: Is this page in main memory or on the disk? Has this memory been written to, in which case we’ll have to write it back to disk before discarding it? What are we allowed to do to this data?

• Valid Bit: The valid bit tells us if the memory is currently in main memory or if it must be retrieved from secondary memory. When a page is taken from disk and put into main memory, the valid bit is set to 1. When a page is overwritten in main memory once the system feels we no longer need it, the valid bit is set to 0.
• Dirty Bit: The dirty bit tells us if memory has been written do during its time in main memory. If it has been, then once we discard the memory we must write it back to disk. If it hasn’t been modified, then we’re saved a disk write when we get rid of the page in this frame, which speeds the system up. When the page is first loaded into memory, its dirty bit is set to 0. If a write instruction to that page occurs during its time in memory, then the dirty bit is set to 1.
• Access Control: A rather primitive form of memory protection, access control indicates what we may do to this frame. Do we have access to read, read/write, or execute from this frame? In this way programs are prevented from doing damage to other data that may belong to other processes.
• Frame Number: If the data is in main memory, since any page can be loaded into any frame, we have to have some data that tells us just which frame the data is at. Hence, the frame number.
• Disk Location: If we need to write back data currently in main memory, or if we need to read a page that is not in main memory, then we need to know where on the disk that data can be found. This is a close analogy to the frame number.

Finding the Real Address

Given a virtual address, we can find its virtual page number by selecting a certain number of leading bits (the number selected depends on both the sizes of our virtual address space and the size of our page). From that, the memory system can access the corresponding entry in the page table to find out just where this data is, retrieve it from disk if necessary, and then, using the frame number of the frame to which it was loaded, derive the corresponding physical address of this virtual address. The process for this can be seen in slide 12 of lecture 16.

When a memory reference is made, you’re given a virtual address. With a page size of 4K, or 2¹², and our virtual address space of 2³², we have 2²⁰ possible pages. The first 20 bits will therefore be the “virtual page number” for this address.

As an example, suppose we’re working with a 4K page size. Take the 32 bit virtual address 0x00072A4C, which in 32-bit binary is:

0000 0000 0000 0111 0010 1010 0100 1100

The leading 20 bits of that are our page number, since the rightmost 12 bits must be used to determine where in the page the byte we’re trying to access is. The page number is therefore 1110010₂ = 114₁₀. The rest of the bits, 101001001100₂ = 2636₁₀, is our page offset.

For the purposes of simplicity, let’s say the page table has as many entries as there are possible pages… that is, 2²⁰ = 1048576 entries. There is a direct correspondence between the entires in the page table and the pages in DISK, e.g., the 23rd page corresponds to the 23rd entry in the page table.

After we have the virtual page number, we look up the corresponding entry in the page table. In our example of the address 0x00072A4E, that’s page number 114 (as shown above). So, we look at entry 114 in our page table. An example of an entry in the page table may be seen in lecture 16, slide 12, and has a valid bit, a dirty bit, an access control field, and a frame number.

If it is valid, then another field in this entry tells us what frame in memory it is at (the frame number). We now have the frame. Using the frame number and the page offset, we can now compute the physical address through roughly the process described on slide 12 of the lecture 16 notes.

If the page we seek is not already loaded into main memory (that is, the valid bit is not set so that we encounter a page fault), then the page must be loaded into a frame in main memory before any reading or writing by the program may occur. We must find a frame to load into.

Selecting a Frame to Replace on Page Fault (NRU and LRU)

Through what mechanism do we select a page that we want to replace? I will describe the “not recently used” algorithm in this section. The flow chart below has a brief summary of it in its upper right-hand box. Also, the algorithm is described on slide 17 of lecture 16.

Suppose that we have an additional data structure that defines a bit for each frame in main memory, and suppose this bit is called “recently used” (RU). Also suppose we have a pointer to the frame that was last replaced called the “last replaced pointer” (LRP). What not recently used does is it looks at the LRP, increments LRP by one (looping around if we’re past the last frame), and checks the frame. Is the RU bit set? If it is not (or if the frame is still empty), we have a frame that we can load data into. If it is set, we skip over this frame, but we set its recently used bit false before repeating this process and incrementing LRP to the next frame.

RU is set to true whenever a memory access (read or write) to that address occurs, to tell the machine that yes, someone is using the page in this frame, so don’t get rid of it yet.

There are optimizations to this algorithm. For example, in the assignment PC, we adjusted this algorithm so that it favors replacing pages whose dirty bits are not set, to avoid the extra time of a drive write whenever possible. I’m not going to go into it aside from mentioning that such an optimization exists.

There is another replacement algorithm called “least recently used” (LRU), and it is exactly analogous to the replacement policy used by fully associative cache. Essentially, you keep track of the exact history of frame accesses, and replace the one that was accessed least recently.

Replacing the Frame

Ideally this frame will be empty, but if the frame already holds data, several steps must be taken. I go through the basics of the steps here.

1. First, we find a suitable frame in main memory to copy the desired page to. This can be done any number of ways, but the way that we’ve had the most experience with is the not recently used algorithm.
2. Once a frame is found that we can load into, we check to see if there is data in this frame; your method for doing this may vary. If there isn’t, we can copy our page from secondary to main memory without consideration of what was there… since there wasn’t anything there in the first place… so skip to step 5.
3. If there is data already in this page frame, the “valid bit” in the page table for which this page is a copy must be cleared to signify that the page we’re replacing may no longer be found in main memory.
4. Further, if the data we’re to get rid of has been modified (ie, the “dirty bit” is active), the changed page must be written back to DISK so that changes are not lost.
5. Copy the data we want to load from the page in DISK to the appropriate frame in main memory. In the page table, for the element of this page, set the valid bit to 1 (since the page is now held in main memory), the dirty bit to 0 (because this is new virgin data exactly as it is in secondary memory), and put the frame number of the frame to which we loaded it in “frame number.”

Now that we know that the data is in this frame (we just copied it, after all), we can compute a physical address based on the frame number and the page offset (again based on the process described in lecture 16, slide 12).

Summary : Virtual to Physical Address

Once all this detail is taken care of, the formula for deriving the actual physical address from the virtual address is simple. You take the virtual address, extract the virtual page number, look up the corresponding entry in the page table, and in the virtual address replace the virtual page number with the frame number. Voilà. You have the physical address. Once this translation is made and we’re assured that the data we want is in main memory, it may be accessed without any trouble.

Here is a link to a flow chart describing the above process graphically.