Virtual Memory and You

Virtual Memory

One of the key components to any computer is working memory/Random Access Memory (RAM). Everyone wants a lot of it! RAM is what the operating system uses to access various forms of data. RAM is not to be confused with a hard disk/drive, which is a data storage device as opposed to a working memory device. A hard disks data is not readily available for processor to use, meaning if you wish to use a program you must first load it into RAM. You may then ask yourself, “what if I don’t have enough RAM?” With virtual memory!

Virtual memory is a “virtual space,” which maps virtual addresses to physical addresses. This enables your hard disk to literally be used in the same way as RAM, however it will take very long time to access the data for a single read or write. To solve this problem, the operating system loads data into memory for quick access for unlimited reading and writing. Usually loading the desired as well as surrounding data, based on the assumption that similar data will be placed near each other. For example, it is likely a 12 MB song will be played from start to finish, so the operating system loads large chunks of the data from disk into RAM rather than calling out to disk every couple of seconds (causing the song to halt). These “chunks” of data are called pages or frames, and are contiguous piece of memory, often several kilobytes in size.

Page Tables

The way that the operating system handles loading a page is by using something called a page table. A page table is simply a file which stores the mapping between virtual and physical memory. Although page size can differ between operating systems, it is constant for a given system. A virtual address usually consists of 32 or 64 bit, where various portions of the virtual address are used as an index to a page table, dictionary or offset. To be more clear, the following is a photo from wikipedia:

In the picture above a 32 bit virtual address is used to point to a physical address. Each portion of the address is used,

The first 2 bits are used to point to a directory table, Dir P (there are 2^2 or 4 directories).
The next 9 bits are used as the index to the page directory, PD (there are 2^9 or 512 page entries for each directory)
The following 9 bits are used as the index to the page table, PT (there are 2^9 or 512 page tables for each page entry)
The remaining 12 bits are often referred to as the offset to the 4Kb memory page (or frame).

Page tables often come in 4Kb sizes (however it does depend on the system), and to use a page table it must first be loaded into memory (RAM) before use. Once loaded into ram, page tables can be used to redirect virtual memory to physical memory. However, to load a table into RAM the operating system must first evict one of the other pages currently loaded, how does the system choose? Optimally, it should only remove the pages that need to be used furthest in the future… but since that would take a ridiculous amount of overhead if it is even possible, here are common schemes:

LRU – Least Recently Used: evict the page table left unutilized for the longest period of time.
LFU – Least Frequently Used: evict the table that was used the least.
NRU – Not Recently Used: If a page table is used set an access bit or flag to 1, if a page needs to be evicted scan and set the access bits set to 1 to 0, and remove the pages that already had the access bits at 0.

With each of those methods comes overhead usually several bits (not really a big deal), common bits used are:

Access Bit: used for NRU
Dirty Bit: has the page been modified
Read/Write Bit: can you write in the given page table

Single-Level Page Table Example

Assume that we have a single-level page table with the following:

32 bit virtual addresses
1Kb page

We would like to access a program, how much space is required for the page table?
To calculate this we do the following:
lg(1Kb) = 10 bits = page offset bits
(32 – 10) = 22 bits = page table offset bits

This means that for each program we must load 2 ^ 22 = 4194304 physical addresses
We then multiply the number of physical addresses by the number of bytes required for a pointer, which is the size of the virtual addresses (32 bits = 4 bytes):
4 * 2 ^ 22 = 2 ^ 2 * 2 ^ 22 = 2 ^ 24
= 16777216 bytes
= 16 Mb

That is a ton to load into RAM every time you would like to load any address space (which could be as small as a single byte). This is inefficient, and is an excellent example of why we use multi-level page tables.

Mult-Level Page Table Example

Assume that we have:

32 bit virtual addresses
4Kb page
Two page tables, PT1 and PT2

In this case we have lg(4Kb) = 12 bits = page offset bits

This leaves use to determine how we wish to allocate to the first and second level. In this case lets assume we use 10 bits for both the first and second level page tables (10 + 10 + 12 (page offset bits) = 32). This means that we only need to load…
2 ^ 10 * 2 ^ 2 (4 bytes/32 bits) = 4Kb for PT1
2 ^ 10 * 2 ^ 2 (4 bytes/32 bits) = 4Kb for PT2
2 ^ 12 = 4Kb for page

Total: 12Kb

When we wish to load a single physical address. This is a significant decrease (several orders of magnitude) in required RAM from single-level page table. We must switch out these pages from time to time to use other mapped physical addresses, which does require a fair amount of time. To combat this we attempt to use different page eviction methods (listed in the page tables section of this post).

Addresses, Pages and Tables Breakdown

Lets take a given address: 0xa45b3c23 (8 hexadcimal numbers), with:

32-bit addresses
4 KB pages (12 bit offset)
two-level page table
12-bit first level page table index

First level page table: 0xa45
Second level page table: 0xb3
Page index: 0xc23

Now lets use the same address for:

32-bit addresses
4 KB pages (12 bit offset)
two-level page table
4-bit first level page table index

First level page table: 0xa
Second level page table: 0x45b3 (16 bit offset)
Page index: 0xc23

Notice the page index did not change, since that is given. Since the first level page table was reduced to only 4 bits, there was a (32 – 4 – 12) 16 bit offset for the second page table. This would would change a second level page table would have to be loaded into RAM since it has more Page addresses it can point to, therefore a higher likelihood of a hit.

Issues and Solutions

A page fault occurs when a new page needs to be brought into RAM because it needs to be accessed, but is not present. The solution is to follow a page eviction algorithm and bring the page into memory.

Thrashing occurs when if there is a poor page eviction algorithm, not have enough usable RAM, or too many programs running on a computer. Generally, the solution is to add more RAM or reduce the number of programs running at a given time.

Additional Links

Video by Dr. Mike Murphy, clear explanation of different page table implementations.
Video by Prof. S. Raman, lecture/example of calculating virtual memory to physical.
Lecture Slides from the University of Iowa.
Example Problem, via stackoverflow.