Effective Access Time with TLB

The Memory Access Workflow

When a CPU needs to access a memory location specified by a logical address, it triggers a sequence of events. The goal is to translate this logical address into a physical address as quickly as possible. Here is the path, from best case to worst case:

1. Check the TLB: The CPU first presents the page number from the logical address to the TLB.
2. TLB Hit (Best Case): If the TLB contains the translation (page number -> frame number), we have a TLB hit. The physical address is formed immediately, and the data is fetched from Main Memory. This is the fastest path.
   Total Time = TLB Access Time + Main Memory Access Time
3. TLB Miss: If the translation is not in the TLB, we have a TLB miss. This is where things get more involved. The system must now consult the full Page Table, which resides in Main Memory.
   • Page Hit (The "Okay" Case): The system accesses the page table in main memory. If the page table entry is valid and points to a frame in memory, we have a page hit. The frame number is retrieved, the physical address is formed, and the data is accessed from Main Memory. The TLB is also updated with this new translation for future use.
     Total Time = TLB Access Time + Main Memory Access Time (for Page Table) + Main Memory Access Time (for data)
   • Page Fault (Worst Case): The system accesses the page table, but the entry indicates the page is not in Main Memory. This triggers a page fault, which is a trap to the Operating System. The OS must then find the required page on the secondary storage (disk), load it into an empty frame in Main Memory, update the page table, and then resume the instruction that caused the fault. This is by far the most time-consuming event.

Calculating EMAT: The Simple Case (No Page Faults)

Let's start by building the fundamental formula for EMAT, assuming for now that a page fault never occurs. The EMAT is a weighted average of the time taken for a TLB hit and a TLB miss.

Let:

• $h$ be the TLB hit ratio (the probability of a TLB hit).
• $(1-h)$ be the TLB miss ratio.
• $T_{tlb}$ be the time to access the TLB.
• $T_{mem}$ be the time to access main memory.

The time for a TLB hit is $T_{hit}=T_{tlb}+T_{mem}$.
The time for a TLB miss (but page is in memory) is $T_{miss}=T_{tlb}+T_{mem}+T_{mem}$. The first $T_{mem}$ is for accessing the page table, and the second is for accessing the data.

So, the formula becomes:
$EMAT=h\times (T_{tlb}+T_{mem})+(1-h)\times (T_{tlb}+T_{mem}+T_{mem})$

This formula is the foundation for all EMAT problems. Let's see it in action.

The Complete Picture: EMAT with Page Faults

In a real system, page faults are a possibility. A page fault is an expensive operation involving disk access, which is orders of magnitude slower than memory access. GATE questions love to test this complete scenario, often adding another layer of complexity: dirty pages.

A dirty page is a page in memory that has been modified but not yet written back to the disk. If the OS needs to swap out a dirty page to make room for a new one, it must first write the modified contents back to the disk, incurring an extra disk access.

Let's outline the problem-solving strategy for these complex questions:

1. Diagram First: Always start by drawing a diagram showing the flow: CPU -> TLB -> Page Table (in MM) -> Main Memory -> Disk.
2. Identify All Outcomes: List every possible final outcome of a memory request.
   • TLB Hit.
   • TLB Miss, Page Hit.
   • TLB Miss, Page Fault (clean page).
   • TLB Miss, Page Fault (dirty page needs write-back).
3. Calculate Cost and Probability for Each Outcome:
   • Cost: For each path, sum the time taken at every step.
   • Probability: Multiply the probabilities along the path.
4. Sum the Weighted Costs: The final EMAT is the sum of (Probability * Cost) for all possible outcomes.

This might seem daunting, so let's walk through a "tough" GATE question with this exact structure.

By breaking the problem into these four mutually exclusive cases, you can build the solution piece by piece, which is much less error-prone than trying to memorize a single giant formula.

Key Takeaways

This lesson provided a structured method for solving one of the most important numerical problems in the Operating Systems syllabus for GATE.

• EMAT is a Weighted Average: The core idea is to calculate the average memory access time by weighting the time cost of each possible scenario by its probability of occurrence.
• The Access Hierarchy Defines the Scenarios: The sequence CPU → TLB → Page Table → Main Memory → Disk dictates the possible outcomes. A clear diagram is your best friend.
• Deconstruct the Costs: Be meticulous. The cost of a TLB miss includes the initial TLB access time. The cost of a page fault includes the TLB access and the page table lookup that discovered the fault.
• Probabilities Must Be Handled Carefully: The probability of a TLB miss and a page hit is not the same as the probability of just a page hit. Remember to multiply probabilities along a decision path. The sum of probabilities of all final outcomes must be 1.

In our next lesson, we will zoom in on the page fault handling process. When a page fault occurs and all memory frames are full, the OS must choose a victim page to evict. We will explore and analyze various Page Replacement Algorithms like FIFO, LRU, and Optimal, learning to trace their behavior and calculate the number of page faults for a given memory reference string.