Effective Access Time with TLB

Introduction

Effective Access Time, or EAT, is the average time required to complete one memory reference. With paging and TLB, a memory reference may follow a fast hit path or a slower miss path.

The main idea is to identify the possible paths first. Once the hit cost, miss cost, and their probabilities are clear, the EAT formula becomes a weighted average.

Quick TLB Recall

A TLB is a small, fast cache that stores recent address translations. It helps the MMU avoid checking the page table for every memory access. The basic outcomes are:

• TLB hit: The required translation is found in the TLB.

• TLB miss: The translation is not in the TLB, so the page table must be checked.

• Hit ratio: Fraction of accesses that are TLB hits.

• Miss ratio: Fraction of accesses that are TLB misses.

If the hit ratio is h, then the miss ratio is 1 - h.

Hit and Miss Paths

Assume a single-level page table, with no page faults. Let the TLB lookup time be e, memory access time be m, and the TLB hit ratio be h.

On a TLB hit, the system checks the TLB and then accesses memory. Therefore, Hit time = e + m.

On a TLB miss, the system checks the TLB, reads the page-table entry from memory, and then accesses the actual data. Therefore, Miss time = e + m + m = e + 2m.

The TLB lookup time is included in both paths because every memory reference checks the TLB before knowing whether it is a hit or miss.

EAT Formula with TLB

Effective Access Time is the weighted average of hit time and miss time.

Effective Access Time = h(e + m) + (1 - h)(e + 2m)

In this formula, h(e + m) represents the TLB hit contribution whereas (1 - h)(e + 2m) represents the TLB miss contribution, where after the TLB lookup, one memory access is needed to read the page-table entry and another to access the actual data. This formula assumes a single-level page table with no page faults.

Worked Example Without Page Faults

Suppose we are given a TLB lookup time of 10 ns, a memory access time of 100 ns, and a TLB hit ratio of 95% (0.95).

In a TLB hit, the lookup takes 10 ns and the memory access takes 100 ns, giving a total of 110 ns. In a TLB miss, we spend 10 ns on the TLB lookup, 100 ns to access the page table, and another 100 ns to access the actual data, giving a total of 210 ns.

Now calculate Effective Access Time by taking weighted average of hit time and miss time.

EAT = 0.95 * 110 + 0.05 * 210 = 104.5 + 10.5 = 115 ns

So the effective access time is 115 ns.

What the Result Means

The EAT lies between the hit time and miss time. In the example, most accesses are hits, so the final average stays close to the hit cost.

A TLB miss is slower even when no page fault occurs. It only means the translation was not cached in the TLB, so the page table must be checked.

EAT with Page Faults

Page faults introduce a much larger cost. A page fault means the page-table check finds that the page is not present, invalid, or not allowed for that access, so the OS page-fault handler must run.

Let the normal memory reference time be t, the page fault rate be p, and the page fault service time be f.

The formula is: EAT = (1 - p)t + pf

Here, t is the normal memory-reference time, and f is the much larger page-fault service time.

Worked Example with Page Faults

Suppose we are given a normal memory reference time of 100 ns, a page fault service time of 8 ms, and a page fault rate of 0.001.

First convert 8 ms to nanoseconds: 8 ms = 8,000,000 ns

Now apply the formula: EAT = 0.999 100 + 0.001 8,000,000 = 99.9 + 8,000 = 8,099.9 ns

Even a small page-fault rate can dominate EAT because page-fault service time is much larger than normal memory access time.

Summary

For a single-level page table without page faults, TLB hit time is e + m, miss time is e + 2m, and EAT = h(e + m) + (1 - h)(e + 2m).

When page faults are included separately, EAT = (1 - p)t + pf. The key habit is to identify each possible path, calculate its cost, attach its probability, and take the weighted average.