4. Paging

Paging

In paging, main memory and virtual memory are divided into equal-sized pages, commonly not the same size as cache blocks. Pages in main memory are sometimes referred to as frames.

• Pages are allocated to a particular process.
• Pages can be non-contiguous in memory.
• Interpret virutal addresses as a pair: $(\text{virtual page number},\text{offset})$
• Each process has its own page table that maps virtual pages to physical pages.

Virtual addresses are divided into two fields:

• Page field: indicates the virtual page location of the address
• Offset: indicates the location of the address within the page

Physical addresses are divided into two fields:

• Page field: indicate the physical page location of the address
• Offset: indicates the location of the address within the page

The page table uses the virtual page index as an index to find the corresponding physical page field.

The valid bit tells us whether the virtual page currently has a corresponding page in main memory. If a process requests a virtual page with a valid bit $=0$ then there is a page fault: the page is fetched from disk.

title: Example 1
Suppose a system has:
- A physical address space of $2^{12}$ addresses.
- A process running on the system that has a virtual address space of $2^{13}$.
- The system uses byte addressing.
- Each physical page contains $2^{10}$ addresses.
 
**How many virtual pages are there?**
- Virtual page size and physical page size are the same so: $\frac{2^{13}}{2^{10}} = 2^{3}$
- Half as many physical pages, $2^2$ physical pages.
 
**How many bits in a virtual address?**
- **Page field**: needs $2^3$ values $\rightarrow 3$ bits
- **Offset**: needs $2^{10}$ values $\rightarrow 10$ bits
- **Total**: $3 + 10 = 13$ bits
 
**How many bits in a physical address?**
- **Page field**: needs $2^2$ values $\rightarrow 2$ bits
- **Offset**: needs $2^{10}$ values $\rightarrow 10$ bits
- **Total**: $2 + 10 = 12$ bits
 
Suppose the page table belonging to the process is as follows:
 
##### What happens when the process requests virtual address $1553_{16}$?
- $1553_{16} = {\color{red}101}{\color{aqua}0101010011}_2$
- Virtual page: ${\color{red}101}_2 = {\color{green}5}_{10}$
- Offset: ${\color{aqua}0101010011}_2$
 
| Index | Valid bit | Physical Page # |
| -----:|:---------:|:---------------:|
|     0 |     0     |        -        |
|     1 |     1     |        3        |
|     2 |     1     |        0        |
|     3 |     0     |        -        |
|     4 |     0     |        -        |
|     5 |     1     |        1        |
|     6 |     1     |        2        |
|     7 |     0     |        -        | 
 
$\color{green}5$ is used to index into the page table.
Valid bit is $1$, so physical page number is extracted and concatenated with offset.
Physical address is $01 \, {\color{aqua}0101010011}_2 = \underline{553_{16}}$.

What happens when the process requests virtual address $1000000000100_2$?

• Virtual page: ${100}_2=4_{10}$
• Offset: ${0000000100}_2$

$4$ is used to index into the page table. Valid bit is $0$, so there is a page fault. The page is retrieved from slower storage. Store newly retrieved page in main memory and update page table:

1. Remove victim page.
2. Set valid bit to $1$.
3. Store physical page #.