Back to ComputerTerms

Virtual Memory

There are two main motivations for Virtual Memory:

1. To allow efficient and safe sharing of memory among multiple programs
2. To remove the programming burdens of a small, limited amount of main memory.

Virtual memory implements the translation of a program's address space to physical addresses. This translation process enforces protection of a program's address space from other programs.

In times past programmers had to make sure their programs fit in the memory available, Virtual memory overcomes this by relieving the programmer of this task.

KEY: A Virtual Memory Block is called a page

KEY: A Virtual Memory Miss is called a page fault

KEY: The CPU produces a Virtual Address.

The process of mapping virtual memory addresses to physical memory address is called memory mapping or address translation. Virtual memory also provides relocation functionality. This allows us to load the program in any physical memory location (remember that DOS required you to run your program in the lower 640K of memory). Further memory is allocated in fixed size blocks (pages) eliminating the need to find a contiguous block of memory to allocate to a program. (Remember that memory references in a program are offsets that assume contiguous memory use.)

FORMAT:

Note that since physical memory is allocated in pages, that the page offset for virtual and physical addresses don't change.

https://www.scotnpatti.com/images/vitualMemorytranslation.jpg

Essentially Memory is a cache for the disk drive system. When we view it in this way we need to consider the extreme difference in speed between the memory and the disk drive. To minimize the effects of this difference we employ the following techniques:

• Pages should be large enough to amortize the high access time.
• Page placement is fully associative
• Page faults can be handled in software because the overhead will be small compared to the disk access time

• The WriteThrough method will not work with virtual memory since writes take too long. Instead VM systems use WriteBack schemes.

Page Table

It is impractical to search the entire memory for a specific entry when translating a virtual address into a physical address as is needed in a fully associative cache. Instead we locate pages by using a full table that indexes the memory, called a page table. P583 Computer Organization and Design state: "Each program has its own page table, which maps the virtual address space of that program to main memory."

https://www.scotnpatti.com/images/pagetable.jpg

Why do you think that the virtual memory space would be smaller than the physical memory space? The best answer that I can come up with is that you may not want a program to have access to all of the memory due to the large page table size. This is not the case in windows, but it maybe the case for an SGI super computer (I don't know that for sure) where you have 16 GB of physical memory, also individual processes are not allowed to use (in general) more than 2 GB. Just a thought.

Managing Page Table Size

1. The simplest technique is to keep a limit register that restricts the size fo teh page table for a given process. If the virtual page number becomes larger than the contents of the limit register, entries must be added to the page table. This technique allows the page table to grow as a process consumes more space.

2. Since programs consist of stack and heap memory, we "segment" the page table into stack and heap. One starts at the top and grows down and the other starts at the bottom and grows up. Thus the first bit of the address can be used to determine which page table to look in. A limit register specifies teh current size of the segment, which grows in units of pages. This type of segmentation is invisible to the programmer.

3. Another approach is to use a hashing function to the virtual address so that the page table data structure need be only the size of the number of physical pages in main memory. Such a structure is called an inverted page table.

4. We could use a multilevel page table just like we use multilevel caches. The first level maps large fixed-size blocks of virtual address space (64-256 pages). These large blocks are sometimes called segments. and the first-level mapping table is sometimes called the segment table, though it is invisible to the programmer. Advantage is for sparce address usage, the disadvantage is the added complexity.

5. Modern systems allow the page tables to be paged. Never ending page faults are handled differently on different machines, but essentially we avoid them by placing all the page tables in the address space of the OS and placing at least some of the page tables for the system in a portion of main memory that is physically addressed adn is always present and never on disk.

Making Address Translation Fast TLB

Translation-lookaside buffer is essentially a cache for the page table.

https://www.scotnpatti.com/images/tlb.jpg

If the page table is equivalent to the card catalog of the library, then the TLB is that little piece of paper that you use when you write down the location of the books you looked up in the card catalog.

Overview of the Memory Hierarchy

https://www.scotnpatti.com/images/memoryhierarchymissscheme.jpg

Back to ComputerTerms