14.3.2. Combinations of Events

In a memory hierarchy organized with a physically indexed physically tagged cache and physical memory along with the TLB for fast accesses, a memory reference can encounter three different types of hits or misses: it can encounter a TLB hit or miss, a page table hit or miss, and a cache hit or miss.

This chunk explains the three types of events that occur during a memory reference in a system with a cache and a TLB (Translation Lookaside Buffer). When a program requests data from memory, it can either find it successfully (hit) or fail to find it (miss) at each level of the memory hierarchy. A TLB hit indicates that the required address is already cached in the TLB, allowing it to be accessed quickly, while a TLB miss means the data must be retrieved from the page table or physical memory. Similar concepts apply to page table and cache hits or misses.

Think of this memory hierarchy as different layers in a restaurant. The TLB is like the waiter who remembers the regular orders of customers (TLB hits); when the order is memorized, service is quick. However, if the order isn't remembered (TLB miss), the waiter needs to check the orders book (page table), which takes longer. If the order is still not available and the customer calls the kitchen (physical memory), then the service is further delayed.

Consider all the combinations of these three events. You have 8 possibilities, such as a TLB miss, but a page hit and a cache hit. For each possibility, we need to verify whether this event can actually occur and, if so, under what circumstances.

This chunk highlights the fact that there are eight possible outcomes when considering hits and misses across TLB, page table, and cache. Not all combinations are valid in practice. For instance, if there is a TLB hit, logically, there will be no need to check the page table, as the data location is already available. Each combination must be carefully analyzed to determine its feasibility within the system’s operational structure.

Consider a task management system. If you have a project manager (TLB hit) who knows what needs to be done without checking the task list (page table), you skip the step of consulting it. However, if she doesn’t know the task (TLB miss), she must check the list, and even then, the task might not be in there (page table miss). Only when you have tasks are they allocated to team members (cache hit) — it illustrates how each layer of task management needs to align.

Examples of possible scenarios when accessing memory include: TLB hit + page table hit + cache hit; TLB miss + page table hit + cache hit; TLB miss + page table miss + cache miss. We assess the circumstances under which these cases occur.

This section describes specific combinations of outcomes that can occur during memory access. For example, if there is a hit in the TLB and the page table, this means that the data is immediately accessible in the cache. However, if there’s a miss in the TLB, the system must check the page table, which could lead to a cache hit or miss, emphasizing the dependency between the three memory components.

Imagine navigating a multi-level parking garage. If you remember where you parked (TLB hit), you go straight to the car (cache hit). If you can't remember but have the garage key (TLB miss, but have access), you check your parking slip (page table hit) and find your car in a specific section (cache hit). If you don’t remember and the slip says you parked in a different garage (page table miss), you'd need to check the location manually, leading to delays.

--