6. EAT and TLB

Virtual memory EAT

If we store page tables in memory, every time we want to access a main memory address we would have to access main memory twice:

1. Access the page table to convert the virtual address to a physical one.
2. Access the physical address.

There is a penalty when using virtual paging: there must be two main memory accesses, one for the page table, one for the actual data.

$$\begin{array}{rl}EAT& =\text{memory access}+\text{hit rate}\times (\text{MA})+\text{miss rate}\times (\text{out of memory access})\\ & =MA+HR\times (MA)+MR\times (OMR)\end{array}$$

title: Example
Suppose we have a main memory access which requires $200 \text{ ns}$ and the page fault rate is $1\%$.
- Assume it costs us $10 \text{ ms}$ to access a page not in main memory (fetching the page from slower storage, updating page table, accessing data)
- The effective access time would be:
  $$
  	EAT = 0.99 \times (200 \text{ ns} + 200 \text{ ns}) + 0.01 \times (10 \text{ ms}) = 100,396 \text{ ns}
  $$

Translation Lookaside Buffer

We can use a Translation Lookaside Buffer (TLB) to store the most recent page table lookups (virtual and physical address pairs) in a special cache.

Use of a TLB reduces access to main memory and speeds up address translation.

Virtual Page #	Physical Page #
-	-
5	1
2	0
-	-
-	-
1	3
6	2

The steps for using a TLB:

1. Extract the virtual page number from the virtual address.
2. Extract the offset from the virtual address.
3. Look up the virtual page number in the TLB.
4. If there is a TLB hit, use the corresponding physical page number. Add the offset to the physical page number to get memory location.
5. If there is a TLB miss, go to the page table to get the necessary frame number. If the page is in memory, use the corresponding frame number and add the offset to yield the physical address.
6. If the page is not in main memory, generate a page fault and restart the access when the page fault is complete.