Think about this problem while you are learning this part:

Why we are doing paging?

This part is crucial for you to implementing OS/161 Assignment 6 correctly!

Paging

Learning Materials

Video:

Intro to Virtual Memory

Translation Lookaside Buffer (TLB)

Virtual memory on x86

Intro to paging

Continuation of paging by Margo Seltzer

Lecture Slides:

Virtual memory (Intro)

Paging

Paging to disk

Readings:

[OSTEP] Memory API

[OSTEP] Translation lookaside buffers

[OSTEP] Free space management

MIPS MMU and TLB

[OSTEP] Introduction to Paging

[OSTEP] Advanced paging

Paging

Definition and Concept

Define paging

The operating system creates the illusion of unlimited memory by using physical memory as a cache of virtual pages.

Page Faults

Paging relaxes the requirement that all the pages in a process's virtual address space must be in physical memory. Instead, we allow a process to have pages either on disk or in memory. When the process issues an access to a page that is on disk, a page fault occurs. The operating system must retrieve the page from disk and bring it into memory.

The translation does not exist in the page table (the page is on disk), the OS must:

1. Allocate a place in physical memory to store the page.
2. (If physical memory is full, evict a page. If the evicted page is modified or does not currently have a copy on disk, write the page to disk)
3. Read the page from disk.
4. Update the page table entry with the new virtual-to-physical address translation.
5. Update the TLB to contain the new translation.
6. Resume execution of the user program.

Notice that when the operating system selects a location in physical memory in which to place the new page, the space may already be occupied. In this case, the operating system must evict that other page from memory. If the page has been modified or does not currently have a copy on disk, then the old page must first be written to disk before the physical page can be reallocated. If the old page has not been modified and already has a copy on disk, then the write to disk can be avoided. The appropriate page table entry must be updated to reflect the fact that the page is no longer in memory.

Memory serves as the cache of disk. As with any caching system, performance of your virtual memory system depends on the policy used to decide which things are kept in memory(cache) and which are evicted (to disk). On a page fault, the kernel must decide which page to replace. Ideally, it will evict a page that will not be needed soon. Many systems (such as UNIX) avoid the delay of synchronously writing memory pages to disk on a page fault by writing modified pages to disk in advance, so that subsequent page faults can be completed more quickly.

Multi-Level Page Tables

Two-level page table:

Use a page directory which points to pages of the page table.

MIPS Virtual Memory Map

KSEG0, KSEG1 addresses: directly map to physical RAM starting at 0

KUSEG, KSEG2 addresses: translate with the help of the TLB

TLB

Associative TLB

Address Translation Process

MIPS MMU and TLB

No hardware support for page tables.

MIPS makes the format and contents of the TLB entry public to the kernel.

MIPS R3000 TLB:

• global: 1 bit; if set, ignore the pid bits in the TLB.
• valid: 1 bit; set if the TLB entry contains a valid translation.
• dirty: 1 bit; enables writing to the page referenced by the entry; if this bit is 0, the page is only accessible for reading.
• nocache: 1 bit; unused in System/161. In a real processor, indicates that the hardware cache will be disabled when accessing this page.
• pid: 6 bits; a process or address space ID that can be used to allow entries to remain in the TLB after a process switch.

How to handle TLB miss in OS/161?

Write vm_fault function:

What is the TLB shootdown?

If we want to evict a page whose virtual-to-physical translation might be in one/more TLBs, we need to revoke the corresponding TLB entry in all the TLBs. But, from one processor you can't directly access another processor's TLB; instead you have to poke the other processor and ask it to do the revocation for you. The process of doing so is called "TLB shootdown".

How to implement the TLB shootdown?

Issue an inter-processor interrupt (IPI) to the processors that (may) have the mappings you want removed in their TLBs. These processors, upon receiving the interrupt, do the necessary TLB flush operations, and then signal back in some fashion that they've finished.

MIPS R3000 Virtual Addresses

How to manage physical memory in OS/161?

Roadmap to A6

Paging to disk

How to choose pages to be evicted to disk? Which pages won't be needed soon? Which pages are easier to evict?(Do all pages need to be written to disk?)

Page replacement algorithm.

Clean pages(Code pages) are easier to evict since they don't need to be written to disk.

/* Function call chain */
foo() -> kmalloc -> getppages -> evict -> write to swap

When a page get evicted, we need to invalidate the page in TLB.

If the page you evict might be in another TLB, do a TLB shootdown.