in Operating System edited by
18,818 views
56 votes
56 votes
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?
in Operating System edited by
18.8k views

4 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!!
3
3

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.

4
4
Is this formula applied in parallel access also?
1
1

7 Answers

52 votes
52 votes
Best answer
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\%$
edited by
by

4 Comments

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

0
0

Thanks @samarpita

0
0
edited by

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.

0
0
91 votes
91 votes

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%

edited by
by

4 Comments

edited by

@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

 

2
2

@iarnav

why have u taken

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

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

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%

4 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

0
0

@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?

0
0
Yes.

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

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?

Answer:

Related questions