These notes are for chapter 9 in the book above.
The memory of a computer is organized as an array of M contiguous bytes. Each byte has a unique address PA. On top of the physical memory is an abstraction in form of a virtual memory.
An address space is an ordered set of nonnegative integer addresses $$\{0,1,2,...\}$$ If the elements of the address space are consecutive, we call the address space linear.
In a system with virtual memory the CPU generates virtual addresses from an address space of $N = 2^n$ addresses called the virtual address space: $$\{0,1,2,...,N - 1\}$$ This address space has size N, and the largest element is the integer $N - 1$. This kind of address space is called an n-bit address space.
A system like this also has a physical address space of size M: $$\{0,1,2,...,M - 1\}$$ M doesn't need to be a power of 2.
Each byte of main memory has a virtual and a physical address.
| 4 | N = 2^4 = 16 | N - 1 = 15 |
| 14 | K = 2^10 \Rightarrow 16K = 2^4 \cdot 2^{10} = 2^{14} | 2^{14} - 1 |
| 24 | 2^{4} M | 2^{24} - 1 = 2^{4} \cdot 2^{20} - 1 = 16 M - 1 |
| 46 | 64T = 2^{6} T = 2^{6} \cdot 2^{40} = 2^{46} | 64T - 1 |
| 54 | 2^{54} = 2^{4} \cdot 2^{50} = 2^{4} P | 16 P - 1 |
VM is organized as N contiguous byte-size cells stored on disk. Each byte has a unique virtual address that serves as an index into the array. VM is partitioned into virtual pages (VP). Each of these pages are $P = 2^{p}$ bytes in size. Physical memory are partitioned in the same way into pages of the same size, but named physical pages (PP). Virtual Pages and Physical Pages are fully associative, meaning one of them can contain the other. The virtual pages can have one of the three following attributes:
Consider L1,L2 and L3 cache as SRAM. Now let the part of main memory that contains the VM be named DRAM. Since DRAM is located in memory it is slower than SRAM.
A page table is a map (an array) of page table entries (PTEs). In terms of the book the PTE's consist of a valid bit and an n-bit address field. The valid bit indicates whether the virtual page is cached in DRAM. If so, the address field contains the address of the start of the corresponding physical page in DRAM where the virtual page is cached. Alternatively the address field can be set to null, meaning the virtual page has not yet been allocated in the virtual memory. Otherwise the address points to the start of the page on disk.
| n | P = 2^{p} | PTEs |
| 12 | 1 K | 2^{12} / 2^{10} = 2^{2} |
| 16 | 16 K | 2^{16} / 2^{14} = 2^{2} |
| 24 | 2 M | 2^{16} / 2^{14} = 2^{2} |
Page Hits If the CPU is reading a word from the PTE where the valid bit is set, the address is constructed by specialized hardware, and we have a page hit.
Page Fault If the valid bit of the PTE the CPU is trying to read, is not set, we have a page fault. The word is hence not located in DRAM.
In case of a page fault the following happens: The proper hardware reads the target PTE (Page Table Entry). The valid bit is false, hence a page fault exception is triggered. The exception invokes a page fault handler in the kernel. This handler select a victim page among the Virtual Pages. If the victim page has been modified, the handler/kernel copies the modified page back to disk. Otherwise data would be lost. The victim page is modified to reflect the fact that it is no longer cached. The asked for page is copied from disk to DRAM (PP = Physical Memory). When the handler returns, the faulting instruction is restarted. And now the asked for page is cached, and we have a page hit.
In all we have a Page Table consisting of entries with a valid bit and an address pointing to either a Physical Memory/DRAM, the Virtual Memory which is a table located on disk, or the address can be null meaning that that PTE (Page Table Entry) is not pointing anywhere. The page table can hence look like
| PTE | Valid | |
| PTE 0 | 0/1 | null/address/PP-number |
| PTE 1 | 0/1 | null/address/PP-number |
| PTE 2 | 0/1 | null/address/PP-number |
| PTE 3 | 0/1 | null/address/PP-number |
| . | ||
| . | ||
| . | ||
We furthermore have a Virtual Memory located on disk
| VP (Virtual Page) 1 |
| VP (Virtual Page) 2 |
| VP (Virtual Page) 3 |
| VP (Virtual Page) 4 |
| . |
| . |
| . |
And a Physical Memory (DRAM) located in the memory
| Id | Value |
| PP (Physical Page) 0 | VP (Virtual Page) x |
| PP (Physical Page) 1 | VP (Virtual Page) y |
| PP (Physical Page) 2 | VP (Virtual Page) z |
Any VP can be contained in any of the PPs and vice versa. Hence we say that the two tables are fully associative.
Allocating Pages To allocate a new page (ex. by using malloc) a new VP is allocated on disk. This VP is pointed to by a PTE. The newly created page is not cached in DRAM, and thus the valid bit stays 0.
Swapping The action of transferring pages from disk to memory is called swapping or paging. Swapping in is from disk to DRAM. Swapping out is from DRAM to disk.
Demand Paging refers to the strategy of swapping at the last possible moment.