cache miss, a TLB miss and page fault

Question

Can someone clearly explain me the difference between a cache miss, a tlb miss and page fault, and how do these affect the effective memory access time?

Radu

Feel free for any queries. – Britneybritni

Why do we need a page table why cant we just point to the physical memory directly? @SumeetSingh – Alcibiades

@Alcibiades I recommend the videos on virtual memory by following youtuber youtube.com/watch?v=qlH4-oHnBb8&t=1s. – Britneybritni

@Alcibiades Just to give you a gist of it, virtual memory is there because we dont want the programmer to bother about actual physical addresses. He/She has enough to worry about algorithm or problem at hand. Therefore, let programmer write the code in virtual(not real) memory and let the memory management unit handle the conversion. – Britneybritni

@Alcibiades Added another answer for you. – Britneybritni

Answer 1

Let me explain all these things step by step.

The CPU generates the logical address, which contains the page number and the page offset.

The page number is used to index into the page table, to get the corresponding page frame number, and once we have the page frame of the physical memory(also called main memory), we can apply the page offset to get the right word of memory.

Why TLB(Translation Look Aside Buffer)

The thing is that page table is stored in physical memory, and sometimes can be very large, so to speed up the translation of logical address to physical address , we sometimes use TLB, which is made of expensive and faster associative memory, So instead of going into page table first, we go into the TLB and use page number to index into the TLB, and get the corresponding page frame number and if it is found, we completely avoid page table( because we have both the page frame number and the page offset) and form the physical address.

TLB Miss

If we don't find the page frame number inside the TLB, it is called a TLB miss only then we go to the page table to look for the corresponding page frame number.

TLB Hit

If we find the page frame number in TLB, its called TLB hit, and we don't need to go to page table.

Page Fault

Occurs when the page accessed by a running program is not present in physical memory. It means the page is present in the secondary memory but not yet loaded into a frame of physical memory.

Cache Hit

Cache Memory is a small memory that operates at a faster speed than physical memory and we always go to cache before we go to physical memory. If we are able to locate the corresponding word in cache memory inside the cache, its called cache hit and we don't even need to go to the physical memory.

Cache Miss

It is only after when mapping to cache memory is unable to find the corresponding block(block similar to physical memory page frame) of memory inside cache ( called cache miss ), then we go to physical memory and do all that process of going through page table or TLB.

So the flow is basically this

1.First go to the cache memory and if its a cache hit, then we are done.

2. If its a cache miss, go to step 3.

3. First go to TLB and if its a TLB hit, go to physical memory using physical address formed, we are done.

4. If its a TLB miss, then go to page table to get the frame number of your page for forming the physical address.

5. If the page is not found, its a page fault.Use one of the page replacement algorithms if all the frames are occupied by some page else just load the required page from secondary memory to physical memory frame.

End Note

The flow I have discussed is related to virtual cache(VIVT)(faster but not sharable between processes), the flow would definitely change in case of physical cache(PIPT)(slower but can be shared between processes). Cache can be addressed in multiple ways. If you are willing to dive deeply have a look at this and this.

Britneybritni

Thanks! That was really helpful. – Radu

I don't think the flow is correct. According to Patterson and Hennessy's "Computer Organization and Design", TLB should be checked to obtain the physical address (which contains physical address tag and cache index), and then you can access the cache based on the cache index and physical address tag. – Conciliatory

@Summet Singh TLB is fast, so I don't think it violates the memory hierarchy. – Conciliatory

@Summet Singh Check out this figure in Patterson and Hennesey's book: harttle.com/assets/img/blog/tlb-cache.png – Conciliatory

@Britneybritni Singh, even in the videos of David Black Shaffer you pointed out it is said that the tlb is looked before taking the cache line (what you call a block). But this is only the "simple" way of doing it, what it is said in the videos is that currently cache and TLB functionnate as a Virtual Indexed Physical Tagged cache (VIPT), and TLB look up and address translation are done simultaneously. – Westcott

@Westcott Its clearly said in the video thats the case of physical cache which is slow. What I have talked about is virtual cache and as said in the video its faster watch the complete video here youtube.com/… – Britneybritni

@Westcott There is never a hard and fast rule in computer organization but the flow I have mentioned will match the most computer organization conventions. – Britneybritni

@Conciliatory The figure you mentioned is about physical cache. – Britneybritni

@Britneybritni Singh By the way, VIPT is a trade-off between cache containing virtual address (what you call virtual cache is a physical cache memory containing virtual address) and cache containing physical address. The VIPT comes at 3min of the video you pointed out youtube.com/… Thank you very much for the link by the way, David Black Shaffer is a very good teacher ! – Westcott

@Summet Singh It's good to add the end note to prevent confusion. – Conciliatory

"Page Fault Occurs when we have formed the physical address, [...] and we do not find it in the main memory." I believe this is wrong. The page fault occurs when the virtual address is not currently mapped to a physical address. – Mitchum

@Mitchum Thanks a lot . I have made the required edit.s – Britneybritni

For context, found this (in my opinion) clear explanation of what a page and a page frame are. And it's basically: The page is the stored data, The page frame is the memory space where the page (the data) is stored. (As mentioned here). – Xanthine

I think Sumeet and @Conciliatory are both right because according to wiki here. – Earflap

If CPU cache is using logical address, TLB is used only after a cache miss. If CPU cache is using physical address, then TLB will be used even before accessing CPU cache. – Earflap

This answer suggests that accessing L1 and TLB happens in parallel, which makes sense. – Earflap

Answer 2

This diagram might help to see what will happen when there is a hit or a miss.

Incommodious

Answer 3

What causes page faults? Is it always because the memory has been moved to hard disk? Or just moved around for other applications?

Well, it depends. If your system does not support multiprogramming(In a multiprogramming system there are one or more programs loaded in main memory which are ready to execute), then definitely page fault has occurred because memory has been moved to hard disk.

If your system does support multiprogramming, then it depends on whether your operating system uses global page replacement or local page replacement. If it uses global, then yes there is a chance that memory has been moved around for other applications. But in local, the memory has been moved back to hard disk. When a process incurs a page fault, a local page replacement algorithm selects for replacement some page that belongs to that same process. On the other hand a global replacement algorithm is free to select any page in from the entire pool of frames. This discussion about these pops up more when dealing with thrashing.

I am confused of the difference between TLB miss and page faults.

TLB miss occurs when the page table entry required for conversion of virtual address to physical address is not present in the TLB(translation look aside buffer). TLB is like a cache, but it does not store data rather it stores page table entries so that we can completely bypass the page table in case of TLB hit as you can see in the diagram.

Is page fault a crash? Or is it the same as a TLB miss?

Neither of them is a crash as crash is not recoverable. But it is well known that we can recover from both page fault and TLB miss without any need for aborting the process execution.

Britneybritni

Answer 4

Just imagine a process is running and requires a data item X.

At first cache memory will be checked to see if it has the requested data item, if it is there(cache hit), it will be returned.If it is not there(cache miss), it will be loaded from main memory.

If there is a cache miss main memory will be checked to see if there is page containing the requested data item(page hit) and if such page is not there (page fault), the page containing the desired item has to be brought into main memory from disk.

While processing the page fault TLB will be checked to see if the desired page's frame number is available there (TLB hit) otherwise (TLB miss)OS has to consult page table for servicing page fault.

Time required to access these types memories:

cache << main memory << disk

Cache access requires least time so a hit or miss at certain level drastically changes the effective access time.

Odontoid

Answer 5

The Operating system uses virtual memory and page tables maps these virtual address to physical address. TLB works as a cache for such mapping.

 program >>> TLB >>> cache >>> Ram

A program search for a page in TLB, if it doesn't find that page it's a TLB miss and then further looks for the page in cache.

If the page is not in cache then it's a cache miss and further looks for the page in RAM.

If the page is not in RAM, then it's a page fault and program look for the data in secondary storage.

So, typical flow would be

Page Requested >> TLB miss >> cache miss >> page fault >> looks in secondary memory. 

Crafty

TLB stores the physical address whereas Cache stores the word. – Marvelofperu