Virtual Memory

This page uses a toy memory model to help you understand how virtual memory works.

Virtual memory solves several problems:

• different programs can be mapped to different parts of memory, so several of them be resident in memory at the same time without interfering with each other
• at any given time only the part of a program's address space that is currently in use needs to be resident in physical memory
• when a program is built, it can be linked to an address space beginning at 0x0; this simplifies linking since that process is the same for all programs
• each program gets an almost unlimited address space no matter how much (or how little) physical memory the computer has

Here's a diagram of a toy system with 2048 bytes of physical memory divided into 8 pages of 256 bytes each

• 2048 bytes of physical memory means that the physical addresses are 11-bits
• 256 bytes per page gives us an 8-bit page offset
• 8 physical pages gives us a 3-bit physical page number
• using 12-bit virtual addresses gives us 4096 bytes of virtual memory and 4-bit virtual page numbers; this means that there are 16 virtual pages

• At the moment, virtual pages 0, 2, 4, 5, 7, 8, 12, and 14 are resident in physical memory (1 in the R column). The others are on disk only (0 in the R column).
• Pages 0, 5, 7, and 14 are dirty (1 in the D column), that is they have been written to, so they will have to be written back to disk when they are evicted from memory.
• Notice that the dashes in the page table appear in exactly those rows that have a zero in the R column. A real system would have values there, but they would be meaningless since those rows would not be mapped. The dashes are there to make the page table easier to read.

• Each yellow block represents 256 bytes of physical memory.

• Since this is a toy, each entry in the page table uses 6 bits.
• In a real computer, each entry in the page table will be one word, divided into bit fields in a similar way.

• Virtual address 0x456 is on virtual page 4 at offset 56.
• Virtual page 4 is resident in memory at physical page 0, so the byte at virtual address 0x456 is in address 0x056 in physical memory.

• Where is the byte at virtual address 0xE23?

• To make things simple in this toy implementation, the boundary between page numbers and page offsets has been made to coincide with the boundary between two hex digits.
• This won't necessarily be the case in real systems.
• In those circumstances, you will have to break the address down into bits, draw the boundary in the correct place, perform the mapping, and translate the bit fields back into hex.

• For example, suppose we have a 4-bit VPN and a 7-bit page offset.
• Now each memory page is 128 bytes, but we can use the same diagram. Why?
• Let's look at virtual address 0x635, which is 110 0011 0101 in binary.
• Regrouping that into VPN and page offset, we get 1100 0110101, so we are on page 12.
• The page table maps virtual page 12 to physical page 7, so our physical address is 0111 0110101.
• Regrouping that back into hex gives us 011 1011 0101, or 0x3B5.
• Notice that two digits changed this time, not just one.

Here are two more images that I stole from the MIT lecture. You should be able to solve the problems that they pose.