In virtual memory, blocks of memory (called pages) are mapped from one set of addresses (called virtual addresses) to another set (called physical addresses). It is also possible for a virtual page to be absent from main memory and not be mapped to a physical address; in that case, the page resides on disk. Physical pages can be shared by having two virtual addresses point to the same physical address. This capability is used to allow two different programs to share data or code.

Unallocated Pages

These are thee pages that have not yet been allocated (or created) by the VM system. Unallocated blocks do not have any data associated with them, and thus do not occupy any space on disk.

Cached Pages

These are those allocated pages that are currently cached in physical memory. They are also present on disk.

Uncached Pages

These are those allocated pages that are not cached in physical memory. They are present on disk.

Example

	Number of addresses in virtual address space
	Number of addresses in physical address space.
	Page Size
	Number of virtual pages
	Number of physical pages

Virtual and Physical Address

In virtual memory, the address is broken into a virtual page number and a page offset.

The physical page number constitutes the upper portion of the physical address, while the page offset, which is not changed, constitutes the lower portion.

The number of bits in the page offset field determines the page size.

A page table is used to carry out the translation from the virtual page number to the physical page number.

Page Table

A page table is indexed with the page number from the virtual address. It maps to a physical address in memory. Each program has its own page table, which maps the virtual address space of that program to main memory. The page table may contain entries for pages not present in memory.

The page table itself also resides in main memory. To indicate the location of the page table in memory, the hardware includes a register that points to the start of the page table; called the Page Table Base Register (PTBR).

The page table, together with the program counter and the registers, specifies the state of a program. This state is often referred as a process. The process is considered active when it is in possession of the processor; otherwise, it is considered inactive. If we want to allow another program to use the processor, we must save this state. The operating system can make a process active by loading the process’s state, including the program counter, which will initiate execution at the value of the saved program counter.

Rather than saving the entire page table, the operating system simply loads the page table register to point to the page table of the process it wants to make active.

The operating system is responsible for allocating the physical memory and updating the page tables, so that the virtual address spaces of different processes do not collide. The use of separate page tables also provides protection of one process from another.

Because the page table contains a mapping for every possible virtual page, no tags are required. The index that is used to access the page table consists of the full block address, which is the virtual page number.

A valid bit is used in each page table entry. If the bit is off, the page is not present in main memory (but present in disk) and a page fault occurs. If the bit is on, the page is in memory and the entry contains the physical page number.

Page Hit

In case of a page hit, the page table entry contains the physical page number.

1. Processor sends Virtual Address (VA).
2. MMU uses PTEA to access Page Table in memory.
3. MMU retrieves Page Table Entry (PTE) from Page Table.
4. MMU sends Physical Address (PA) to L1 cache.
5. L1 cache sends data word to processor.

Page Fault

If the valid bit for a virtual page is off, a page fault occurs. Control is transferred to the operating system via the exception mechanism.

Once the operating system gets control, it must find the page in the next level of the hierarchy and decide where to place the requested page in main memory.

The space on the disk reserved for the full virtual memory space of a process is called the swap space. The operating system allocates this swap space.

The operating system also tracks which processes and which virtual addresses use each physical page. When a page fault occurs, if all the pages in main memory are in use, the operating system must choose a page to replace.

The operating system searches for the least recently used (LRU) page, assuming that a page that has not been used in a long time is less likely to be needed than a more recently accessed page. The replaced pages are written to swap space on the disk.

1. Processor sends Virtual Address (VA).
2. MMU uses PTEA to access Page Table in memory.
3. MMU retrieves Page Table Entry (PTE) from Page Table.
4. Valid bit is zero, so MMU triggers page fault exception.
5. Handler identifies victim, and if dirty pages it out to disk.
6. Handler pages in new page and updates PTE in memory.
7. Handler returns to original process, restarting faulting instruction.