48

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?

user2357112
  • 260,549
  • 28
  • 431
  • 505
Pushp Sra
  • 606
  • 1
  • 6
  • 6
  • Feel free for any queries. – Sumeet Jun 15 '16 at 06:38
  • 1
    Why do we need a page table why cant we just point to the physical memory directly? @SumeetSingh – marsh Feb 27 '18 at 20:24
  • 4
    @marsh I recommend the videos on virtual memory by following youtuber https://www.youtube.com/watch?v=qlH4-oHnBb8&t=1s. – Sumeet Feb 28 '18 at 06:15
  • 3
    @marsh 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. – Sumeet Feb 28 '18 at 06:18
  • 1
    @marsh Added another answer for you. – Sumeet Feb 28 '18 at 07:01

5 Answers5

63

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.

greybeard
  • 2,249
  • 8
  • 30
  • 66
Sumeet
  • 8,086
  • 3
  • 25
  • 45
  • Thanks! That was really helpful. – Pushp Sra Jun 15 '16 at 06:55
  • 11
    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. – user1036719 May 23 '17 at 01:17
  • @Summet Singh TLB is fast, so I don't think it violates the memory hierarchy. – user1036719 May 23 '17 at 09:04
  • 4
    @Summet Singh Check out this figure in Patterson and Hennesey's book: http://harttle.com/assets/img/blog/tlb-cache.png – user1036719 May 23 '17 at 09:05
  • @Sumeet 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. – Hugo Mar 01 '18 at 17:01
  • @Hugo 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 https://www.youtube.com/watch?v=3sX5obQCHNA&list=PLiwt1iVUib9s2Uo5BeYmwkDFUh70fJPxX&index=13 – Sumeet Mar 01 '18 at 17:12
  • @Hugo There is never a hard and fast rule in computer organization but the flow I have mentioned will match the most computer organization conventions. – Sumeet Mar 01 '18 at 17:15
  • @user1036719 The figure you mentioned is about physical cache. – Sumeet Mar 02 '18 at 14:26
  • @Sumeet 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 https://www.youtube.com/watch?v=3sX5obQCHNA&list=PLiwt1iVUib9s2Uo5BeYmwkDFUh70fJPxX&index=13 Thank you very much for the link by the way, David Black Shaffer is a very good teacher ! – Hugo Mar 02 '18 at 19:10
  • @Summet Singh It's good to add the end note to prevent confusion. – user1036719 Mar 26 '18 at 08:37
  • 2
    "**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**. – Zulan May 14 '18 at 10:25
  • @Zulan Thanks a lot . I have made the required edit.s – Sumeet May 14 '18 at 15:12
  • For context, found [this](https://qr.ae/pGgXde) (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](https://qr.ae/pGgXL9)). – Lennin Aug 06 '21 at 21:03
  • I think Sumeet and @user1036719 are both right because according to wiki [here](https://en.wikipedia.org/wiki/Translation_lookaside_buffer#:~:text=If%20the%20cache%20is%20virtually%20addressed%2C%20requests%20are%20sent%20directly%20from%20the%20CPU%20to%20the%20cache%2C%20and%20the%20TLB%20is%20accessed%20only%20on%20a%20cache%20miss.%20If%20the%20cache%20is%20physically%20addressed%2C%20the%20CPU%20does%20a%20TLB%20lookup%20on%20every%20memory%20operation%2C%20and%20the%20resulting%20physical%20address%20is%20sent%20to%20the%20cache.). – HCSF Dec 01 '21 at 12:59
  • 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. – HCSF Dec 01 '21 at 13:00
  • [This answer](https://www.quora.com/Is-a-first-level-CPU-cache-indexed-using-virtual-addresses-or-physical-addresses#:~:text=The%20CPU%20accesses%20the%20L1%20cache%20and%20the%20TLB%20in%20parallel) suggests that accessing L1 and TLB happens in parallel, which makes sense. – HCSF Dec 01 '21 at 13:15
21

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

Tadele Ayelegn
  • 4,126
  • 1
  • 35
  • 30
7

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 enter image description here

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

Rupsingh
  • 1,128
  • 1
  • 18
  • 34
7

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.

enter image description here

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.

Sumeet
  • 8,086
  • 3
  • 25
  • 45
-2

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.
saurabh agarwal
  • 2,124
  • 4
  • 24
  • 46