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

Does 2 level virtual memory means two level page table??

---

What's the meaning of the line " access efficiency is within 80% of its maximum value"?

Does it say THAT the total Access time should be within 80% of the time to work for maximum efficiency (minimum time to Access memory I.e. Time to access first two able and then data)?

@arjunsir

How did u solve after the line of ur solution "we are given" ??

---

maximum access is access efficiency.

That is why , only best case is taken as answer

---

Maximum access means.. Maximum access in less time..Right?

I couldn't understand the equations given in Arjun sir's solution after "we are given" . Can you explain those..@srestha

---

Actually in 3 level of access it could only access 80%

Among it if total hit it will take 3*10^-8

otherwise in miss it will take only data access time

---

Yahh I got that reason..

Where is "h" hit time in following eqn. How we got this eqn? U are saying only 80% of it can be used then why is that whole equal to 3x 10^-8 (Lhs)

"3×10^-8=0.8[3×10⁻⁸+(1−h)×10⁻³]

⟹0.6×10⁻⁸=0.8×10⁻³−0.8h×10⁻³⟹h=8×10⁻⁴−6×10⁻⁹8×10−4=1−0.75×10 "

---

Here we have assumed no page faults for page tables. ?

---

Yes ..

---

@ ARJUN sir  

What does it mean  by two level virtual  memory? Please explain  .

---

Why hit ratio is not used in the equation and only miss is used?Arjun sir can you please explain solution a bit.

---

@Arjun Sir

plz chk the solution

$3 \times 10^{-8} = 0.8 \left[ {\color{Blue} 3} \times 10^{-8} + (1-h) \times 10^{-3}\right]$

should it not be

$3 \times 10^{-8} = 0.8 \left[ {\color{Blue} h} \times 10^{-8} + (1-h) \times 10^{-3}\right]$

doubt in that line

otherwise plz tell me why that should be 3?

---

I agree with srestha doubt

Also it says 80% of maximum value is 3*10^-8 so why are we not multiplying RHS with .8 instead of LHS

---

@rahul 80% of its maximum value. Ok. Whatever is in LHS i.e the minimum time (best case)
 if you will multiply 0.8 in LHS then it will become even lesser. So it will increase efficiency more than 100% so you will get h more than 1.
So think again.  It will be multiplied in RHS. (OR it will be divided in LHS to make time more i.e to reduce efficiency)

---

@srestha  No, Arjun Sir is correct. i.e 3 not h.
I guess you are confused because you are following another way of applying it, you are mixing these 2 way of solving the same in one.
You can see my answer I have done it in the way you are talking about.
Answer is 0.99 too.

---

@srestha @Ahwan
Please Explain a bit about "2 level virtual memory"- does it mean that the first level is the Main memory and the second level is Disk? If so why to MM is Virtual, MM use to Physical memory?

and which "2-page tables" are talked about I think it is "not 2 level page table"(which is different), are those table for separately for MM and Disk but we in general use single page table per process, so what else could be these tables?

I didn't get which "3 Main Memory reference"(except the last 1 for fetching data from MM) sir is talking about?

---

"access efficiency is within 80 percent of its maximum value"

can be read as "access efficiency is within 80 percent of the maximum efficiency"

What is maximum efficiency ? Maximum efficiency arises when hit ratio is 100%. That means, all access of pages are in main memory. There by, $3 X 10^{-8}$ is the maximum efficiency.

I hope I am right.

--

Now, Let emat be effective memory access time, p be the miss rate, $t_{m}$ be the memory access time and PFS be the page fault service time,

emat = p( $t_{m}$ + PFS ) + (1-p)$t_{m}$

emat = p(PFS) + $t_{m}$

$3*10^{-8} = 0.8[p*10^{-3} + 3*10^{-8}]$

Now get p and h = 1-p

---

Arjun Sir, Why did you consider 2 level page table as 2 level virtual memory which in fact makes 3 level memory access [ PT1 -> PT2 -> MAIN MEMORY ] 

Cant we take it as simple two level memory,  h*10^-8 + (1-h)* 10^-3  as effective memory access. 

---

@Arjun Sir is this 2 level page table used in this problem or any other 

Red line is access when miss

---

@Srestha,Here according to you h*10^-8 coz the data could be found in MM or in case of a miss,it could be in SM. Am I right?Also, since there is no cache memory involved,the overhead is fairly small. Isn't it?

---

@Sir Arjun,How have we assumed that paging is being used and not swapping?If not explicitly mentioned,then we'll assume paging?

---

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?

---

My two cents

Assuming PT1 and PT2 is always in MM [Important]

EMAT = tm + tm + h*tm + (1-h)(tm+tsm) [First two tm are always two hit for page tables]

           = 3tm + tsm(1-h)

Max efficiency(100%) means we always get page in MM.Thus
tmin = 3tm

So, 0.8*(3tm + tsm(1-h)) = 3tm
      h = 99.99%

---

But many sources say answer is 20%

---

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

---

arjun sir please explain the efficiency equation why 0.8 is multiplied to RHS

---

@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

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