GATE CSE 2014 | Set 3 | Question: 33

Question

Consider a paging hardware with a $TLB$. Assume that the entire page table and all the pages are in the physical memory. It takes $10$ milliseconds to search the $TLB$ and $80$ milliseconds to access the physical memory. If the $TLB$ hit ratio is $0.6$, the effective memory access time (in milliseconds) is _________.

Comments

entire page table

means 1 level of page table used.

 

so, the formula become-

EMAT=TLB hit × (TLB access time + memory access time) + TLB miss X (TLB access time + no of page table access time +memory access time)

---

Level : Easy 

---

122 ms is the answer.

---

thanks @Sharadamani_K_N for making picture 

Answer 1

EMAT$=$TLB hit $\times$ (TLB access time $+$ memory access time) $+$ TLB miss(TLB access time $+$ page table access time+memory access time)

        $ =0.6(10+80)+0.4(10+80+80)$

       $ =  54+68$

        $=122\; \text{msec}$

Comments

`JEET

One more simple doubt.

TLB hit ratio 6 means, Out of 10 times, 6 times we found the frame number in TLB,  also Out of 100 times, 60 times we found frame number in TLB. Isn't ?

Then EMAT should be depend on the total number of times of access ? What i am trying to ask is " EMAT of a total of 10 access should be less than EMAT of a total of 100 access". It should vary for different number of total times of access Isn't ? Why the EMAT is fixed 122 m sec(here)?

 

---

The 'effective access time' is essentially the (weighted) $\color{blue}{\text{average time}}$ it takes to get a value from memory.

TLB hit ratio means the total number of times you found the address in the tlb divided by the total number of queries to the tlb.

---

Ok, Thanks.. Its for "a" value.. Now it is clear.

Answer 2

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, every time 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. TLB hit ratio- 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. In the case that the page is found in the TLB (TLB hit) the total time would be the time of search in the TLB plus the time to access memory, so TLB_hit_time := TLB_search_time + memory_access_time In the case that the page is not found in the TLB (TLB miss) the total time would be the time to search the TLB (you don't find anything, but searched nontheless) plus the time to access memory to get the page table and frame, plus the time to access memory to get the data, so TLB_miss_time := TLB_search_time + memory_access_time + memory_access_time But this is in individual cases, when you want to know an average measure of the TLB performance, you use the Effective Access Time, that is the weighted average of the previous measures EAT := TLB_miss_time * (1- hit_ratio) + TLB_hit_time * hit_ratio. EAT := (TLB_search_time + 2*memory_access_time) * (1- hit_ratio) + (TLB_search_time + memory_access_time)* hit_ratio. As both page table and page are in physical memory T(eff) = hit ratio * (TLB access time + Main memory access time) + (1 - hit ratio) * (TLB access time + 2 * main memory time) = 0.6*(10+80) + (1-0.6)*(10+2*80) = 0.6 * (90) + 0.4 * (170) = 122

Answer 3

Method 1:

- We are having TLB lookup irrespective of a miss or hit

- We are having access to the physical memory irrespective of a miss or hit

- Extra time in case of a hit = 0ms

- Extra time in case of a miss = 80ms

Total time = TLB lookup time + Memory access time + 0.4*(Extra times in case of miss) + 0.6*(Extra time in case of hit)

Total time = 10 + 80 + 0.4*80 + 0.6*0 = 122ms

Method 2:

Total time = (Virtual address to physical address conversion time)  + (Memory access time)

-- In case of TLB hit : 

Virtual address to physical address conversion time = TLB lookup time = 10ms

-- In case of TLB miss :

Virtual address to physical address conversion time = TLB lookup time + Access physical memory of page table

Virtual address to physical address conversion time = 10 + 80 = 90ms

-- Average Virtual address to physical address conversion time

Virtual address to physical address conversion time = 0.6*(In case of TLB hit) + 0.4*(In case of TLB miss)

Virtual address to physical address conversion time = 0.6*10 + 0.4*90 = 42ms

-- Total time

Total time = (Virtual address to physical address conversion time)  + (Memory access time) = 42ms + 80ms = 122ms

Answer 4

Answer

Answer 5

For simplification we do like this ,

E.M.A.T = 10 + 0.4 ×80 + 80 = 122 m.s.

Like we do in cache.