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

@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

E.M.A.T will be 30ns/.80 = 37.5 ns 

@manu why didn't you do 30 *0.8 ?

am i geeting the maning of "acccess efficiency within 80 % of it maximum value" wrong ?

---

@junaid if efficiency is hight then time should be low. when efficiency was 100% you took 30ns time to do a job, but when your efficiency was 80% how can you take 30*.8 = 24 ns?

---

Thanks manu for help,such a blunder i am doing :(

---

@Manu Thakur

in this line in ur ans

37.5ns = H(30ns) + (1-H)(10−3)

why u took hit time with effective access time?

I mean logically we do hit*memory access time

---

@sreshtha,

I think if we got a hit, means our page is present in physical memory, so now page tables can be consulted to get effective address of respective page in physical memory,

So, when we get a hit, we access 2 level page table from memory and then data from memory.

---

If page in physical memory why 3 level access required? We access page table to see bit is valid or invalid. If already a valid bit there, why we access next level page table?

See page table definition from Galvin :)

---

Okay, but valid bit won't help much in fetching the actual page right.

Fetching or accessing that page would be only possible via the help of virtual to physical translation?

---

I donot get u

u means here page translation not needed, then why 3 level accessing required?

---

In general we will consider when it is miss 30ns also right. (1-h)(30+10^6) as 30 is very small compared to 10^6 is it ignored?

---

Thanks for Explaining in the very detailed manner, now I understand the complete solution except one thing that in the statement "access efficiency is 80% of it's max value", here why max value refers to max efficiency?? Max value is 10^-3 sec,But in case of max efficiency it is 3*10^-8 sec

---

Great explanation 

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)

If efficiency reduces then access time will increases.not decrease.

---

@srestha

are we ignoring the memory access that we need to do if miss happens ?

like if page fault happens then we need to access the disk and bring page to main memory and then update page table then access the main memory to get the page right ?

so in case of miss it should be (5*main memory access + disk access time)

---

in case of miss it should be (5*main memory access + disk access time)

why? 

---

are we using 2 level page table ? or main memory is level1 and disk is level 2 ?

---

 two-level virtual memory

right?What that means?

are we using 2 level page table ? or main memory is level1 and disk is level 2 ?

Page table always be in main memory.So, is there any difference between these two?

---

Yes.

in memory there is one page table.

so first we check page table = m sec

if not found we go to disk and grab that page = d sec

we come back to main mem and update the page table = m sec

we then access the frame = m sec

so total = 3m + d sec.

---

It will be like this,

two level virtual memory, means already two level page table in MM, that requires 2 level memory access

Now, if page found another level memory access required to access data.

Now, if not found another memory access required to access secondary memory . and no more memory access required anytime.

right?

---

two level virtual memory, means already two level page table in MM, that requires 2 level memory access

after this one more memory acces to go to physical address .right ?

so total 3m access in case of hit.

 

if page not found

already two level page table in MM, that requires 2 level memory access and page was not found in them = 2m

so we access it from secondary memory. = d

then update info in both the page tables = 2m

then we access physical address.=m

so total 5m+d in case of miss

---

 

no, it will be best time

Best time would be 3* (10^-8)  if efficiency is 1.

See Ahwan solution

 

---

Ans should be 99.99925%

---

effeciency is 1 means we are taking only the hit case since hit would be 100% = 3m = $3*10^{-8}$ (3m is discussed in my comment)....this part is okay.

I want to know how we are calculating the  miss case ?

---

See this

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

isnot here hit or miss, everything taken? 

---

Yes this is my doubt ....how are we calculating it ?

According to me it should be

$3m / 0.8 = Hit(3m) + Miss(5m+d)$ as i explained in the above comment.

LHS part i understood ....

what is the concept/theory for RHS part ?

---

• Go maximum two level in memory
• If data is found, pick data with another memory access(we call it hit)
• If not found , go to secondary memory and pick data

---

Okay

why have you written $2*10^{-8}$ in the equation ?

---

• Going two level of Memory which is already in Main Memory

---

So why have we excluded it from both the hit and the miss cases ?

Is it because it is common thing to do in both the cases ?

---

Remember, here we are equating efficiency

Efficiency means

 is one that uses the minimum amount of computer resources possible to complete its task

Here we need to equate minimum amount of time (with memory hit or without hit) require to complete the task. So, with hit or without hit , in both cases it will just do one time main memory access. Then why do we do it two times??

---

@Satbir

What do you mean by "two memory accesses for updating page table"?

Besides, you could include the memory access times in miss case, but it won't make much difference since $T_m$ and $T_d$ differ by fraction of a $10^5$. 

And, also where do we restrict ourselves in this case? In worst case, the main memory might already be full with all pages having modified bit set to 1. Now, we would need to write any two tables to the disk before we bring the required pages in memory? Should we consider that disc access too? 

---

Yes @toxicdesire

That is what i am asking. Are we ignoring page fault service time and just directly accessing the page from disk when page fault occurs ?

Two memory is because i am thinking that it is 2 level page table after reading arjun sir's answer and so we need to update both the page tables when page fault occurs.

 Now how 2 level page table ?

if there is hit then

we access outer page table, then inner page table , then physical address = 3m = 3*10^{-8} which arjun sir has written in the answer.

---

other possibility that srestha mam is saying that we have only 1 page table, and 2 level virtual memory means one is main memory and other level is hard disk.

@srestha

If data is found then pick data with other memory access(hit) $= 10^{-8}$ this is hit time

If not found , go to secondary memory and pick data $= (10^{-8}+10^{-3})$ this is miss time

effeciency = hit ratio*hit time + miss ratio*miss time

These are the hit and the miss cases are wriiten

Now why are we using $2*10^{8}$ i.e. 2 extra memory references ?

---

@Satbir

donot go by only a formula , there are many OS question , where this formula not work. Go by logic, what the question telling

---

What is the logic of using $2*10^{-8}$

• Go maximum two level in memory .....why are we doing this is not understood.
• If data is found, pick data with another memory access(we call it hit) -> Hit case
• If not found , go to secondary memory and pick data -> miss case

What is the meaning of 2 level memory here ?

---

@Satbir

check this ques https://gateoverflow.in/318/gate2004-47, and tell me , r u getting it?

efficiency = hit ratio*hit time + miss ratio*miss time

this formula applicable only that part of the question, where it is reliable

---

Yes i understood it by my doubt is not that

See the answer by arjun sir

$3×10^{−8}=0.8[3×10^{−8}+(1−h)×10^{−3}] $

Just tell me that in this line why sir has written only $10^{-3}$ and not

$3×10^{−8}=0.8[3×10^{−8}+(1−h)×(10^{-8}+10^{−3} )] $

because first we check main memory then if data is not there we go to secondary memory to get the data

so time for accesing secondary memory and time to access main memory both should be included in miss case right ?

---

@Satbir Yes, we go to secondary memory only when miss in primary memory happens. This is why the $3 \times 10^{-8}$ comes and not $2 \times 10^{-8}.$ You can do the calculation anyway. 

---

@Satbir

$3×10^{−8}=0.8[3×10^{−8}+(1−h)×(10^{-8}+10^{−3} )] $

this also give same answer.

We can ignore $10^{8}$ as it is much larger than $10^{-3}$

That is why it has not much effect on calculation

See the answer by arjun sir

$3×10^{−8}=0.8[3×10^{−8}+(1−h)×10^{−3}] $

that is reason behind 

---

chk this:

---

@Arjun Sir

he is asking, when there is a miss in main memory, will not two level of primary memory access and again two level for secondary memory access and then data access?

i.e. total five level of memory access?

---

@srestha @Arjun

Please check my understanding and tell where am i going wrong.(refering the above diagram)

two level virtual memory, means already two level page table in MM, that requires 2 level memory access

We go to p1->p2 -> data so total 3m access in case of hit.(in case if page is present in main memory)i.e HIT

 

if page not found

already we did two level page table in MM, that requires 2 level memory access and page was not found in them = 2m

so we access the page from secondary memory. = d

then update info in both the page tables = 2m

then we access physical address.=m

so total 5m+d in case of miss

 

---

@Satbir

then update info in both the page tables = 2m 

This is the point I think, u r wrong about.

though page table is in memory, but it is not in physical or main memory. So, In physical memory , there is nothing but data.

Data pages(in diagram) are nothing but physical memory. So, after two level of page table access, if it is found data in main memory, other wise just go to secondary memory (which is same another level of memory, like the given picture)

---

though page table is in memory, but it is not in physical or main memory .

How can we say this ?

if it is not in main memory then where is it ?

There are basically only two types of memory -> main memory like RAM and secondary memory like disk.

Though other types like cache, register are also there but they are not related to this question.

---

if is true then also we need to do 3m+d right instead of doing 5m+d.

---

Satbir

from VA, OS will check in Outer level PT, if found then go to next inner level PT, then the final M.M( It's called hit).

H(3m)

If not found in outer level PT, then go to secondary memory(d), load that page into memory & restart again from outer PT. ( d + 3m)

It's not like that, after accessing two levels PT & then it founds that the desired page is not in memory. No, Os deosn't cheat like that.

If Outer level PT checking is passed then it's guranteed to be in M.M (that's how the paging level is built).If outer level PT checking is not passed then Os have to load it from seconadry memory to Main Memory.

---

@MRINMOY_HALDER

Here main problem is page table upgradation require every time or not??

@Satbir

Can u tell me one thing, if page table access is same as main memory access, then why some question gives page fault service time differently?

---

understood now. thankyou mrinmoy

---

because in case of page fault we access both main memory and secondary memory in order to swap the desired page to main memory from secondary memory and then updating the page table.

Also if main memory is full then we have to put back pages from main to secondary memory if it is a dirty page.

So the page fault is kind of a procedure in itself which is executed in various steps and involves accessing both main and secondary memory.

---

srestha

I think if u think about practically, then after page fault & loading a page from secondary to Main, there may be many times M.M can be accessed.

but In theoritically one thing we must say that it's compulsary to access M.M (n+1) times in n level paging after page falult service. This is always happen.( yes you can consider also about updating PT 1, then pT2......) but also you can ignore them by arguing that d >>>> any no. of m

for GATE, I think upto (n+1).m is enough to understand.

---

@Satbir

then we can do it with  main memory access time and secondary memory access time. But why do we need page fault service time differently?

@Arjun Sir 

Can u tell me, is it always require, page table access time is same as main memory access time?

@MRINMOY_HALDER

If second level page table or last level page table can decide, that a page is in main memory or not, then why do we need to add main memory access time every time before secondary memory access time?

---

why do we need to add main memory access time every time before secondary memory access time?

can't get this 

---

we do like this

EAT=hit* primary memory access time+(1-hit)(Main memory access time+secondary memory access time)

But According to u formula should be

EAT=hit* primary memory access time+(1-hit)(secondary memory access time)

which one should be correct?

OR, 

can it say, Main Memory access is nothing but second leel page table access?

How do u define that MM access??

---

Do you agree that secondary memory access >> Main Memory access ???

---

may be.

but my question not answered still.

Can we tell something certainly about it?

---

EAT=hit* primary memory access time+(1-hit)(Main memory access time+secondary memory access time)

this is correct formula.

We are ignoring Main memory access time because $10^{-3} >>10^{-8}$

 

---

then we can do it with  main memory access time and secondary memory access time. But why do we need page fault service time differently?

because there are many steps involved in page fault service.

if page fault service time is not given then we calculate it using main memory and secondary memory access time.

---

EAT=hit* primary memory access time+(1-hit)(Main memory access time+secondary memory access time)

this is correct formula.

We are ignoring Main memory access time because 10−3>>10−8

@Satbir

I know this. plz read more carefully, what I asked Mrinmoy

---

 

because there are many steps involved in page fault service.

if page fault service time is not given then we calculate it using main memory and secondary memory access time.

if this is main scenario, then maximum question ignore it. But maximum GATE question includes it. 

---

@Satbir

I got this

 

Typically, page tables are said to be stored in the kernel-owned physical memory. However page tables can get awfully big since each process have their own page tables (unless the OS uses inverted paging scheme). For even a 32 bit address space with a typical 4KB page size, we shall require a 20 Bit virtual page number and a 12 bit offset. A 20 bit VPN(Virtual Page Number) implies that there would be 2^20 translations. Even if each translation i.e the Page Table entry requires 4 Bytes of memory, it amounts to 4x(2^20)= 4MB of memory, all just of address translations, which is awful. 

Hence modern OSes place such large page tables in virtual kernel memory which is the Hard Disk, and swaps them to the physical memory whenever required. Thus page table is virtualized the same way each page is virtualized.

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

Link:https://stackoverflow.com/questions/24322135/how-page-tables-are-stored-in-the-main-memory

---

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?