Hi;

I have to find the hit ratio for the following 9 logical addresses supported by TLB and using FIFO. My Addresses are: 9-8-4-5-9-6-4-7-5 and I don't have the foggiest idea where to start! Help! Thanks

You haven't the foggiest idea huh?? Lets try and dispel the fog bit by bit.

What is a cache??
A mechanism where we maintain a copy of the data in a faster area as compared to the real data that may be in a slower area. For example, hardware cache memory. Cache memory is faster than main memory: so if we maintain a copy of the data in cache, then the next time the same data is accessed, then if the copy of that data is in cache, then there is no need to go all the way to memory to fetch the data. So, cache speeds up the access to data in main memory.

What is a Cache hit??
When the CPU generates a load instruction, the cache is first checked to see if the data being loaded is already in the cache. How did it get into the cache?? From a prior access to the same data, which went all the way to memory and stored a copy in the cache. When the data is found in the cache itself, we call this as a Cache hit. If you do not find it in the cache, it is called a cache miss. On a cache miss, data has to be fetched from memory itself.

What is a TLB??
TLB stands for Translation Lookaside Buffer. In Virtual memory systems, the cpu generates virtual memory addresses. But, the data is stored in actual physical memory i.e. we need to place a physical memory address on the memory bus to fetch the data from the memory circuitry. So, a special table is maintained by the operating system called the Page table. This table contains a mapping between the virtual addresses and physical addresses. So, everytime a cpu generates a virtual address, the operating system page table has to be looked up to find the corresponding physical address. To speed this up, there is hardware support called the TLB. The TLB is a high speed cache of the page table i.e. contains recently accessed virtual to physical translations.

What is a TLB hit ratio??
Just like the cache hit, a TLB hit is the no of times a virtual-to-physical address translation was already found in the TLB, instead of going all the way to the page table which is located in slower physical memory.

TLB hit ratio is nothing but the ratio of TLB hits/Total no of queries into TLB. For example, if I asked the TLB 10 times for virtual-to-physical mappings, and found the mapping 4 times, then my hit ratio is 4/10 i.e. 40%.

In your example, 984506475 is the logical/virtual address sequence. Assuming an infinite size TLB, how many tlb hits will we have?? 9, 4, 5 are accessed more than once. So, hit ration is 3/9 = 33%.

But, the question also mentions that the TLB is a FIFO i.e. this means that the TLB size is limited. So, there is missing info in the question. Lets assume that the TLB size is 4. So, here is what happens when each new address is accessed:
9
89
489
5489
0548
6054
4605
7460
5746

If you notice, the above is a FIFO simulation. So, how many hits will we have?? None. So, hit ratio is 0%.

Hope that helps.

Thanks very much!!! I am also been introduced to LRU and if I think about what you explained the same sequence using LRU would show my hit ratio of 100% correct?

Not quite. Lets take the same example that you initially quoted: 984506475.

Assuming an infinite size TLB, how many tlb hits will we have?? Since an infinite TLB size implies that we never have to evict anybody, we will never have to use an LRU algorithm to choose somebody to evict. So, since 9, 4, 5 are accessed more than once, only those three accesses will have a TLB hit. Since other logical addresses are accessed only once, they will take a TLB miss each time they are accessed. So, hit ratio is still 3/9 = 33%.

But. lets assume that the TLB size is fixed at 4, and we are using an LRU algorithm to evict the oldest logical address.

984506475

9
89
489
5489
Least recently used at this point is 9. So, evict 9 and insert 0 in its place
5480
Least recently used at this point is 8. So, evict 8 and insert 6 in its place
5460
4 is accessed again, but is already in the cache. So, it is a hit, and its access time becomes more recent.
5460
Least recently used at this point is 5. So, evict 5 and insert 7 in its place.
7460
Least recently used at this point is 0. So, evict 0 and insert 5 in its place.
7465

So, the hit ratio = 1/9.

Thank you very much. I wonder though would it make a difference if the cache is already full to start with?

but i think we do have a hit after 6054 for '4' in ur first example. So i think ur 1st exmple works same as LRU.