GATE CSE 1990 | Question: 7-b

Question

In a two-level virtual memory, the memory access time for main memory, $t_{M}=10^{-8}$ sec, and the memory access time for the secondary memory, $t_D=10^{-3}$ sec. What must be the hit ratio, $H$ such that the access efficiency is within $80$ percent of its maximum value?

Comments

Can someone please tell me, how can I distinguish which of the below formula to use:
 
EMAT= H(AT1) + M(AT2)

EMAT= AT1 + M(AT2)

EMAT=> Effective Memory Access Time
AT1=> Access Time for Level 1 memory
AT2=> Access Time for Level 2 memory
H=> Hit ratio of level 1 memory
M=> Miss rate of level 1 memory
(Last level memory will always be a hit)

I have came across it multiple times in Operating Systems and Computer Organization & Architecture in topics like TLB, multilevel cache, multiple memory hierarchies. I can't decide which formula to use.

Please help!!

---

EMAT=hM+(1-h)(M+SM)
hM+M+SM-hM-hSM
M+SM(1-h)
EMAT=M+m(SM)

h-> hit rate for MM

M->Main Memory access time

SM->Secondary memory access time

m->miss rate for MM

 

This how the second equation got derived from first.

---

Is this formula applied in parallel access also?

Answer 1

In $2$ level virtual memory, for every memory access, we need $2$ page table access (TLB is missing in the question) and $1$ memory access for data. In the question TLB is not mentioned (old architecture). So, best case memory access time

$= 3 \times 10^{-8}\; s$.

We are given

$3 \times 10^{-8} = 0.8 \left[ \underset{\text{2 for Page Tables and 1 Mem}}{3 \times 10^{-8}} + (1-h) \times 10^{-3}\right]$

(For above, the main memory access time and page table access times are included for all memory accesses -- hence $h$ is not multiplied with $3 \times 10^{-8})$

$\implies 0.6 \times 10^{-8} = 0.8 \times 10^{-3} - 0.8h \times 10^{-3}
\\ \implies h = \frac{8 \times 10^{-4} - 6 \times 10^{-9}}{8 \times 10^{-4}} = 1 - 0.75 \times 10^{-5} \approx 99.99\%$

Comments

@JAINchiNMay refer manu thakur sir answer….you will get the clarity.

---

Thanks @samarpita

---

Hope this helps somebody –

Page tables are always present in the MM (refer Arjun sir’s video https://youtu.be/bArypfVmPb8 for https://gateoverflow.in/490/gate-cse-2008-question-67?show=94002#c94002), so there won’t be any page faults while referring page tables. Now, whether or not the required process page is page-faulted or not, we need two page table accesses (which are nothing but two main memory accesses, as there are no TLBs mentioned in the question), and one main memory access (without/after a page fault service for the process page). But, there is a probability of \((1-h)\) that the process page might be page faulted, and so, on average, you would require an additional \((1-h)*(page\ fault\ service\ time)\) amount of time to access the required memory location, which is nothing but \((1-h)*10^{-3}\) (as nothing more than the secondary memory access time information is given). Plugging all of the above, you get the equation for the effective memory access time (EMAT) as provided in the best answer.

Also, IIUC, ‘access efficiency’ is not a standard terminology, but the (implied) definition for that as given in the best answer seems the most appropriate (consider the ratio \(\dfrac{best \ case \ memoy \ access \ time}{effective \ memory \ access \ time \ (EMAT)}\), and try varying the value of \(h\) in EMAT from \(1\) to \(0\) to convince yourself).

P.S. - Now, coming the question of whether or not page fault service time includes main memory access time, there seems to be much discord surrounding this on GO, with many of the experts voting for either. Nevertheless, whether or not the answer to that question is yes or no, it hardly matter when calculating the effective memory access time, because in any practical scenario, the secondary memory access (inevitable in a page fault service) time is quite large compared to the main memory access time. Even in this question, \(10^{-3} \ (t_D) \ >>10^{-8} \ (t_M)\), so whatever approach you choose to proceed with, the answer hardly changes.

Answer 2

Best time would be 3* (10^-8)  if efficiency is 1.
but efficiency is 0.8.
3*(10^-8) / time taken  = 0.8
So time taken = (3*10^-8) / 0.8

Now
time taken = 2 page table access + h(1 memory access) + (1-h)(1 memory access+ 1 disk access)
3*(10^-8) / 0.8 =  2*10^-8  + h ( 10^-8 ) + (1 - h) (  10^-8 + 10^ -3)
Solving this will give value of h ≈ 99.99%

Comments

@srestha I guess you were talking about this.

---

@Arjun Sir  @Bikram sir Please say, here in 2nd part it should be  (1 memory access+ 1 disk access)  or (1 disk access only)   It will not change the answer here though.  The changed value is after 4 decimal places.
We know PFS includes memory access time too. But here what to do? But here nothing like pfs is mentioned. We are bringing from disk. So we are bringing the frame to memory then accessing or directly accessing it?

---

Is access efficiency same as access time here?

---

@Ahwan

when do we do page table access? to check valid or invalid bit, right?

why u do hit and page table access separately?

If there is a hit in PTE then do we need 2 level page table access and then disk access separately?

---

@Srestha
To access a frame, we need to find it's address from page table.
In 2 level paging, we have to go through 2 page tables to find the address of the frame where the actual frame we are looking for exists.

Now I did not get your question exactly.

---

@Ahwan Nice answer but may you please tell how to solve this equation mathematically?

3*(10^-8) / 0.8 =  2*10^-8  + h ( 10^-8 ) + (1 - h) (  10^-8 + 10^ -3)

 

I'm stuck here as - 

3*10^-8/0.8 = H(2*10^-8 + 10^-8) + (1-H) (10^-8 + 10^-3)

My Take so far - 

3*10^-8/0.8 = H(3*10^-8) + (1-H) (10^-11)

3*10^-8/0.8 = H(3*10^-8) + 10^-11 - 10^-11*H

 

---

@iarnav

why have u taken

3*10^-8/0.8 = H(2*10^-8 + 10^-8) + (1-H) (10^-8 + 10^-3)

---

Srestha , I'm way out of loop now. Will tell, when I see OS again!

Answer 3

For maximum efficiency hit ratio should be 1.

when H=1, then we need 3 memory access, two m/m access to access the two-level page tables, and one more m/m access to access the physical memory.

So, maximum efficiency when H=1, E.M.A.T = $3*10^-8$ or 30ns

Efficiency should be 80% from 100%. 
When efficiency is 100% then E.M.A.T is 30ns
When efficiency is 80% then E.M.A.T will be 30ns/.80 = 37.5 ns (80% of 37.5ns is 30ns)

Now calculate the value of H:

37.5ns = H(30ns) + (1-H)($10^{-3}$)

(or)

37.5ns = H(30ns) + (1-H)($10^6$ns)

now all time units are same.

37.5 = H(30) + (1-H)($10^6$)

37.5 = 30H + $10^6$ -H$10^6$

H = $\frac{999962.5}{9999970}$ = 99.99%

Comments

This is done in modern days, but in what we study for GATE ...if size of page table is too big then we use demand paging and multilevel paging.

Is that mean page  table in main memory or page table swapped in main memory?

Page table is swapped to main memory

---

@Satbir

yes, and page table only used for mapping from virtual addresses to physical addresses. So, if it is inside physical memory, then will it be possible for page table?

---

Yes.

We take some space from physical memory to store page table and the remaining space will be mapped to virtual memory.

Answer 4

As mentioned on wikipedia, The efficiency of an entity (a device, component, or system) in electronics and electrical engineering is defined as useful power output divided by the total electrical power consumed (a fractional expression),

https://en.wikipedia.org/wiki/Electrical_efficiency

Let $h$ be the hit rate then

$\Rightarrow 80 = \dfrac{3 \times 10^{-8}h }{\underbrace{3\times 10^{-8}h} + (1-h)\times 10^{-3}} \times 100$

$\Rightarrow 3 \times 10^{-8}h = 0.8[\underbrace{3\times 10^{-8}h} + (1-h)\times 10^{-3}]$

$\Rightarrow 30h \times 10^{-9} = 24h \times 10^{-9} + 0.8\times 10^{-3} -0.8h \times 10^{-3}$

$\Rightarrow 6h \times 10^{-9} + 0.8h\times 10^{-3} = 0.8 \times 10^{-3}$

$\Rightarrow h = \dfrac{0.8 \times 10^{-3}}{0.800006 \times 10^{-3}} $

$\Rightarrow h = 0.999925$

Hence hit ratio should be $99.99 \%$

In the selected ans in the equation

$3 \times 10^{-8} = 0.8[\underbrace{3\times 10^{-8}} + (1-h)\times 10^{-3}]$

why $h$ is not multiplied here as $h$ refers to hit rate. When there is miss then it will be $(1-h)$ miss rate with which secondary memory will be accessed but why hit rate is not considered when 2 level page table and corresponding frame is being accessed?