How to Calculate Effective Access Time

operating-system paging tlb page-tables
Mrose814 picture Mrose814 · Apr 25, 2015 · Viewed 15.5k times · Source

Assume TLB hit ratio is 90%, physical memory access takes 100ns, TLB access takes 20 ns, compute the effective access time for a processor that uses two level page tables, and parallel TLB and page table indexing.

This was my formula: 

(H)(TLB access time + mem access time) + (1-H)(TLB access + PT access + mem access)

This was my calculation:

EAT = [(.90) * (100ns + 20ns) + (1-.90)(20ns + 100ns*2 + 100ns)] = 130ns

I understand 2* 100ns because of the two-level page table, my confusion was when my professor said the TLB access time 20ns should not be included within the miss calculation.

Could someone please explain the reasoning behind this?

Answer

Ekleog picture Ekleog · Apr 27, 2015

The TLB and PT indexing is assumed to be "parallel". So lookup for TLB and PT are simultaneous.

Upon memory lookup, the processor launches both a PT and TLB query. If the TLB has an answer, it will answer first; that's hit case. If not, the query will continue to run until the PT answers; that's the non-hit case.

The thing of importance is that the PT has already started to look the answer up during the time the TLB determines it cannot answer. So the TLB lookup time should not be taken into account upon a cache miss.

Related questions

How does multi-level page table save memory space?

I am trying to understand how multi-level page table saves memory. As per my understanding, Multi-level page table in total consumes more memory than single-level page table. Example : Consider a memory system with page size 64KB and 32-bit processor. Each …

Read More
What is page table entry size?

I found this example. Consider a system with a 32-bit logical address space. If the page size in such a system is 4 KB (2^12), then a page table may consist of up to 1 million entries (2^32/2^12). Assuming that each entry consists of 4 …

Read More
Differences or similarities between Segmented paging and Paged segmentation?

I was studying combined paging/segmentation systems and in my book there were two approaches to this : 1.paged segmentation 2.segmented paging I could not make out the difference between the two. I think in paged segmentation the segment is divided …

Read More