Question

when using physical addresses directly, there is no virtual to physical translation overhead. assume it takes 100 nanoseconds to make a memory reference. if we used physical addresses directly, then all memory references will take 100 nanoseconds each. if we use virtual addresses with page tables to do the translation, then without a tlb we must first access the page table to get the approprate page table entry (pte) for translating an address, do the translation, and then make a memory reference. assume it also takes 100 nanoseconds to access the page table and do the translation. in this scheme, what is the effective memory reference time (time to access the page table time to make the memory reference)? if we use a tlb, ptes will be cached so that translation can happen as part of referencing memory. but, tlbs are very limited in size and cannot hold all ptes, so not all memory references will hit in the tlb. assume translation using the tlb adds no extra time and the tlb hit rate is 75%. what is the effective average memory reference time with this tlb? if we use a tlb that has a 99.5% hit rate, what is the effective average memory reference time now? (this hit rate is close to what tlbs typically achieve in practice.)

Answer 1

Without a TLB, the effective memory reference time is 200 nanoseconds. With a 75% hit rate TLB, it's 50 nanoseconds, and with a 99.5% hit rate TLB, it's 2.5 nanoseconds.

Let's calculate the effective memory reference time for each scenario:

1. Without TLB (Translation Lookaside Buffer):

- Time to access the page table and do the translation = 100 nanoseconds

- Time to make the memory reference = 100 nanoseconds

- Effective memory reference time = 100 + 100 = 200 nanoseconds

2. With TLB (75% Hit Rate):

- TLB hit rate = 75%

- TLB miss rate = 25%

- For TLB hits, no extra time is added.

- For TLB misses, the time to access the page table and do the translation is 100 nanoseconds.

- The effective memory reference time is a weighted average of hit and miss times:

`\[ \text{Effective Memory Reference Time} = (\text{TLB Hit Rate} * 0) + (\text{TLB Miss Rate} * \text{Time for TLB miss}) \] \[ = (0.75 * 0) + (0.25 * (100 + 100)) = 50 \text{ nanoseconds} \]`

3. With TLB (99.5% Hit Rate):

- TLB hit rate = 99.5%

- TLB miss rate = 0.5%

- Similar calculation as above:

`\[ \text{Effective Memory Reference Time} = (0.995 * 0) + (0.005 * (100 + 100)) = 2.5 \text{ nanoseconds} \]`

In summary:

- Without TLB: 200 nanoseconds

- With TLB (75% Hit Rate): 50 nanoseconds

- With TLB (99.5% Hit Rate): 2.5 nanoseconds